GENERALIZED COUNTERS AND REVERSAL COMPLEXITY

DOI10.1142/S0129054108006352MaRDI QIDQ3606557zbMATH OpenFDO

Authors M. V. Panduranga Rao

Publication date 26 February 2009

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

language recognitiondeterministic counter automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Theory and Applications of Models of Computation
• Reversal complexity revisited
• scientific article; zbMATH DE number 4007730
• Reversal Complexity
• Reversal-Bounded Counter Machines Revisited
• Enumeration of reversible functions and its application to circuit complexity
• Reversal Complexity Classes for Alternating Turing Machines
• Reversal-bounded nondeterministic multicounter machines and complementation
• Reversibility in space-bounded computation
• scientific article; zbMATH DE number 3982521

Cites work

• Deterministic two-way one-head pushdown automata are very powerful
• Extended finite automata over groups
• Finite automata with multiplication
• Fooling a two way automaton or one pushdown store is better than one counter for two way machines
• ON THE EQUIVALENCE OF TWO-WAY PUSHDOWN AUTOMATA AND COUNTER MACHINES OVER BOUNDED LANGUAGES
• Remarks on blind and partially blind one-way multicounter machines
• Remarks on two-way automata with weak-counters
• Two-Way Counter Machines and Diophantine Equations
• Two-way deterministic multi-weak-counter machines
• Two-way finite automata with quantum and classical states.

Cited in

(2)

• Reverse complexity
• Solvable problems for transformers with reversal-bounded counters

This page was built for publication: GENERALIZED COUNTERS AND REVERSAL COMPLEXITY

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