Theories of orders on the set of words

DOI10.1051/ita:2005039zbMath1098.03021OpenAlexW2077350163MaRDI QIDQ3374756

Dietrich Kuske

Publication date: 22 February 2006

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2006__40_1_53_0

zbMATH Keywords

wordsundecidabilityfirst-order theorydecidabilitysubword orderinfix orderhomomorphism preorderlexicographic path

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Decidability of theories and sets of sentences (03B25)

Related Items

Definability in First Order Theories of Graph Orderings ⋮ The Subtrace Order and Counting First-Order Logic ⋮ Unnamed Item ⋮ Definability in the structure of words with the inclusion relation ⋮ Complexity in Young's lattice ⋮ Definability of closure operations in the \(h\)-quasiorder of labeled forests ⋮ Alternating complexity of counting first-order logic for the subword order ⋮ Existential Definability over the Subword Ordering ⋮ On the homomorphism order of labeled posets ⋮ Well-Quasi Orders and Hierarchy Theory ⋮ Labeled posets are universal ⋮ A Gandy Theorem for Abstract Structures and Applications to First-Order Definability ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Definability in the Infix Order on Words ⋮ Definability of Recursive Predicates in the Induced Subgraph Order ⋮ Definability in the \(h\)-quasiorder of labeled forests

Cites Work

• Orderings for term-rewriting systems
• Nonexistence of a Kruskal-Katona type theorem for subword orders
• A new method for undecidability proofs of first order theories
• On quasi orders of words and the confluence property
• The first-order theory of lexicographic path orderings is undecidable
• Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup
• Coding in the existential theory of concatenation
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
• Term Rewriting and All That
• Homotopy Spheres in Formal Language
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Ordering by Divisibility in Abstract Algebras
• Well-structured transition systems everywhere!
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item