Fundamenta Informaticae - Volume 136, issue 1-2

Authors: Bensch, Suna | Drewes, Frank | Hirvensalo, Mika | Otto, Friedrich

Article Type: Other

DOI: 10.3233/FI-2015-1141

Citation: Fundamenta Informaticae, vol. 136, no. 1-2, pp. v-vi, 2015

Authors: Dassow, Jürgen | Manea, Florin | Truthe, Bianca

Article Type: Research Article

Abstract: In this paper, we approach the problem of accepting all recursively enumerable languages by accepting networks of evolutionary processors (ANEPs, for short) with a fixed architecture. More precisely, we show that every recursively enumerable language can be accepted by an ANEP with an underlying graph in the form of a star with 13 nodes or by an ANEP with an underlying grid with 13 × 4 = 52 nodes as well as by ANEPs having underlying graphs in the form of a chain, a ring, or a wheel with 29 nodes each. In all these cases, the size and form …as well as the general working strategy of the constructed networks do not depend on the accepted language; only the rewriting rules and the filters associated to each node of the networks depend on this language. Noteworthy is also the fact that the filtering process is implemented using random context conditions only. Our results answer problems which were left open in a paper published by J. Dassow and F. Manea at the conference on Descriptional Complexity of Formal Systems (DCFS) 2010 and improve a result published by B. Truthe at the conference on Non-Classical Models of Automata and Applications (NCMA) 2013. Show more

Keywords: Formal Languages, Networks of Evolutionary Processors, Computational Power, Random Context Conditions

DOI: 10.3233/FI-2015-1142

Citation: Fundamenta Informaticae, vol. 136, no. 1-2, pp. 1-35, 2015

Authors: Droste, Manfred | Heusel, Doreen

Article Type: Research Article

Abstract: We investigate the supports of weighted unranked tree automata. Our main result states that the support of a weighted unranked tree automaton over a zero-sum free, commutative strong bimonoid is recognizable. For this, we use methods of Kirsten (DLT 2009), in particular, his construction of finite automata recognizing the supports of weighted automata on strings over zero-sum free, commutative semirings. We also get an effective construction of a finite tree automaton recognizing the support of a given weighted unranked tree automaton for zero-sum free, commutative strong bimonoids where Kirsten's zero generation problem is decidable. In addition, we give a translation …of nested weighted automata into weighted unranked tree automata for arbitrary commutative strong bimonoids. As a consequence, we derive analogous results for the supports of nested weighted automata. Finally, we give similar results for the supports of weighted pushdown automata. Show more

DOI: 10.3233/FI-2015-1143

Citation: Fundamenta Informaticae, vol. 136, no. 1-2, pp. 37-58, 2015

Authors: Freund, Rudolf | Oswald, Marion | Păun, Gheorghe

Article Type: Research Article

Abstract: The questions whether catalytic P systems with only one catalyst and purely catalytic P systems with only two catalysts can already be computationally complete in the generative case, still are open problems. For accepting P systems or P automata, the situation is even more complicated when we consider sets of vectors of natural numbers and not only sets of natural numbers – the number of catalysts increases with the dimension of the vectors. We here establish computational completeness for catalytic P systems and P automata with only one catalyst as well as for purely catalytic P systems and P automata …with only two catalysts in the skin membrane by using specific variants of additional control mechanisms: in P systems and P automata with label selection, we only use rules from one set of a finite number of sets of rules in each computation step; in time-varying P systems and P automata the available sets of rules change periodically with time. The same control mechanisms also allow for computing partial recursive relations or functions of (vectors of) natural numbers when being used in catalytic P systems with one catalyst and purely catalytic P systems with two catalysts. Finally, these variants of P systems can also be used to generate or accept strings and to compute partial relations or functions on strings, and again we obtain computational completeness with only one catalyst in the case of catalytic P systems and two catalysts in the case of purely catalytic P systems. Show more

DOI: 10.3233/FI-2015-1144

Citation: Fundamenta Informaticae, vol. 136, no. 1-2, pp. 59-84, 2015

Authors: Hoffmann, Petr

Article Type: Research Article

Abstract: Single k-reversible restarting automata are a special version of restarting automata which can be effectively learned from samples. We show that their power lies between GCSL and CSL. We show that their subclasses form an infinite hierarchy of classes of languages with respect to the reversibility level k and we also show that limiting types of allowed rewrites lowers the power of the model. Finally, we study their relation to strictly locally testable restarting automata.

DOI: 10.3233/FI-2015-1145

Citation: Fundamenta Informaticae, vol. 136, no. 1-2, pp. 85-112, 2015

Authors: Holzer, Markus | Jakobi, Sebastian

Article Type: Research Article

Abstract: We show how to minimize biautomata with adaptations of classical minimization algorithms for ordinary deterministic finite automata and moreover by a Brzozowski-like minimization algorithm by applying reversal and power-set construction twice to the biautomaton under consideration. Biautomata were recently introduced in [O. KLÍMA, L. POLÁK: On biautomata. RAIRO—Theor. Inf. Appl., 46(4), 2012] as a generalization of ordinary finite automata, reading the input from both sides. The correctness of the Brzozowski-like minimization algorithm needs a little bit more argumentation than for ordinary finite automata since for a biautomaton its dual or reverse automaton, built by reversing all transitions, does not necessarily …accept the reversal of the original language. To this end we first use the recently introduced notion of nondeterminism for biautomata [M. HOLZER, S. JAKOBI: Nondeterministic Biautomata and Their Descriptional Complexity. In: 15th DCFS, Number 8031 of LNCS, 2013] and take structural properties of the forward- and backward-transitions of the automaton into account. This results in a variety of biautomata models, the accepting power of which is characterized. As a byproduct we give a simple structural characterization of cyclic regular and commutative regular languages in terms of deterministic biautomata. Show more

Keywords: nondeterministic biautomata, structural properties, minimization, commutative languages, cyclic languages

DOI: 10.3233/FI-2015-1146

Citation: Fundamenta Informaticae, vol. 136, no. 1-2, pp. 113-137, 2015

Authors: Kutrib, Martin | Provillard, Julien | Vaszil, György | Wendlandt, Matthias

Article Type: Research Article

Abstract: Deterministic one-way Turing machines with sublinear space bounds are systematically studied. We distinguish among the notions of strong, weak, and restricted space bounds. The latter is motivated by the study of P automata. The space available on the work tape depends on the number of input symbols read so far, instead of the entire input. The class of functions space constructible by such machines is investigated, and it is shown that every function f that is space constructible by a deterministic two-way Turing machine, is space constructible by a strongly f space-bounded deterministic one-way Turing machine as well. We prove …that the restricted mode coincides with the strong mode for space constructible functions. The known infinite, dense, and strict hierarchy of strong space complexity classes is derived also for the weak mode by Kolmogorov complexity arguments. Finally, closure properties under AFL operations, Boolean operations and reversal are shown. Show more

DOI: 10.3233/FI-2015-1147

Citation: Fundamenta Informaticae, vol. 136, no. 1-2, pp. 139-155, 2015

Authors: Pighizzini, Giovanni | Pisoni, Andrea

Article Type: Research Article

Abstract: Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence between 2-limited automata and pushdown automata, comparing the relative sizes of their descriptions. We prove exponential upper and lower bounds for the sizes of pushdown automata simulating 2-limited automata. In the case of the conversion of deterministic 2-limited automata into deterministic pushdown automata the upper bound is double exponential and we conjecture that it cannot be reduced. On …the other hand, from pushdown automata we can obtain equivalent 2-limited automata of polynomial size, also preserving determinism. From our results, it follows that the class of languages accepted by deterministic 2-limited automata coincides with the class of deterministic context-free languages. Show more

Keywords: finite automata, formal languages, Turing machines, deterministic context-free languages, descriptional complexity

DOI: 10.3233/FI-2015-1148

Citation: Fundamenta Informaticae, vol. 136, no. 1-2, pp. 157-176, 2015

Authors: Vollweiler, Marcel

Article Type: Research Article

Abstract: Synchronous systems of parallel communicating one-way finite automata have already been investigated. There, all components work stepwise in parallel, and the communication between the components is realized by requesting states in a one-directional manner. This means that one component can request information in form of the current state from another component, where the latter one sends its current state without realizing that a communication takes place. Here, we introduce asynchronous systems of parallel communicating one-way and two-way finite automata with a bidirectional communication protocol. A communication only takes place, when both components - the requesting and the responding component - …are ready to communicate. It is shown that almost all language classes that are characterized by these systems coincide with the language classes that are characterized by multi-head finite automata. Moreover, our communication protocol uses blocking point-to-point communications, i.e. a communication takes place between two components, and a communicating component is blocked until the communication has been finished. There have also been studied asynchronous systems of finite automata with non-blocking communication in the literature. Thus, we compare synchronous and asynchronous systems on the one hand and asynchronous systems with blocking and non-blocking communication on the other hand. Finally, we give some results on the communication complexity of our systems, where the amount of communication is measured by counting each message which is sent from one component to another during a computation of a system. Particularly, we show that with constantly many communications our systems can only accept regular languages, and at most linearly (polynomially) many communications are needed for systems of one-way (two-way) components depending on the length of the input. Further, there exists no system that executes more than constantly many and less than linearly many communications. Show more

DOI: 10.3233/FI-2015-1149

Citation: Fundamenta Informaticae, vol. 136, no. 1-2, pp. 177-197, 2015