Termination and derivational complexity of confluent one-rule string-rewriting systems

DOI10.1016/S0304-3975(00)00367-4zbMath0992.68120OpenAlexW1981958367MaRDI QIDQ5958138

Masashi Katsura, Yuji Kobayashi, Kayoko Shikishima-Tsuji

Publication date: 3 March 2002

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00367-4

zbMATH Keywords

derivation complexitystring rewriting systemtermination problem

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (5)

Termination proofs for string rewriting systems via inverse match-bounds ⋮ A canonical automaton for one-rule length-preserving string rewrite systems ⋮ Match-bounded string rewriting systems ⋮ Decision problems for semi-Thue systems with a few rules ⋮ Non-Looping String Rewriting

Cites Work

• Unnamed Item
• Unnamed Item
• On termination of confluent one-rule string-rewriting systems
• A complete characterization of termination of 0p 1q→1r 0s
• Rewrite systems for integer arithmetic
• On the termination problem for one-rule semi-Thue system
• Confluence of one-rule Thue systems

This page was built for publication: Termination and derivational complexity of confluent one-rule string-rewriting systems