94 citations · 376 across the 55 of their papers we have counts for
3 papers · 1 filter
Uncountable realtime probabilistic classes
Maksims Dimitrijevs, Abuzer Yakaryılmaz
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 rea…
Zero-Error Affine, Unitary, and Probabilistic OBDDs
Rishat Ibrahimov, Kamil Khadiev, Krisjanis Prusis +2
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreo…
Exact Affine Counter Automata
Masaki Nakanishi, Kamil Khadiev, Krišjānis Prūsis +2
We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a la…