Minsky machines and algorithmic problems

2015/04/29 by Mark Sapir, Sapir, Mark
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #math.GR #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1504.07736

19 pages

arxiv created 2015/04/29 · openalex publication_date 2015/04/29 · arxiv updated 2015/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This is a survey of using Minsky machines to study algorithmic problems in semigroups, groups and other algebraic systems.

Citations

• Algorithmically complex residually finite groups

Related

• A Study of NP-Completeness and Undecidable Word Problems in Semigroups
• Automata and automata mappings of semigroups
• Problems in group theory motivated by cryptography
• Recent advances in algorithmic problems for semigroups
• Algorithmic and asymptotic properties of groups