Linearizing well quasi-orders and bounding the length of bad sequences
DOI10.1016/J.TCS.2015.07.012zbMATH Open1347.03086OpenAlexW1452987818MaRDI QIDQ744984FDOQ744984
Authors: Sergio Abriola, Santiago Figueira, Gabriel Senno 
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
Recommendations
lexicographic orderingfast growing hierarchywell quasi-ordercontrolled bad sequencemajoring orderingmultiset orderingproduct ordering
Other combinatorial set theory (03E05) Recursive functions and relations, subrecursive hierarchies (03D20)
Cites Work
- Graph minors. XX: Wagner's conjecture
- Nonconstructive tools for proving polynomial-time decidability
- Proving termination with multiset orderings
- Weak Bisimulation Approximants
- Partial well‐ordering of sets of vectors
- Multiply-recursive upper bounds with Higman's lemma
- Hierarchies of number-theoretic functions. I
- Well-structured transition systems everywhere!
- Title not available (Why is that?)
- On Ordered Division Rings
- Ordering by Divisibility in Abstract Algebras
- Title not available (Why is that?)
- Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
- The Ordinal-Recursive Complexity of Timed-arc Petri Nets, Data Nets, and Other Enriched Nets
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Ensuring completeness of symbolic verification methods for infinite-state systems
Cited In (6)
- The Parametric Complexity of Lossy Counter Machines
- Lower bounds on the state complexity of population protocols
- Multiply-recursive upper bounds with Higman's lemma
- Complexity hierarchies beyond elementary
- Linearizing bad sequences: upper bounds for the product and majoring well quasi-orders
- Population protocols: beyond runtime analysis
This page was built for publication: Linearizing well quasi-orders and bounding the length of bad sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744984)
