Christoph Karg
Abstract:
In this note, we show that LR(k) testing of context-free grammars with
respect to random instances is many-one complete for DistNP
(Distributional NP). The same result holds for testing whether a
context-free grammar is LL(k), strong LL(k), SLR(k), LC(k) or strong
LC(k), respectively.