Name
Title | ||
|---|---|---|
The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints. |
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. |
Year | Venue | Keywords |
|---|---|---|
2019 | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | probabilistic automaton,quantum automaton,uncountable languages,recognition with cutpoint,unary languages |
DocType | Volume | Issue |
Journal | 22.0 | 1.0 |
ISSN | Citations | PageRank |
1462-7264 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aleksejs Naumovs | 1 | 0 | 0.34 |
| Maksims Dimitrijevs | 2 | 3 | 3.14 |
| Abuzer Yakaryilmaz | 3 | 168 | 25.31 |