A finitely axiomatizable undecidable equational theory with recursively solvable word problems

被引:7
作者
Delic, D [1 ]
机构
[1] Univ Waterloo, Dept Pure Math, Waterloo, ON N2L 3G1, Canada
关键词
multisorted logic; universal theory; variety; equational theory; word problem;
D O I
10.1090/S0002-9947-99-02339-9
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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).
引用
收藏
页码:3065 / 3101
页数:37
相关论文
共 18 条
[1]  
[Anonymous], 1989, COMPUTABILITY COMPLE
[2]  
[Anonymous], 1967, ELEMENTS MATH LOGIC
[3]   POLYNOMIAL-TIME UNIFORM WORD-PROBLEMS [J].
BURRIS, S .
MATHEMATICAL LOGIC QUARTERLY, 1995, 41 (02) :173-182
[4]  
Burris S., 1981, COURSE UNIVERSAL ALG, DOI DOI 10.1007/978-1-4613-8130-3
[5]   A variety with locally solvable but globally unsolvable word problem [J].
Crvenkovic, S ;
Delic, D .
ALGEBRA UNIVERSALIS, 1996, 35 (03) :420-424
[6]  
Kharlampovich O. G., 1995, International Journal of Algebra and Computation, V5, P379, DOI 10.1142/S0218196795000227
[7]  
Kozen Dexter, 1977, P 9 ANN ACM S THEORY, P164, DOI [10.1145/800105.803406, DOI 10.1145/800105.803406]
[8]  
Malcev, 1958, UCHEN ZAP IVANOVSKOG, V119, P49
[9]   THE COMPLEXITY OF THE WORD-PROBLEMS FOR COMMUTATIVE SEMIGROUPS AND POLYNOMIAL IDEALS [J].
MAYR, EW ;
MEYER, AR .
ADVANCES IN MATHEMATICS, 1982, 46 (03) :305-329
[10]   SPECTRA, AND NEGATIVE SOLUTION OF DECISION PROBLEM FOR IDENTITIES HAVING A FINITE NONTRIVIAL MODEL [J].
MCKENZIE, R .
JOURNAL OF SYMBOLIC LOGIC, 1975, 40 (02) :186-196