Search

• < Previous
• 1
• Next >

---

On the Complexity of Equivalence and Minimisation for Q-weighted Automata

Stefan Kiefer ; Andrzej Murawski ; Joel Ouaknine ; Bjoern Wachter ; James Worrell.

This paper is concerned with the computational complexity of equivalence and minimisation for automata with transition weights in the field Q of rational numbers. We use polynomial identity testing and the Isolation Lemma to obtain complexity bounds, focussing on the class NC of problems within P&nbsp;[&hellip;]

---

A Static Analysis Framework for Livelock Freedom in CSP

Joel Ouaknine ; Hristina Palikareva ; A. W. Roscoe ; James Worrell.

In a process algebra with hiding and recursion it is possible to create processes which compute internally without ever communicating with their environment. Such processes are said to diverge or livelock. In this paper we show how it is possible to conservatively classify processes as livelock-free&nbsp;[&hellip;]

---

Two Variable vs. Linear Temporal Logic in Model Checking and Games

Michael Benedikt ; Rastislav Lenhardt ; James Worrell.

Model checking linear-time properties expressed in first-order logic has non-elementary complexity, and thus various restricted logical languages are employed. In this paper we consider two such restricted specification logics, linear temporal logic (LTL) and two-variable first-order logic (FO2).&nbsp;[&hellip;]

---

On the Expressiveness and Monitoring of Metric Temporal Logic

Hsi-Ming Ho ; Joël Ouaknine ; James Worrell.

It is known that Metric Temporal Logic (MTL) is strictly less expressive than the Monadic First-Order Logic of Order and Metric (FO[<, +1]) when interpreted over timed words; this remains true even when the time domain is bounded a priori. In this work, we present an extension of MTL with the same&nbsp;[&hellip;]

---