113 citations · 317 across the 70 of their papers we have counts for
9 papers · 1 filter
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…
Controlling the Depth, Size, and Number of Subtrees for Two-variable Logic on Trees
Saguy Benaim, Michael Benedikt, Rastislav Lenhardt +1
Verification of properties of first order logic with two variables FO2 has been investigated in a number of contexts. Over arbitrary structures it is known to be decidable with NEX…
Revisiting the Equivalence Problem for Finite Multitape Automata
James Worrell
The decidability of determining equivalence of deterministic multitape automata (or transducers) was a longstanding open problem until it was resolved by Harju and Karhumäki in the…
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…