A variant of inductive counting

DOI10.1016/S0304-3975(99)00338-2MaRDI QIDQ1566745zbMATH OpenOpenAlexFDO

Authors Viliam Geffert

Publication date 4 June 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(99)00338-2

zbMATH Keywords

Computational complexityInductive countingSpace complexitySublogarithmic space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• Inductive counting below LOGSPACE
• scientific article; zbMATH DE number 18628
• One pebble versus n bits
• Using inductive counting to simulate nondeterministic computation
• Two Applications of Inductive Counting for Complementation Problems

Cites work

• A hierarchy that does not collapse : alternations in low level space
• Bridging across the (n) space frontier
• Inductive counting for width-restricted branching programs
• Nondeterministic Space is Closed under Complementation
• On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
• Relationships between nondeterministic and deterministic tape complexities
• Strong optimal lower bounds for Turing machines that accept nonregular languages
• Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
• The alternation hierarchy for sublogarithmic space is infinite
• The method of forced enumeration for nondeterministic automata
• The Sublogarithmic Alternating Space World
• Turing machines with sublogarithmic space
• Using inductive counting to simulate nondeterministic computation

Cited in

(5)

• Using inductive counting to simulate nondeterministic computation
• Two Applications of Inductive Counting for Complementation Problems
• scientific article; zbMATH DE number 18628 (Why is no real title available?)
• Another Way of Counting N^N
• Inductive counting below LOGSPACE

This page was built for publication: A variant of inductive counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1566745)