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

---

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

---