scientific article; zbMATH DE number 3363526

zbMath0229.02033MaRDI QIDQ5636862

Richard E. Stearns, Juris Hartmanis, Philip Lewis

Publication date: 1970

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

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

This page was built for publication: