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

---

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

---