Naumovs, Aleksejs and Dimitrijevs, Maksims and Yakaryılmaz, Abuzer - The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints

dmtcs:5450 - Discrete Mathematics & Theoretical Computer Science, April 30, 2020, vol. 22 no. 1
The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints

Authors: Naumovs, Aleksejs and Dimitrijevs, Maksims and Yakaryılmaz, Abuzer

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.


Volume: vol. 22 no. 1
Section: Automata, Logic and Semantics
Published on: April 30, 2020
Submitted on: May 13, 2019
Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Computational Complexity,Quantum Physics


Share

Consultation statistics

This page has been seen 143 times.
This article's PDF has been downloaded 17 times.