Article PDF
Avoid common mistakes on your manuscript.
References
S. I. Adyan and S. G. Makanin, “Study on algorithmic questions of algebra,” in: Algebra, Mathematical Logic, Number Theory, and Topology [in Russian], Collection of Survey Articles. Vol. 1: To the 50 Years of the Institute, Nauka, Moscow, 1984, pp. 197–217. (Trudy Mat. Inst. Steklov.;167.
W. V. O. Quine, “Concatenation as a basis for arithmetic,” J. Symbolic Logic,11, 105–114 (1946).
V. G. Durnev, “On the positive theory of a free semigroup,” Dokl. Akad. Nauk SSSR,211, No. 4, 772–774 (1973).
S. S. Marchenkov, “Undecidability of the positive ∀∃-theory of a free semigroup,” Sibirsk. Mat. Zh.,23, No. 1, 196–198 (1982).
A. I. Mal'tsev, Algorithms and Recursive Functions [in Russian], Nauka, Moscow (1965).
N. K. Kosovskii, “Some properties of solutions to equations in a free semigroup,” Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI),32, 21–28 (1972).
N. K. Kosovskii, Elements of Mathematical Logic and Its Applications to the Theory of Subrecursive Algorithms [in Russian], Leningrad. Univ., Leningrad (1981).
V. G. Durnev, “On the positive theory of a free semigroup,” Uchen. Zap. Mat. Kafedry Tul'sk. Ped. Inst., No. 2, 215–241 (1970).
A. D. Taimanov and Yu. I. Khmelevskii, “Decidability of the universal theory of a free semigroup,” Sibirsk. Mat. Zh.,21, No. 1, 228–230 (1980).
G. S. Makanin, “The decidability problem for equations in a free semigroup,” Dokl. Akad. Nauk SSSR,233, No. 2, 287–290 (1977).
Makanin G. S. “The decidability problem for equations in a free semigroup,” Mat. Sb.,103, No. 2, 147–236 (1977).
G. S. Makanin, “Decidability of the universal and positive theory of a free semigroup,” Izv. Akad. Nauk SSSR Ser. Mat.,48, No. 4, 735–749 (1984).
Yu. I. Khmelevskii, “Equations in a free semigroup,” Trudy Mat. Inst. Steklov. (LOMI),107, 21–28 (1971).
J. R. Büchi and S. Senger, “Coding in the existential theory on concatenation,” Arch. Math. Logic,26, No. 1–2, 101–106 (1986/1987).
S. Senger, The Existential Theory of Concatenation, Ph. D. Dissertation, Purdue University (1982).
S. I. Adyan, The Burnside Problem and Identities in Groups [in Russian], Nauka, Moscow (1975).
R. C. Lyndon and M. P. Schützenberger, “The equationa M =b N c P in a free group,” Michigan Math. J.,9, 289–298 (1962).
Yu. I. Merzlyakov, “Positive formulas on free groups,” Algebra i Logika,5, No. 4, 25–42 (1966).
Yu. V. Matiyasevich, “Simple examples of undecidable associative calculi,” Dokl. Akad. Nauk SSSR,173, No. 6, 1264–1266 (1967).
Author information
Authors and Affiliations
Additional information
This research was partially supported by the International Science Foundation (ISF) (Grant MUV 000).
Translated fromSibirskii Matematicheskii Zhurnal, Vol. 36, No. 5, pp. 1067–1080, September–October, 1995.
Rights and permissions
About this article
Cite this article
Durnev, V.G. Undecidability of the positive ∀∃3-theory of a free semigroup. Sib Math J 36, 917–929 (1995). https://doi.org/10.1007/BF02112533
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02112533