Match-bounds revisited

DOI10.1016/J.IC.2009.02.010MaRDI QIDQ1041044zbMATH OpenOpenAlexFDO

Authors Martin Korp, Aart Middeldorp

Publication date 27 November 2009

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2009.02.010

zbMATH Keywords

automationdependency pairsmatch-boundsterm rewritingterminationtree automata

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Tight bound for matching
• Erratum to: Tight bound for matching
• Revisiting the matching function
• Tight bounds on maximal and maximum matchings
• scientific article; zbMATH DE number 2081000
• scientific article; zbMATH DE number 5167271
• Improved bounds for Erdős' matching conjecture
• New estimates on the matching problem
• New bounds for matching vector families
• New bounds for matching vector families

Cites work

• Automating the dependency pair method
• Decidability for left-linear growing term rewriting systems.
• FINDING FINITE AUTOMATA THAT CERTIFY TERMINATION OF STRING REWRITING SYSTEMS
• Frontiers of Combining Systems
• scientific article; zbMATH DE number 3729436 (Why is no real title available?)
• scientific article; zbMATH DE number 1765702 (Why is no real title available?)
• Improving dependency pairs
• Logic for Programming, Artificial Intelligence, and Reasoning
• Match-bounded string rewriting systems
• Match-Bounds with Dependency Pairs for Proving Termination of Rewrite Systems
• Mechanizing and improving dependency pairs
• On tree automata that certify termination of left-linear term rewriting systems
• Orderings for term-rewriting systems
• Proving Termination of Rewrite Systems Using Bounds
• Termination of string rewriting proved automatically
• Termination of term rewriting using dependency pairs
• Termination proofs for string rewriting systems via inverse match-bounds
• Tyrolean termination tool: techniques and features

Cited in

(11)

• Match-bounded string rewriting systems
• Cwikel's bound reloaded
• Match-Bounds with Dependency Pairs for Proving Termination of Rewrite Systems
• Reachability, confluence, and termination analysis with state-compatible automata
• Beyond Dependency Graphs
• CSI -- a confluence tool
• Mathematical Foundations of Computer Science 2003
• Proving Termination of Rewrite Systems Using Bounds
• Term Rewriting and Applications
• Termination proofs for string rewriting systems via inverse match-bounds
• On tree automata that certify termination of left-linear term rewriting systems

Describes a project that uses

Uses Software

• AProVE
• Tyrolean
• Matchbox

This page was built for publication: Match-bounds revisited

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