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

DOI10.1016/J.TCS.2015.07.012MaRDI QIDQ744984zbMATHOpenAlexFDO

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Recommendations

• Linearizing bad sequences: upper bounds for the product and majoring well quasi-orders
• Complexity of controlled bad sequences over finite sets of \(\mathbb{N}^d\)
• Multiply-recursive upper bounds with Higman's lemma
• On well-quasi-ordering finite sequences
• scientific article; zbMATH DE number 536973

Cites work

• scientific article; zbMATH DE number 3921958 (Why is no real title available?)
• scientific article; zbMATH DE number 1256757 (Why is no real title available?)
• scientific article; zbMATH DE number 1142316 (Why is no real title available?)
• scientific article; zbMATH DE number 3247155 (Why is no real title available?)
• Alternating automata on data trees and XPath satisfiability
• Complexity bounds for some finite forms of Kruskal's theorem
• Ensuring completeness of symbolic verification methods for infinite-state systems
• Graph minors. XX: Wagner's conjecture
• Hierarchies of number-theoretic functions. I
• Multiply-recursive upper bounds with Higman's lemma
• Nonconstructive tools for proving polynomial-time decidability
• On Ordered Division Rings
• On the finite containment problem for Petri nets
• Ordering by Divisibility in Abstract Algebras
• Ordinal recursive bounds for Higman's theorem
• Partial well‐ordering of sets of vectors
• Petri nets and large finite sets
• Proving termination with multiset orderings
• The ordinal-recursive complexity of timed-arc Petri nets, data nets, and other enriched nets
• Using unavoidable set of trees to generalize Kruskal's theorem
• Weak Bisimulation Approximants
• Well rewrite orderings and well quasi-orderings
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• Well-structured transition systems everywhere!

Cited in

(6)

• Multiply-recursive upper bounds with Higman's lemma
• The Parametric Complexity of Lossy Counter Machines
• Linearizing bad sequences: upper bounds for the product and majoring well quasi-orders
• Complexity of controlled bad sequences over finite sets of \(\mathbb{N}^d\)
• Population protocols: beyond runtime analysis
• Complexity hierarchies beyond elementary

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)