Geodesic
The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1

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

It is known that 2-state binary and 3-state unary probabilistic finite automata and 2-state unary quantum finite automata recognize uncountably many languages with cutpoints. These results have been obtained by associating each recognized language with a cutpoint and then by using the fact that there are uncountably many cutpoints. In this note, we prove the same results for fixed cutpoints: each recognized language is associated with an automaton (i.e., algorithm), and the proofs use the fact that there are uncountably many automata. For each case, we present a new construction.
DOI : 10.23638/DMTCS-22-1-13
Classification : 68Q45, 81P68 
@article{DMTCS_2020_22_1_a12,
     author = {Naumovs, Aleksejs and Dimitrijevs, Maksims and Yakary{\i}lmaz, Abuzer},
     title = {The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2020-2021},
     doi = {10.23638/DMTCS-22-1-13},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-13/}
}
TY  - JOUR
AU  - Naumovs, Aleksejs
AU  - Dimitrijevs, Maksims
AU  - Yakaryılmaz, Abuzer
TI  - The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-13/
DO  - 10.23638/DMTCS-22-1-13
LA  - en
ID  - DMTCS_2020_22_1_a12
ER  - 
%0 Journal Article
%A Naumovs, Aleksejs
%A Dimitrijevs, Maksims
%A Yakaryılmaz, Abuzer
%T The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-13/
%R 10.23638/DMTCS-22-1-13
%G en
%F DMTCS_2020_22_1_a12
Naumovs, Aleksejs; Dimitrijevs, Maksims; Yakaryılmaz, Abuzer. The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1. doi: 10.23638/DMTCS-22-1-13

Cité par Sources :