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

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Κύριοι συγγραφείς:	Karimov, T, Lefaucheux, E, Ouaknine, J, Purser, D, Varonka, A, Whiteland, MA, Worrell, J
Μορφή:	Conference item
Γλώσσα:	English
Έκδοση:	Association for Computing Machinery 2022

Παρόμοια τεκμήρια

The 2-dimensional constraint loop problem is decidable
ανά: Guilmant, Q, κ.ά.
Έκδοση: (2024)

The Orbit Problem for parametric linear dynamical systems
ανά: Baier, C, κ.ά.
Έκδοση: (2021)

Deciding ω-regular properties on linear recurrence sequences
ανά: Almagor, S, κ.ά.
Έκδοση: (2021)

Porous invariants for linear systems
ανά: Lefaucheux, E, κ.ά.
Έκδοση: (2024)

Parameter synthesis for parametric probabilistic dynamical systems and prefix-independent specifications
ανά: Baier, C, κ.ά.
Έκδοση: (2022)

On the decidability of Presburger arithmetic expanded with powers
ανά: Karimov, T, κ.ά.
Έκδοση: (2025)

Porous invariants
ανά: Lefaucheux, E, κ.ά.
Έκδοση: (2021)

On the decidability of reachability in linear time-invariant systems
ανά: Fijalkow, N, κ.ά.
Έκδοση: (2019)

The pseudo-Skolem Problem is decidable
ανά: D'Costa, J, κ.ά.
Έκδοση: (2021)

On the decidability of monadic second-order logic with arithmetic predicates
ανά: Berthé, V, κ.ά.
Έκδοση: (2024)

Safety metric temporal logic is fully decidable
ανά: Ouaknine, J, κ.ά.
Έκδοση: (2006)

On the decidability of Metric Temporal Logic
ανά: Ouaknine, J, κ.ά.
Έκδοση: (2005)

O-minimal invariants for linear loops
ανά: Almagor, S, κ.ά.
Έκδοση: (2018)

Termination of linear loops over the integers
ανά: Hosseini, M, κ.ά.
Έκδοση: (2019)

ON THE DECIDABILITY AND COMPLEXITY OF METRIC TEMPORAL LOGIC OVER FINITE WORDS
ανά: Ouaknine, J, κ.ά.
Έκδοση: (2007)

On the decidability of membership in matrix-exponential semigroups
ανά: Ouaknine, J, κ.ά.
Έκδοση: (2019)

What is Decidable about Strings?
ανά: Ganesh, Vijay, κ.ά.
Έκδοση: (2011)

On LTL model-checking for low-dimensional discrete linear dynamical systems
ανά: Karimov, T, κ.ά.
Έκδοση: (2020)

On the decidability and complexity of Metric Temporal Logic over finite words
ανά: Joel Ouaknine, κ.ά.
Έκδοση: (2007-02-01)

On the complexity of the Escape Problem for linear dynamical systems over compact semialgebraic sets
ανά: D'Costa, J, κ.ά.
Έκδοση: (2021)

On positivity and minimality for second-order holonomic sequences
ανά: Kenison, G, κ.ά.
Έκδοση: (2021)

Bounding the escape time of a linear dynamical system over a compact semialgebraic set
ανά: D'Costa, J, κ.ά.
Έκδοση: (2022)

Decidability and complexity results for timed automata via channel machines
ανά: Abdulla, P, κ.ά.
Έκδοση: (2005)

What can you Decide about Resetable Arrays?
ανά: Roscoe, A, κ.ά.
Έκδοση: (2001)

How fast can you escape a compact polytope?
ανά: D'Costa, J, κ.ά.
Έκδοση: (2020)

What is decidable about string constraints with ReplaceAll function
ανά: Chen, T, κ.ά.
Έκδοση: (2017)

The pseudo-reachability problem for diagonalisable linear dynamical systems
ανά: D'Costa, J, κ.ά.
Έκδοση: (2022)

Decision Problems for Linear Recurrence Sequences.
ανά: Ouaknine, J, κ.ά.
Έκδοση: (2012)

Decidability boundaries in linear dynamical systems
ανά: de Sousa Pinto, J
Έκδοση: (2017)

Deciding Bit−Vector Arithmetic with Abstraction
ανά: Bryant, R, κ.ά.
Έκδοση: (2007)

Invariants for continuous linear dynamical systems
ανά: Kelmendi, E, κ.ά.
Έκδοση: (2020)

On the Monniaux Problem in abstract interpretation
ανά: Fijalkow, N, κ.ά.
Έκδοση: (2019)

On recurrent reachability for continuous linear dynamical systems
ανά: Ouaknine, J, κ.ά.
Έκδοση: (2016)

On the skolem problem for continuous linear dynamical systems
ανά: Chonev, V, κ.ά.
Έκδοση: (2016)

On the Skolem Problem for continuous linear dynamical systems
ανά: Ouaknine, J, κ.ά.
Έκδοση: (2016)

On recurrent reachability for continuous linear dynamical systems
ανά: Chonev, V, κ.ά.
Έκδοση: (2016)

How to read a paper. Getting your bearings (deciding what the paper is about).
ανά: Greenhalgh, T
Έκδοση: (1997)

Algebraic model checking for discrete linear dynamical systems
ανά: Luca, F, κ.ά.
Έκδοση: (2022)

Decidable Expansions of Labelled Linear Orderings
ανά: Alexis Bes, κ.ά.
Έκδοση: (2011-05-01)

When is containment decidable for probabilistic automata?
ανά: Daviaud, L, κ.ά.
Έκδοση: (2018)