Search


Volume

Section

Author

Year

  • < Previous
  • 1
  • Next >
3 results

Soundness in negotiations

Javier Esparza ; Denis Kuperberg ; Anca Muscholl ; Igor Walukiewicz.
Negotiations are a formalism for describing multiparty distributed cooperation. Alternatively, they can be seen as a model of concurrency with synchronized choice as communication primitive. Well-designed negotiations must be sound, meaning that, whatever its current state, the negotiation can still&nbsp;[&hellip;]
Published on January 16, 2018
Volume 14, Issue 1
Concurrency theory

One-way definability of two-way word transducers

Félix Baschenis ; Olivier Gauwin ; Anca Muscholl ; Gabriele Puppis.
Functional transductions realized by two-way transducers (or, equally, by streaming transducers or MSO transductions) are the natural and standard notion of "regular" mappings from words to words. It was shown in 2013 that it is decidable if such a transduction can be implemented by some one-way&nbsp;[&hellip;]
Published on December 7, 2018
Volume 14, Issue 4

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-visible alphabet) using a common deterministic transition graph, such that each language is associated with an initial&nbsp;[&hellip;]
Published on February 13, 2020
Volume 16, Issue 1
  • < Previous
  • 1
  • Next >