Kruskal's tree theorem for acyclic term graphs

MaRDI QIDQ5015375zbMATH OpenFDO

Authors Georg Moser, Maria A. Schett

Publication date 7 December 2021

Full work available at URL https://arxiv.org/abs/1609.03642, http://eptcs.web.cse.unsw.edu.au/paper.cgi?TERMGRAPH2016.5

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Partial orders, general (06A06) Grammars and rewriting systems (68Q42)

Recommendations

• Using unavoidable set of trees to generalize Kruskal's theorem
• scientific article; zbMATH DE number 1361503
• A constructive proof of the topological Kruskal theorem
• Complexity bounds for some finite forms of Kruskal's theorem
• scientific article; zbMATH DE number 1223728

Cites work

• A combination framework for complexity
• Analysing the complexity of functional programs: higher-order meets first-order
• Complexity of acyclic term graph rewriting
• scientific article; zbMATH DE number 1361503 (Why is no real title available?)
• scientific article; zbMATH DE number 1437942 (Why is no real title available?)
• scientific article; zbMATH DE number 3198033 (Why is no real title available?)
• Non-simplifying graph rewriting termination
• Ordering by Divisibility in Abstract Algebras
• Orderings for term-rewriting systems
• Proving termination and memory safety for programs with pointer arithmetic
• Proving termination of graph transformation systems using weighted type graphs over semirings
• Proving termination of programs automatically with AProVE
• Simple termination of rewrite systems
• Termination analysis for graph transformation systems
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture

Cited in

(4)

• Using unavoidable set of trees to generalize Kruskal's theorem
• Termination of graph transformation systems using weighted subgraph counting
• Termination of graph transformation systems via generalized weighted type graphs
• Termination of graph transformation systems using weighted subgraph counting

Describes a project that uses

Uses Software

• TcT
• Grez
• AProVE

This page was built for publication: Kruskal's tree theorem for acyclic term graphs

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