94 citations · 176 across the 26 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.CC2022★ 1 cited
Real-Time, Constant-Space, Constant-Randomness Verifiers
M. Utkan Gezer, Özdeniz Dolu, Nevzat Ersoy +1
We study the class of languages that have membership proofs which can be verified by real-time finite-state machines using only a constant number of random bits, regardless of the…
cs.CC2022
Energy Complexity of Regular Languages
Fırat Kıyak, A. C. Cem Say
Each step that results in a bit of information being ``forgotten'' by a computing device has an intrinsic energy cost. Although any Turing machine can be rewritten to be thermodyna…