Search

• < Previous
• 1
• Next >

---

Linear Temporal Logic for Regular Cost Functions

Denis Kuperberg.

Regular cost functions have been introduced recently as an extension to the notion of regular languages with counting capabilities, which retains strong closure, equivalence, and decidability properties. The specificity of cost functions is that exact values are not considered, but only estimated.&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;]

---

Computing the Width of Non-deterministic Automata

Denis Kuperberg ; Anirban Majumdar.

We introduce a measure called width, quantifying the amount of nondeterminism in automata. Width generalises the notion of good-for-games (GFG) automata, that correspond to NFAs of width 1, and where an accepting run can be built on-the-fly on any accepted input. We describe an incremental&nbsp;[&hellip;]

---

Positive First-order Logic on Words and Graphs

Denis Kuperberg.

We study FO+, a fragment of first-order logic on finite words, where monadic predicates can only appear positively. We show that there is an FO-definable language that is monotone in monadic predicates but not definable in FO+. This provides a simple proof that Lyndon's preservation theorem fails on&nbsp;[&hellip;]

---