The theory of well-quasi-ordering: a frequently discovered concept

DOI10.1016/0097-3165(72)90063-5zbMath0244.06002OpenAlexW2110917011WikidataQ55881457 ScholiaQ55881457MaRDI QIDQ2554710

Publication date: 1972

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(72)90063-5

Mathematics Subject Classification ID

Partial orders, general (06A06)

Related Items (only showing first 100 items - show all)

The tree alternative conjecture under the topological minor relation ⋮ Subgraph complementation and minimum rank ⋮ On total regulators generated by derivation relations ⋮ Well quasi-orders and regular languages ⋮ An infinite antichain of planar tanglegrams ⋮ Termination of rewriting ⋮ Reverse mathematical bounds for the termination theorem ⋮ Computable linearizations of well-partial-orderings ⋮ On well-quasi-ordering-finite graphs by immersion ⋮ Learning languages in a union ⋮ A notion of branching rank for semilattices with descending chain condition ⋮ Well quasi-orders arising from finite ordered semigroups ⋮ Vietoris hyperspaces over scattered Priestley spaces ⋮ Ordinal notation systems corresponding to Friedman's linearized well-partial-orders with gap-condition ⋮ Finite automata and algebraic extensions of functions fields ⋮ Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs ⋮ Integer packing sets form a well-quasi-ordering ⋮ Using unavoidable set of trees to generalize Kruskal's theorem ⋮ WQO is decidable for factorial languages ⋮ Well-quasi-order of relabel functions ⋮ Definability in the structure of words with the inclusion relation ⋮ Unification in commutative semigroups ⋮ Inventories of unavoidable languages and the word-extension conjecture ⋮ Well quasi-orders generated by a word-shuffle rewriting ⋮ Labelled induced subgraphs and well-quasi-ordering ⋮ The Möbius function of generalized subword order ⋮ Theory of interaction ⋮ Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces ⋮ On block pumpable languages ⋮ Corrigendum to: ``Finiteness theorems and algorithms for permutation invariant chains of Laurent lattice ideals ⋮ Fine hierarchies via Priestley duality ⋮ Controlling a random population ⋮ The maximal linear extension theorem in second order arithmetic ⋮ On well-quasi-ordering finite structures with labels ⋮ Linear Clique‐Width for Hereditary Classes of Cographs ⋮ Bounded-rank tensors are defined in bounded degree ⋮ Basic formulas and languages. I: The theory ⋮ Basic formulas and languages. II: Applications to EOL systems and forms ⋮ Embedding dualities for set partitions and for relational structures ⋮ Developments from enquiries into the learnability of the pattern languages from positive data ⋮ Set systems: order types, continuous nondeterministic deformations, and quasi-orders ⋮ On structural descriptions of lower ideals of series parallel posets ⋮ Better quasi-orders for uncountable cardinals ⋮ Finite Gröbner bases in infinite dimensional polynomial rings and applications ⋮ Generalizations of Khovanskiĭ's theorems on the growth of sumsets in abelian semigroups ⋮ Reduction and covering of infinite reachability trees ⋮ Well, Better and In-Between ⋮ Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind ⋮ Well quasi orders in a categorical setting ⋮ The finite antichain property in Coxeter groups. ⋮ The size of Higman-Haines sets ⋮ The behavior of ascending chain conditions on submodules of bounded finite generation in direct sums ⋮ The complexity of querying indefinite data about linearly ordered domains ⋮ Well-quasi-ordering versus clique-width ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Multiply-Recursive Upper Bounds with Higman’s Lemma ⋮ An order-theoretic characterization of the Howard-Bachmann-hierarchy ⋮ Computable fixpoints in well-structured symbolic model checking ⋮ Partial orders on words, minimal elements of regular languages, and state complexity ⋮ From wqo to bqo, via Ellentuck's theorem ⋮ On the expressiveness of interaction ⋮ Well-partial-orderings and the big Veblen number ⋮ Well rewrite orderings and well quasi-orderings ⋮ On operations and linear extensions of well partially ordered sets ⋮ Well quasi-orders and context-free grammars ⋮ Rationality of the Möbius function of a composition poset ⋮ The Möbius function of a composition poset ⋮ Well-quasi-ordering versus clique-width: new results on bigenic classes ⋮ Degree spectra of structures ⋮ Effective constructions in well-partially-ordered free monoids ⋮ A note on language equations involving morphisms ⋮ Deciding branching time properties for asynchronous programs ⋮ Well quasi-ordered sets and ideals in free semigroups and algebras ⋮ On canonical antichains ⋮ A new class of unique product monoids with applications to ring theory. ⋮ Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes ⋮ Stability in the homology of unipotent groups ⋮ Definability in the \(h\)-quasiorder of labeled forests ⋮ On regularity of context-free languages ⋮ Well-quasi-ordering Does Not Imply Bounded Clique-width ⋮ On well quasi orders of free monoids ⋮ Complexity Hierarchies beyond Elementary ⋮ On quasi orders of words and the confluence property ⋮ Ordered sets with no chains of ideals of a given type ⋮ On power varieties of semigroups ⋮ FI- and OI-modules with varying coefficients ⋮ Modal companions of \(K4^+\) ⋮ Well-quasi-ordering and the Hausdorff quasi-uniformity ⋮ Remarks on a paper of J. Barát and P.P. Varjú ⋮ Combinatorial properties of regressive mappings ⋮ Regular solutions of language inequalities and well quasi-orders ⋮ A regularity test for dual bordered OS systems ⋮ A note on off-line machines with 'Brownian' input heads ⋮ Une généralisation des théorèmes de Higman et de Simon aux mots infinis ⋮ Rules with parameters in modal logic. I. ⋮ Dimension de Krull des ensembles ordonnés. (Krull dimension of ordered sets) ⋮ Another generalization of Higman's well quasi order result on \(\Sigma ^*\) ⋮ Homomorphic image orders on combinatorial structures. ⋮ Some quasi-ordered classes of finite commutative semigroups ⋮ Generalized Post embedding problems

Cites Work

This page was built for publication: The theory of well-quasi-ordering: a frequently discovered concept