Termination proofs for string rewriting systems via inverse match-bounds

DOI10.1007/s10817-005-9024-8zbMath1105.68054OpenAlexW2093130576MaRDI QIDQ851146

Alfons Geser, Johannes Waldmann, Dieter Hofbauer

Publication date: 17 November 2006

Published in: Journal of Automated Reasoning (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2060/20040086792

Mathematics Subject Classification ID

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

Related Items

On rationally controlled one-rule insertion systems ⋮ Lower bounds for runtime complexity of term rewriting ⋮ Match-Bounds with Dependency Pairs for Proving Termination of Rewrite Systems ⋮ Automatic Termination ⋮ Match-bounds revisited ⋮ On prefixal one-rule string rewrite systems

Uses Software

• Matchbox

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deleting string rewriting systems preserve regularity
• Termination of rewriting
• On normalizing, non-terminating one-rule string rewriting systems
• A complete characterization of termination of \(0^p1^q\to 1^r0^s\)
• Match-bounded string rewriting systems
• Context-Limited Grammars
• Mathematical Foundations of Computer Science 2003
• FINDING FINITE AUTOMATA THAT CERTIFY TERMINATION OF STRING REWRITING SYSTEMS
• Mappings which preserve context sensitive languages
• Semi-Thue systems with an inhibitor
• Termination and derivational complexity of confluent one-rule string-rewriting systems