Halting space-bounded computations
From MaRDI portal
Publication:1134515
DOI10.1016/0304-3975(80)90053-5zbMath0423.68011OpenAlexW1975698236MaRDI QIDQ1134515
Publication date: 1980
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(80)90053-5
two-way finite automatatwo-way multihead finite automatadeterministic Turing machinedeterministic computationhalting space-bounded computations
Related Items (52)
State-complexity of finite-state devices, state compressibility and incompressibility ⋮ On pebble automata ⋮ Weak and strong one-way space complexity classes ⋮ On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes ⋮ A Deterministic Two-Way Multi-head Finite Automaton Can Be Converted into a Reversible One with the Same Number of Heads ⋮ Characterization of realizable space complexities ⋮ Some observations concerning alternating Turing machines using small space ⋮ Computational complexity of functions ⋮ Inequalities for space-bounded Kolmogorov complexity ⋮ A survey of two-dimensional automata theory ⋮ The problem of space invariance for sequential machines ⋮ Complementing two-way finite automata ⋮ If deterministic and nondeterministic space complexities are equal for log log n then they are also equal for log n ⋮ Space hierarchy theorem revised. ⋮ Size complexity of rotating and sweeping automata ⋮ Computational complexity of reversible reaction systems ⋮ State complexity of transforming graph-walking automata to halting, returning and reversible ⋮ A time to cast away stones ⋮ Once-Marking and Always-Marking 1-Limited Automata ⋮ On multi-head automata with restricted nondeterminism ⋮ If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n ⋮ Two-way automata and length-preserving homomorphisms ⋮ On the State Complexity of Operations on Two-Way Finite Automata ⋮ Reversibility of computations in graph-walking automata ⋮ Two-way automata making choices only at the endmarkers ⋮ Space bounded computations: Review and new separation results ⋮ New decidability results concerning two-way counter machines and applications ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties ⋮ A note on the space complexity of some decision problems for finite automata ⋮ On space functions constructed by two-dimensional Turing machines ⋮ Walking on data words ⋮ A survey of space complexity ⋮ Some remarks on two-dimensional finite automata ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ Linear-time limited automata ⋮ On the descriptional power of heads, counters, and pebbles ⋮ Complement for two-way alternating automata ⋮ Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space ⋮ Size Complexity of Two-Way Finite Automata ⋮ Bridging across the \(\log(n)\) space frontier ⋮ A Survey on Picture-Walking Automata ⋮ Some notes on strong and weak log log n space complexity ⋮ Reversible space equals deterministic space ⋮ Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space ⋮ State complexity of union and intersection on graph-walking automata ⋮ The alternation hierarchy for sublogarithmic space is infinite ⋮ On efficient recognition of transductions and relations ⋮ Sublogarithmic $\sum _2$-space is not closed under complement and other separation results ⋮ Notes on looping deterministic two-way pushdown automata ⋮ Degrees of restriction for two-dimensional automata
Cites Work
- Unnamed Item
- Unnamed Item
- Transformational methods and their application to complexity problems
- On tape bounds for single letter alphabet language processing
- Transformational methods and their application to complexity problems. Corrigenda
- On two-way multihead automata
- Nondeterminism and the size of two way finite automata
- Some Results on Tape-Bounded Turing Machines
This page was built for publication: Halting space-bounded computations
