Two-sided derivatives for regular expressions and for hairpin expressions. (English) Zbl 1377.68105
Dediu, Adrian-Horia (ed.) et al., Language and automata theory and applications. 7th international conference, LATA 2013, Bilbao, Spain, April 2–5, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-37063-2/pbk). Lecture Notes in Computer Science 7810, 202-213 (2013).
Summary: The aim of this paper is to design the polynomial construction of a finite recognizer for hairpin completions of regular languages. This is achieved by considering completions as new expression operators and by applying derivation techniques to the associated extended expressions called hairpin expressions. More precisely, we extend partial derivation of regular expressions to two-sided partial derivation of hairpin expressions and we show how to deduce a recognizer for a hairpin expression from its two-sided derived term automaton, providing an alternative proof of the fact that hairpin completions of regular languages are linear context-free.
For the entire collection see [Zbl 1258.68008].
For the entire collection see [Zbl 1258.68008].
MSC:
| 68Q45 | Formal languages and automata |
Keywords:
finite automaton; partial derivation; two-sided derivation; linear context-free language; hairpin completion of regular languages; hairpin expressionReferences:
| [1] | Antimirov, V., Partial derivatives of regular expressions and finite automaton constructions, Theoret. Comput. Sci., 155, 291-319 (1996) · Zbl 0872.68120 · doi:10.1016/0304-3975(95)00182-4 |
| [2] | Brzozowski, J.A.: Regular-like expressions for some irregular languages. In: SWAT (FOCS), pp. 278-286. IEEE Computer Society (1968) |
| [3] | Caron, P.; Champarnaud, J.-M.; Mignot, L.; Dediu, A.-H.; Inenaga, S.; Martín-Vide, C., Partial Derivatives of an Extended Regular Expression, Language and Automata Theory and Applications, 179-191 (2011), Heidelberg: Springer, Heidelberg · Zbl 1330.68148 · doi:10.1007/978-3-642-21254-3_13 |
| [4] | Caron, P.; Champarnaud, J.-M.; Mignot, L.; Moreira, N.; Reis, R., Multi-Tilde-Bar Derivatives, Implementation and Application of Automata, 321-328 (2012), Heidelberg: Springer, Heidelberg · Zbl 1297.68110 · doi:10.1007/978-3-642-31606-7_28 |
| [5] | Champarnaud, J.-M.; Jeanne, H.; Mignot, L.; Dediu, A.-H.; Martín-Vide, C., Approximate Regular Expressions and Their Derivatives, Language and Automata Theory and Applications, 179-191 (2012), Heidelberg: Springer, Heidelberg · Zbl 1350.68165 · doi:10.1007/978-3-642-28332-1_16 |
| [6] | Cheptea, D., Martìn-Vide, C., Mitrana, V.: A new operation on words suggested by DNA biochemistry: hairpin completion. Transgressive Computing, 216-228 (2006) · Zbl 1191.92013 |
| [7] | Diekert, V.; Kopecki, S.; Mitrana, V., Deciding regularity of hairpin completions of regular languages in polynomial time, Inf. Comput., 217, 12-30 (2012) · Zbl 1279.68093 · doi:10.1016/j.ic.2012.04.003 |
| [8] | Kari, L.; Seki, S.; Kopecki, S., On the regularity of iterated hairpin completion of a single word, Fundam. Inform., 110, 1-4, 201-215 (2011) · Zbl 1229.68064 |
| [9] | Kleene, S., Representation of events in nerve nets and finite automata, Automata Studies Ann. Math. Studies, 34, 3-41 (1956) |
| [10] | Lombardy, S.; Sakarovitch, J., Derivatives of rational expressions with multiplicity, Theor. Comput. Sci., 332, 1-3, 141-177 (2005) · Zbl 1070.68074 · doi:10.1016/j.tcs.2004.10.016 |
| [11] | Manea, F.; Martín-Vide, C.; Mitrana, V., On some algorithmic problems regarding the hairpin completion, Discrete Applied Mathematics, 157, 9, 2143-2152 (2009) · Zbl 1185.68392 · doi:10.1016/j.dam.2007.09.022 |
| [12] | 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) · Zbl 1160.68022 · doi:10.1016/j.tcs.2008.09.049 |
| [13] | Sempere, J. M., On a class of regular-like expressions for linear languages, Journal of Automata, Languages and Combinatorics, 5, 3, 343-354 (2000) · Zbl 0960.68099 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
