FINDING FINITE AUTOMATA THAT CERTIFY TERMINATION OF STRING REWRITING SYSTEMS

DOI10.1142/S0129054105003108zbMath1097.68052MaRDI QIDQ5462118

Johannes Waldmann, Alfons Geser, Dieter Hofbauer, Hans Zantema

Publication date: 1 August 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

finite automataterminationString rewriting systemsmatch bounds

Mathematics Subject Classification ID

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

Related Items

Termination proofs for string rewriting systems via inverse match-bounds, On tree automata that certify termination of left-linear term rewriting systems, Unnamed Item, Match-Bounds with Dependency Pairs for Proving Termination of Rewrite Systems, Beyond Dependency Graphs, Automatic Termination, Match-bounds revisited

Cites Work

• Deleting string rewriting systems preserve regularity
• Monadic Thue systems
• A complete characterization of termination of \(0^p1^q\to 1^r0^s\)
• Match-bounded string rewriting systems
• Cancellation rules and extended word problems
• Context-Limited Grammars