Space bounds for processing contentless inputs
From MaRDI portal
Publication:1218269
DOI10.1016/S0022-0000(75)80052-3zbMath0307.68036MaRDI QIDQ1218269
Richard E. Ladner, Allen R. Freedman
Publication date: 1975
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items (24)
On pebble automata ⋮ Some observations concerning alternating Turing machines using small space ⋮ A remark on middle space bounded alternating Turing machines ⋮ Finite automata and unary languages ⋮ Hierarchies of one-way multihead automata languages ⋮ Space hierarchy theorem revised. ⋮ TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE ⋮ Space bounded computations: Review and new separation results ⋮ Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties ⋮ A hierarchy that does not collapse : alternations in low level space ⋮ On space functions constructed by two-dimensional Turing machines ⋮ A survey of space complexity ⋮ Minimal Size of Counters for (Real-Time) Multicounter Automata ⋮ On tape bounds for single letter alphabet language processing ⋮ Techniques for separating space complexity classes ⋮ Relating refined space complexity classes ⋮ New Results on the Minimum Amount of Useful Space ⋮ Some classes of languages in \(NC^ 1\) ⋮ Bridging across the \(\log(n)\) space frontier ⋮ Some notes on strong and weak log log n space complexity ⋮ Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space ⋮ Bandwidth constraints on problems complete for polynomial time ⋮ The recursion-theoretic structure of complexity classes ⋮ Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
Cites Work
This page was built for publication: Space bounds for processing contentless inputs
