Kruskal's tree theorem for acyclic term graphs

zbMATH Open1482.68121arXiv1609.03642MaRDI QIDQ5015375FDOQ5015375

Authors: Georg Moser, Maria A. Schett 

Publication date: 7 December 2021

Full work available at URL: https://arxiv.org/abs/1609.03642

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

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

Uses Software

• AProVE
• TcT
• Grez

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)