Joël Ouaknine

collaborators

3 papers

cs.LO2024

On the Decidability of Presburger Arithmetic Expanded with Powers

Toghrul Karimov, Florian Luca, Joris Nieuwveld +2

We prove that for any integers $α, β > 1$ , the existential fragment of the first-order theory of the structure $⟨ Z; 0, 1, <, +, α^{N}, β^{N} ⟩$ …

cs.LO2024

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,…

cs.LO2023

The Monadic Theory of Toric Words

Valérie Berthé, Toghrul Karimov, Joël Ouaknine +2

For which unary predicates $P_{1}, \dots, P_{m}$ is the MSO theory of the structure $⟨ N; <, P_{1}, \dots, P_{m} ⟩$ decidable? We survey the state of the art, leadin…