A variant of inductive counting (Q1566745)

We present a new version of the inductive counting, accepting the complement of an NSPACE\((s(n))\) language nondeterministically in space \(O(s(n))\), independent of whether \(s(n)\geqslant\log n\), but using an additional ``one-way pebble'' -- a movable marker placed on the input tape. This reduces the space used by inductive counting to \(\log n+O(s(n))\) bits on the binary work tape and gives the weakest known nondeterministic device accepting a co\(-\)NSPACE\((o(\log n))\) language.