113 citations · 317 across the 70 of their papers we have counts for
12 papers · 1 filter
Transcendence of Sturmian Numbers over an Algebraic Base
Florian Luca, Joel Ouaknine, James Worrell
We consider numbers of the form for a Sturmian sequence over a binary alp…
Multiplicity Problems on Algebraic Series and Context-Free Grammars
Nikhil Balaji, Lorenzo Clemente, Klara Nosan +2
In this paper we obtain complexity bounds for computational problems on algebraic power series over several commuting variables. The power series are specified by systems of polyno…
Probabilistic Automata of Bounded Ambiguity
Nathanaël Fijalkow, Cristian Riveros, James Worrell
Probabilistic automata are an extension of nondeterministic finite automata in which transitions are annotated with probabilities. Despite its simplicity, this model is very expres…
Effective Definability of the Reachability Relation in Timed Automata
Martin Fränzle, Karin Quaas, Mahsa Shirmohammadi +1
We give a new proof of the result of Comon and Jurski that the binary reachability relation of a timed automaton is definable in linear arithmetic.
Termination of Linear Loops over the Integers
Mehran Hosseini, Joël Ouaknine, James Worrell
We consider the problem of deciding termination of single-path while loops with integer variables, affine updates, and affine guard conditions. The question is whether such a loop…
When is Containment Decidable for Probabilistic Automata?
Laure Daviaud, Marcin Jurdziński, Ranko Lazić +3
The emptiness and containment problems for probabilistic automata are natural quantitative generalisations of the classical language emptiness and inclusion problems for Boolean au…