Extending regular expressions with homomorphic replacement

DOI10.1051/ITA/2010013MaRDI QIDQ3566350zbMATH OpenOpenAlexWikidataFDO

Authors Markus Holzer, Henning Bordihn, Jürgen 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, https://semanticscholar.org/paper/0f5932372f835529df0fc06a101c751bc8eede5a

zbMATH Keywords

computational complexityhomomorphic replacementregular languages

Mathematics Subject Classification ID

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

Recommendations

• Inside the class of REGEX languages
• Inside the Class of REGEX Languages
• Pattern expressions and pattern automata
• scientific article; zbMATH DE number 1502115
• scientific article; zbMATH DE number 1008508

Cites work

• A characterization of context-free languages
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Cap expressions for context-free languages
• Complete problems for deterministic polynomial time
• Complexity of some problems concerningL systems
• Extended regular expressions of star degree at most two
• Formal languages defined by uniform substitutions
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3692678 (Why is no real title available?)
• scientific article; zbMATH DE number 3720386 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 1346517 (Why is no real title available?)
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• scientific article; zbMATH DE number 3802813 (Why is no real title available?)
• IO and OI. I
• Multi-pattern languages
• Parallel context-free languages
• Pattern expressions and pattern automata
• Recognition of deterministic ETOL languages in logarithmic space
• Synchronized regular expressions
• The theory of formal languages

Cited in

(5)

• Characterising REGEX languages by regular languages equipped with factor-referencing
• Extended regular expressions: succinctness and decidability
• scientific article; zbMATH DE number 1502115 (Why is no real title available?)
• Inside the class of REGEX languages
• On the computational and descriptional complexity of multi-pattern languages

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3566350)