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

Полное описание

Библиографические подробности
Главные авторы:	D'Costa, J, Lefaucheux, E, Neumann, E, Ouaknine, J, Worrell, J
Формат:	Conference item
Язык:	English
Опубликовано:	Schloss Dagstuhl – Leibniz-Zentrum für Informatik 2022
Предметы:	Logic and verification Theory of computation

Схожие документы

On the complexity of the Escape Problem for linear dynamical systems over compact semialgebraic sets
по: D'Costa, J, и др.
Опубликовано: (2021)

Reachability and escape problems in linear dynamical systems
по: Dcosta, J
Опубликовано: (2024)

How fast can you escape a compact polytope?
по: D'Costa, J, и др.
Опубликовано: (2020)

The Semialgebraic Orbit Problem
по: Almagor, S, и др.
Опубликовано: (2019)

Parameter synthesis for parametric probabilistic dynamical systems and prefix-independent specifications
по: Baier, C, и др.
Опубликовано: (2022)

Skolem meets Schanuel
по: Bilu, Y, и др.
Опубликовано: (2022)

Semialgebraic invariant synthesis for the Kannan-Lipton Orbit Problem
по: Fijalkow, N, и др.
Опубликовано: (2017)

Semialgebraic invariant synthesis for the Kannan-Lipton orbit problem
по: Fijalkow, N, и др.
Опубликовано: (2017)

Complete semialgebraic invariant synthesis for the Kannan-Lipton orbit problem
по: Fijalkow, N, и др.
Опубликовано: (2019)

On the complexity of the orbit problem
по: Chonev, V, и др.
Опубликовано: (2016)

Efficient simplicial replacement of semialgebraic sets
по: Saugata Basu, и др.
Опубликовано: (2023-01-01)

Underapproximating backward reachable sets by semialgebraic sets
по: Xue, Bai, и др.
Опубликовано: (2018)

Porous invariants for linear systems
по: Lefaucheux, E, и др.
Опубликовано: (2024)

Complexity of semialgebraic proofs
по: Grigoriev, D, и др.
Опубликовано: (2002)

Regularity and Semialgebraicity of Solutions of Linear Equations Systems
по: Marcello Malagutti
Опубликовано: (2024-01-01)

On the polytope escape problem for continuous linear dynamical systems
по: Ouaknine, J, и др.
Опубликовано: (2017)

Automated Verification of Shape and Size
по: Nguyen, Huu Hai, и др.
Опубликовано: (2007)

What's decidable about linear loops?
по: Karimov, T, и др.
Опубликовано: (2022)

Linear Completeness Thresholds for Bounded Model Checking.
по: Kroening, D, и др.
Опубликовано: (2011)

On the decidability and complexity of Metric Temporal Logic over finite words
по: Joel Ouaknine, и др.
Опубликовано: (2007-02-01)

Safety Constraint-Guided Reinforcement Learning with Linear Temporal Logic
по: Ryeonggu Kwon, и др.
Опубликовано: (2023-11-01)

Alternating Timed Automata over Bounded Time
по: Jenkins, M, и др.
Опубликовано: (2010)

Termination of linear loops over the integers
по: Hosseini, M, и др.
Опубликовано: (2019)

Alternating Timed Automata over Bounded Time
по: Jenkins, M, и др.
Опубликовано: (2010)

Semialgebraic methods and generalized sum-product phenomena
по: Yifan Jing, и др.
Опубликовано: (2022-12-01)

Porous invariants
по: Lefaucheux, E, и др.
Опубликовано: (2021)

The 2-dimensional constraint loop problem is decidable
по: Guilmant, Q, и др.
Опубликовано: (2024)

The pseudo-reachability problem for diagonalisable linear dynamical systems
по: D'Costa, J, и др.
Опубликовано: (2022)

Fuzzy coloured petri nets‐based method to analyse and verify the functionality of software
по: Mina Chavoshi, и др.
Опубликовано: (2023-09-01)

Position Verification in Connected Vehicles for Cyber Resilience Using Geofencing and Fuzzy Logic
по: Maria Drolence Mwanje, и др.
Опубликовано: (2024-01-01)

An Abstraction Technique for Verifying Shared-Memory Concurrency
по: Wytse Oortwijn, и др.
Опубликовано: (2020-06-01)

On reachability for hybrid automata over bounded time
по: Brihaye, T, и др.
Опубликовано: (2011)

On the Expressive Power of Some Extensions of Linear Temporal Logic
по: Anton Gnatenko, и др.
Опубликовано: (2018-10-01)

Towards a Theory of Time-Bounded Verification.
по: Ouaknine, J, и др.
Опубликовано: (2010)

Nonnegativity problems for matrix semigroups
по: D'Costa, J, и др.
Опубликовано: (2024)

Time-Bounded Verification
по: Ouaknine, J, и др.
Опубликовано: (2009)

Synthesis and alternating automata over real time
по: Jenkins, M, и др.
Опубликовано: (2012)

On Using First-Order Theorem Provers in the Jahob Data Structure Verification System
по: Bouillaguet, Charles, и др.
Опубликовано: (2006)

Generating and Employing Witness Automata for ACTLW Formulae
по: Rok Vogrin, и др.
Опубликовано: (2022-01-01)

Formal Verification of Three-Valued Digital Waveforms
по: Nina Yu. Kutsak, и др.
Опубликовано: (2019-09-01)