Selected publications by Stefan Schwoon

Abstract:
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.

@article{ERS-beatcs00,
   author = {Esparza, Javier and Rossmanith, Peter and Schwoon, Stefan},
   journal = {EATCS Bulletin},
   month = oct,
   pages = {169-177},
   publisher = {European Association for Theoretical Computer Science},
   title = {A Uniform Framework for Problems on Context-Free Grammars},
   url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/ehr-beatcs00.ps},
   volume = {72},
   year = {2000},
}

About LSV