Name
Abstract | ||
|---|---|---|
We investigate the minimal cases for realtime probabilistic machines that can define uncountably many languages with bounded error. We show that logarithmic space is enough for realtime PTMs on unary languages. On non-unary case, we obtain the same result for double logarithmic space, which is also tight. When replacing the work tape with a few counters, we can still achieve similar results for unary linear-space two-counter automata, unary sublinear-space three-counter automata, and non-unary sublinear-space two-counter automata. We also show how to slightly improve the sublinear-space constructions by using more counters. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1142/S012905411950028X | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
DocType | Volume | Issue |
Conference | 30 | 8 |
ISSN | Citations | PageRank |
0129-0541 | 1 | 0.37 |
References | Authors | |
4 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maksims Dimitrijevs | 1 | 3 | 3.14 |
| Abuzer Yakaryilmaz | 2 | 168 | 25.31 |