Linearizing well quasi-orders and bounding the length of bad sequences

DOI10.1016/j.tcs.2015.07.012zbMath1347.03086OpenAlexW1452987818MaRDI QIDQ744984

Gabriel Senno, Sergio Abriola, Santiago Figueira

Publication date: 12 October 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.07.012

zbMATH Keywords

lexicographic orderingfast growing hierarchywell quasi-ordercontrolled bad sequencemajoring orderingmultiset orderingproduct ordering

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Other combinatorial set theory (03E05)

Related Items (4)

Lower bounds on the state complexity of population protocols ⋮ Population protocols: beyond runtime analysis ⋮ The Parametric Complexity of Lossy Counter Machines ⋮ Complexity Hierarchies beyond Elementary

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Petri nets and large finite sets
• Using unavoidable set of trees to generalize Kruskal's theorem
• Ordinal recursive bounds for Higman's theorem
• Well rewrite orderings and well quasi-orderings
• On the finite containment problem for Petri nets
• Complexity bounds for some finite forms of Kruskal's theorem
• Alternating automata on data trees and XPath satisfiability
• The Ordinal-Recursive Complexity of Timed-arc Petri Nets, Data Nets, and Other Enriched Nets
• Multiply-Recursive Upper Bounds with Higman’s Lemma
• Weak Bisimulation Approximants
• Nonconstructive tools for proving polynomial-time decidability
• Proving termination with multiset orderings
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• Hierarchies of number-theoretic functions. I
• On Ordered Division Rings
• Ordering by Divisibility in Abstract Algebras
• Partial well‐ordering of sets of vectors
• Well-structured transition systems everywhere!
• Ensuring completeness of symbolic verification methods for infinite-state systems

This page was built for publication: Linearizing well quasi-orders and bounding the length of bad sequences