6533b7d5fe1ef96bd12651b2

RESEARCH PRODUCT

Uncountable Realtime Probabilistic Classes

Abuzer YakaryilmazMaksims Dimitrijevs

subject

Discrete mathematicsUnary operationComputer scienceProbabilistic logic020206 networking & telecommunicationsComputerApplications_COMPUTERSINOTHERSYSTEMS0102 computer and information sciences02 engineering and technology01 natural sciencesLogarithmic spaceBounded error010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineeringComputer Science (miscellaneous)020201 artificial intelligence & image processingUncountable setBinary case

description

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.

yearjournalcountryeditionlanguage
2018-05-14International Journal of Foundations of Computer Science
https://doi.org/10.1142/s012905411950028x