Deleting string rewriting systems preserve regularity

DOI10.1016/J.TCS.2004.04.009zbMath1071.68034OpenAlexW2054568242MaRDI QIDQ703575

Dieter Hofbauer, Johannes Waldmann

Publication date: 11 January 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.04.009

zbMATH Keywords

Regular languagesContext-free languagesPreserving regularityString rewriting systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (15)

On rationally controlled one-rule insertion systems ⋮ Controlled Term Rewriting ⋮ Termination proofs for string rewriting systems via inverse match-bounds ⋮ On tree automata that certify termination of left-linear term rewriting systems ⋮ Computing by observing: simple systems and simple observers ⋮ Proving Quadratic Derivational Complexities Using Context Dependent Interpretations ⋮ Computational power of two stacks with restricted communication ⋮ On Regularity-Preservation by String-Rewriting Systems ⋮ Computing by commuting. ⋮ Bounded hairpin completion ⋮ Bounded Hairpin Completion ⋮ FINDING FINITE AUTOMATA THAT CERTIFY TERMINATION OF STRING REWRITING SYSTEMS ⋮ Automatic Termination ⋮ Weighted automata computation of edit distances with consolidations and fragmentations ⋮ On prefixal one-rule string rewrite systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Theory of relations. Transl. from the French by P. Clote
• Monadic Thue systems
• Some undecidability results concerning the property of preserving regularity
• Proving termination with multiset orderings
• Context-Limited Grammars
• Regular canonical systems
• Mathematical Foundations of Computer Science 2003
• Mappings which preserve context sensitive languages
• Canonical systems which produce periodic sets
• Formal Reductions of the General Combinatorial Decision Problem

This page was built for publication: Deleting string rewriting systems preserve regularity