Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2512.23665 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908737783988224 |
|---|---|
| author | Vieira, Tim Cotterell, Ryan Eisner, Jason |
| author_facet | Vieira, Tim Cotterell, Ryan Eisner, Jason |
| contents | Much algorithmic research in NLP aims to efficiently manipulate rich formal structures. An algorithm designer typically seeks to provide guarantees about their proposed algorithm -- for example, that its running time or space complexity is upper-bounded as a certain function of its input size. They may also wish to determine the necessary properties of the quantities derived by the algorithm to synthesize efficient data structures and verify type errors. In this paper, we develop a system for helping programmers to perform these types of analyses. We apply our system to a number of NLP algorithms and find that it successfully infers types, dead and redundant code, and parametric runtime and space complexity bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_23665 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Automating the Analysis of Parsing Algorithms (and other Dynamic Programs) Vieira, Tim Cotterell, Ryan Eisner, Jason Programming Languages F.3.1; I.2.7 Much algorithmic research in NLP aims to efficiently manipulate rich formal structures. An algorithm designer typically seeks to provide guarantees about their proposed algorithm -- for example, that its running time or space complexity is upper-bounded as a certain function of its input size. They may also wish to determine the necessary properties of the quantities derived by the algorithm to synthesize efficient data structures and verify type errors. In this paper, we develop a system for helping programmers to perform these types of analyses. We apply our system to a number of NLP algorithms and find that it successfully infers types, dead and redundant code, and parametric runtime and space complexity bounds. |
| title | Automating the Analysis of Parsing Algorithms (and other Dynamic Programs) |
| topic | Programming Languages F.3.1; I.2.7 |
| url | https://arxiv.org/abs/2512.23665 |