Quasirelations in a free group and transformator equivalence problems

DOI10.1007/BF01987299MaRDI QIDQ1820772zbMATH OpenOpenAlexFDO

Authors L. P. Lisovik

Publication date 1986

Published in Algebra and Logic (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/187338

zbMATH Keywords

algorithmic decidability of the inclusion problemequivalence problemquasirelation in a free groupTuring machines

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Review text

The author proves a special quasirelation in a free group and uses it to prove the algorithmic decidability of the inclusion problem (and, thereby, the equivalence problem) for maps given by transformators sufficiently close to the class of Turing machines of restricted regime.

Recommendations

• Solvable problems for transformers with reversal-bounded counters
• scientific article; zbMATH DE number 3864474
• scientific article; zbMATH DE number 3894494
• scientific article; zbMATH DE number 3916533
• scientific article; zbMATH DE number 1222568

Cited in

(1)

• Quasimorphismes sur le monoïde libre, et substitutions dans les mesures invariantes

This page was built for publication: Quasirelations in a free group and transformator equivalence problems

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