Minsky Machines and Algorithmic Problems

DOI10.1007/978-3-319-23534-9_17MaRDI QIDQ2947180zbMATH OpenOpenAlexFDO

Authors Mark Sapir

Publication date 22 September 2015

Published in Fields of Logic and Computation II (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.07736

zbMATH Keywords

groupidentityMinsky machinessemigroupuniform word problemvarietyword problem

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Word problems, etc. in computability and recursion theory (03D40) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05)

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

Cites work

• Algorithmic problems for amalgams of finite semigroups
• Algorithmic problems for finite groups and finite \(0\)-simple semigroups
• ALGORITHMIC PROBLEMS IN VARIETIES
• Algorithmic problems in varieties of semigroups
• Algorithmically complex residually finite groups
• Automata Studies. (AM-34)
• Combinatorial algebra: syntax and semantics. With contributions by Victor S. Guba and Mikhail V. Volkov
• Finite and infinite cyclic extensions of free groups
• scientific article; zbMATH DE number 3162939 (Why is no real title available?)
• scientific article; zbMATH DE number 4154724 (Why is no real title available?)
• scientific article; zbMATH DE number 3815955 (Why is no real title available?)
• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 3526785 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 459345 (Why is no real title available?)
• scientific article; zbMATH DE number 475447 (Why is no real title available?)
• scientific article; zbMATH DE number 1563405 (Why is no real title available?)
• scientific article; zbMATH DE number 3285229 (Why is no real title available?)
• Potential Divisibility in Finite Semigroups is Undecidable
• Quantifying residual finiteness.
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Solution of the restricted Burnside problem for 2-groups
• Some Connections between Residual Finiteness, Finite Embeddability and the Word Problem
• SOME DUALITY CONJECTURES FOR FINITE GRAPHS AND THEIR GROUP THEORETIC CONSEQUENCES
• The decision problem for exponential diophantine equations
• The isomorphism problem for profinite completions of finitely presented, residually finite groups.
• The Potential -Relation and Amalgamation Bases for Finite Semigroups
• The restricted Burnside problem for varieties of semigroups
• The triviality problem for profinite completions
• Unsolvability of the universal theory of finite groups
• Word Problems Solvable in Logspace

Cited in

(2)

• Algorithmically complex residually finite groups
• scientific article; zbMATH DE number 7561474 (Why is no real title available?)

This page was built for publication: Minsky Machines and Algorithmic Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947180)