×

zbMATH — the first resource for mathematics

The word problem for finitely presented quandles is undecidable. (English) Zbl 06484964
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 (ISBN 978-3-662-47708-3/pbk; 978-3-662-47709-0/ebook). Lecture Notes in Computer Science 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:
03B70 Logic in computer science
PDF BibTeX XML Cite
Full Text: DOI