Search

• < Previous
• 1
• Next >

---

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;]

---

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;]

---

Pumping lemmas for weighted automata

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,&nbsp;[&hellip;]

---