Aleksejs Naumovs ; Maksims Dimitrijevs ; Abuzer Yakaryılmaz - 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 - https://doi.org/10.23638/DMTCS-22-1-13
The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpointsArticle

Authors: Aleksejs Naumovs ; Maksims Dimitrijevs ; Abuzer Yakaryılmaz

    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
    Accepted on: April 5, 2020
    Submitted on: May 13, 2019
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Computational Complexity,Quantum Physics

    Consultation statistics

    This page has been seen 611 times.
    This article's PDF has been downloaded 243 times.