On LALR(k) testing

Seppo Sippu, Eljas Soisalon-Soininen

Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKonferensbidragVetenskapligPeer review


The problem of testing whether or not a context-free grammar possesses the LALR(k) property is studied. The uniform problem (i.e. both the subject grammar and the integer k are problem parameters) is shown to be complete for polynomial space (PSPACE) when k is expressed in unary, and complete for nondeterministic (one-level) exponential time (NE) when k is expressed in binary. This solves an open problem by Hunt, Szymanski and Ullman, who showed that for k in binary LR(k), LL(k) and even strong LL(k) testing is NE-complete, and that LALR(k) testing is at least NE-hard. For k in unary the lower bound of the problem follows from the recently obtained result that even for fixed k > 0 (i.e. only the subject grammar is a problem parameter) the problem is PSPACE-hard. Thus, the results lead to the striking conclusion that for k in binary LALR(k) testing is no harder (with respect to polynomial time reductions) than e.g. strong LL(k) testing, and for k in unary no harder than LALR(1) testing.
Titel på gästpublikationAutomata, Languages and Programming : Eigth Colloquium, Acre (Akko), Israel, July 13-17, 1981
RedaktörerS. Even, O. Kariv
Antal sidor10
UtgivningsortBerlin-Heidelberg-New York
ISBN (tryckt)3-540-10843-2
StatusPublicerad - 1981
MoE-publikationstypA4 Artikel i en konferenspublikation
EvenemangInternational Colloquium on Automata, Languages and Programming - Acre (Akko), Israel
Varaktighet: 13 jul 198117 jul 1981
Konferensnummer: 8 (ICALP)


NamnLecture Notes in Computer Science


  • 113 Data- och informationsvetenskap

Citera det här