Solvable problems for transformers with reversal-bounded counters

DOI10.1007/BF01078820zbMath0608.68067OpenAlexW2020041969MaRDI QIDQ3747751

A. P. Lisovik

Publication date: 1985

Published in: Cybernetics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01078820

zbMATH Keywords

equivalence problemfunctional equivalencetwo-way deterministic finite automatafinite transformers with reversal-bounded counterslinearly rigid semigroupnonemptiness of a recognizable languagetransformers on marked trees

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (1)

Language recognition by two-way deterministic pushdown automata

Cites Work

• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Strict sets and finite semigroup coverings
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• The Diophantine Problem for Addition and Divisibility
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Solvable problems for transformers with reversal-bounded counters