10.23638/DMTCS-22-1-13
Naumovs, Aleksejs
Aleksejs
Naumovs
Dimitrijevs, Maksims
Maksims
Dimitrijevs
YakaryÄ±lmaz, Abuzer
Abuzer
YakaryÄ±lmaz
The minimal probabilistic and quantum finite automata recognizing
uncountably many languages with fixed cutpoints
episciences.org
2020
Computer Science - Formal Languages and Automata Theory
Computer Science - Computational Complexity
Quantum Physics
contact@episciences.org
episciences.org
2019-05-13T15:16:47+02:00
2020-07-17T12:01:30+02:00
2020-04-30
eng
Journal article
https://dmtcs.episciences.org/5450
arXiv:1904.01381
1365-8050
PDF
1
Discrete Mathematics & Theoretical Computer Science ; vol. 22 no. 1 ; Automata, Logic and Semantics ; 1365-8050
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.
Comment: 12 pages, minor revisions, changing the format to "dmtcs-episciences"
style