Search

• < Previous
• 1
• Next >

---

A lower bound on web services composition

Anca Muscholl ; Igor Walukiewicz.

A web service is modeled here as a finite state machine. A composition problem for web services is to decide if a given web service can be constructed from a given set of web services; where the construction is understood as a simulation of the specification by a fully asynchronous product of the&nbsp;[&hellip;]

---

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

---

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

---