Deleting string rewriting systems preserve regularity
From MaRDI portal
Publication:703575
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
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
