The recognition of deterministic CFLs in small time and space

DOI10.1016/S0019-9958(83)80049-7zbMath0535.68023OpenAlexW1975937255MaRDI QIDQ3319777

Rutger Verbeek, Burchard von Braunmühl, Kurt Mehlhorn, Stephen A. Cook

Publication date: 1983

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(83)80049-7

Mathematics Subject Classification ID

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

Related Items (5)

Space-efficient recognition of sparse self-reducible languages ⋮ Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-\(k\) storage automata ⋮ Linear-space recognition for grammars with contexts ⋮ Space-time trade-offs for stack-based algorithms ⋮ Fast recognition of deterministic cfl's with a smaller number of processors

This page was built for publication: The recognition of deterministic CFLs in small time and space