Solvable problems for transformers with reversal-bounded counters

DOI10.1007/BF01078820MaRDI QIDQ3747751zbMATH OpenOpenAlexFDO

Authors 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 problemfinite transformers with reversal-bounded countersfunctional equivalencelinearly rigid semigroupnonemptiness of a recognizable languagetransformers on marked treestwo-way deterministic finite automata

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3894494
• Reversal-Bounded Counter Machines Revisited
• Unboundedness problems for machines with reversal-bounded counters
• Automata with Reversal-Bounded Counters: A Survey
• GENERALIZED COUNTERS AND REVERSAL COMPLEXITY
• Theory and Applications of Models of Computation
• scientific article; zbMATH DE number 3928351
• On reversal bounded alternating Turing machines
• Reversal-bounded nondeterministic multicounter machines and complementation
• scientific article; zbMATH DE number 512847

Cites work

• scientific article; zbMATH DE number 3471979 (Why is no real title available?)
• scientific article; zbMATH DE number 3894494 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Strict sets and finite semigroup coverings
• The Diophantine Problem for Addition and Divisibility

Cited in

(4)

• Quasirelations in a free group and transformator equivalence problems
• Language recognition by two-way deterministic pushdown automata
• Solvability of equivalence problem for program machines
• scientific article; zbMATH DE number 3894494 (Why is no real title available?)

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

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