Abstract
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.
| Original language | English |
|---|---|
| Article number | 13 |
| Journal | Discrete Mathematics and Theoretical Computer Science |
| Volume | 22 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 2020 |
OECD Field of Science
- 1.2 Computer and Information Sciences
Keywords
- probabilistic automaton
- quantum automaton
- recognition with cutpoint
- unary languages
- uncountable languages
Fingerprint
Dive into the research topics of 'The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver