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 languages, homomorphic replacement, computational complexity
@article{ITA_2010__44_2_229_0,
author = {Bordihn, Henning and Dassow, J\"urgen and Holzer, Markus},
title = {Extending regular expressions with homomorphic replacement},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {229--255},
year = {2010},
publisher = {EDP Sciences},
volume = {44},
number = {2},
doi = {10.1051/ita/2010013},
mrnumber = {2674542},
zbl = {1208.68134},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ita/2010013/}
}
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 - Informatique Théorique et Applications PY - 2010 SP - 229 EP - 255 VL - 44 IS - 2 PB - EDP Sciences UR - https://www.numdam.org/articles/10.1051/ita/2010013/ DO - 10.1051/ita/2010013 LA - en ID - ITA_2010__44_2_229_0 ER -
%0 Journal Article %A Bordihn, Henning %A Dassow, Jürgen %A Holzer, Markus %T Extending regular expressions with homomorphic replacement %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2010 %P 229-255 %V 44 %N 2 %I EDP Sciences %U https://www.numdam.org/articles/10.1051/ita/2010013/ %R 10.1051/ita/2010013 %G en %F ITA_2010__44_2_229_0
Bordihn, Henning; Dassow, Jürgen; Holzer, Markus. Extending regular expressions with homomorphic replacement. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 2, pp. 229-255. doi: 10.1051/ita/2010013
[1] , Algorithms for finding patterns in strings, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen. Elsevier (1990) 255-300. | Zbl
[2] and , Languages with homomorphic replacements, in Proceedings of the 7th International Colloquium on Automata Languages and Programming. Lect. Notes Comput. Sci. 85 (1980) 19-29. | Zbl
[3] , and , Structural Complexity I. EATCS Monographs on Theoretical Computer Science, Vol. 11. Springer (1988). | Zbl
[4] , Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. System Sci. 38 (1989) 150-164. | Zbl
[5] and , Formal languages defined by uniform substitutions. Theoret. Comput. Sci. 132 (1994) 243-258. | Zbl
[6] and , Pattern expressions and pattern automata. Inform. Process. Lett. 92 (2004) 267-274. | Zbl
[7] and , 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. | Zbl
[8] and , Regulated Rewriting in Formal Language Theory. EATCS Monographs in Theoretical Computer Science, Vol. 18. Springer (1989). | Zbl
[9] and , 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. | Zbl
[10] , sed & awk. O'Reilly & Associates (1990).
[11] and , IO and OI. Part I and II. J. Comput. System Sci. 15 (1977) 328-353; J. Comput. System Sci. 16 (1977) 67-99. | Zbl
[12] and , Two-dimensional languages, in Handbook of Formal Languages, Vols. 1-3, edited by G. Rozenberg and A. Salomaa. Springer (1997) 215-267. | Zbl
[13] , A characterization of context-free languages. J. Comput. System Sci. 5 (1971) 353-364. | Zbl
[14] , and , 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] and , Extended regular expressions of degree at most two. Theoret. Comput. Sci. 76 (1990) 273-284. | Zbl
[16] and , Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979). | Zbl
[17] and , Complete problems for deterministic polynomial time. Theoret. Comput. Sci. 3 (1977) 105-117. | Zbl
[18] and , Recognition of deterministic ET0L languages in logarithmic space. Inform. Comput. 35 (1977) 177-181. | Zbl
[19] and , Complexity of some problems concerning L systems. Math. Syst. Theor. 13 (1979) 29-43. | Zbl
[20] , , and , Multi-pattern languages. Theoret. Comput. Sci. 141 (1995) 253-268. | Zbl
[21] , 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] and , 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] , Regular behaviour for concurrent processes. Bulletin of the European Association for Theoretical Computer Science 27 (1985) 56-67.
[24] , , and , Synchronized regular expressions. Acta Informatica 39 (2003) 31-70. | Zbl
[25] and , The Mathematical Theory of L Systems, Pure and Applied Mathematics, Vol. 90. Academic Press (1980). | Zbl
[26] Edited by G. Rozenberg and A. Salomaa, Handbook of Formal Languages, Vols. 1-3. Springer (1997). | Zbl
[27] and , Parallel context-free grammars. Inform. Control. 24 (1974) 155-162. | Zbl
[28] , A note on tape-bounded complexity classes and linear context-free languages. J. ACM 22 (1975) 499-500. | Zbl
[29] , Cap expressions for context-free languages. Inform. Control. 18 (1971) 311-318. | Zbl
Cité par Sources :
