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

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Karimov, T, Lefaucheux, E, Ouaknine, J, Purser, D, Varonka, A, Whiteland, MA, Worrell, J
Formáid:	Conference item
Teanga:	English
Foilsithe / Cruthaithe:	Association for Computing Machinery 2022

Míreanna comhchosúla

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

The Orbit Problem for parametric linear dynamical systems
de réir: Baier, C, et al.
Foilsithe / Cruthaithe: (2021)

Deciding ω-regular properties on linear recurrence sequences
de réir: Almagor, S, et al.
Foilsithe / Cruthaithe: (2021)

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

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

On the decidability of Presburger arithmetic expanded with powers
de réir: Karimov, T, et al.
Foilsithe / Cruthaithe: (2025)

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

On the decidability of reachability in linear time-invariant systems
de réir: Fijalkow, N, et al.
Foilsithe / Cruthaithe: (2019)

The pseudo-Skolem Problem is decidable
de réir: D'Costa, J, et al.
Foilsithe / Cruthaithe: (2021)

On the decidability of monadic second-order logic with arithmetic predicates
de réir: Berthé, V, et al.
Foilsithe / Cruthaithe: (2024)

Safety metric temporal logic is fully decidable
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2006)

On the decidability of Metric Temporal Logic
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2005)

O-minimal invariants for linear loops
de réir: Almagor, S, et al.
Foilsithe / Cruthaithe: (2018)

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

ON THE DECIDABILITY AND COMPLEXITY OF METRIC TEMPORAL LOGIC OVER FINITE WORDS
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2007)

On the decidability of membership in matrix-exponential semigroups
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2019)

What is Decidable about Strings?
de réir: Ganesh, Vijay, et al.
Foilsithe / Cruthaithe: (2011)

On LTL model-checking for low-dimensional discrete linear dynamical systems
de réir: Karimov, T, et al.
Foilsithe / Cruthaithe: (2020)

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

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)

On positivity and minimality for second-order holonomic sequences
de réir: Kenison, G, et al.
Foilsithe / Cruthaithe: (2021)

Bounding the escape time of a linear dynamical system over a compact semialgebraic set
de réir: D'Costa, J, et al.
Foilsithe / Cruthaithe: (2022)

Decidability and complexity results for timed automata via channel machines
de réir: Abdulla, P, et al.
Foilsithe / Cruthaithe: (2005)

What can you Decide about Resetable Arrays?
de réir: Roscoe, A, et al.
Foilsithe / Cruthaithe: (2001)

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

What is decidable about string constraints with ReplaceAll function
de réir: Chen, T, et al.
Foilsithe / Cruthaithe: (2017)

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

Decision Problems for Linear Recurrence Sequences.
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2012)

Decidability boundaries in linear dynamical systems
de réir: de Sousa Pinto, J
Foilsithe / Cruthaithe: (2017)

Deciding Bit−Vector Arithmetic with Abstraction
de réir: Bryant, R, et al.
Foilsithe / Cruthaithe: (2007)

Invariants for continuous linear dynamical systems
de réir: Kelmendi, E, et al.
Foilsithe / Cruthaithe: (2020)

On the Monniaux Problem in abstract interpretation
de réir: Fijalkow, N, et al.
Foilsithe / Cruthaithe: (2019)

On recurrent reachability for continuous linear dynamical systems
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2016)

On the skolem problem for continuous linear dynamical systems
de réir: Chonev, V, et al.
Foilsithe / Cruthaithe: (2016)

On the Skolem Problem for continuous linear dynamical systems
de réir: Ouaknine, J, et al.
Foilsithe / Cruthaithe: (2016)

On recurrent reachability for continuous linear dynamical systems
de réir: Chonev, V, et al.
Foilsithe / Cruthaithe: (2016)

How to read a paper. Getting your bearings (deciding what the paper is about).
de réir: Greenhalgh, T
Foilsithe / Cruthaithe: (1997)

Algebraic model checking for discrete linear dynamical systems
de réir: Luca, F, et al.
Foilsithe / Cruthaithe: (2022)

Decidable Expansions of Labelled Linear Orderings
de réir: Alexis Bes, et al.
Foilsithe / Cruthaithe: (2011-05-01)

When is containment decidable for probabilistic automata?
de réir: Daviaud, L, et al.
Foilsithe / Cruthaithe: (2018)