On the complexity of the orbit problem

On the complexity of the orbit problem

Taispeáin leaganacha eile (1)

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...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Chonev, V, Ouaknine, J, Worrell, J
Formáid:	Journal article
Foilsithe / Cruthaithe:	Association for Computing Machinery 2016

Míreanna comhchosúla

On the complexity of the orbit problem
de réir: Chonev, V, et al.
Foilsithe / Cruthaithe: (2016)

The orbit problem in higher dimensions
de réir: Chonev, V, et al.
Foilsithe / Cruthaithe: (2013)

On the skolem problem for continuous linear dynamical systems
de réir: Chonev, V, et al.
Foilsithe / Cruthaithe: (2016)

On the Skolem Problem for continuous linear dynamical systems
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2016)

The Semialgebraic Orbit Problem
de réir: Almagor, S, et al.
Foilsithe / Cruthaithe: (2019)

On recurrent reachability for continuous linear dynamical systems
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2016)

On recurrent reachability for continuous linear dynamical systems
de réir: Chonev, V, et al.
Foilsithe / Cruthaithe: (2016)

First-order orbit queries
de réir: Almagor, S, et al.
Foilsithe / Cruthaithe: (2020)

Semialgebraic invariant synthesis for the Kannan-Lipton Orbit Problem
de réir: Fijalkow, N, et al.
Foilsithe / Cruthaithe: (2017)

Semialgebraic invariant synthesis for the Kannan-Lipton orbit problem
de réir: Fijalkow, N, et al.
Foilsithe / Cruthaithe: (2017)

Complete semialgebraic invariant synthesis for the Kannan-Lipton orbit problem
de réir: Fijalkow, N, et al.
Foilsithe / Cruthaithe: (2019)

On the Complexity of the Equivalence Problem for Probabilistic Automata
de réir: Kiefer, S, et al.
Foilsithe / Cruthaithe: (2012)

The Orbit Problem for parametric linear dynamical systems
de réir: Baier, C, et al.
Foilsithe / Cruthaithe: (2021)

Decision Problems for Linear Recurrence Sequences.
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2012)

The polytope-collision problem
de réir: Almagor, S, et al.
Foilsithe / Cruthaithe: (2017)

ON THE DECIDABILITY AND COMPLEXITY OF METRIC TEMPORAL LOGIC OVER FINITE WORDS
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2007)

On the complexity of the Escape Problem for linear dynamical systems over compact semialgebraic sets
de réir: D'Costa, J, et al.
Foilsithe / Cruthaithe: (2021)

Reachability problems for linear dynamical systems
de réir: Chonev, V
Foilsithe / Cruthaithe: (2015)

Decision problems for second-order holonomic sequences
de réir: Neumann, E, et al.
Foilsithe / Cruthaithe: (2021)

Nonnegativity problems for matrix semigroups
de réir: D'Costa, J, et al.
Foilsithe / Cruthaithe: (2024)

On the Relationship between Reachability Problems in Timed and Counter Automata
de réir: Haase, C, et al.
Foilsithe / Cruthaithe: (2012)

On the relationship between reachability problems in timed and counter automata
de réir: Haase, C, et al.
Foilsithe / Cruthaithe: (2012)

On the decidability and complexity of Metric Temporal Logic over finite words
de réir: Joel Ouaknine, et al.
Foilsithe / Cruthaithe: (2007-02-01)

On reachability problems for low-dimensional matrix semigroups
de réir: Colcombet, T, et al.
Foilsithe / Cruthaithe: (2019)

On the polytope escape problem for continuous linear dynamical systems
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2017)

The Church Synthesis Problem with Metric
de réir: Jenkins, M, et al.
Foilsithe / Cruthaithe: (2011)

On the Skolem problem and prime powers
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2020)

On expressiveness and complexity in real-time model checking
de réir: Bouyer, P, et al.
Foilsithe / Cruthaithe: (2008)

The 2-dimensional constraint loop problem is decidable
de réir: Guilmant, Q, et al.
Foilsithe / Cruthaithe: (2024)

Decidability and complexity results for timed automata via channel machines
de réir: Abdulla, P, et al.
Foilsithe / Cruthaithe: (2005)

ON THE COMPLEXITY OF EQUIVALENCE AND MINIMISATION FOR Q-WEIGHTED AUTOMATA
de réir: Kiefer, S, et al.
Foilsithe / Cruthaithe: (2013)

On metric temporal logic and faulty turing machines
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2006)

Some Recent Results in Metric Temporal Logic
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2008)

Towards a Theory of Time-Bounded Verification.
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2010)

Safety metric temporal logic is fully decidable
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2006)

On the Skolem problem and the Skolem conjecture
de réir: Lipton, RJ, et al.
Foilsithe / Cruthaithe: (2022)

On the Monniaux Problem in abstract interpretation
de réir: Fijalkow, N, et al.
Foilsithe / Cruthaithe: (2019)

The pseudo-Skolem Problem is decidable
de réir: D'Costa, J, et al.
Foilsithe / Cruthaithe: (2021)

The pseudo-reachability problem for diagonalisable linear dynamical systems
de réir: D'Costa, J, et al.
Foilsithe / Cruthaithe: (2022)

Undecidability of Universality for Timed Automata with Minimal Resources
de réir: Adams, S, et al.
Foilsithe / Cruthaithe: (2007)