Automatic Termination

DOI10.1007/978-3-642-02348-4_1MaRDI QIDQ3636815zbMATH OpenOpenAlexFDO

Authors Johannes Waldmann

Publication date 30 June 2009

Published in Rewriting Techniques and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02348-4_1

Mathematics Subject Classification ID

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

Recommendations

• Weighted automata for proving termination of string rewriting
• Max/Plus tree automata for termination of term rewriting
• Weighted automata define a hierarchy of terminating string rewriting systems
• Matrix Interpretations for Proving Termination of Term Rewriting
• Matrix interpretations for proving termination of term rewriting

Cites work

• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 1944407 (Why is no real title available?)
• scientific article; zbMATH DE number 2146309 (Why is no real title available?)
• scientific article; zbMATH DE number 2182486 (Why is no real title available?)
• scientific article; zbMATH DE number 3299786 (Why is no real title available?)
• A Kleene theorem for weighted tree automata
• A complete characterization of termination of \(0^p1^q\to 1^r0^s\)
• Arctic Termination ...Below Zero
• Certification of Proving Termination of Term Rewriting by Matrix Interpretations
• Complexity analysis of term rewriting based on matrix and context dependent interpretations
• Deleting string rewriting systems preserve regularity
• FINDING FINITE AUTOMATA THAT CERTIFY TERMINATION OF STRING REWRITING SYSTEMS
• Local Termination
• Match-bounded string rewriting systems
• Matrix interpretations for proving termination of term rewriting
• Monadic Thue systems
• On semigroups of matrices over the tropical semiring
• On tree automata that certify termination of left-linear term rewriting systems
• Peg-solitaire, string rewriting systems and finite automata
• Proving Termination of Rewrite Systems Using Bounds
• Term rewriting and applications. 18th international conference, RTA 2007, Paris, France, June 26--28, 2007. Proceedings
• Termination by Quasi-periodic Interpretations
• Termination of String Rewriting with Matrix Interpretations
• Termination of rewriting systems by polynomial interpretations and its implementation
• Termination of term rewriting using dependency pairs
• Termination proofs for string rewriting systems via inverse match-bounds
• Theory and Applications of Satisfiability Testing
• Weighted automata define a hierarchy of terminating string rewriting systems
• Weighted automata for proving termination of string rewriting
• Weighted tree automata and weighted logics

Cited in

(7)

• Weighted automata for proving termination of string rewriting
• Max/Plus tree automata for termination of term rewriting
• Weighted automata
• Arctic Termination ...Below Zero
• Lower bounds for runtime complexity of term rewriting
• Weighted automata define a hierarchy of terminating string rewriting systems
• Efficient completion of weighted automata

Describes a project that uses

Uses Software

• REVE
• CoLoR
• MiniSat
• Coq

This page was built for publication: Automatic Termination

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