Timeline for Word equations with integer parameters
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 30, 2022 at 18:08 | comment | added | Louis | It is given by theorem 1 of [1]: the idea would be to take the NFA for the final language (where Σ has been removed) and quantify over the number of times each transition is taken and add some constraints to make sure a corresponding run exists (this gives a linear size formula). Then you might want to eliminate quantifiers (but if I remember correctly this is expensive). [1] hal.archives-ouvertes.fr/hal-00159525/file/icalp04pres.pdf | |
| Mar 30, 2022 at 13:37 | comment | added | Drup | Thanks, that's a very interesting technique ! Do you have some pointers for a readable description of algorithms to compute the Presburger formula for the Parikh image of a regular automaton (or a regex with shuffle and intersection) ? | |
| Mar 29, 2022 at 8:20 | vote | accept | Denis | ||
| Mar 28, 2022 at 18:07 | history | answered | Louis | CC BY-SA 4.0 |