Linearizing well quasi-orders and bounding the length of bad sequences
From MaRDI portal
Publication:744984
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
lexicographic orderingfast growing hierarchywell quasi-ordercontrolled bad sequencemajoring orderingmultiset orderingproduct ordering
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
