113 citations · 317 across the 70 of their papers we have counts for
6 papers · 1 filter
Minimisation of Multiplicity Tree Automata
Stefan Kiefer, Ines Marusic, James Worrell
We consider the problem of minimising the number of states in a multiplicity tree automaton over the field of rational numbers. We give a minimisation algorithm that runs in polyno…
Three Variables Suffice for Real-Time Specification
Timos Antonopoulos, Paul Hunter, Shahab Raza +1
A natural framework for real-time specification is monadic first-order logic over the structure ---the ordered real line with unary function. Our main resul…
On Termination of Integer Linear Loops
Joël Ouaknine, João Sousa Pinto, James Worrell
A fundamental problem in program verification concerns the termination of simple linear loops of the form x := u ; while Bx >= b do {x := Ax + a} where x is a vector of variables,…
The Polyhedron-Hitting Problem
Ventsislav Chonev, Joël Ouaknine, James Worrell
We consider polyhedral versions of Kannan and Lipton's Orbit Problem (STOC '80 and JACM '86)---determining whether a target polyhedron V may be reached from a starting point x unde…
Model Checking Markov Chains Against Unambiguous Buchi Automata
Michael Benedikt, Rastislav Lenhardt, James Worrell
We give a polynomial-time algorithm for model checking finite Markov chains against omega-regular specifications given as unambiguous Buchi automata.
Complexity of Equivalence and Learning for Multiplicity Tree Automata
Ines Marusic, James Worrell
We consider the complexity of equivalence and learning for multiplicity tree automata, i.e., weighted tree automata over a field. We first show that the equivalence problem is logs…