113 citations · 260 across the 57 of their papers we have counts for
7 papers · 1 filter
On the Complexity of Temporal-Logic Path Checking
Daniel Bundala, Joël Ouaknine
Given a formula in a temporal logic such as LTL or MTL, a fundamental problem is the complexity of evaluating the formula on a given finite word. For LTL, the complexity of this ta…
Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences
Joel Ouaknine, James Worrell
We consider the decidability and complexity of the Ultimate Positivity Problem, which asks whether all but finitely many terms of a given rational linear recurrence sequence (LRS)…
On the Positivity Problem for Simple Linear Recurrence Sequences
Joel Ouaknine, James Worrell
Given a linear recurrence sequence (LRS) over the integers, the Positivity Problem} asks whether all terms of the sequence are positive. We show that, for simple LRS (those whose c…
Positivity Problems for Low-Order Linear Recurrence Sequences
Joel Ouaknine, James Worrell
We consider two decision problems for linear recurrence sequences (LRS) over the integers, namely the Positivity Problem (are all terms of a given LRS positive?) and the Ultimate P…
A Static Analysis Framework for Livelock Freedom in CSP
Joel Ouaknine, Hristina Palikareva, A. W. Roscoe +1
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 sai…
On the Complexity of the Orbit Problem
Ventsislav Chonev, Joël Ouaknine, James Worrell
We consider higher-dimensional versions of Kannan and Lipton's Orbit Problem---determining whether a target vector space V may be reached from a starting point x under repeated app…
On the Complexity of Equivalence and Minimisation for Q-weighted Automata
Stefan Kiefer, Andrzej Murawski, Joel Ouaknine +2
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…