What's decidable about linear loops?

What's decidable about linear loops?

We consider the MSO model-checking problem for simple linear loops, or equivalently discrete-time linear dynamical systems, with semialgebraic predicates (i.e., Boolean combinations of polynomial inequalities on the variables). We place no restrictions on the number of program variables, or equivale...

Volledige beschrijving

Bibliografische gegevens
Hoofdauteurs:	Karimov, T, Lefaucheux, E, Ouaknine, J, Purser, D, Varonka, A, Whiteland, MA, Worrell, J
Formaat:	Conference item
Taal:	English
Gepubliceerd in:	Association for Computing Machinery 2022

Gelijkaardige items

The 2-dimensional constraint loop problem is decidable
door: Guilmant, Q, et al.
Gepubliceerd in: (2024)

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

Deciding ω-regular properties on linear recurrence sequences
door: Almagor, S, et al.
Gepubliceerd in: (2021)

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

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

On the decidability of Presburger arithmetic expanded with powers
door: Karimov, T, et al.
Gepubliceerd in: (2025)

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

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

The pseudo-Skolem Problem is decidable
door: D'Costa, J, et al.
Gepubliceerd in: (2021)

On the decidability of monadic second-order logic with arithmetic predicates
door: Berthé, V, et al.
Gepubliceerd in: (2024)

Safety metric temporal logic is fully decidable
door: Ouaknine, J, et al.
Gepubliceerd in: (2006)

On the decidability of Metric Temporal Logic
door: Ouaknine, J, et al.
Gepubliceerd in: (2005)

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

Termination of linear loops over the integers
door: Hosseini, M, et al.
Gepubliceerd in: (2019)

ON THE DECIDABILITY AND COMPLEXITY OF METRIC TEMPORAL LOGIC OVER FINITE WORDS
door: Ouaknine, J, et al.
Gepubliceerd in: (2007)

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

What is Decidable about Strings?
door: Ganesh, Vijay, et al.
Gepubliceerd in: (2011)

On LTL model-checking for low-dimensional discrete linear dynamical systems
door: Karimov, T, et al.
Gepubliceerd in: (2020)

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

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 positivity and minimality for second-order holonomic sequences
door: Kenison, G, et al.
Gepubliceerd in: (2021)

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

Decidability and complexity results for timed automata via channel machines
door: Abdulla, P, et al.
Gepubliceerd in: (2005)

What can you Decide about Resetable Arrays?
door: Roscoe, A, et al.
Gepubliceerd in: (2001)

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

What is decidable about string constraints with ReplaceAll function
door: Chen, T, et al.
Gepubliceerd in: (2017)

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

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

Decidability boundaries in linear dynamical systems
door: de Sousa Pinto, J
Gepubliceerd in: (2017)

Deciding Bit−Vector Arithmetic with Abstraction
door: Bryant, R, et al.
Gepubliceerd in: (2007)

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

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

On recurrent reachability for continuous linear dynamical systems
door: Ouaknine, J, et al.
Gepubliceerd in: (2016)

On the skolem problem for continuous linear dynamical systems
door: Chonev, V, et al.
Gepubliceerd in: (2016)

On the Skolem Problem for continuous linear dynamical systems
door: Ouaknine, J, et al.
Gepubliceerd in: (2016)

On recurrent reachability for continuous linear dynamical systems
door: Chonev, V, et al.
Gepubliceerd in: (2016)

How to read a paper. Getting your bearings (deciding what the paper is about).
door: Greenhalgh, T
Gepubliceerd in: (1997)

Algebraic model checking for discrete linear dynamical systems
door: Luca, F, et al.
Gepubliceerd in: (2022)

Decidable Expansions of Labelled Linear Orderings
door: Alexis Bes, et al.
Gepubliceerd in: (2011-05-01)

When is containment decidable for probabilistic automata?
door: Daviaud, L, et al.
Gepubliceerd in: (2018)