Abstract
We introduce and investigate nondeterministic finite automata with the additional ability to apply the hairpin inversion operation to the remaining part of the input. We consider three different modes of hairpin operations, namely left-most hairpin, general hairpin, and right-most hairpin. We show that these operations do not increase the computation power, when the number of operations is bounded by a constant. An unbounded number of these operations leads to language families that are properly contained in the family of context-sensitive languages and are supersets of the family of regular languages. Moreover, we show that in most cases we obtain incomparability results for the language families under consideration. Finally, we summarize closure properties of language families accepted by variants of hairpin finite automata.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adleman, L.: Molecular computation of solutions to combinatorial problems. Science 266, 1021–1024 (1994)
Bordihn, H., Holzer, M., Kutrib, M.: Input reversals and iterated pushdown automata—a new characterization of Khabbaz geometric hierarchy of languages. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol. 3340, pp. 102–113. Springer, Heidelberg (2004)
Bordihn, H., Holzer, M., Kutrib, M.: Revolving-input finite automata. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol. 3572, pp. 168–179. Springer, Heidelberg (2005)
Daley, M., Ibarra, O., Kari, L.: Closure properties and decision questions of some language classes under ciliate bio-operations. Theoretical Computer Science 306, 19–38 (2003)
Daley, M., Kari, L., McQuillan, I.: Families of languages defined by ciliate bio-operations. Theoretical Computer Science 320, 51–69 (2004)
Dassow, J., Holzer, M.: Language families defined by a ciliate bio-operation: Hierarchies and decision problems. International Journal of Foundations of Computer Science 16, 645–662 (2005)
Dassow, J., Mitrana, V., Salomaa, A.: Operations and language generating devices suggested by genome evolution. Theoretical Computer Science 270, 701–738 (2002)
Dassow, J., Păun, G.: Remarks on operations suggested by mutations in genomes. Fundamenta Informaticae 36, 183–200 (1998)
Ehrenfeucht, A., Prescott, D.M., Rozenberg, G.: Computational aspects of gene (un)scrambling in ciliates. In: Landweber, L.F., Winfree, E. (eds.) Evolution as Computation, pp. 45–86. Springer, Heidelberg (2001)
Holzer, M., Kutrib, M.: Flip-pushdown automata: k + 1 pushdown reversals are better than k. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 490–501. Springer, Heidelberg (2003)
Kari, L., Landweber, L.F.: Computational power of gene rearrangement. In: Winfree, E., Gifford, D. (eds.) DNA Based Computers V, DIMACS 54, pp. 207–216 (2000)
Prescott, D.M.: Cutting, slicing, reordering, and elimination of DNA sequences in hypotrichous ciliates. BioEssays 14, 317–324 (1992)
Prescott, D.M.: Genome gymnastics: Unique modes of DNA evolution and processing in ciliates. Nature Review Genetics 1, 191–198 (2000)
Sarkar, P.: Pushdown automaton with the ability to flip its stack. Report TR01-081, Electronic Colloquium on Computational Complexity (ECCC) (November 2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bordihn, H., Holzer, M., Kutrib, M. (2007). Hairpin Finite Automata. In: Harju, T., Karhumäki, J., Lepistö, A. (eds) Developments in Language Theory. DLT 2007. Lecture Notes in Computer Science, vol 4588. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73208-2_13
Download citation
DOI: https://doi.org/10.1007/978-3-540-73208-2_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73207-5
Online ISBN: 978-3-540-73208-2
eBook Packages: Computer ScienceComputer Science (R0)