34 citations · 78 across the 22 of their papers we have counts for
3 papers · 1 filter
Minimization of visibly pushdown automata is NP-complete
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-v…
On Synthesis of Resynchronizers for Transducers
Sougata Bose, Shankara Narayanan Krishna, Anca Muscholl +2
We study two formalisms that allow to compare transducers over words under origin semantics: rational and regular resynchronizers, and show that the former are captured by the latt…
Equivalence of finite-valued streaming string transducers is decidable
Anca Muscholl, Gabriele Puppis
In this paper we provide a positive answer to a question left open by Alur and and Deshmukh in 2011 by showing that equivalence of finite-valued copyless streaming string transduce…