A Uniform Framework for Problems on Context-Free Grammars Article Swipe
Related Concepts
Javier Esparza
,
Peter Rossmanith
,
Stefan Schwoon
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2410.19386
· OA: W77498777
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2410.19386
· OA: W77498777
In a paper published in Information Processing Letters in 2000, Bouajjani et al. 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 the work by Bouajjani et al. 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.
Related Topics
Finding more related topics…