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

Fuld beskrivelse

Bibliografiske detaljer
Main Authors:	D'Costa, J, Lefaucheux, E, Neumann, E, Ouaknine, J, Worrell, J
Format:	Conference item
Sprog:	English
Udgivet:	Schloss Dagstuhl – Leibniz-Zentrum für Informatik 2022
Fag:	Logic and verification Theory of computation

Lignende værker

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

Reachability and escape problems in linear dynamical systems
af: Dcosta, J
Udgivet: (2024)

How fast can you escape a compact polytope?
af: D'Costa, J, et al.
Udgivet: (2020)

The Semialgebraic Orbit Problem
af: Almagor, S, et al.
Udgivet: (2019)

Parameter synthesis for parametric probabilistic dynamical systems and prefix-independent specifications
af: Baier, C, et al.
Udgivet: (2022)

Skolem meets Schanuel
af: Bilu, Y, et al.
Udgivet: (2022)

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

Semialgebraic invariant synthesis for the Kannan-Lipton orbit problem
af: Fijalkow, N, et al.
Udgivet: (2017)

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

On the complexity of the orbit problem
af: Chonev, V, et al.
Udgivet: (2016)

Efficient simplicial replacement of semialgebraic sets
af: Saugata Basu, et al.
Udgivet: (2023-01-01)

Underapproximating backward reachable sets by semialgebraic sets
af: Xue, Bai, et al.
Udgivet: (2018)

Porous invariants for linear systems
af: Lefaucheux, E, et al.
Udgivet: (2024)

Complexity of semialgebraic proofs
af: Grigoriev, D, et al.
Udgivet: (2002)

Regularity and Semialgebraicity of Solutions of Linear Equations Systems
af: Marcello Malagutti
Udgivet: (2024-01-01)

On the polytope escape problem for continuous linear dynamical systems
af: Ouaknine, J, et al.
Udgivet: (2017)

Automated Verification of Shape and Size
af: Nguyen, Huu Hai, et al.
Udgivet: (2007)

What's decidable about linear loops?
af: Karimov, T, et al.
Udgivet: (2022)

Linear Completeness Thresholds for Bounded Model Checking.
af: Kroening, D, et al.
Udgivet: (2011)

On the decidability and complexity of Metric Temporal Logic over finite words
af: Joel Ouaknine, et al.
Udgivet: (2007-02-01)

Safety Constraint-Guided Reinforcement Learning with Linear Temporal Logic
af: Ryeonggu Kwon, et al.
Udgivet: (2023-11-01)

Alternating Timed Automata over Bounded Time
af: Jenkins, M, et al.
Udgivet: (2010)

Termination of linear loops over the integers
af: Hosseini, M, et al.
Udgivet: (2019)

Alternating Timed Automata over Bounded Time
af: Jenkins, M, et al.
Udgivet: (2010)

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

Porous invariants
af: Lefaucheux, E, et al.
Udgivet: (2021)

The 2-dimensional constraint loop problem is decidable
af: Guilmant, Q, et al.
Udgivet: (2024)

The pseudo-reachability problem for diagonalisable linear dynamical systems
af: D'Costa, J, et al.
Udgivet: (2022)

Fuzzy coloured petri nets‐based method to analyse and verify the functionality of software
af: Mina Chavoshi, et al.
Udgivet: (2023-09-01)

Position Verification in Connected Vehicles for Cyber Resilience Using Geofencing and Fuzzy Logic
af: Maria Drolence Mwanje, et al.
Udgivet: (2024-01-01)

An Abstraction Technique for Verifying Shared-Memory Concurrency
af: Wytse Oortwijn, et al.
Udgivet: (2020-06-01)

On reachability for hybrid automata over bounded time
af: Brihaye, T, et al.
Udgivet: (2011)

On the Expressive Power of Some Extensions of Linear Temporal Logic
af: Anton Gnatenko, et al.
Udgivet: (2018-10-01)

Towards a Theory of Time-Bounded Verification.
af: Ouaknine, J, et al.
Udgivet: (2010)

Nonnegativity problems for matrix semigroups
af: D'Costa, J, et al.
Udgivet: (2024)

Time-Bounded Verification
af: Ouaknine, J, et al.
Udgivet: (2009)

Synthesis and alternating automata over real time
af: Jenkins, M, et al.
Udgivet: (2012)

On Using First-Order Theorem Provers in the Jahob Data Structure Verification System
af: Bouillaguet, Charles, et al.
Udgivet: (2006)

Generating and Employing Witness Automata for ACTLW Formulae
af: Rok Vogrin, et al.
Udgivet: (2022-01-01)

Formal Verification of Three-Valued Digital Waveforms
af: Nina Yu. Kutsak, et al.
Udgivet: (2019-09-01)