TY - GEN
T1 - Uncountable realtime probabilistic classes
AU - Dimitrijevs, Maksims
AU - Yakaryilmaz, Abuzer
N1 - Publisher Copyright:
© IFIP International Federation for Information Processing 2017.
PY - 2017
Y1 - 2017
N2 - We investigate the minimum 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 binary case, we follow the same result for double logarithmic space, which is tight. When replacing the worktape with some limited memories, we can follow uncountable results on unary languages for two counters.
AB - We investigate the minimum 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 binary case, we follow the same result for double logarithmic space, which is tight. When replacing the worktape with some limited memories, we can follow uncountable results on unary languages for two counters.
UR - https://www.scopus.com/pages/publications/85022324354
U2 - 10.1007/978-3-319-60252-3_8
DO - 10.1007/978-3-319-60252-3_8
M3 - Conference paper
AN - SCOPUS:85022324354
SN - 9783319602516
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 102
EP - 113
BT - Descriptional Complexity of Formal Systems - 19th IFIP WG 1.02 International Conference, DCFS 2017, Proceedings
A2 - Pighizzini, Giovanni
A2 - Campeanu, Cezar
PB - Springer Verlag
T2 - 19th International Conference of Descriptional Complexity of Formal Systems, DCFS 2017
Y2 - 3 July 2017 through 5 July 2017
ER -