×

The word problem for finitely presented quandles is undecidable. (English) Zbl 1465.03079

Paiva, Valeria (ed.) et al., Logic, language, information, and computation. 22nd international workshop, WoLLIC 2015, Bloomington, IN, USA, July 20–23, 2015. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9160, 1-13 (2015).
Summary: This work presents an algorithmic reduction of the word problem for recursively presented groups to the word problem for recursively presented quandles. The faithfulness of the reduction follows from the conjugation quandle construction on groups. It follows that the word problem for recursively presented quandles is not effectively computable, in general. This article also demonstrates that a recursively presented quandle can be encoded as a recursively presented rack. Hence, the word problem for recursively presented racks is also not effectively computable.
For the entire collection see [Zbl 1319.03010].

MSC:

03D40 Word problems, etc. in computability and recursion theory
08A50 Word problems (aspects of algebraic structures)
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
57K12 Generalized knots (virtual knots, welded knots, quandles, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Burris, S.; Sankappanavar, HP, A Course in Universal Algebra (1981), Berlin: Springer, Berlin · Zbl 0478.08001 · doi:10.1007/978-1-4613-8130-3
[2] Chang, CC; Keisler, HJ, Model Theory (1992), Amsterdam: North-Holland, Amsterdam
[3] Coxeter, HMS; Moser, WOJ, Generators and Relations for Discrete Groups (1980), New York: Springer, New York · Zbl 0422.20001 · doi:10.1007/978-3-662-21943-0
[4] Evans, T., The word problem for abstract algebras, J. Lond. Math. Soc., s1-26(1), 64-71 (1951) · Zbl 0042.03303 · doi:10.1112/jlms/s1-26.1.64
[5] Gödel, K., Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik, 38, 173-198 (1931) · JFM 57.0054.02 · doi:10.1007/BF01700692
[6] Hopcroft, JE; Motwani, R.; Ullman, JD, Introduction to Automata Theory, Languages, and Computation (2001), Reading: Addison-Wesley, Reading · Zbl 0980.68066
[7] Jech, T., Set Theory (2003), Berlin: Springer, Berlin · Zbl 1007.03002
[8] Joyce, D., A classifying invariant of knots, the knot quandle, J. Pure Appl. Algebra, 23, 37-66 (1982) · Zbl 0474.57003 · doi:10.1016/0022-4049(82)90077-9
[9] Knuth, DE; Bendix, PB; Leach, J., Simple word problems in universal algebras, Computational Algebra, 263-297 (1970), Oxford: Pergamon Press, Oxford · Zbl 0188.04902
[10] Lane, SM, Categories for the Working Mathematician (1998), New York: Springer, New York · Zbl 0906.18001
[11] Laver, R., The algebra of elementary embeddings of a rank into itself, Adv. Math., 110, 2, 334-346 (1995) · Zbl 0822.03031 · doi:10.1006/aima.1995.1014
[12] Laver, R., The left-distributive law and the freeness of an algebra of elementary embeddings, Adv. Math., 91, 2, 209-231 (1995) · Zbl 0822.03030 · doi:10.1016/0001-8708(92)90016-E
[13] Nobikov, PS, On the algorithmic unsolvability of the word problem in group theory, Proc. Steklov Inst. Math., 44, 1-143 (1955)
[14] Rotman, J., An introduction to the Theory of Groups (1999), New York: Springer, New York
[15] Rourke, C.; Fenn, R., Racks and links in codimension 2, J. Knot Theory Ramif., 1, 4, 343-406 (1992) · Zbl 0787.57003 · doi:10.1142/S0218216592000203
[16] Smith, JHD, Introduction to Abstract Algebra (2008), Boca Raton: Taylor and Francis Ltd, Boca Raton
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.