|
A finitely axiomatizable undecidable equational theory with recursively solvable word problems
Author(s):
Dejan
Delic
Journal:
Trans. Amer. Math. Soc.
352
(2000),
3065-3101.
MSC (1991):
Primary 03B25;
Secondary 08A50, 08B05
Posted:
October 5, 1999
Retrieve article in:
PDF
This article is available free of charge
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:
- 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:
10.1090/S0002-9947-99-02339-9
PII:
S 0002-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
Posted:
October 5, 1999
Copyright of article:
Copyright
2000,
American Mathematical Society
|
Comments: webmaster@ams.org