Fundamenta Informaticae - Volume 181, issue 2-3

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