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.
Additional Information
- Dejan Delić
- Affiliation: Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario, N2L 3G1 Canada
- Email: ddelic@math.uwaterloo.ca
- Received by editor(s): June 21, 1996
- Received by editor(s) in revised form: January 8, 1998
- Published electronically: October 5, 1999
- © Copyright 2000 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 352 (2000), 3065-3101
- MSC (1991): Primary 03B25; Secondary 08A50, 08B05
- DOI: https://doi.org/10.1090/S0002-9947-99-02339-9
- MathSciNet review: 1615947