Zobrazeno 1 - 10
of 20
pro vyhledávání: '"Karimov, Toghrul"'
We prove that for any integers $\alpha, \beta > 1$, the existential fragment of the first-order theory of the structure $\langle \mathbb{Z}; 0,1,<, +, \alpha^{\mathbb{N}}, \beta^{\mathbb{N}}\rangle$ is decidable (where $\alpha^{\mathbb{N}}$ is the se
Externí odkaz:
http://arxiv.org/abs/2407.05191
Autor:
Aghamov, Rajab, Baier, Christel, Karimov, Toghrul, Nieuwveld, Joris, Ouaknine, Joël, Piribauer, Jakob, Vahanwala, Mihir
The conventional perspective on Markov chains considers decision problems concerning the probabilities of temporal properties being satisfied by traces of visited states. However, consider the following query made of a stochastic system modelling the
Externí odkaz:
http://arxiv.org/abs/2406.15087
Autor:
Berthé, Valérie, Karimov, Toghrul, Nieuwveld, Joris, Ouaknine, Joël, Vahanwala, Mihir, Worrell, James
We investigate the decidability of the monadic second-order (MSO) theory of the structure $\langle \mathbb{N};<,P_1, \ldots,P_k \rangle$, for various unary predicates $P_1,\ldots,P_k \subseteq \mathbb{N}$. We focus in particular on "arithmetic" predi
Externí odkaz:
http://arxiv.org/abs/2405.07953
In discrete-time linear dynamical systems (LDSs), a linear map is repeatedly applied to an initial vector yielding a sequence of vectors called the orbit of the system. A weight function assigning weights to the points in the orbit can be used to mod
Externí odkaz:
http://arxiv.org/abs/2405.06512
We consider reachability decision problems for linear dynamical systems: Given a linear map on $\mathbb{R}^d$ , together with source and target sets, determine whether there is a point in the source set whose orbit, obtained by repeatedly applying th
Externí odkaz:
http://arxiv.org/abs/2403.06515
For which unary predicates $P_1, \ldots, P_m$ is the MSO theory of the structure $\langle \mathbb{N}; <, P_1, \ldots, P_m \rangle$ decidable? We survey the state of the art, leading us to investigate combinatorial properties of almost-periodic, morph
Externí odkaz:
http://arxiv.org/abs/2311.04895
We survey the state of the art on the algorithmic analysis of discrete linear dynamical systems, focussing in particular on reachability, model-checking, and invariant-generation questions, both unconditionally as well as relative to oracles for the
Externí odkaz:
http://arxiv.org/abs/2206.11412
Autor:
D'Costa, Julian, Karimov, Toghrul, Majumdar, Rupak, Ouaknine, Joël, Salamati, Mahmoud, Worrell, James
We study fundamental reachability problems on pseudo-orbits of linear dynamical systems. Pseudo-orbits can be viewed as a model of computation with limited precision and pseudo-reachability can be thought of as a robust version of classical reachabil
Externí odkaz:
http://arxiv.org/abs/2204.12253
Autor:
Baier, Christel, Funke, Florian, Jantsch, Simon, Karimov, Toghrul, Lefaucheux, Engel, Luca, Florian, Ouaknine, Joël, Purser, David, Whiteland, Markus A., Worrell, James
We study a parametric version of the Kannan-Lipton Orbit Problem for linear dynamical systems. We show decidability in the case of one parameter and Skolem-hardness with two or more parameters. More precisely, consider a $d$-dimensional square matrix
Externí odkaz:
http://arxiv.org/abs/2104.10634
We consider the problem of deciding $\omega$-regular properties on infinite traces produced by linear loops. Here we think of a given loop as producing a single infinite trace that encodes information about the signs of program variables at each time
Externí odkaz:
http://arxiv.org/abs/2010.14432