Extending regular expressions with homomorphic replacement

DOI10.1051/ita/2010013zbMath1208.68134OpenAlexW1997713618WikidataQ122688822 ScholiaQ122688822MaRDI QIDQ3566350

Markus Holzer, Henning Bordihn, Juergen Dassow

Publication date: 7 June 2010

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/44620

zbMATH Keywords

computational complexityregular languageshomomorphic replacement

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Word problems, etc. in computability and recursion theory (03D40)

Related Items (3)

Characterising REGEX languages by regular languages equipped with factor-referencing ⋮ Extended regular expressions: succinctness and decidability ⋮ INSIDE THE CLASS OF REGEX LANGUAGES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multi-pattern languages
• Pattern expressions and pattern automata
• Extended regular expressions of star degree at most two
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Complete problems for deterministic polynomial time
• IO and OI. I
• Formal languages defined by uniform substitutions
• The theory of formal languages
• Synchronized regular expressions
• A characterization of context-free languages
• Complexity of some problems concerningL systems
• Parallel context-free languages
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• Recognition of deterministic ETOL languages in logarithmic space
• Cap expressions for context-free languages

This page was built for publication: Extending regular expressions with homomorphic replacement