Deleting string rewriting systems preserve regularity

DOI10.1016/J.TCS.2004.04.009zbMATH Open1071.68034OpenAlexW2054568242MaRDI QIDQ703575FDOQ703575

Authors: 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

Recommendations

• scientific article; zbMATH DE number 2040918
• Some undecidability results concerning the property of preserving regularity
• Small size insertion and deletion systems
• Regularity and context-freeness over word rewriting systems
• On the property of preserving regularity for string-rewriting systems

zbMATH Keywords

Regular languagesContext-free languagesPreserving regularityString rewriting systems

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (17)

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

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

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