On the pre-AFL of \([lg\;n]\) space and related families of languages

DOI10.1016/0304-3975(76)90082-7zbMath0341.68054OpenAlexW2057676191MaRDI QIDQ1231780

Frederick Neil Springsteel

Publication date: 1976

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

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

Mathematics Subject Classification ID

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

Related Items

Two-way automata and length-preserving homomorphisms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• What makes some language theory problems undecidable
• Syntactic Analysis and Operator Precedence
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Turing machines with restricted memory access
• A note on undecidable properties of formal languages
• Counter machines and counter languages
• Classes of automata and transitive closure
• Quasi-realtime languages
• A Basis Theorem for a Class of Two‐Way Automata
• Language recognition by marking automata
• Bounded context syntactic analysis