Bounding the escape time of a linear dynamical system over a compact semialgebraic set

Bounding the escape time of a linear dynamical system over a compact semialgebraic set

We study the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets. We establish a uniform upper bound on the number of iterations it takes for every orbit of a rational matrix to escape a compact semialgebraic set defined over rational data. Our bound is doubly e...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	D'Costa, J, Lefaucheux, E, Neumann, E, Ouaknine, J, Worrell, J
Formáid:	Conference item
Teanga:	English
Foilsithe / Cruthaithe:	Schloss Dagstuhl – Leibniz-Zentrum für Informatik 2022
Ábhair:	Logic and verification Theory of computation

Míreanna comhchosúla

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 and escape problems in linear dynamical systems
de réir: Dcosta, J
Foilsithe / Cruthaithe: (2024)

How fast can you escape a compact polytope?
de réir: D'Costa, J, et al.
Foilsithe / Cruthaithe: (2020)

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

Parameter synthesis for parametric probabilistic dynamical systems and prefix-independent specifications
de réir: Baier, C, et al.
Foilsithe / Cruthaithe: (2022)

Skolem meets Schanuel
de réir: Bilu, Y, et al.
Foilsithe / Cruthaithe: (2022)

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 orbit problem
de réir: Chonev, V, et al.
Foilsithe / Cruthaithe: (2016)

Efficient simplicial replacement of semialgebraic sets
de réir: Saugata Basu, et al.
Foilsithe / Cruthaithe: (2023-01-01)

Underapproximating backward reachable sets by semialgebraic sets
de réir: Xue, Bai, et al.
Foilsithe / Cruthaithe: (2018)

Porous invariants for linear systems
de réir: Lefaucheux, E, et al.
Foilsithe / Cruthaithe: (2024)

Complexity of semialgebraic proofs
de réir: Grigoriev, D, et al.
Foilsithe / Cruthaithe: (2002)

Regularity and Semialgebraicity of Solutions of Linear Equations Systems
de réir: Marcello Malagutti
Foilsithe / Cruthaithe: (2024-01-01)

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

Automated Verification of Shape and Size
de réir: Nguyen, Huu Hai, et al.
Foilsithe / Cruthaithe: (2007)

What's decidable about linear loops?
de réir: Karimov, T, et al.
Foilsithe / Cruthaithe: (2022)

Linear Completeness Thresholds for Bounded Model Checking.
de réir: Kroening, D, et al.
Foilsithe / Cruthaithe: (2011)

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

Safety Constraint-Guided Reinforcement Learning with Linear Temporal Logic
de réir: Ryeonggu Kwon, et al.
Foilsithe / Cruthaithe: (2023-11-01)

Alternating Timed Automata over Bounded Time
de réir: Jenkins, M, et al.
Foilsithe / Cruthaithe: (2010)

Termination of linear loops over the integers
de réir: Hosseini, M, et al.
Foilsithe / Cruthaithe: (2019)

Alternating Timed Automata over Bounded Time
de réir: Jenkins, M, et al.
Foilsithe / Cruthaithe: (2010)

Semialgebraic methods and generalized sum-product phenomena
de réir: Yifan Jing, et al.
Foilsithe / Cruthaithe: (2022-12-01)

Porous invariants
de réir: Lefaucheux, E, et al.
Foilsithe / Cruthaithe: (2021)

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

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

Fuzzy coloured petri nets‐based method to analyse and verify the functionality of software
de réir: Mina Chavoshi, et al.
Foilsithe / Cruthaithe: (2023-09-01)

Position Verification in Connected Vehicles for Cyber Resilience Using Geofencing and Fuzzy Logic
de réir: Maria Drolence Mwanje, et al.
Foilsithe / Cruthaithe: (2024-01-01)

An Abstraction Technique for Verifying Shared-Memory Concurrency
de réir: Wytse Oortwijn, et al.
Foilsithe / Cruthaithe: (2020-06-01)

On reachability for hybrid automata over bounded time
de réir: Brihaye, T, et al.
Foilsithe / Cruthaithe: (2011)

On the Expressive Power of Some Extensions of Linear Temporal Logic
de réir: Anton Gnatenko, et al.
Foilsithe / Cruthaithe: (2018-10-01)

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

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

Time-Bounded Verification
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2009)

Synthesis and alternating automata over real time
de réir: Jenkins, M, et al.
Foilsithe / Cruthaithe: (2012)

On Using First-Order Theorem Provers in the Jahob Data Structure Verification System
de réir: Bouillaguet, Charles, et al.
Foilsithe / Cruthaithe: (2006)

Generating and Employing Witness Automata for ACTLW Formulae
de réir: Rok Vogrin, et al.
Foilsithe / Cruthaithe: (2022-01-01)

Formal Verification of Three-Valued Digital Waveforms
de réir: Nina Yu. Kutsak, et al.
Foilsithe / Cruthaithe: (2019-09-01)