Minimizing LR(1) State Machines is NP-Hard

kjosib / booze-tools

Booze Tools will become the complete programming-language development workbench, all written in Python 3.9 (for now).

MIT License

14 stars 1 forks source link

Minimizing LR(1) State Machines is NP-Hard #50

Closed modulovalue closed 7 months ago

modulovalue commented 10 months ago

Regarding the following statement:

I seem to recall reading somewhere that optimizing LR parse tables is hard, in the sense that it’s difficult to prove there’s not some alternative table with fewer states that recognizes the same language.

This fills in the implicit '[citation needed]': https://arxiv.org/abs/2110.00776

modulovalue commented 7 months ago

I'm closing this as stale.