Semialgebraic invariant synthesis for the Kannan-Lipton orbit problem

Semialgebraic invariant synthesis for the Kannan-Lipton orbit problem

Toon andere (1) versies

<p>The Orbit Problem consists of determining, given a linear transformation A on Qd, together with vectors x and y, whether the orbit of x under repeated applications of A can ever reach y. This problem was famously shown to be decidable by Kannan and Lipton in the 1980s.</p> <br/>...

Volledige beschrijving

Bibliografische gegevens
Hoofdauteurs:	Fijalkow, N, Ohlmann, P, Ouaknine, J, Pouly, A, Worrell, J
Formaat:	Journal article
Gepubliceerd in:	Schloss Dagstuhl 2017

Gelijkaardige items

Semialgebraic invariant synthesis for the Kannan-Lipton Orbit Problem
door: Fijalkow, N, et al.
Gepubliceerd in: (2017)

Complete semialgebraic invariant synthesis for the Kannan-Lipton orbit problem
door: Fijalkow, N, et al.
Gepubliceerd in: (2019)

The Semialgebraic Orbit Problem
door: Almagor, S, et al.
Gepubliceerd in: (2019)

On the Monniaux Problem in abstract interpretation
door: Fijalkow, N, et al.
Gepubliceerd in: (2019)

On the complexity of the Escape Problem for linear dynamical systems over compact semialgebraic sets
door: D'Costa, J, et al.
Gepubliceerd in: (2021)

On the decidability of reachability in linear time-invariant systems
door: Fijalkow, N, et al.
Gepubliceerd in: (2019)

Bounding the escape time of a linear dynamical system over a compact semialgebraic set
door: D'Costa, J, et al.
Gepubliceerd in: (2022)

On strongest algebraic program invariants
door: Hrushovski, E, et al.
Gepubliceerd in: (2023)

Polynomial invariants for affine programs
door: Hrushovski, E, et al.
Gepubliceerd in: (2018)

Algebraic invariants for linear hybrid automata
door: Majumdar, R, et al.
Gepubliceerd in: (2020)

Complexity of semialgebraic proofs
door: Grigoriev, D, et al.
Gepubliceerd in: (2002)

On the complexity of the orbit problem
door: Chonev, V, et al.
Gepubliceerd in: (2016)

On the complexity of the orbit problem
door: Chonev, V, et al.
Gepubliceerd in: (2016)

The orbit problem in higher dimensions
door: Chonev, V, et al.
Gepubliceerd in: (2013)

Efficient simplicial replacement of semialgebraic sets
door: Saugata Basu, et al.
Gepubliceerd in: (2023-01-01)

Underapproximating backward reachable sets by semialgebraic sets
door: Xue, Bai, et al.
Gepubliceerd in: (2018)

Semialgebraic methods and generalized sum-product phenomena
door: Yifan Jing, et al.
Gepubliceerd in: (2022-12-01)

Regularity and Semialgebraicity of Solutions of Linear Equations Systems
door: Marcello Malagutti
Gepubliceerd in: (2024-01-01)

Urban bias - Seers versus Lipton
Gepubliceerd in: (1977)

Porous invariants
door: Lefaucheux, E, et al.
Gepubliceerd in: (2021)

First-order orbit queries
door: Almagor, S, et al.
Gepubliceerd in: (2020)

Invariants for continuous linear dynamical systems
door: Kelmendi, E, et al.
Gepubliceerd in: (2020)

O-minimal invariants for linear loops
door: Almagor, S, et al.
Gepubliceerd in: (2018)

On termination and invariance for faulty channel machines
door: Bouyer, P, et al.
Gepubliceerd in: (2012)

Porous invariants for linear systems
door: Lefaucheux, E, et al.
Gepubliceerd in: (2024)

A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model.
door: Xiang Tian, et al.
Gepubliceerd in: (2020-01-01)

The Church Synthesis Problem with Metric
door: Jenkins, M, et al.
Gepubliceerd in: (2011)

O-minimal invariants for discrete-time dynamical systems
door: Almagor, S, et al.
Gepubliceerd in: (2022)

An observation on Kannan mappings
door: Nakanishi Masato, et al.
Gepubliceerd in: (2010-02-01)

On the decidability of membership in matrix-exponential semigroups
door: Ouaknine, J, et al.
Gepubliceerd in: (2019)

Solvability of matrix-exponential equations
door: Ouaknine, J, et al.
Gepubliceerd in: (2016)

Solvability of matrix-exponential equations
door: Ouaknine, J, et al.
Gepubliceerd in: (2016)

Solvability of matrix-exponential equations
door: Ouaknine, J, et al.
Gepubliceerd in: (2016)

Relations and equivalences between circuit lower bounds and Karp-Lipton theorems
door: Williams, Richard Ryan, et al.
Gepubliceerd in: (2021)

The Orbit Problem for parametric linear dynamical systems
door: Baier, C, et al.
Gepubliceerd in: (2021)

Fractals of Interpolative Kannan Mappings
door: Xiangting Shi, et al.
Gepubliceerd in: (2024-08-01)

An Extended Kannan Contraction Mapping and Applications
door: R. P. Pant
Gepubliceerd in: (2024-08-01)

Model checking flat freeze LTL on one-counter automata
door: Lechner, A, et al.
Gepubliceerd in: (2016)

Decision Problems for Linear Recurrence Sequences.
door: Ouaknine, J, et al.
Gepubliceerd in: (2012)

Spatial Cluster Analysis by the Adleman-Lipton DNA Computing Model and Flexible Grids
door: Xiyu Liu, et al.
Gepubliceerd in: (2012-01-01)