The linear context-free languages are included in NL, and there exist linear languages that are NL-complete. On the other hand, the set of linear deterministic context-free languages is included in L. The set of real-time context-free languages includes languages that are NL-complete. What is the tape complexity of real-time deterministic context-free languages?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top
