Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
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)