Fundamenta Informaticae - Volume 110, issue 1-4

Authors: Gao, Yuan | Salomaa, Kai | Yu, Sheng

Article Type: Research Article

Abstract: We consider the transition complexity of regular languages based on the incomplete deterministic finite automata. We establish tight bounds for the transition complexity of Boolean operations, in the case of union the upper and lower bounds differ by a multiplicative constant two. We show that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity bounds turn out to be similar to the corresponding bounds for state complexity.

Keywords: transition complexity, deterministic finite automaton, incomplete automaton, regular languages, Boolean operations

DOI: 10.3233/FI-2011-533

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 143-158, 2011

Authors: Holzer, Markus | Klein, Andreas | Kutrib, Martin | Ruepp, Oliver

Article Type: Research Article

Abstract: We show that the popular pencil puzzle NURIKABE is intractable from the computational complexity point of view, that is, it is NP-complete, even when the involved numbers are 1 and 2 only. To this end, we show how to simulate Boolean gates by the puzzle under consideration. Moreover, we also study some NURIKABE variants, which remain NP-complete, too.

DOI: 10.3233/FI-2011-534

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 159-174, 2011

Authors: Honkala, Juha

Article Type: Research Article

Abstract: We study the DT0L sequence equivalence problem for marked morphisms. We show that to decide this problem it is enough to consider initial terms involving at most 2n morphisms where n is the cardinality of the underlying alphabet.

Keywords: DT0L system, DT0L sequence equivalence problem, marked morphism, decidability

DOI: 10.3233/FI-2011-535

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 175-182, 2011

Authors: Ilie, Lucian | Smyth, William F.

Article Type: Research Article

Abstract: Unique substrings appear scattered in the stringology literature and have important applications in bioinformatics. In this paper we initiate a study of minimum unique substrings in a given string; that is, substrings that occur exactly once while all their substrings are repeats. We discover a strong duality between minimum unique substrings and maximum repeats which, in particular, allows fast computation of one from the other. We give several optimal algorithms, some of which are very simple and efficient. Their combinatorial properties are investigated and a number of open problems are proposed.

DOI: 10.3233/FI-2011-536

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 183-195, 2011

Authors: Karhumäki, Juhani | Saarela, Aleksi

Article Type: Research Article

Abstract: We show by a simple reduction that the unique decipherability problem in the language monoid of regular languages over a non-unary alphabet is undecidable.

DOI: 10.3233/FI-2011-537

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 197-200, 2011

Authors: Kari, Lila | Seki, Shinnosuke | Kopecki, Steffen

Article Type: Research Article

Abstract: Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand w = xαy\bar{α}, and outputs w' = xαy\bar{α}\bar{x}, where \bar{x} denotes the Watson-Crick complement of x. In this paper, we focus on the problem of finding conditions under which the iterated hairpin completion of a given word is regular. According to the numbers of words α and \bar{α} that initiate hairpin completion and how they are scattered, we classify the set of all words w. For some basic classes of words w containing small numbers of occurrences of α and \bar{α}, we prove …that the iterated hairpin completion of w is regular. For other classes with higher numbers of occurrences of α and \bar{α}, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular. Show more

Keywords: combinatorics on words, commutativity of words, DNA computing, iterated hairpin completion, regularity test, single-primer hairpin completion

DOI: 10.3233/FI-2011-538

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 201-215, 2011

Authors: Kleijn, Jetty | Koutny, Maciej

Article Type: Research Article

Abstract: In membrane systems, biochemical reactions taking place in the compartments of a cell are abstracted to evolution rules that specify which and how many objects are consumed and produced. The recently proposed reaction systems also investigate processes carried by biochemical reactions, but the resulting computational model is remarkably different. A key difference is that in reaction systems, biochemical reactions are modeled using a qualitative rather than a quantitative approach. In this paper, we introduce so-called set membrane systems, a variant of membrane systems with qualitative evolution rules inspired by reaction systems. We then relate set membrane systems to Petri nets …which leads to a new class of Petri nets: set-nets with localities. This Petri net model provides a faithful match with the operational semantics of set membrane systems. Show more

Keywords: membrane system, reaction system, biochemistry, natural computing, Petri net, set-net, locality, inhibitor, promoter

DOI: 10.3233/FI-2011-539

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 217-230, 2011

Authors: Kunc, Michal | Okhotin, Alexander

Article Type: Research Article

Abstract: The number of states in a two-way nondeterministic finite automaton (2NFA) needed to represent intersection of languages given by an m-state 2NFA and an n-state 2NFA is shown to be at least m+n and at most m+n+1. For the union operation, the number of states is exactly m+n. The lower bound is established for languages over a one-letter alphabet. The key point of the argument is the following number-theoretic lemma: for all m, n ≥ 2 with m, n ≠ 6 (and with finitely many other exceptions), there exist partitions m = p1 +. . .+ pk and …n = q1 +. . .+ql , where all numbers p1 , . . . , pk , q1 , . . . , ql ≥ 2 are powers of pairwise distinct primes. For completeness, an analogous statement about partitions of any two numbers m, n ∉ {4, 6} (with a few more exceptions) into sums of pairwise distinct primes is established as well. Show more

Keywords: Finite automata, two-way automata, state complexity, partitions into sums of primes

DOI: 10.3233/FI-2011-540

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 231-239, 2011

Authors: Morita, Kenichi

Article Type: Research Article

Abstract: A two-way reversible multi-head finite automaton (RMFA) is introduced as a simple model of reversible computing, and its language accepting capability is studied. We show that various non-regular context-free languages, and non-context-free context-sensitive languages are accepted by RMFAs with a few heads. For example, we give an RMFA with three heads that accepts the language consisting of all words whose length is a prime number. A construction method of a garbage-less RMFA from a given RFMA is also shown.

Keywords: reversible computing, multi-head finite automaton, language recognition

DOI: 10.3233/FI-2011-541

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 241-254, 2011

Authors: Okubo, Fumiya | Yokomori, Takashi

Article Type: Research Article

Abstract: Hairpin completion and its variant called bounded hairpin completion are operations on formal languages, inspired by a hairpin formation in molecular biology. Another variant called hairpin lengthening has been recently introduced, and the related closure properties and algorithmic problems concerning several families of languages have been studied. In this paper, we introduce a new operation of this kind, called hairpin incompletion which is not only an extension of bounded hairpin completion, but also a restricted (bounded) variant of hairpin lengthening. Further, the hairpin incompletion operation provides a formal language theoretic framework that models a bio-molecular technique nowadays known as Whiplash …PCR. We study the closure properties of language families under both the operation and its iterated version. We show that a family of languages closed under intersection with regular sets, concatenation with regular sets, and finite union is closed under one-sided iterated hairpin incompletion, and that a family of languages containing all linear languages and closed under circular permutation, left derivative and substitution is also closed under iterated hairpin incompletion. Show more

DOI: 10.3233/FI-2011-542

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 255-269, 2011