Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup

DOI10.1007/BF02112533zbMath0853.20035OpenAlexW2005759788MaRDI QIDQ1921846

V. G. Durnev

Publication date: 8 January 1997

Published in: Siberian Mathematical Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02112533

zbMATH Keywords

free semigroupsfree generatorsalgorithmically undecidable theoriespositive \(\forall\exists^ 3\)-theory

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Undecidability and degrees of sets of sentences (03D35)

Related Items (14)

Non-structural subtype entailment in automata theory ⋮ The decision problem for some logics for finite words on infinite alphabets ⋮ On equations in free semigroups with certain constraints on their solutions. ⋮ Finding all solutions of equations in free groups and monoids with involution ⋮ Word equations in the context of string solving ⋮ Unnamed Item ⋮ Inclusion problems for patterns with a bounded number of variables ⋮ Languages generated by conjunctive query fragments of FC[REG] ⋮ On equations in free monoids and semigroups with restrictions on solutions ⋮ On ``simple undecidable fragments of the positive theory of a free semigroup ⋮ Theories of orders on the set of words ⋮ On equations and first-order theory of one-relator monoids ⋮ Undecidability of a simple fragment of a positive theory with a single constant for a free semigroup of rank two ⋮ \(\forall \exists^{5}\)-equational theory of context unification is undecidable

Cites Work

• The equation \(a_ M=b^ Nc^ P\) in a free group
• Coding in the existential theory of concatenation
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Concatenation as a basis for arithmetic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup