Geodesic
New results on classical and quantum counter automata
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2019_21_4_a11,
     author = {Nakanishi, Masaki and Yakary{\i}lmaz, Abuzer and Gainutdinova, Aida},
     title = {New results on classical and quantum counter automata},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2019},
     doi = {10.23638/DMTCS-21-4-12},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-12/}
}
TY  - JOUR
AU  - Nakanishi, Masaki
AU  - Yakaryılmaz, Abuzer
AU  - Gainutdinova, Aida
TI  - New results on classical and quantum counter automata
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-12/
DO  - 10.23638/DMTCS-21-4-12
LA  - en
ID  - DMTCS_2019_21_4_a11
ER  - 
%0 Journal Article
%A Nakanishi, Masaki
%A Yakaryılmaz, Abuzer
%A Gainutdinova, Aida
%T New results on classical and quantum counter automata
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-12/
%R 10.23638/DMTCS-21-4-12
%G en
%F DMTCS_2019_21_4_a11
Nakanishi, Masaki; Yakaryılmaz, Abuzer; Gainutdinova, Aida. New results on classical and quantum counter automata. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4. doi: 10.23638/DMTCS-21-4-12

Cité par Sources :