Article

Complexity results and the growths of hairpin completions of regular languages

Authors:

Volker Diekert,

Steffen KopeckiAuthors Info & Claims

CIAA'10: Proceedings of the 15th international conference on Implementation and application of automata

Pages 105 - 114

Published: 12 August 2010 Publication History

Abstract

The hairpin completion is a natural operation on formal languages which has been inspired by molecular phenomena in biology and by DNA-computing. In 2009 we presented in [6] a (polynomial time) decision algorithm to decide regularity of the hairpin completion. In this paper we provide four new results: 1.) We show that the decision problem is NL-complete. 2.) There is a polynomial time decision algorithm which runs in time O(n⁸), this improves [6], which provided O(n²⁰). 3.) For the one-sided case (which is closer to DNA computing) the time is O(n²), only. 4.) The hairpin completion is unambiguous linear context-free. This result allows to compute the growth (generating function) of the hairpin completion and to compare it with the growth of the underlying regular language.

References

[1]

Baker, B.S., Book, R.V.: Reversal-bounded multi-pushdown machines. In: Annual IEEE Symposium on Foundations of Computer Science, pp. 207-211 (1972).

Digital Library

[2]

Berstel, J., Reutenauer, C.: Rational series and their languages. Springer, New York (1988).

Digital Library

[3]

Ceccherini-Silberstein, T.: On the growth of linear languages. Advances in Applied Mathematics 35(3), 243-253 (2005).

Digital Library

[4]

Cheptea, D., Martin-Vide, C., Mitrana, V.: A new operation on words suggested by DNA biochemistry: Hairpin completion. Transgressive Computing, 216-228 (2006).

[5]

Deaton, R., Murphy, R., Garzon, M., Franceschetti, D., Stevens, S.: Good encodings for DNA-based solutions to combinatorial problems. In: Proc. of DNA-Based computers DIMACS Series, vol. 44, pp. 247-258 (1998).

[6]

Diekert, V., Kopecki, S., Mitrana, V.: On the hairpin completion of regular languages. In: Leucker, M., Morgan, C. (eds.) ICTAC 2009. LNCS, vol. 5684, pp. 170-184. Springer, Heidelberg (2009).

Digital Library

[7]

Diekert, V., Kopecki, S.: Complexity Result and the Growths of Hairpin Completions of Regular Languages. Technical Report Computer Science 2010/04, University of Stuttgart (June 2010).

[8]

Garzon, M., Deaton, R., Neathery, P., Murphy, R., Franceschetti, D., Stevens, E.: On the encoding problem for DNA computing. In: The Third DIMACS Workshop on DNA-Based Computing, pp. 230-237 (1997).

[9]

Garzon, M., Deaton, R., Nino, L., Stevens Jr., S., Wittner, M.: Genome encoding for DNA computing. In: Proc. Third Genetic Programming Conference, pp. 684- 690 (1998).

[10]

Gawrychowski, P., Krieger, D., Rampersad, N., Shallit, J.: Finding the growth rate of a regular or context-free language in polynomial time. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 339-358. Springer, Heidelberg (2008).

Digital Library

[11]

Greibach, S.A.: A note on undecidable properties of formal languages. Mathematical Systems Theory 2(1), 1-6 (1968).

[12]

Hopcroft, J.E., Ulman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979).

Digital Library

[13]

Kari, L., Konstantinidis, S., Losseva, E., Sosík, P., Thierrin, G.: Hairpin structures in DNA words. In: Carbone, A., Pierce, N.A. (eds.) DNA 2005. LNCS, vol. 3892, pp. 158-170. Springer, Heidelberg (2006).

Digital Library

[14]

Kari, L., Mahalingam, K., Thierrin, G.: The syntactic monoid of hairpin-free languages. Acta Inf. 44(3-4), 153-166 (2007).

Digital Library

[15]

Kuich, W.: On the entropy of context-free languages. Information and Control 16, 173-200 (1970).

[16]

Manea, F., Mitrana, V., Yokomori, T.: Two complementary operations inspired by the DNA hairpin formation: Completion and reduction. Theor. Comput. Sci. 410(4- 5), 417-425 (2009).

Digital Library

[17]

Papadimitriou, C.H.: Computatational Complexity. Addison Wesley, Reading (1994).

[18]

Sakamoto, K., Gouzu, H., Komiya, K., Kiga, D., Yokoyama, S., Yokomori, T., Hagiya, M.: Molecular Computation byDNA Hairpin Formation. Science 288(5469), 1223-1226 (2000).

Cited By

Kari LKopecki SSeki S(2012)Iterated hairpin completions of non-crossing wordsProceedings of the 38th international conference on Current Trends in Theory and Practice of Computer Science10.1007/978-3-642-27660-6_28(337-348)Online publication date: 21-Jan-2012
https://dl.acm.org/doi/10.1007/978-3-642-27660-6_28

Index Terms

Complexity results and the growths of hairpin completions of regular languages
1. Theory of computation

Recommendations

Deciding regularity of hairpin completions of regular languages in polynomial time

Hairpin completion is an operation on formal languages that has been inspired by hairpin formation in DNA biochemistry and by DNA computing. In this paper we investigate the one- and two-sided hairpin completion of regular languages. We solve an open ...
Hairpin completions and reductions: semilinearity properties
Abstract
This paper is part of the investigation of some operations on words and languages with motivations coming from DNA biochemistry, namely three variants of hairpin completion and three variants of hairpin reduction. Since not all the hairpin ...
On the Hairpin Completion of Regular Languages
ICTAC '09: Proceedings of the 6th International Colloquium on Theoretical Aspects of Computing

The hairpin completion is a natural operation of formal languages which has been inspired by molecular phenomena in biology and by DNA-computing. The hairpin completion of a regular language is linear context-free and we consider the problem to decide ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CIAA'10: Proceedings of the 15th international conference on Implementation and application of automata

August 2010

332 pages

ISBN:9783642180972

Editors:
Michael Domaratzki
University of Manitoba, Department of Computer Science, Winnipeg, MB, Canada
,
Kai Salomaa
Queen's University, School of Computing Kingston, ON, Canada

Sponsors

The Fields Institute
UMANITOBA: University of Manitoba
MITACS

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 12 August 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kari LKopecki SSeki S(2012)Iterated hairpin completions of non-crossing wordsProceedings of the 38th international conference on Current Trends in Theory and Practice of Computer Science10.1007/978-3-642-27660-6_28(337-348)Online publication date: 21-Jan-2012
https://dl.acm.org/doi/10.1007/978-3-642-27660-6_28

View Options

View options

Media

Figures

Other

Tables

View Table of Contents