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)