Match-bounded string rewriting systems

DOI10.1007/s00200-004-0162-8zbMath1101.68048OpenAlexW2137374798MaRDI QIDQ1762560

Alfons Geser, Johannes Waldmann, Dieter Hofbauer

Publication date: 9 February 2005

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

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

zbMATH Keywords

terminationsemi-Thue systemstring rewriting systemmatch-bounded

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Grammars and rewriting systems (68Q42)

Related Items (17)

On rationally controlled one-rule insertion systems ⋮ Termination of string rewriting proved automatically ⋮ Termination proofs for string rewriting systems via inverse match-bounds ⋮ On tree automata that certify termination of left-linear term rewriting systems ⋮ Mechanizing and improving dependency pairs ⋮ Recognizable languages of arrows and cospans ⋮ Unnamed Item ⋮ Match-Bounds with Dependency Pairs for Proving Termination of Rewrite Systems ⋮ Loop detection in term rewriting using the eliminating unfoldings ⋮ Towards a Systematic Method for Proving Termination of Graph Transformation Systems ⋮ Unnamed Item ⋮ FINDING FINITE AUTOMATA THAT CERTIFY TERMINATION OF STRING REWRITING SYSTEMS ⋮ Bottom-up rewriting for words and terms ⋮ Automatic Termination ⋮ Local Termination ⋮ Match-bounds revisited ⋮ On prefixal one-rule string rewrite systems

Cites Work

• Termination of rewriting
• Monadic Thue systems
• Termination of term rewriting: Interpretation and type elimination
• A complete characterization of termination of \(0^p1^q\to 1^r0^s\)
• Context-Limited Grammars
• Non-Looping String Rewriting
• Mathematical Foundations of Computer Science 2003
• Implementation and Application of Automata
• Mappings which preserve context sensitive languages
• The termination hierarchy for term rewriting
• Semi-Thue systems with an inhibitor
• Termination and derivational complexity of confluent one-rule string-rewriting systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Match-bounded string rewriting systems