Automating the Analysis and Improvement of Dynamic Programming Algorithms with Applications to Natural Language Processing
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911514452033536 |
|---|---|
| author | Vieira, Tim |
| author_facet | Vieira, Tim |
| contents | This thesis develops a system for automatically analyzing and improving dynamic programs, such as those that have driven progress in natural language processing and computer science, more generally, for decades. Finding a correct program with the optimal asymptotic runtime can be unintuitive, time-consuming, and error-prone. This thesis aims to automate this laborious process. To this end, we develop an approach based on
1. a high-level, domain-specific language called Dyna for concisely specifying dynamic programs
2. a general-purpose solver to efficiently execute these programs
3. a static analysis system that provides type analysis and worst-case time/space complexity analyses
4. a rich collection of meaning-preserving transformations to programs, which systematizes the repeated insights of numerous authors when speeding up algorithms in the literature
5. a search algorithm for identifying a good sequence of transformations that reduce the runtime complexity, given an initial, correct program
We show that, in practice, automated search -- like the mental search performed by human programmers -- can find substantial improvements to the initial program. Empirically, we show that many speed-ups described in the NLP literature could have been discovered automatically by our system. We provide a freely available prototype system at https://github.com/timvieira/dyna-pi. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_13242 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Automating the Analysis and Improvement of Dynamic Programming Algorithms with Applications to Natural Language Processing Vieira, Tim Programming Languages Computation and Language Formal Languages and Automata Theory This thesis develops a system for automatically analyzing and improving dynamic programs, such as those that have driven progress in natural language processing and computer science, more generally, for decades. Finding a correct program with the optimal asymptotic runtime can be unintuitive, time-consuming, and error-prone. This thesis aims to automate this laborious process. To this end, we develop an approach based on 1. a high-level, domain-specific language called Dyna for concisely specifying dynamic programs 2. a general-purpose solver to efficiently execute these programs 3. a static analysis system that provides type analysis and worst-case time/space complexity analyses 4. a rich collection of meaning-preserving transformations to programs, which systematizes the repeated insights of numerous authors when speeding up algorithms in the literature 5. a search algorithm for identifying a good sequence of transformations that reduce the runtime complexity, given an initial, correct program We show that, in practice, automated search -- like the mental search performed by human programmers -- can find substantial improvements to the initial program. Empirically, we show that many speed-ups described in the NLP literature could have been discovered automatically by our system. We provide a freely available prototype system at https://github.com/timvieira/dyna-pi. |
| title | Automating the Analysis and Improvement of Dynamic Programming Algorithms with Applications to Natural Language Processing |
| topic | Programming Languages Computation and Language Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2603.13242 |