A finitely axiomatizable undecidable equational theory with recursively solvable word problems

Delić, Dejan

doi:10.1090/S0002-9947-99-02339-9

A finitely axiomatizable undecidable equational theory with recursively solvable word problems
HTML articles powered by AMS MathViewer

by Dejan Delić PDF

Trans. Amer. Math. Soc. 352 (2000), 3065-3101 Request permission

Abstract:

In this paper we construct a finitely based variety, whose equational theory is undecidable, yet whose word problems are recursively solvable, which solves a problem stated by G. McNulty (1992). The construction produces a discriminator variety with the aforementioned properties starting from a class of structures in some multisorted language (which may include relations), axiomatized by a finite set of universal sentences in the given multisorted signature. This result also presents a common generalization of the earlier results obtained by B. Wells (1982) and A. Mekler, E. Nelson, and S. Shelah (1993).

References

E. Börger, Computability, complexity, logic, Studies in Logic and the Foundations of Mathematics, vol. 128, North-Holland Publishing Co., Amsterdam, 1989. Translated from the German by J. C. Harvey. MR 1007830
Stanley Burris, Polynomial time uniform word problems, Math. Logic Quart. 41 (1995), no. 2, 173–182. MR 1330852, DOI 10.1002/malq.19950410204
Stanley Burris and H. P. Sankappanavar, A course in universal algebra, Graduate Texts in Mathematics, vol. 78, Springer-Verlag, New York-Berlin, 1981. MR 648287
S. Crvenković and D. Delić, A variety with locally solvable but globally unsolvable word problem, Algebra Universalis 35 (1996), no. 3, 420–424. MR 1387913, DOI 10.1007/BF01197182
O. G. Kharlampovich and M. V. Sapir, Algorithmic problems in varieties, Internat. J. Algebra Comput. 5 (1995), no. 4-5, 379–602. MR 1361261, DOI 10.1142/S0218196795000227
Dexter Kozen, Complexity of finitely presented algebras, Conference Record of the Ninth Annual ACM Symposium on Theory of Computing (Boulder, Colo., 1977) Assoc. Comput. Mach., New York, 1977, pp. 164–177. MR 0488999
G. Kreisel and J.-L. Krivine, Elements of mathematical logic. Model theory, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., Amsterdam, 1967. MR 0219380
A.I. Mal’cev, On homomorphisms onto finite groups (in Russian), Učen. Zap. Ivan. Ped. Inst., 18 (1958), 49–60.
Ernst W. Mayr and Albert R. Meyer, The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. in Math. 46 (1982), no. 3, 305–329. MR 683204, DOI 10.1016/0001-8708(82)90048-2
Ralph McKenzie, On spectra, and the negative solution of the decision problem for identities having a finite nontrivial model, J. Symbolic Logic 40 (1975), 186–196. MR 376323, DOI 10.2307/2271899
Ralph N. McKenzie, George F. McNulty, and Walter F. Taylor, Algebras, lattices, varieties. Vol. I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1987. MR 883644
Ralph McKenzie and Matthew Valeriote, The structure of decidable locally finite varieties, Progress in Mathematics, vol. 79, Birkhäuser Boston, Inc., Boston, MA, 1989. MR 1033992, DOI 10.1007/978-1-4612-4552-0
George F. McNulty, A field guide to equational logic, J. Symbolic Comput. 14 (1992), no. 4, 371–397. MR 1187240, DOI 10.1016/0747-7171(92)90013-T
Alan H. Mekler, Evelyn Nelson, and Saharon Shelah, A variety with solvable, but not uniformly solvable, word problem, Proc. London Math. Soc. (3) 66 (1993), no. 2, 225–256. MR 1199065, DOI 10.1112/plms/s3-66.2.225
A. Schmidt, Über deduktive Theorien mit mehreren Sorten von Grunddingen, Math. Ann., 115 (1938), 485–506.
Walter Taylor, Characterizing Mal′cev conditions, Algebra Universalis 3 (1973), 351–397. MR 349537, DOI 10.1007/BF02945141
Benjamin Wells, Pseudorecursive varieties of semigroups. I, Internat. J. Algebra Comput. 6 (1996), no. 4, 457–510. MR 1414350, DOI 10.1142/S0218196796000271
B. Wells, Pseudorecursive Varieties and Their Implications for Word Problems. PhD thesis, University of California, Berkeley, 1982.