The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints

Aleksejs Naumovs; Maksims Dimitrijevs; Abuzer Yakaryılmaz

doi:10.23638/DMTCS-22-1-13

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.

https://doi.org/10.23638/DMTCS-22-1-13

Source: arXiv.org:1904.01381

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

Licence: Attribution 4.0 International (CC BY 4.0)