Source author record

Ventsislav Chonev

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Systems and Control Data Structures and Algorithms Symbolic Computation

Catalog footprint

Research overview

4works

4topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On Recurrent Reachability for Continuous Linear Dynamical Systems

The continuous evolution of a wide variety of systems, including continuous-time Markov chains and linear hybrid automata, can be described in terms of linear differential equations. In this paper we study the decision problem of whether the solution $\boldsymbol{x}(t)$ of a system of linear differential equations $d\boldsymbol{x}/dt=A\boldsymbol{x}$ reaches a target halfspace infinitely often. This recurrent reachability problem can equivalently be formulated as the following Infinite Zeros Problem: does a real-valued function $f:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}$ satisfying a given linear differential equation have infinitely many zeros? Our main decidability result is that if the differential equation has order at most $7$ , then the Infinite Zeros Problem is decidable. On the other hand, we show that a decision procedure for the Infinite Zeros Problem at order $9$ (and above) would entail a major breakthrough in Diophantine Approximation, specifically an algorithm for computing the Lagrange constants of arbitrary real algebraic numbers to arbitrary precision.

preprint2016arXiv

On the Complexity of the Orbit Problem

We consider higher-dimensional versions of Kannan and Lipton's Orbit Problem---determining whether a target vector space V may be reached from a starting point x under repeated applications of a linear transformation A. Answering two questions posed by Kannan and Lipton in the 1980s, we show that when V has dimension one, this problem is solvable in polynomial time, and when V has dimension two or three, the problem is in NP^{RP}.

preprint2016arXiv

On the Skolem Problem for Continuous Linear Dynamical Systems

The Continuous Skolem Problem asks whether a real-valued function satisfying a linear differential equation has a zero in a given interval of real numbers. This is a fundamental reachability problem for continuous linear dynamical systems, such as linear hybrid automata and continuous-time Markov chains. Decidability of the problem is currently open---indeed decidability is open even for the sub-problem in which a zero is sought in a bounded interval. In this paper we show decidability of the bounded problem subject to Schanuel's Conjecture, a unifying conjecture in transcendental number theory. We furthermore analyse the unbounded problem in terms of the frequencies of the differential equation, that is, the imaginary parts of the characteristic roots. We show that the unbounded problem can be reduced to the bounded problem if there is at most one rationally linearly independent frequency, or if there are two rationally linearly independent frequencies and all characteristic roots are simple. We complete the picture by showing that decidability of the unbounded problem in the case of two (or more) rationally linearly independent frequencies would entail a major new effectiveness result in Diophantine approximation, namely computability of the Diophantine-approximation types of all real algebraic numbers.

preprint2014arXiv

The Polyhedron-Hitting Problem

We consider polyhedral versions of Kannan and Lipton's Orbit Problem (STOC '80 and JACM '86)---determining whether a target polyhedron V may be reached from a starting point x under repeated applications of a linear transformation A in an ambient vector space Q^m. In the context of program verification, very similar reachability questions were also considered and left open by Lee and Yannakakis in (STOC '92). We present what amounts to a complete characterisation of the decidability landscape for the Polyhedron-Hitting Problem, expressed as a function of the dimension m of the ambient space, together with the dimension of the polyhedral target V: more precisely, for each pair of dimensions, we either establish decidability, or show hardness for longstanding number-theoretic open problems.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ventsislav Chonev

Research overview

Is this your work?

4 publications

On Recurrent Reachability for Continuous Linear Dynamical Systems

On the Complexity of the Orbit Problem

On the Skolem Problem for Continuous Linear Dynamical Systems

The Polyhedron-Hitting Problem

See the researcher in context

Building this map preview