Finding finite automata that certify termination of string rewriting

DOI10.1007/978-3-540-30500-2_13MaRDI QIDQ5463973zbMATH OpenOpenAlexFDO

Authors Alfons Geser, Dieter Hofbauer, Johannes Waldmann, Hans Zantema

Publication date 17 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b105090

Mathematics Subject Classification ID

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

Recommendations

• FINDING FINITE AUTOMATA THAT CERTIFY TERMINATION OF STRING REWRITING SYSTEMS
• Weighted automata for proving termination of string rewriting
• Termination of string rewriting proved automatically
• Termination proofs for string rewriting systems via inverse match-bounds
• Automata Presenting Structures: A Survey of the Finite String Case
• A Finite Axiomatisation of Finite-State Automata Using String Diagrams
• Reducing the gradedness problem of string rewriting systems to a termination problem
• Proving non-termination by finite automata
• A string diagrammatic axiomatisation of finite-state automata
• A canonical automaton for one-rule length-preserving string rewrite systems

Cited in

(13)

• Match-bounded string rewriting systems
• Finding and certifying loops
• Weighted automata for proving termination of string rewriting
• Efficient completion of weighted automata
• Sparse tiling through overlap closures for termination of string rewriting
• Proving non-termination by finite automata
• Transforming cycle rewriting into string rewriting
• Mathematical Foundations of Computer Science 2003
• Proving Termination of Rewrite Systems Using Bounds
• FINDING FINITE AUTOMATA THAT CERTIFY TERMINATION OF STRING REWRITING SYSTEMS
• On tree automata that certify termination of left-linear term rewriting systems
• Termination of string rewriting proved automatically
• On tree automata that certify termination of left-linear term rewriting systems

Describes a project that uses

Uses Software

• AProVE
• TORPA
• Matchbox

This page was built for publication: Finding finite automata that certify termination of string rewriting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5463973)