Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions

• Autorzy: Champarnaud J.-M. , Dubernard J.-P. , Jeanne H. , Mignot L.

Identyfikatory

DOI

10.3233/FI-2015-1189

• Języki publikacji: EN

Abstrakty

EN

The aim of this paper is to design a 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.

Słowa kluczowe

EN

expression derivatives; hairpin expression; two sided derivatives; finite recognizer

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 137, nr 4
• Strony: 425--455
• Opis fizyczny: Bibliogr. 24 poz.

Twórcy

autor

Champarnaud J.-M.

• LITIS, Université de Rouen, 76801 Saint-Étienne du Rouvray Cedex, France

autor

Dubernard J.-P.

• LITIS, Université de Rouen, 76801 Saint-Étienne du Rouvray Cedex, France

autor

Jeanne H.

• LITIS, Université de Rouen, 76801 Saint-Étienne du Rouvray Cedex, France

autor

Mignot L.

• LITIS, Université de Rouen, 76801 Saint-Étienne du Rouvray Cedex, France

Bibliografia

• [1] Antimirov, V.: Partial derivatives of regular expressions and finite automaton constructions, Theoret. Comput. Sci., 155, 1996, 291–319.
• [2] Bottoni, P., Labella, A., Manca, V., Mitrana, V.: Superposition Based on Watson-Crick-Like Complementarity, Theory Comput. Syst., 39(4), 2006, 503–524.
• [3] Brzozowski, J. A.: Regular-Like Expressions for Some Irregular Languages, SWAT (FOCS), IEEE Computer Society, 1968.
• [4] Caron, P., Champarnaud, J.-M., Mignot, L.: Partial Derivatives of an Extended Regular Expression, LATA (A. H. Dediu, S. Inenaga, C. Martín-Vide, Eds.), 6638, Springer, 2011, ISBN 978-3-642-21253-6.
• [5] Caron, P., Champarnaud, J.-M., Mignot, L.: Multi-Tilde-Bar Derivatives, CIAA (N. Moreira, R. Reis, Eds.), 7381, Springer, 2012, ISBN 978-3-642-31605-0.
• [6] Castellanos, J., Mitrana, V.: Some Remarks on Hairpin and Loop Languages, Words, Semigroups, and Transductions (M. Ito, G. Paun, S. Yu, Eds.),World Scientific, 2001, ISBN 981-02-4739-7.
• [7] Champarnaud, J.-M., Dubernard, J.-P., Jeanne, H., Mignot, L.: Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions, LATA (A. H. Dediu, C. Martín-Vide, B. Truthe, Eds.), 7810, Springer, 2013, ISBN 978-3-642-37063-2.
• [8] Champarnaud, J.-M., Jeanne, H.,Mignot, L.: Approximate Regular Expressions and Their Derivatives, LATA (A. H. Dediu, C. Martín-Vide, Eds.), 7183, Springer, 2012, ISBN 978-3-642-28331-4.
• [9] Cheptea, D., Martìn-Vide, C., Mitrana, V.: A new operation on words suggested by DNA biochemistry: hairpin completion, Transgressive Computing, 2006, 216–228.
• [10] Diekert, V., Kopecki, S.,Mitrana, V.: On the Hairpin Completion of Regular Languages, ICTAC (M. Leucker, C. Morgan, Eds.), 5684, Springer, 2009, ISBN 978-3-642-03465-7.
• [11] Diekert, V., Kopecki, S., Mitrana, V.: Deciding regularity of hairpin completions of regular languages in polynomial time, Inf. Comput., 217, 2012, 12–30.
• [12] Ito, M., Leupold, P., Manea, F., Mitrana, V.: Bounded hairpin completion, Inf. Comput., 209(3), 2011, 471–485.
• [13] Kari, L., Kopecki, S., Seki, S.: Iterated Hairpin Completions of Non-crossing Words, SOFSEM (M. Bieliková, G. Friedrich, G. Gottlob, S. Katzenbeisser, G. Turán, Eds.), 7147, Springer, 2012, ISBN 978-3-642-27659-0.
• [14] Kari, L., Seki, S., Kopecki, S.: On the Regularity of Iterated Hairpin Completion of a SingleWord, Fundam. Inform., 110(1-4), 2011, 201–215.
• [15] Kleene, S.: Representation of events in nerve nets and finite automata, Automata Studies, Ann. Math. Studies 34, 1956, 3–41, Princeton U. Press.
• [16] Kopecki, S.: On iterated hairpin completion, Theor. Comput. Sci., 412(29), 2011, 3629–3638.
• [17] Lombardy, S., Sakarovitch, J.: Derivatives of rational expressions with multiplicity., Theor. Comput. Sci., 332(1-3), 2005, 141–177.
• [18] Manea, F., Martín-Vide, C., Mitrana, V.: On some algorithmic problems regarding the hairpin completion, Discrete Applied Mathematics, 157(9), 2009, 2143–2152.
• [19] Manea, F., Martín-Vide, C., Mitrana, V.: Hairpin Lengthening, CiE (F. Ferreira, B. Löwe, E. Mayordomo, L. M. Gomes, Eds.), 6158, Springer, 2010, ISBN 978-3-642-13961-1.
• [20] Manea, F.,Mitrana, V.: Hairpin CompletionVersus Hairpin Reduction, CiE (S. B. Cooper, B. Löwe, A. Sorbi, Eds.), 4497, Springer, 2007, ISBN 978-3-540-73000-2.
• [21] Manea, F., Mitrana, V., Yokomori, T.: Two complementary operations inspired by the DNA hairpin formation: Completion and reduction, Theor. Comput. Sci., 410(4-5), 2009, 417–425.
• [22] Manea, F., Mitrana, V., Yokomori, T.: Some Remarks on the Hairpin Completion, Int. J. Found. Comput. Sci., 21(5), 2010, 859–872.
• [23] Mitrana, V., Manea, F.,Martín-Vide, C.: On Some Algorithmic Problems Regarding the Hairpin Completion, Electronic Notes in Discrete Mathematics, 27, 2006, 71–72.
• [24] Sempere, J. M.: On a Class of Regular-like Expressions for Linear Languages, Journal of Automata, Languages and Combinatorics, 5(3), 2000, 343–354.