Extending regular expressions with homomorphic replacement

Henning Bordihn; Jürgen Dassow; Markus Holzer

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 44, Issue: 2, page 229-255
  • ISSN: 0988-3754

Abstract

top
We define H- and EH-expressions as extensions of regular expressions by adding homomorphic and iterated homomorphic replacement as new operations, resp. The definition is analogous to the extension given by Gruska in order to characterize context-free languages. We compare the families of languages obtained by these extensions with the families of regular, linear context-free, context-free, and EDT0L languages. Moreover, relations to language families based on patterns, multi-patterns, pattern expressions, H-systems and uniform substitutions are also investigated. Furthermore, we present their closure properties with respect to TRIO operations and discuss the decidability status and complexity of fixed and general membership, emptiness, and the equivalence problem.

How to cite

top

Bordihn, Henning, Dassow, Jürgen, and Holzer, Markus. "Extending regular expressions with homomorphic replacement." RAIRO - Theoretical Informatics and Applications 44.2 (2010): 229-255. <http://eudml.org/doc/250764>.

@article{Bordihn2010,
abstract = { We define H- and EH-expressions as extensions of regular expressions by adding homomorphic and iterated homomorphic replacement as new operations, resp. The definition is analogous to the extension given by Gruska in order to characterize context-free languages. We compare the families of languages obtained by these extensions with the families of regular, linear context-free, context-free, and EDT0L languages. Moreover, relations to language families based on patterns, multi-patterns, pattern expressions, H-systems and uniform substitutions are also investigated. Furthermore, we present their closure properties with respect to TRIO operations and discuss the decidability status and complexity of fixed and general membership, emptiness, and the equivalence problem. },
author = {Bordihn, Henning, Dassow, Jürgen, Holzer, Markus},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Regular languages; homomorphic replacement; computational complexity; regular languages; computational complexity},
language = {eng},
month = {5},
number = {2},
pages = {229-255},
publisher = {EDP Sciences},
title = {Extending regular expressions with homomorphic replacement},
url = {http://eudml.org/doc/250764},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Bordihn, Henning
AU - Dassow, Jürgen
AU - Holzer, Markus
TI - Extending regular expressions with homomorphic replacement
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/5//
PB - EDP Sciences
VL - 44
IS - 2
SP - 229
EP - 255
AB - We define H- and EH-expressions as extensions of regular expressions by adding homomorphic and iterated homomorphic replacement as new operations, resp. The definition is analogous to the extension given by Gruska in order to characterize context-free languages. We compare the families of languages obtained by these extensions with the families of regular, linear context-free, context-free, and EDT0L languages. Moreover, relations to language families based on patterns, multi-patterns, pattern expressions, H-systems and uniform substitutions are also investigated. Furthermore, we present their closure properties with respect to TRIO operations and discuss the decidability status and complexity of fixed and general membership, emptiness, and the equivalence problem.
LA - eng
KW - Regular languages; homomorphic replacement; computational complexity; regular languages; computational complexity
UR - http://eudml.org/doc/250764
ER -

References

top
  1. A.V. Aho, Algorithms for finding patterns in strings, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen. Elsevier (1990) 255–300.  
  2. J. Albert and L. Wegner, Languages with homomorphic replacements, in Proceedings of the 7th International Colloquium on Automata Languages and Programming. Lect. Notes Comput. Sci.85 (1980) 19–29.  
  3. J.L. Balcázar, J. Díaz and J. Gabarró, Structural Complexity I. EATCS Monographs on Theoretical Computer Science, Vol. 11. Springer (1988).  
  4. D.A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. System Sci.38 (1989) 150–164.  
  5. J.-C. Birget and J.B. Stephen, Formal languages defined by uniform substitutions. Theoret. Comput. Sci.132 (1994) 243–258.  
  6. C. Câmpeanu and S. Yu, Pattern expressions and pattern automata. Inform. Process. Lett.92 (2004) 267–274.  
  7. J. Dassow and K.-J. Lange, Complexity of automata with abstract storages, in Proceedings of the 8th International Conference on Fundamentals of Computation Theory. Lect. Notes Comput. Sci.529 (1991) 200–209.  
  8. J. Dassow and Gh. Păun, Regulated Rewriting in Formal Language Theory. EATCS Monographs in Theoretical Computer Science, Vol. 18. Springer (1989).  
  9. P. Dembiński and J. Małuszyński, Two level grammars: CF-grammars with equation schemes, in Proceedings of the 6th International Colloquium on Automata Languages and Programming. Lect. Notes Cumput. Sci.71 (1979) 171–187.  
  10. D. Dougherty, sed & awk. O'Reilly & Associates (1990).  
  11. J. Engelfriet and E.M. Schmidt, IO and OI. Part I and II. J. Comput. System Sci.15 (1977) 328–353; J. Comput. System Sci.16 (1977) 67–99.  
  12. D. Giammarresi and A. Restivo, Two-dimensional languages, in Handbook of Formal Languages, Vols. 1–3, edited by G. Rozenberg and A. Salomaa. Springer (1997) 215–267.  
  13. J. Gruska, A characterization of context-free languages. J. Comput. System Sci.5 (1971) 353–364.  
  14. J. Hartmanis, N. Immerman and S. Mahaney, One-way log-tape reductions, in Proceedings of the 19th Annual Symposium on Foundations of Computer Science. IEEE Society Press, Ann Arbor, Michigan (1978) 65–72.  
  15. K. Hashiguchi and H. Yoo, Extended regular expressions of degree at most two. Theoret. Comput. Sci.76 (1990) 273–284.  
  16. J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979).  
  17. N.D. Jones and W.T. Laaser, Complete problems for deterministic polynomial time. Theoret. Comput. Sci.3 (1977) 105–117.  
  18. N.D. Jones and S. Skyum, Recognition of deterministic ET0L languages in logarithmic space. Inform. Comput.35 (1977) 177–181.  
  19. N.D. Jones and S. Skyum, Complexity of some problems concerning L systems. Math. Syst. Theor.13 (1979) 29–43.  
  20. L. Kari, A. Mateescu, Gh. Păun and A. Salomaa, Multi-pattern languages. Theoret. Comput. Sci.141 (1995) 253–268.  
  21. S.C. Kleene, Representation of events in nerve nets and finite automata, in Automata studies, Annals of mathematics studies, Vol. 34, edited by C.E. Shannon and J. McCarthy. Princeton University Press (1956) 2–42.  
  22. A. Mateescu and A. Salomaa, Aspects of classical language theory, in Handbook of Formal Languages, Vols. 1–3, edited by G. Rozenberg and A. Salomaa. Springer (1997) 175–251.  
  23. E. Ochmanski, Regular behaviour for concurrent processes. Bulletin of the European Association for Theoretical Computer Science27 (1985) 56–67.  
  24. G. Della Penna, B. Intrigilla, E. Tronci and M. Venturini Zilli, Synchronized regular expressions. Acta Informatica39 (2003) 31–70.  
  25. G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems, Pure and Applied Mathematics, Vol. 90. Academic Press (1980).  
  26. Edited by G. Rozenberg and A. Salomaa, Handbook of Formal Languages, Vols. 1–3. Springer (1997).  
  27. R. Siromoney and K. Krithivasan, Parallel context-free grammars. Inform. Control.24 (1974) 155–162.  
  28. I.H. Sudborough, A note on tape-bounded complexity classes and linear context-free languages. J. ACM22 (1975) 499–500.  
  29. M.K. Yntema, Cap expressions for context-free languages. Inform. Control.18 (1971) 311–318.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.