Zobrazeno 1 - 10
of 222
pro vyhledávání: '"Ouaknine, Joël"'
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 numbers of the form $S_\beta(\boldsymbol{u}):=\sum_{n=0}^\infty \frac{u_n}{\beta^n}$, where $\boldsymbol{u}=\langle u_n \rangle_{n=0}^\infty$ is an infinite word over a finite alphabet and $\beta\in \mathbb{C}$ satisfies $|\beta|>1$. Our
Externí odkaz:
http://arxiv.org/abs/2405.05279
A linear constraint loop is specified by a system of linear inequalities that define the relation between the values of the program variables before and after a single execution of the loop body. In this paper we consider the problem of determining w
Externí odkaz:
http://arxiv.org/abs/2405.12992
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
Autor:
Jindal, Gorav, Ouaknine, Joël
The Skolem Problem asks, given an integer linear recurrence sequence (LRS), to determine whether the sequence contains a zero term or not. Its decidability is a longstanding open problem in theoretical computer science and automata theory. Currently,
Externí odkaz:
http://arxiv.org/abs/2403.00098
We introduce the notion of a twisted rational zero of a non-degenerate linear recurrence sequence (LRS). We show that any non-degenerate LRS has only finitely many such twisted rational zeros. In the particular case of the Tribonacci sequence, we sho
Externí odkaz:
http://arxiv.org/abs/2401.06537
The matrix semigroup membership problem asks, given square matrices $M,M_1,\ldots,M_k$ of the same dimension, whether $M$ lies in the semigroup generated by $M_1,\ldots,M_k$. It is classical that this problem is undecidable in general but decidable i
Externí odkaz:
http://arxiv.org/abs/2311.06241