Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Purchase individual online access for 1 year to this journal.
Price: EUR 410.00Impact Factor 2024: 0.4
Fundamenta Informaticae is an international journal publishing original research results in all areas of theoretical computer science. Papers are encouraged contributing:
- solutions by mathematical methods of problems emerging in computer science
- solutions of mathematical problems inspired by computer science.
Topics of interest include (but are not restricted to): theory of computing, complexity theory, algorithms and data structures, computational aspects of combinatorics and graph theory, programming language theory, theoretical aspects of programming languages, computer-aided verification, computer science logic, database theory, logic programming, automated deduction, formal languages and automata theory, concurrency and distributed computing, cryptography and security, theoretical issues in artificial intelligence, machine learning, pattern recognition, algorithmic game theory, bioinformatics and computational biology, quantum computing, probabilistic methods, & algebraic and categorical methods.
Article Type: Other
DOI: 10.3233/FI-1980-3301
Citation: Fundamenta Informaticae, vol. 3, no. 3, pp. i-ix, 1980
Authors: Rus, Teodor
Article Type: Research Article
Abstract: This paper is an attempt to direct present-day research in programming language specification and their compiler construction towards a more natural approach. In order to do that, a language is considered for what it is, namely a communication device between systems. In view of this evidence, the first section of the paper develops a framework for the natural specification of language. Section two of the paper develops the HAS-Hierarchy as a device to be used in this natural language specification. Section three of the paper constructs a general model for programming language specification by the HAS-Hierarchy. Section four is devoted …to the problem of compiler construction by using the HAS-Hierarchy as a natural tool for programming language specification. Show more
Keywords: Syntax, semantics, heterogeneous algebra, contextfree grammar, normal algorithm, pattern matching process, compiler, compiler construction
DOI: 10.3233/FI-1980-3302
Citation: Fundamenta Informaticae, vol. 3, no. 3, pp. 269-293, 1980
Authors: Rozenberg, Grzegorz | Vermeir, Dirk
Article Type: Research Article
Abstract: A theorem is presented which characterizes the maximal growth in FTOL systems with rank.
Keywords: formal language theory, FTOL systems, growth functions, rank
DOI: 10.3233/FI-1980-3303
Citation: Fundamenta Informaticae, vol. 3, no. 3, pp. 295-302, 1980
Authors: Adrianopoli, Faurto
Article Type: Research Article
Abstract: It is shown here that using the Kleene’s normal form for partial recursive functions (p.r. functions) it is possible to develop a different normal form which will give a relation between these p.r. functions and certain related step-counting ones. Also this new form suggests an interesting serial expansion in terms of minimal functions of these p.r. functions. The notion of conjugated systems of computational complexity is eventually introduced.
Keywords: measure of computational complexity, step-counting function
DOI: 10.3233/FI-1980-3304
Citation: Fundamenta Informaticae, vol. 3, no. 3, pp. 303-309, 1980
Authors: Salwicki, Andrzej
Article Type: Research Article
Abstract: The algorithmic theory of stacks, ATS, formalizes properties of relational systems of stacks. It turns out that apart from previously known axioms a new axiom of algorithmic nature, while ¬ empty (s ) do s : = pop (s ) true is in place. The representation theorem stating that every relational system of stacks is isomorphic to a system of finite sequences of elements is proved. The connections between ATS and a type STACKS declaration (written in LOGLAN programming language) are shown.
Keywords: abstract data types, algorithmic theory, - of stacks, - of dictionaires, of stacks and links, interpretability relation between theories, model, representation theorem, type declaration
DOI: 10.3233/FI-1980-3305
Citation: Fundamenta Informaticae, vol. 3, no. 3, pp. 311-331, 1980
Authors: Orłowska, Ewa
Article Type: Research Article
DOI: 10.3233/FI-1980-3306
Citation: Fundamenta Informaticae, vol. 3, no. 3, pp. 333-361, 1980
Authors: Grant, John
Article Type: Research Article
Abstract: In this paper we investigate the inclusion of incomplete information in the relational database model. This is done by allowing nonatomic entries, i.e. sets, as elements in the database. A nonatomic entry is interpreted as a set of possible elements, one of which is the correct one. We deal primarily with numerical entries where an allowed set is an interval, and character string entries. We discuss the various operations of the relational algebra as well as the notion of functional dependency for the database model.
Keywords: relational database, incomplete information, relational algebra, functional dependency
DOI: 10.3233/FI-1980-3307
Citation: Fundamenta Informaticae, vol. 3, no. 3, pp. 363-377, 1980
Authors: Truszczyński, Mirosław
Article Type: Research Article
Abstract: Acyclic families of sets are investigated. A theorem giving necessary and sufficient conditions for the family of sets to be acyclic is formulated and proved. Then an algorithm is described of finding the acyclic f -graph for a given family of sets whenever this family is acyclic. Its computational complexity is equal to O ( n 3 + n 2 k ) , so it is better than the other algorithms known so far.
Keywords: consecutive retrieval, storage, records, f-graph, acyclic family
DOI: 10.3233/FI-1980-3308
Citation: Fundamenta Informaticae, vol. 3, no. 3, pp. 379-395, 1980
Authors: Penttonen, Martti
Article Type: Research Article
Abstract: Most NP -complete problems remain NP -complete even though the notation for integers is changed to unary. The knapsack problem is an exception, it becomes provably polynomial time recognizable. However, we present a modified knapsack problem that remains NP -complete also in unary notation.
Keywords: NP-completeness, satisfiability, chromatic number, exact cover knapsack, unary notation
DOI: 10.3233/FI-1980-3309
Citation: Fundamenta Informaticae, vol. 3, no. 3, pp. 397-400, 1980
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
[email protected]
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office [email protected]
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
如果您在出版方面需要帮助或有任何建, 件至: [email protected]