Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties

DOI10.1007/BF02088003zbMath0661.68048MaRDI QIDQ3811712

Oscar H. Ibarra, Bala Ravikumar

Publication date: 1988

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

complexity classes; sublogarithmic space

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D10: Turing machines and related notions

Related Items

Two-way automata and length-preserving homomorphisms, CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES, On some variations of two-way probabilistic finite automata models, A survey of space complexity, Two-way automata versus logarithmic space, Two-Way Automata versus Logarithmic Space

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