PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
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.
Wydawca
Rocznik
Strony
425--455
Opis fizyczny
Bibliogr. 24 poz.
Twórcy
  • LITIS, Université de Rouen, 76801 Saint-Étienne du Rouvray Cedex, France
  • LITIS, Université de Rouen, 76801 Saint-Étienne du Rouvray Cedex, France
autor
  • LITIS, Université de Rouen, 76801 Saint-Étienne du Rouvray Cedex, France
autor
  • 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-fc8182d8-a3ad-4519-a899-363c8d03bb69
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.