Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
From MaRDI portal
Publication:3811712
DOI10.1007/BF02088003zbMath0661.68048OpenAlexW2088539304MaRDI QIDQ3811712
Oscar H. Ibarra, Bala Ravikumar
Publication date: 1988
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02088003
Related Items
Two-way non-uniform finite automata ⋮ On some variations of two-way probabilistic finite automata models ⋮ Determinism and Nondeterminism in Finite Automata with Advice ⋮ Two-Way Non-Uniform Finite Automata ⋮ Two-way automata and length-preserving homomorphisms ⋮ Two-Way Automata versus Logarithmic Space ⋮ A survey of space complexity ⋮ Two-way automata versus logarithmic space ⋮ Unnamed Item ⋮ CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On pebble automata
- Some observations concerning alternating Turing machines using small space
- There are no fully space constructible functions between log log n and log n
- Halting space-bounded computations
- Space bounds for processing contentless inputs
- Remarks on the complexity of nondeterministic counter languages
- On tape bounds for single letter alphabet language processing
- Lower bounds on space complexity for contextfree recognition
- Relationships between nondeterministic and deterministic tape complexities
- A note on multihead automata and context-sensitive languages
- Circuit-size lower bounds and non-reducibility to sparse sets
- On efficient deterministic simulation of turing machine computations below logaspace
- Nondeterminism and the size of two way finite automata
This page was built for publication: Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
