Deleting string rewriting systems preserve regularity

DOI10.1016/J.TCS.2004.04.009MaRDI QIDQ703575zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Regular languagesContext-free languagesPreserving regularityString rewriting systems

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 1615227 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 2040918 (Why is no real title available?)
• scientific article; zbMATH DE number 194781 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• scientific article; zbMATH DE number 3305019 (Why is no real title available?)
• Canonical systems which produce periodic sets
• Context-Limited Grammars
• Formal Reductions of the General Combinatorial Decision Problem
• Mappings which preserve context sensitive languages
• Mathematical Foundations of Computer Science 2003
• Monadic Thue systems
• Proving termination with multiset orderings
• Regular canonical systems
• Some undecidability results concerning the property of preserving regularity
• Theory of relations. Transl. from the French by P. Clote

Cited in

(17)

• On prefixal one-rule string rewrite systems
• scientific article; zbMATH DE number 2040918 (Why is no real title available?)
• 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)