6533b835fe1ef96bd129f458

RESEARCH PRODUCT

New results on classical and quantum counter automata

Masaki NakanishiAbuzer YakaryılmazAida Gainutdinova

subject

FOS: Computer and information sciencesComputer Science - Computational ComplexityQuantum PhysicsTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESFormal Languages and Automata Theory (cs.FL)FOS: Physical sciencesComputer Science - Formal Languages and Automata TheoryComputational Complexity (cs.CC)Quantum Physics (quant-ph)Nonlinear Sciences::Cellular Automata and Lattice GasesComputer Science::Formal Languages and Automata Theory

description

We show that one-way quantum one-counter automaton with zero-error is more powerful than its probabilistic counterpart on promise problems. Then, we obtain a similar separation result between Las Vegas one-way probabilistic one-counter automaton and one-way deterministic one-counter automaton. We also obtain new results on classical counter automata regarding language recognition. It was conjectured that one-way probabilistic one blind-counter automata cannot recognize Kleene closure of equality language [A. Yakaryilmaz: Superiority of one-way and realtime quantum machines. RAIRO - Theor. Inf. and Applic. 46(4): 615-641 (2012)]. We show that this conjecture is false, and also show several separation results for blind/non-blind counter automata.

yearjournalcountryeditionlanguage
2019-09-27
https://dx.doi.org/10.23638/dmtcs-21-4-12