Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

A finitely axiomatizable undecidable
equational theory with recursively
solvable word problems


Author: Dejan Delic
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
Published electronically: October 5, 1999
MathSciNet review: 1615947
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. E. Börger, Computability, Complexity, Logic, North-Holland, Amsterdam, 1989. MR 90h:68041
  • 2. S. Burris, Polynomial time uniform word problems, Math. Logic Quart., 41 (1995), 173-182. MR 96j:08004
  • 3. S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Graduate Texts in Mathematics, vol. 78, Springer-Verlag, New York, 1981. MR 83k:08001
  • 4. S. Crvenkovi\'{c} and D. Deli\'{c}, A variety with locally solvable but globally unsolvable word problem, Algebra Universalis, 35 (1996), 420-424. MR 97d:03058
  • 5. O. Kharlampovich and M.V. Sapir, Algorithmic problems in varieties, Internat. J. Algebra Comput., 5 (1995), 379-602. MR 96m:20045
  • 6. D. Kozen, Complexity of finitely presented algebras, Proc. of the 9th Symposium, STOC, pages 164-177, 1977. MR 58:8487
  • 7. G. Kreisel and J.L. Krivine, Elements of Mathematical Logic, North-Holland, Amsterdam, 1967. MR 36:2463
  • 8. A.I. Mal'cev, On homomorphisms onto finite groups (in Russian), U\v{c}en. Zap. Ivan. Ped. Inst., 18 (1958), 49-60.
  • 9. E.W. Mayr and A.R. Meyer, The complexity of the word problem for commutative semigroups and polynomial ideals, Adv. in Math., 46 (1982), 305-329. MR 84g:20099
  • 10. R. McKenzie, On spectra, and the negative solution of the decision problem for identities having a nontrivial model, J. Symbolic Logic, 40 (1975), 186-196. MR 51:12499
  • 11. R. McKenzie, G. McNulty, and W. Taylor, Algebras, Lattices, Varieties, Vol.I, Wadsworth & Brooks/Cole, Monterey, CA, 1987. MR 88e:08001
  • 12. R. McKenzie and M. Valeriote, The Structure of Locally Finite Decidable Varieties, Progress in Mathematics, vol. 79, Birkhäuser, Boston, 1989. MR 92j:08001
  • 13. G. McNulty, A field guide to equational logic, J. Symbolic Comp., 14 (1992), 371-397. MR 94g:03065
  • 14. A. Mekler, E. Nelson, and S. Shelah, A variety with solvable, but not uniformly solvable, word problem, Proc. London Math. Soc., 66 (1993), 225-256. MR 93m:03018
  • 15. A. Schmidt, Über deduktive Theorien mit mehreren Sorten von Grunddingen, Math. Ann., 115 (1938), 485-506.
  • 16. W. Taylor, Characterizing Mal'cev conditions, Algebra Universalis, 3 (1973), 351-397. MR 50:2030
  • 17. B. Wells, Pseudorecursive varieties of semigroups. I, Internat. J. Algebra Comput. MR 97k:20099
  • 18. B. Wells, Pseudorecursive Varieties and Their Implications for Word Problems. PhD thesis, University of California, Berkeley, 1982.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 03B25, 08A50, 08B05

Retrieve articles in all journals with MSC (1991): 03B25, 08A50, 08B05


Additional Information

Dejan Delic
Affiliation: Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario, N2L 3G1 Canada
Email: ddelic@math.uwaterloo.ca

DOI: https://doi.org/10.1090/S0002-9947-99-02339-9
Keywords: Multisorted logic, universal theory, variety, equational theory, word problem
Received by editor(s): June 21, 1996
Received by editor(s) in revised form: January 8, 1998
Published electronically: October 5, 1999
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society