Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
From MaRDI portal
Publication:5541375
DOI10.2307/1993287zbMath0158.27002OpenAlexW4240833632WikidataQ29032171 ScholiaQ29032171MaRDI QIDQ5541375
Publication date: 1960
Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/1993287
Related Items
Termination of term rewriting by interpretation ⋮ A MATHEMATICAL COMMITMENT WITHOUT COMPUTATIONAL STRENGTH ⋮ Labelled well-quasi-order for permutation classes ⋮ Structure theorem for tournaments omitting N5 ⋮ Embedding with patterns and associated recursive path ordering ⋮ Polynomial time termination and constraint satisfaction tests ⋮ More problems in rewriting ⋮ Unnamed Item ⋮ Nichtbeweisbarkeit von gewissen kombinatorischen Eigenschaften endlicher Bäume;Unprovability of certain combinatorial properties of finite trees ⋮ Unnamed Item ⋮ ASYMPTOTIC ANALYSIS OF SKOLEM’S EXPONENTIAL FUNCTIONS ⋮ E-Unification based on Generalized Embedding ⋮ Une extension d'un théorème de P. Jullien sur les âges de mots ⋮ Generalized fusible numbers and their ordinals ⋮ A proof of the tree alternative conjecture under the topological minor relation ⋮ On approximately identifying concept classes in the limit ⋮ The next 700 program transformers ⋮ Bachmann-Howard derivatives ⋮ Fraïssé’s conjecture in Π11-comprehension ⋮ Unavoidable languages, cuts and innocent sets of words ⋮ Well-quasi-ordering Friedman ideals of finite trees proof of Robertson's magic-tree conjecture ⋮ Unnamed Item ⋮ Deciding Innermost Loops ⋮ Termination Proof of S-Expression Rewriting Systems with Recursive Path Relations ⋮ Unnamed Item ⋮ A Pumping Lemma for Permitting Semi-Conditional Languages ⋮ A Biologically Inspired Model with Fusion and Clonation of Membranes ⋮ SMT-based verification of data-aware processes: a model-theoretic approach ⋮ Strong WQO Tree Theorems ⋮ Recent Progress on Well-Quasi-ordering Graphs ⋮ The Reverse Mathematics of wqos and bqos ⋮ Well-Quasi Orders and Hierarchy Theory ⋮ A Mechanized Proof of Higman’s Lemma by Open Induction ⋮ Well-Partial Orderings and their Maximal Order Types ⋮ Unnamed Item ⋮ Skolem + Tetration Is Well-Ordered ⋮ Gap Embedding for Well-Quasi-Orderings ⋮ Recursive models and the divisibility poset ⋮ The narrowing-driven approach to functional logic program specialization ⋮ Two applications of analytic functors ⋮ Unnamed Item ⋮ On Better-Quasi-Ordering Countable Series-Parallel Orders ⋮ Generalizing Kruskal's theorem to pairs of cohabitating trees ⋮ Laver and set theory ⋮ Graph minor theory ⋮ A Fast-Growing Sequence Inspired by TREE(k) ⋮ Simple termination revisited ⋮ Forward analysis for WSTS, part I: completions ⋮ On the expressive power of process interruption and compensation ⋮ Well-quasi-orderings and sets of finite sequences ⋮ An application of graphical enumeration to PA * ⋮ Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered ⋮ What you always wanted to know about rigid E-unification ⋮ From Kruskal’s theorem to Friedman’s gap condition ⋮ Order-sorted Homeomorphic Embedding Modulo Combinations of Associativity and/or Commutativity Axioms* ⋮ Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs ⋮ Type-Based Homeomorphic Embedding and Its Applications to Online Partial Evaluation ⋮ Calculating Maximal Order Types for Finite Rooted Unstructured Labeled Trees ⋮ A Glimpse of $$ \sum_{3} $$-elementarity ⋮ Well-Quasi-Ordering Infinite Graphs with Forbidden Finite Planar Minor ⋮ The Complexity of the Diagonal Problem for Recursion Schemes ⋮ The tree alternative conjecture under the topological minor relation ⋮ Minimal bad sequences are necessary for a uniform Kruskal theorem ⋮ Equivalence between Fraïssé's conjecture and Jullien's theorem ⋮ Better-quasi-orderings and coinduction ⋮ A comparison of well-known ordinal notation systems for \(\varepsilon _{0}\) ⋮ Algorithm for finding structures and obstructions of tree ideals ⋮ Verification as a parameterized testing (experiments with the SCP4 supercompiler) ⋮ An infinite antichain of planar tanglegrams ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Termination of rewriting ⋮ Graph minors. IV: Tree-width and well-quasi-ordering ⋮ Graph minors. VIII: A Kuratowski theorem for general surfaces ⋮ Computable linearizations of well-partial-orderings ⋮ History and basic features of the critical-pair/completion procedure ⋮ An effective proof of the well-foundedness of the multiset path ordering ⋮ Proving open properties by induction ⋮ Orderings for term-rewriting systems ⋮ Using unavoidable set of trees to generalize Kruskal's theorem ⋮ Certified Kruskal’s Tree Theorem ⋮ Well-quasi-order of relabel functions ⋮ Inventories of unavoidable languages and the word-extension conjecture ⋮ On the verification of membrane systems with dynamic structure ⋮ A notation for lambda terms. A generalization of environments ⋮ Well-quasi-ordering \(H\)-contraction-free graphs ⋮ Modularity in term rewriting revisited ⋮ Simple termination of rewrite systems ⋮ Labelled induced subgraphs and well-quasi-ordering ⋮ Analysis of a Double Kruskal Theorem ⋮ A note on simplification orderings ⋮ Analysing the implicit complexity of programs. ⋮ Deciding safety properties in infinite-state pi-calculus via behavioural types ⋮ Branch-width and Rota's conjecture ⋮ The maximal linear extension theorem in second order arithmetic ⋮ Contracting planar graphs to contractions of triangulations ⋮ On effective construction of the greatest solution of language inequality \(XA\subseteq BX\) ⋮ On well-quasi-ordering finite structures with labels ⋮ Grid classes and partial well order ⋮ On two classes of hereditarily finitely based semigroup identities ⋮ Better quasi-orders for uncountable cardinals ⋮ Intersection properties of graphs ⋮ On Ordinal Invariants in Well Quasi Orders and Finite Antichain Orders ⋮ The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings ⋮ An analysis of loop checking mechanisms for logic programs ⋮ What's so special about Kruskal's theorem and the ordinal \(\Gamma{}_ 0\)? A survey of some results in proof theory ⋮ Analyzing Nash-Williams' partition theorem by means of ordinal types ⋮ From wqo to bqo, via Ellentuck's theorem ⋮ Unprovable combinatorial statements ⋮ Obituary: Ernest Corominas ⋮ Rank functions on rooted tree quivers. ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ Unnamed Item ⋮ Well rewrite orderings and well quasi-orderings ⋮ A framework for computing finite SLD trees ⋮ Finite structure for Friedman ideals of finite trees ⋮ Skolem functions and constructive models ⋮ On operations and linear extensions of well partially ordered sets ⋮ Proving weak properties of rewriting ⋮ Polynomial functions with exponentiation are well ordered ⋮ Forbidden substructures and combinatorial dichotomies: WQO and universality ⋮ Two forbidden induced subgraphs and well-quasi-ordering ⋮ Non-primitive recursive decidability of products of modal logics with expanding domains ⋮ Type-based homeomorphic embedding for online termination ⋮ Homogeneous families on trees and subsymmetric basic sequences ⋮ Petri nets with name creation for transient secure association ⋮ An ordinal bound for the set of polynomial functions with exponentiation ⋮ An initial segment of the set of polynomial functions with exponentiation ⋮ On a problem of R. Halin concerning infinite graphs ⋮ Condition de chaîne en théorie des rélations ⋮ Parameterized verification of monotone information systems ⋮ Pure \(\Sigma_2\)-elementarity beyond the core ⋮ Non-deterministic semantics for dynamic topological logic ⋮ Critical properties and complexity measures of read-once Boolean functions ⋮ Linearizing well quasi-orders and bounding the length of bad sequences ⋮ Universally axiomatizable subclasses of locally finite classes of models ⋮ Programming by predicates: a formal model for interactive synthesis ⋮ Decidability Border for Petri Nets with Data: WQO Dichotomy Conjecture ⋮ Some special properties of cofinality of ordinal numbers ⋮ Ordinals. II: Some applications and a functorial approach ⋮ Reactive synthesis from interval temporal logic specifications ⋮ Wohlquasigeordnete Klassen endlicher Graphen ⋮ On well quasi orders of free monoids ⋮ On the modal definability of simulability by finite transitive models ⋮ FI- and OI-modules with varying coefficients ⋮ Sur les premeilleurs ordres. (On prémeilleurs orderings) ⋮ On Fraïssé's conjecture for linear orders of finite Hausdorff rank ⋮ The theory of well-quasi-ordering: a frequently discovered concept ⋮ Language equations ⋮ Well-quasi-ordering and the Hausdorff quasi-uniformity ⋮ The varieties of arboreal experience ⋮ Branch-width and well-quasi-ordering in matroids and graphs. ⋮ Inflations of geometric grid classes of permutations ⋮ Graphs without \(K_ 4\) and well-quasi-ordering ⋮ Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation ⋮ Relative undecidability in term rewriting. I: The termination hierarchy ⋮ Relative undecidability in term rewriting. II: The confluence hierarchy ⋮ Regular solutions of language inequalities and well quasi-orders ⋮ On better quasi-ordering countable trees ⋮ Semi-unification ⋮ Some quasi-ordered classes of finite commutative semigroups ⋮ Termination orderings for associative-commutative rewriting systems
