I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - A Uniform Framework for Problems on Context-Free Grammars


Javier Esparza, Peter Rossmanith, and Stefan Schwoon. A uniform framework for problems on context-free grammars. EATCS Bulletin, 72:169–177, October 2000.


Bouajjani and others presented an automata-based approach to a number of elementary problems on context-free grammars. This approach is of pedagogical interest since it provides a uniform solution to decision procedures usually solved by independent algorithms in textbooks. This paper improves upon previous work in a number of ways. We present a new algorithm which not only has a better space complexity but is also (in our opinion) easier to read and understand. Moreover, a closer inspection reveals that the new algorithm is competitive to well-known solutions for most (but not all) standard problems.

Suggested BibTeX entry:

    author = {Javier Esparza and Peter Rossmanith and Stefan Schwoon},
    journal = {EATCS Bulletin},
    month = {October},
    pages = {169--177},
    title = {A Uniform Framework for Problems on Context-Free Grammars},
    volume = {72},
    year = {2000}

GZipped PostScript (46 kB)