1 citations · 3 across the 13 of their papers we have counts for
13 papers
Preservation Theorems for Transducer Outputs
Valérie Berthé, Herman Goulet-Ouellet, Toghrul Karimov +2
Suppose we have a deterministic finite-state transducer and an infinite word , and run on to obtain an infinite word . Which properties of are guaranteed t…
Equivalence of Continuous-Time Markov Chains and Linear Dynamical Systems
Mihir Vahanwala
The purpose of this short note is to record that an analogue of the following result, which is known for discrete-time linear dynamical systems, also holds in the continuous-time s…
On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic
Piotr Bacik, Joris Nieuwveld, Joël Ouaknine +3
We consider expansions of Presburger arithmetic with families of monadic polynomial predicates. (Examples of such predicates are the set of perfect squares, or the set of integers…
Temporal Properties of Conditional Independence in Dynamic Bayesian Networks
Rajab Aghamov, Christel Baier, Joel Ouaknine +3
Dynamic Bayesian networks (DBNs) are compact graphical representations used to model probabilistic systems where interdependent random variables and their distributions evolve over…
Automata on -adic words
Valérie Berthé, Toghrul Karimov, Mihir Vahanwala
A fundamental question in logic and verification is the following: for which unary predicates is the monadic second-order theory of $\langle \mathbb{N}; <, P_1,…
Model Checking Markov Chains as Distribution Transformers
Rajab Aghamov, Christel Baier, Toghrul Karimov +4
The conventional perspective on Markov chains considers decision problems concerning the probabilities of temporal properties being satisfied by traces of visited states. However,…
On the Decidability of Monadic Theories of Arithmetic Predicates
Valérie Berthé, Toghrul Karimov, Joris Nieuwveld +3
We investigate the decidability of the monadic second-order (MSO) theory of the structure , for various unary predicates $P_1,\ldots,P…
The Monadic Theory of Toric Words
Valérie Berthé, Toghrul Karimov, Joël Ouaknine +2
For which unary predicates is the MSO theory of the structure decidable? We survey the state of the art, leadin…
Characterising Robust Instances of Ultimate Positivity for Linear Dynamical Systems
Mihir Vahanwala
Linear Dynamical Systems, both discrete and continuous, are invaluable mathematical models in a plethora of applications such the verification of probabilistic systems, model check…
Unified Fairness for Weak Memory Verification
Parosh Aziz Abdulla, Mohamed Faouzi Atig, Adwait Godbole +2
We consider the verification of omega-regular linear temporal properties of concurrent programs running under weak memory semantics. We observe that in particular, these properties…
Skolem and Positivity Completeness of Ergodic Markov Chains
Mihir Vahanwala
We consider the following Markov Reachability decision problems that view Markov Chains as Linear Dynamical Systems: given a finite, rational Markov Chain, source and target states…
Robust Positivity Problems for Linear Recurrence Sequences
Mihir Vahanwala
Linear Recurrence Sequences (LRS) are a fundamental mathematical primitive for a plethora of applications such as the verification of probabilistic systems, model checking, computa…
On Robustness for the Skolem, Positivity and Ultimate Positivity Problems
S. Akshay, Hugo Bazille, Blaise Genest +1
The Skolem problem is a long-standing open problem in linear dynamical systems: can a linear recurrence sequence (LRS) ever reach 0 from a given initial configuration? Similarly, t…