scientific article; zbMATH DE number 3363526

zbMATH Open0229.02033MaRDI QIDQ5636862FDOQ5636862

Authors: R. E. Stearns, J. Hartmanis, Philip Lewis

Publication date: 1970

Title of this publication is not available (Why is that?)

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Cited In (only showing first 100 items - show all)

On the computational complexity of membrane systems
Translation from classical two-way automata to pebble two-way automata
A note on alternating on-line Turing machines
The effect of end-markers on counter machines and commutativity
Passively mobile communicating machines that use restricted space
Space bounded computations: Review and new separation results
A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors
Bridging across the $\log(n)$ space frontier
Relating refined space complexity classes
Techniques for separating space complexity classes
k$+1$ heads are better than k for PDAs
There are no fully space constructible functions between log log n and log n
A hierarchy that does not collapse : alternations in low level space
Two-Way Automata versus Logarithmic Space
Comparing complexity classes
Unary coded PSPACE-complete languages in $\mathrm{ASPACE}(\log\log n)$
Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
Dimension and the structure of complexity classes
The recursion-theoretic structure of complexity classes
Characterization of realizable space complexities
On pebble automata
Nonexistence of program optimizers in several abstract settings
For completeness, sublogarithmic space is no space.
Reverse complexity
Accepting networks of splicing processors: complexity results
An application of the translational method
On restricted turing computability
The theory of languages
Weak and strong one-way space complexity classes
Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs
The theory of languages
Hierarchies of Turing machines with restricted tape alphabet size
Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
On small, reduced, and fast universal accepting networks of splicing processors
Amplification of slight probabilistic advantage at absolutely no cost in space
Deterministic versus nondeterministic space in terms of synchronized alternating machines
On the size complexity of hybrid networks of evolutionary processors
Translational lemmas, polynomial time, and $(\log n)^j$-space
Multitape one-way nonwriting automata
The polynomial-time hierarchy
A survey of two-dimensional automata theory
Halting space-bounded computations
Time- and tape-bounded Turing acceptors and AFLs
A remark on middle space bounded alternating Turing machines
Two-way automata versus logarithmic space
Complexity of probabilistic versus deterministic automata
Data structures for distributed counting
Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
Random languages for nonuniform complexity classes
On time hierarchies
On the computational power of pushdown automata
On non-determinacy in simple computing devices
Space bounds for processing contentless inputs
On space functions constructed by two-dimensional Turing machines
Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
Remarks on languages acceptable in log log n space
An NP-complete language accepted in linear time by a one-tape Turing machine
Complexity problems in real time languages
The enumerability and invariance of complexity classes
A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
Complexity lower bounds for machine computing models
Some observations concerning alternating Turing machines using small space
A machine description and the hierarchy of initial Grzegorczyk classes
Principal AFL
Relativization of questions about log space computability
A characterization of the power of vector machines
Computing equilibria: a computational complexity perspective
Alternating space is closed under complement and other simulations for sublogarithmic space
Amount of nonconstructivity in deterministic finite automata
Space hierarchy theorem revised.
Subrecursiveness: Machine-independent notions of computability in restricted time and storage
Writing pushdown acceptors
A space lower bound for acceptance by one-way $\Pi_2$-alternating machines
A note on one-way and two-way automata
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
Amount of Nonconstructivity in Finite Automata
An optimal lower bound for nonregular languages
Writing stack acceptors
Complexity barriers as independence
On the language of primitive words
Computational power of one-way Turing machines with sublogarithmic memory restrictions
Improved approximations for hard optimization problems via problem instance classification
Notes on looping deterministic two-way pushdown automata
Minimal Size of Counters for (Real-Time) Multicounter Automata
On store languages of language acceptors
Alternating demon space is closed under complement and other simulations for sublogarithmic space
Space-bounded OTMs and REG ∞
On relationships between complexity classes of Turing machines
The complexity of model-checking tail-recursive higher-order fixpoint logic
Alternating time versus deterministic time: A separation
P-RAM vs. RP-RAM
A survey of space complexity
Minimum-complexity pairing functions
Space-efficient recognition of sparse self-reducible languages
Push complexity: optimal bounds and unary inputs
A note on first-order spectra with binary relations
A quadratic size-hierarchy theorem for small-depth multilinear formulas
Some notes on strong and weak log log n space complexity
Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space

This page was built for publication:

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