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

Mô tả đầy đủ

Chi tiết về thư mục
Những tác giả chính:	Karimov, T, Lefaucheux, E, Ouaknine, J, Purser, D, Varonka, A, Whiteland, MA, Worrell, J
Định dạng:	Conference item
Ngôn ngữ:	English
Được phát hành:	Association for Computing Machinery 2022

Những quyển sách tương tự

The 2-dimensional constraint loop problem is decidable
Bằng: Guilmant, Q, et al.
Được phát hành: (2024)

The Orbit Problem for parametric linear dynamical systems
Bằng: Baier, C, et al.
Được phát hành: (2021)

Deciding ω-regular properties on linear recurrence sequences
Bằng: Almagor, S, et al.
Được phát hành: (2021)

Porous invariants for linear systems
Bằng: Lefaucheux, E, et al.
Được phát hành: (2024)

Parameter synthesis for parametric probabilistic dynamical systems and prefix-independent specifications
Bằng: Baier, C, et al.
Được phát hành: (2022)

On the decidability of Presburger arithmetic expanded with powers
Bằng: Karimov, T, et al.
Được phát hành: (2025)

Porous invariants
Bằng: Lefaucheux, E, et al.
Được phát hành: (2021)

On the decidability of reachability in linear time-invariant systems
Bằng: Fijalkow, N, et al.
Được phát hành: (2019)

The pseudo-Skolem Problem is decidable
Bằng: D'Costa, J, et al.
Được phát hành: (2021)

On the decidability of monadic second-order logic with arithmetic predicates
Bằng: Berthé, V, et al.
Được phát hành: (2024)

Safety metric temporal logic is fully decidable
Bằng: Ouaknine, J, et al.
Được phát hành: (2006)

On the decidability of Metric Temporal Logic
Bằng: Ouaknine, J, et al.
Được phát hành: (2005)

O-minimal invariants for linear loops
Bằng: Almagor, S, et al.
Được phát hành: (2018)

Termination of linear loops over the integers
Bằng: Hosseini, M, et al.
Được phát hành: (2019)

ON THE DECIDABILITY AND COMPLEXITY OF METRIC TEMPORAL LOGIC OVER FINITE WORDS
Bằng: Ouaknine, J, et al.
Được phát hành: (2007)

On the decidability of membership in matrix-exponential semigroups
Bằng: Ouaknine, J, et al.
Được phát hành: (2019)

What is Decidable about Strings?
Bằng: Ganesh, Vijay, et al.
Được phát hành: (2011)

On LTL model-checking for low-dimensional discrete linear dynamical systems
Bằng: Karimov, T, et al.
Được phát hành: (2020)

On the decidability and complexity of Metric Temporal Logic over finite words
Bằng: Joel Ouaknine, et al.
Được phát hành: (2007-02-01)

On the complexity of the Escape Problem for linear dynamical systems over compact semialgebraic sets
Bằng: D'Costa, J, et al.
Được phát hành: (2021)

On positivity and minimality for second-order holonomic sequences
Bằng: Kenison, G, et al.
Được phát hành: (2021)

Bounding the escape time of a linear dynamical system over a compact semialgebraic set
Bằng: D'Costa, J, et al.
Được phát hành: (2022)

Decidability and complexity results for timed automata via channel machines
Bằng: Abdulla, P, et al.
Được phát hành: (2005)

What can you Decide about Resetable Arrays?
Bằng: Roscoe, A, et al.
Được phát hành: (2001)

How fast can you escape a compact polytope?
Bằng: D'Costa, J, et al.
Được phát hành: (2020)

What is decidable about string constraints with ReplaceAll function
Bằng: Chen, T, et al.
Được phát hành: (2017)

The pseudo-reachability problem for diagonalisable linear dynamical systems
Bằng: D'Costa, J, et al.
Được phát hành: (2022)

Decision Problems for Linear Recurrence Sequences.
Bằng: Ouaknine, J, et al.
Được phát hành: (2012)

Decidability boundaries in linear dynamical systems
Bằng: de Sousa Pinto, J
Được phát hành: (2017)

Deciding Bit−Vector Arithmetic with Abstraction
Bằng: Bryant, R, et al.
Được phát hành: (2007)

Invariants for continuous linear dynamical systems
Bằng: Kelmendi, E, et al.
Được phát hành: (2020)

On the Monniaux Problem in abstract interpretation
Bằng: Fijalkow, N, et al.
Được phát hành: (2019)

On recurrent reachability for continuous linear dynamical systems
Bằng: Ouaknine, J, et al.
Được phát hành: (2016)

On the skolem problem for continuous linear dynamical systems
Bằng: Chonev, V, et al.
Được phát hành: (2016)

On the Skolem Problem for continuous linear dynamical systems
Bằng: Ouaknine, J, et al.
Được phát hành: (2016)

On recurrent reachability for continuous linear dynamical systems
Bằng: Chonev, V, et al.
Được phát hành: (2016)

How to read a paper. Getting your bearings (deciding what the paper is about).
Bằng: Greenhalgh, T
Được phát hành: (1997)

Algebraic model checking for discrete linear dynamical systems
Bằng: Luca, F, et al.
Được phát hành: (2022)

Decidable Expansions of Labelled Linear Orderings
Bằng: Alexis Bes, et al.
Được phát hành: (2011-05-01)

When is containment decidable for probabilistic automata?
Bằng: Daviaud, L, et al.
Được phát hành: (2018)