1
$\begingroup$

I wonder if all the linear languages are in NL?

I was thinking that we can take an input-language $L$ and convert it to linear normal form. If this is not possible, the machine rejects. If the language can be written in linear normal form, the machine accepts. The work tape only needs to store the current production, so that it works in logarithmic time.

Am I completely lost or is this a good start?

Improve this question
$\endgroup$
3
  • $\begingroup$ What is a linear language? Is it a language that can be decided in O(n) time? $\endgroup$
    – nir shahar
    Jun 5, 2020 at 16:25
  • $\begingroup$ No, it is a language that can be produced by a linear grammar $G=(V,\Sigma,R,S)$, with rules that are only on the forms $A\to uBv$ and $A\to u$ where $A,B\in V$ and $u,v\in\Sigma^*$. $\endgroup$
    – frenkie21
    Jun 5, 2020 at 17:00
  • 1
    $\begingroup$ Can you edit your post to elaborate on how you would construct the Turing machine and how you know it uses logarithmic space? $\endgroup$
    – D.W. ♦
    Jun 5, 2020 at 18:36

1 Answer 1

Reset to default
2
$\begingroup$

The following survey states that the result is proved by Ibarra, Jiang, Ravikumar in Information Processing Letters (1988).

Unambiguous Auxiliary Pushdown Automata and Semi-unbounded Fan-in Circuits. Niedermeier R., Rossmanith, P., Information and Computation 118(2), 227-245, 1995.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.