19 citations · 30 across the 5 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.CC2013
Verifying whether One-Tape Non-Deterministic Turing Machines Run in Time
David Gajser
We discuss the following family of problems, parameterized by integers and : Does a given one-tape non-deterministic -state Turing machine make at most …
cs.LO2013★ 11 cited
Verifying Time Complexity of Deterministic Turing Machines
David Gajser
We show that, for all reasonable functions , we can algorithmically verify whether a given one-tape Turing machine runs in time at most . This is a tight bou…