Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T23:12:50.572Z Has data issue: false hasContentIssue false
  • English
  • Français

Extending regular expressions with homomorphic replacement

Published online by Cambridge University Press:  26 January 2010

Henning Bordihn ,
Jürgen Dassow  and
Markus Holzer
Henning Bordihn
Affiliation:
Institut für Informatik, Universität Potsdam, August-Bebel-Straße 89, 14482 Potsdam, Germany.
Jürgen Dassow
Affiliation:
Fakultät für Informatik, Otto-von-Guericke-Universität Magdeburg, Postfach 4120, 39016 Magdeburg, Germany.
Markus Holzer
Affiliation:
Institut für Informatik, Universität Giessen, Arndtstraße 2, 35392 Giessen, Germany; [email protected]
Get access

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.

Keywords

Regular languageshomomorphic replacementcomputational complexity
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 44 , Issue 2 , April 2010 , pp. 229 - 255
Copyright
© EDP Sciences, 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

A.V. Aho, Algorithms for finding patterns in strings, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen. Elsevier (1990) 255–300.
Albert, J. and Wegner, L., Languages with homomorphic replacements, in Proceedings of the 7th International Colloquium on Automata Languages and Programming. Lect. Notes Comput. Sci. 85 (1980) 19–29. CrossRef
J.L. Balcázar, J. Díaz and J. Gabarró, Structural Complexity I. EATCS Monographs on Theoretical Computer Science, Vol. 11. Springer (1988).
Barrington, D.A., Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. System Sci. 38 (1989) 150–164. CrossRef
Birget, J.-C. and Stephen, J.B., Formal languages defined by uniform substitutions. Theoret. Comput. Sci. 132 (1994) 243–258. CrossRef
Câmpeanu, C. and Pattern, S. Yu expressions and pattern automata. Inform. Process. Lett. 92 (2004) 267–274. CrossRef
Dassow, J. and Lange, K.-J., 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. CrossRef
J. Dassow and Gh. Păun, Regulated Rewriting in Formal Language Theory. EATCS Monographs in Theoretical Computer Science, Vol. 18. Springer (1989).
Dembiński, P. and Małuszyński, J., 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. CrossRef
D. Dougherty, sed & awk. O'Reilly & Associates (1990).
Engelfriet, J. and Schmidt, E.M., OI, IO . Part I and II. J. Comput. System Sci. 15 (1977) 328–353; J. Comput. System Sci. 16 (1977) 67–99. CrossRef
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.
Gruska, J., A characterization of context-free languages. J. Comput. System Sci. 5 (1971) 353–364. CrossRef
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.
Hashiguchi, K. and Yoo, H., Extended regular expressions of degree at most two. Theoret. Comput. Sci. 76 (1990) 273–284. CrossRef
J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979).
Jones, N.D. and Laaser, W.T., Complete problems for deterministic polynomial time. Theoret. Comput. Sci. 3 (1977) 105–117. CrossRef
Jones, N.D. and Skyum, S., Recognition of deterministic ET0L languages in logarithmic space. Inform. Comput. 35 (1977) 177–181.
Jones, N.D. and Skyum, S., Complexity of some problems concerning L systems. Math. Syst. Theor. 13 (1979) 29–43. CrossRef
Kari, L., Mateescu, A., Păun, Gh. and Salomaa, A., Multi-pattern languages. Theoret. Comput. Sci. 141 (1995) 253–268. CrossRef
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.
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.
Ochmanski, E., Regular behaviour for concurrent processes. Bulletin of the European Association for Theoretical Computer Science 27 (1985) 56–67.
Della Penna, G., Intrigilla, B., Tronci, E. and Venturini Zilli, M., Synchronized regular expressions. Acta Informatica 39 (2003) 31–70. CrossRef
G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems, Pure and Applied Mathematics, Vol. 90. Academic Press (1980).
Edited by G. Rozenberg and A. Salomaa, Handbook of Formal Languages, Vols. 1–3. Springer (1997).
Siromoney, R. and Krithivasan, K., Parallel context-free grammars. Inform. Control. 24 (1974) 155–162. CrossRef
Sudborough, I.H., A note on tape-bounded complexity classes and linear context-free languages. J. ACM 22 (1975) 499–500. CrossRef
Yntema, M.K., Cap expressions for context-free languages. Inform. Control. 18 (1971) 311–318. CrossRef