On the complexities of linear LL(1) and LR(1) grammars

Several notions of deterministic linear languages are considered and compared with respect to their complexities and to the families of formal languages they generate. We exhibit close relationships between simple linear languages and the deterministic linear languages both according to Nasu and Honda and to Ibarra, Jiang, and Ravikumar. Deterministic linear languages turn out to be special cases of languages generated by linear grammars restricted to LL(1) conditions, which have a membership problem solvable in NC1. In contrast to that, deterministic linear languages defined via automata models turn out to have a DSPACE(logn)-complete membership problem. Moreover, they coincide with languages generated by linear grammars subject to LR(1) conditions.