A Uniform Framework for Problems on Context-Free Grammars
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912085583069184 |
|---|---|
| author | Esparza, Javier Rossmanith, Peter Schwoon, Stefan |
| author_facet | Esparza, Javier Rossmanith, Peter Schwoon, Stefan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_19386 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Uniform Framework for Problems on Context-Free Grammars Esparza, Javier Rossmanith, Peter Schwoon, Stefan Formal Languages and Automata Theory F.4.2; F.1.1 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. |
| title | A Uniform Framework for Problems on Context-Free Grammars |
| topic | Formal Languages and Automata Theory F.4.2; F.1.1 |
| url | https://arxiv.org/abs/2410.19386 |