A survey of space complexity
type: Item
instance of: scholarly article
title: A survey of space complexity
zbMATH Open document ID: 0780.68042
DOI: 10.1016/0304-3975(92)90151-5
author: Pascal Michel
published in: Theoretical Computer Science
publication date: 1992-09-27T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 64584
zbMATH Keywords: deterministic and nondeterministic space complexity classes
zbMATH Keywords: closure under complementation
MaRDI profile type: Publication
full work available at URL: 0304-3975(92)90151-5
OpenAlex ID: W1981296138
cites work: Q3692869
cites work: Q4144808
cites work: On relativizing auxiliary pushdown machines
cites work: Q3692867
cites work: Uniform characterizations of non-uniform complexity measures
cites work: Q3753480
cites work: Q4039803
cites work: Q3996675
cites work: On languages accepted by space-bounded oracle machines
cites work: Relativizing Time, Space, and Time-Space
cites work: Parallel computation for well-endowed rings and space-bounded probabilistic machines
cites work: Relativized alternation and space-bounded computation
cites work: Alternation
cites work: Erratum to: Some observations concerning alternating Turing machines using small space
cites work: Q3944008
cites work: Fast Parallel Matrix Inversion Algorithms
cites work: Space bounds for processing contentless inputs
cites work: Q3912023
cites work: Q3326840
cites work: Q3341893
cites work: Q3805900
cites work: Q4038686
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Deterministic simulation of tape-bounded probabilistic Turing machine transducers
cites work: Q3795226
cites work: New developments in structural complexity theory
cites work: On tape bounds for single letter alphabet language processing
cites work: Q3820009
cites work: Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
cites work: Q3975135
cites work: Some Results on Tape-Bounded Turing Machines
cites work: Q5592246
cites work: A Hierarchy Theorem for Polynomial-Space Recognition
cites work: Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
cites work: Languages that Capture Complexity Classes
cites work: Nondeterministic Space is Closed under Complementation
cites work: Q3912025
cites work: Q3735080
cites work: Q3957950
cites work: There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator
cites work: On the power of two-way random generators and the impossibility of deterministic poly-space simulation
cites work: Q3819053
cites work: On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
cites work: Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\)
cites work: Classes of languages and linear-bounded automata
cites work: Alternating Pushdown and Stack Automata
cites work: Relativization of questions about log space computability
cites work: On efficient deterministic simulation of turing machine computations below logaspace
cites work: Space complexity in on-line computation
cites work: Q3751569
cites work: Q3871927
cites work: On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
cites work: Limitations on Separating Nondeterministic Complexity Classes
cites work: Approximate formulas for some functions of prime numbers
cites work: On uniform circuit complexity
cites work: Space-bounded hierarchies and probabilistic computations
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: A note on relativized log space
cites work: The network complexity and the Turing machine complexity of finite functions
cites work: Techniques for separating space complexity classes
cites work: Relating refined space complexity classes
cites work: Q4139697
cites work: On tape-bounded probabilistic Turing machine acceptors
cites work: Halting space-bounded computations
cites work: The problem of space invariance for sequential machines

A survey of space complexity (cites work)
cites work: Q5636862

A survey of space complexity (cites work)
cites work: The method of forced enumeration for nondeterministic automata

A survey of space complexity (cites work)
cites work: There are no fully space constructible functions between log log n and log n

A survey of space complexity (cites work)
cites work: Remarks on languages acceptable in log log n space

A survey of space complexity (cites work)
cites work: If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n

A survey of space complexity (cites work)
cites work: Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space

A survey of space complexity (cites work)
cites work: Some notes on strong and weak log log n space complexity

A survey of space complexity (cites work)
cites work: An extension of Savitch's theorem to small space bounds

A survey of space complexity (cites work)
cites work: Space measures for storage modification machines

A survey of space complexity (cites work)
cites work: Q3707407

A survey of space complexity (cites work)
cites work: Randomised algorithms

A survey of space complexity (cites work)
cites work: Q4038687

A survey of space complexity (cites work)
cites work: A measure of relativized space which is faithful with respect to depth