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.
Authors: Durand-Lose, Jérôme | Kari, Jarkko | Verlan, Sergey
Article Type: Other
DOI: 10.3233/FI-2021-2052
Citation: Fundamenta Informaticae, vol. 181, no. 2-3, pp. i-iii, 2021
Authors: Geffert, Viliam | Bednárová, Zuzana
Article Type: Research Article
Abstract: We show that, for automata using a finite number of counters, the minimal space that is required for accepting a nonregular language is (log n )ɛ . This is required for weak space bounds on the size of their counters, for real-time and one-way, and for nondeterministic and alternating versions of these automata. The same holds for two-way automata, independent of whether they work with strong or weak space bounds, and of whether they are deterministic, nondeterministic, or alternating. (Here ɛ denotes an arbitrarily small—but fixed—constant; the “space” refers to the values stored in the counters, rather than to the …lengths of their binary representation.) On the other hand, we show that the minimal space required for accepting a nonregular language is n ɛ for multicounter automata with strong space bounds, both for real-time and one-way versions, independent of whether they are deterministic, nondeterministic, or alternating, and also for real-time and one-way deterministic multicounter automata with weak space bounds. All these bounds are optimal both for unary and general nonregular languages. However, for automata equipped with only one counter, it was known that one-way nondeterministic automata cannot recognize any unary nonregular languages at all, even if the size of the counter is not restricted, while, with weak space bound log n , we present a real-time nondeterministic automaton recognizing a binary nonregular language here. Show more
Keywords: space complexity, pushdown automata, counter automata, real-time automata
DOI: 10.3233/FI-2021-2053
Citation: Fundamenta Informaticae, vol. 181, no. 2-3, pp. 99-127, 2021
Authors: Whyman, Richard
Article Type: Research Article
Abstract: We present the concept of a theory machine, which is an atemporal computational formalism that is deployable within an arbitrary logical system. Theory machines are intended to capture computation on an arbitrary system, both physical and unphysical, including quantum computers, Blum-Shub-Smale machines, and infinite time Turing machines. We demonstrate that for finite problems, the computational power of any device characterisable by a finite first-order theory machine is equivalent to that of a Turing machine. Whereas for infinite problems, their computational power is equivalent to that of a type-2 machine. We then develop a concept of complexity for theory machines, and …prove that the class of problems decidable by a finite first order theory machine with polynomial resources is equal to 𝒩𝒫 ∩ co-𝒩𝒫. Show more
Keywords: Physical computation, Computable analysis, Blum-Shub-Smale machines, Hypercomputation, The Church-Turing thesis, Non-Causal Computation, Atemporal Computation
DOI: 10.3233/FI-2021-2054
Citation: Fundamenta Informaticae, vol. 181, no. 2-3, pp. 129-161, 2021
Authors: Perrot, Kévin | Perrotin, Pacôme | Sené, Sylvain
Article Type: Research Article
Abstract: Boolean automata networks (BANs) are a generalisation of Boolean cellular automata. In such, any theorem describing the way BANs compute information is a strong tool that can be applied to a wide range of models of computation. In this paper we explore a way of working with BANs which involves adding external inputs to the base model (via modules), and more importantly, a way to link networks together using the above mentioned inputs (via wirings). Our aim is to develop a powerful formalism for BAN (de)composition. We formulate three results: the first one shows that our modules/wirings definition is complete; …the second one uses modules/wirings to prove simulation results amongst BANs; the final one expresses the complexity of the relation between modularity and the dynamics of modules. Show more
Keywords: Boolean automata networks, modules, wirings, simulation
DOI: 10.3233/FI-2021-2055
Citation: Fundamenta Informaticae, vol. 181, no. 2-3, pp. 163-188, 2021
Authors: Fernau, Henning | Kuppusamy, Lakshmanan | Oladele, Rufus O. | Raman, Indhumathi
Article Type: Research Article
Abstract: A simple semi-conditional (SSC) grammar is a form of regulated rewriting system where the derivations are controlled either by a permitting string alone or by a forbidden string alone and this condition is specified in the rule. The maximum length i (j , resp.) of the permitting (forbidden, resp.) strings serves as a measure of descriptional complexity known as the degree of such grammars. In addition to the degree, the numbers of nonterminals and of conditional rules are also counted into the descriptional complexity measures of these grammars. We improve on some previously obtained results on the computational completeness …of SSC grammars by minimizing the number of nonterminals and / or the number of conditional rules for a given degree (i , j ). More specifically we prove, using a refined analysis of a normal form for type-0 grammars due to Geffert, that every recursively enumerable language is generated by an SSC grammar of (i) degree (2, 1) with eight conditional rules and nine nonterminals, (ii) degree (3, 1) with seven conditional rules and seven nonterminals (iii) degree (4, 1) with six conditional rules and seven nonterminals and (iv) degree (4, 1) with eight conditional rules and six nonterminals. Show more
Keywords: simple semi-conditional grammars, computational completeness, Geffert normal forms, descriptional complexity measures
DOI: 10.3233/FI-2021-2056
Citation: Fundamenta Informaticae, vol. 181, no. 2-3, pp. 189-211, 2021
Authors: Nagy, Benedek | Vályi, Sándor
Article Type: Research Article
Abstract: Interval-valued computing is a kind of massively parallel computing. It operates on specific subsets of the interval [0,1) – unions of subintervals. They serve as basic data units and are called interval-values. It was established in [9], by a rather simple observation, that interval-valued computing, as a digital computing model, has computing power equivalent to Turing machines. However, this equivalence involves an unlimited number of interval-valued variables. In [14], the equivalence with Turing machines is established using a simulation that uses only a fixed number of interval-valued variables and this number depends only on the number of states of the …Turing machine – in a logarithmic way. The simulation given there allows us to extend interval-valued computations into infinite length to capture the computing power of red-green Turing machines. In this extension of [14], based on the quasi-periodic techniques used in the simulations in that paper, a reformulation of the interval-valued computations is given, named circular interval-valued computers. This reformulation enforces the finiteness of the number of used interval-valued variables by building the finiteness into the syntax rules. Show more
Keywords: unconventional computing, massively parallel computing, interval-valued computing, red-green Turing machines, simulation, hypercomputation
DOI: 10.3233/FI-2021-2057
Citation: Fundamenta Informaticae, vol. 181, no. 2-3, pp. 213-238, 2021
Authors: Alhazov, Artiom | Freund, Rudolf | Ivanov, Sergiu | Oswald, Marion
Article Type: Research Article
Abstract: We extend and refine previous results within the general framework for regulated rewriting based on the applicability of rules in sequential grammars [3]. Besides the well-known control mechanisms as control graphs, matrices, permitting and forbidden rules, partial order on rules, and priority relations on rules we also consider the new variant of activation and blocking of rules as investigated in [1, 2, 4]. Moreover, we exhibit special results for strings and multisets as well as for arrays in the general variant defined on Cayley grids of finitely presented groups. Especially we prove that array grammars defined on Cayley grids …of finitely presented groups using #-context-free array productions together with control mechanisms as control graphs, matrices, permitting and forbidden rules, partial order on rules, priority relations on rules, or activation and blocking of rules have the same computational power as such array grammars using arbitrary array productions. Show more
Keywords: general framework, regulating rewriting, sequential grammars
DOI: 10.3233/FI-2021-2058
Citation: Fundamenta Informaticae, vol. 181, no. 2-3, pp. 239-271, 2021
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]