Undecidability of a simple fragment of a positive theory with a single constant for a free semigroup of rank two

DOI10.1007/BF02686241MaRDI QIDQ1582961zbMATH OpenOpenAlexFDO

Authors V. G. Durnev

Publication date 17 May 2001

Published in Mathematical Notes (Search for Journal in Brave)

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

zbMATH Keywords

free semigroupundecidability

Mathematics Subject Classification ID

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

Review text

This paper is a note about the algorithmic nature of some simple fragments of positive theories with few constants for noncyclic semigroups. The authors prove 3 theorems and 4 corollaries on the undecidability of the positive theory with the constants \(a_1, a_2,\dots,a_{n-1}\) for the free semigroup of rank \(n\).

Recommendations

• On ``simple undecidable fragments of the positive theory of a free semigroup
• On ``simple algorithmically undecidable fragments of elementary theory of an infinitely generated free semigroup
• Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup
• scientific article; zbMATH DE number 665291
• scientific article; zbMATH DE number 3924767
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• scientific article; zbMATH DE number 4031660
• scientific article; zbMATH DE number 130848
• scientific article; zbMATH DE number 4087622
• Publication:4508453

Cites work

• Concatenation as a basis for arithmetic
• scientific article; zbMATH DE number 3924767 (Why is no real title available?)
• scientific article; zbMATH DE number 3752812 (Why is no real title available?)
• scientific article; zbMATH DE number 3462133 (Why is no real title available?)
• scientific article; zbMATH DE number 3577484 (Why is no real title available?)
• Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup

Cited in

(5)

• Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup
• scientific article; zbMATH DE number 3924767 (Why is no real title available?)
• scientific article; zbMATH DE number 665291 (Why is no real title available?)
• On ``simple algorithmically undecidable fragments of elementary theory of an infinitely generated free semigroup
• scientific article; zbMATH DE number 7120897 (Why is no real title available?)

This page was built for publication: Undecidability of a simple fragment of a positive theory with a single constant for a free semigroup of rank two

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1582961)