On tape bounds for single letter alphabet language processing

DOI10.1016/0304-3975(76)90024-4zbMath0351.68014OpenAlexW2091565038MaRDI QIDQ1235507

K. Appert

Publication date: 1977

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(76)90024-4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (11)

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ On pebble automata ⋮ Some observations concerning alternating Turing machines using small space ⋮ Finite automata and unary languages ⋮ Hierarchies of one-way multihead automata languages ⋮ Halting space-bounded computations ⋮ Space hierarchy theorem revised. ⋮ Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties ⋮ A survey of space complexity ⋮ A lower bound for primality ⋮ Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space

Cites Work

• Unnamed Item
• Unnamed Item
• Space bounds for processing contentless inputs
• Two memory bounds for the recognition of primes by automata
• Some Results on Tape-Bounded Turing Machines

This page was built for publication: On tape bounds for single letter alphabet language processing