Fundamenta Informaticae - Volume 148, issue 3-4

Authors: Bensch, Suna | Freund, Rudolf | Hirvensalo, Mika | Otto, Friedrich

Article Type: Other

DOI: 10.3233/FI-2016-1433

Citation: Fundamenta Informaticae, vol. 148, no. 3-4, pp. i-ii, 2016

Authors: Câmpeanu, Cezar | Moreira, Nelma | Reis, Rogério

Article Type: Research Article

Abstract: Given a language L , we study the language of words D(L ), that distinguish between pairs of different left quotients of L . We characterize this distinguishability operation, show that its iteration has always a fixed point, and we generalize this result to operations derived from closure operators and Boolean operators. For the case of regular languages, we give an upper bound for the state complexity of the distinguishability operation, and prove its tightness. We show that the set of minimal words that can be used to distinguish between different left quotients of a regular language L has …at most n – 1 elements, where n is the state complexity of L , and we also study the properties of its iteration. We generalize the results for the languages of words that distinguish between pairs of different right quotients and two-sided quotients of a language L . Show more

Keywords: Formal Languages, Myhill-Nerode Relations, Quotients, Language Operations, Closures, Regular Languages, State Complexity

DOI: 10.3233/FI-2016-1434

Citation: Fundamenta Informaticae, vol. 148, no. 3-4, pp. 243-266, 2016

Authors: Holzer, Markus | Jakobi, Sebastian | Wendlandt, Matthias

Article Type: Research Article

Abstract: We consider the computational complexity of problems related to partial word automata. Roughly speaking, a partial word is a word in which some positions are unspecified and a partial word automaton is a finite automaton that accepts a partial word language—here the unspecified positions in the word are represented by a “hole” symbol ⋄. A partial word language L ′ can be transformed into an ordinary language L by using a ⋄-substitution. In particular, we investigate the complexity of the compression or minimization problem for partial word automata, which is known to be NP -hard. We improve on the …previously known complexity on this problem, by showing PSPACE -completeness. In fact, it turns out that almost all problems related to partial word automata, such as, e.g., equivalence and universality, are already PSPACE -complete. Moreover, we also study these problems under the further restriction that the involved automata accept only finite languages. In this case, the complexities of the studied problems drop from PSPACE -completeness down to coNP -hardness and containment in ∑ 2 P depending on the problem investigated. Show more

DOI: 10.3233/FI-2016-1435

Citation: Fundamenta Informaticae, vol. 148, no. 3-4, pp. 267-289, 2016

Authors: Ibarra, Oscar H.

Article Type: Research Article

Abstract: We generalize the models of visibly pushdown automata (VPDAs) and visibly pushdown transducers (VPDTs) by equipping them with reversal-bounded counters. We show that some of the results for VPDAs and VPDTs (e.g., closure under intersection and decidability of emptiness for VPDA languages) carry over to the generalized models, but other results (e.g., determinization and closure under complementation) do not carry over, in general. We define a model that combines the desirable features of a VPDA and reversal-bounded counters, called 2-phase VPCM, and show that the deterministic and nondeterministic versions are equivalent and that the family of languages they define is …closed under Boolean operations and has decidable emptiness, infiniteness, disjointness, containment, and equivalence problems. We also investigate the finite-ambiguity and finite-valuedness problems concerning these devices. Show more

Keywords: pushdown automaton, pushdown transducer, visibly pushdown automaton, visibly pushdown transducer, reversal-bounded counters, ambiguous, finite-valued, decidable, undecidable

DOI: 10.3233/FI-2016-1436

Citation: Fundamenta Informaticae, vol. 148, no. 3-4, pp. 291-308, 2016

Authors: Krtek, Lukáš | Mráz, František

Article Type: Research Article

Abstract: Motivated by possible machine learning of picture languages, we introduce a new two-dimensional automaton called two-dimensional limited context restarting automaton. Our model is a simplification of the two-dimensional restarting tiling automaton, from which it differs in that it does not require to scan input pictures in a fixed order. We show that the two-dimensional limited context restarting automaton is equally powerful as the two-dimensional sgraffito automaton. Moreover, the correctness preserving version of the new model, while still being nondeterministic, is equivalent to the deterministic sgraffito automaton. However, the property of being correctness preserving is not even semi-decidable for two-dimensional limited …context restarting automata. Show more

DOI: 10.3233/FI-2016-1437

Citation: Fundamenta Informaticae, vol. 148, no. 3-4, pp. 309-340, 2016

Authors: Kutrib, Martin | Malcher, Andreas | Wendlandt, Matthias

Article Type: Research Article

Abstract: Deterministic finite automata equipped with the storage medium of a queue are investigated towards their ability to perform reversible computations, that is, computations in which every occurring configuration has exactly one successor and exactly one predecessor. A first result is that any queue automaton can be simulated by a reversible one. So, reversible queue automata are as powerful as Turing machines. Therefore it is of natural interest to impose time restrictions to queue automata. Here we consider quasi realtime and realtime computations. It is shown that every reversible quasi realtime queue automaton can be sped up to realtime. On the …other hand, under realtime conditions reversible queue automata are less powerful than general queue automata. Furthermore, we exhibit a lower bound of Ω ( n 2 log ( n ) ) time steps for realtime queue automata witness languages to be accepted by any equivalent reversible queue automaton. We study the closure properties of reversible realtime queue automata and obtain similar results as for reversible deterministic pushdown automata. Finally, we investigate decidability questions and obtain that all commonly studied questions such as emptiness, finiteness, or equivalence are not semidecidable for reversible realtime queue automata. Furthermore, it is not semidecidable whether an arbitrary given realtime queue automaton is reversible. Show more

DOI: 10.3233/FI-2016-1438

Citation: Fundamenta Informaticae, vol. 148, no. 3-4, pp. 341-368, 2016

Authors: Pighizzini, Giovanni

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 . When d ≥ 2, these devices characterize the class of context-free languages. In this paper we consider restricted versions of these models which we call strongly limited automata , where rewrites, head reversals, and state changes are allowed only at certain points of the computation. Those restrictions are inspired by a simple algorithm for accepting Dyck languages on 2-limited automata. We prove that the models so defined are still able to recognize …all context-free languages. We also consider descriptional complexity aspects. We prove that there are polynomial transformations of context-free grammars and pushdown automata into strongly limited automata and vice versa. Show more

DOI: 10.3233/FI-2016-1439

Citation: Fundamenta Informaticae, vol. 148, no. 3-4, pp. 369-392, 2016

Article Type: Other

Citation: Fundamenta Informaticae, vol. 148, no. 3-4, pp. 393-394, 2016