2 results
Agnishom Chattopadhyay ; Filip Mazowiecki ; Anca Muscholl ; Cristian Riveros.
We present pumping lemmas for five classes of functions definable by fragments of weighted automata over the min-plus semiring, the max-plus semiring and the semiring of natural numbers. As a corollary we show that the hierarchy of functions definable by unambiguous, finitely-ambiguous, […]
Published on July 21, 2021
Olivier Gauwin ; Anca Muscholl ; Michael Raskin.
We show that the minimization of visibly pushdown automata is NP-complete. This result is obtained by introducing immersions, that recognize multiple languages (over a usual, non-visible alphabet) using a common deterministic transition graph, such that each language is associated with an initial […]
Published on February 13, 2020