On reachability problems for low-dimensional matrix semigroups

On reachability problems for low-dimensional matrix semigroups

We consider the Membership and the Half-Space Reachability problems for matrices in dimensions two and three. Our first main result is that the Membership Problem is decidable for finitely generated sub-semigroups of the Heisenberg group over rational numbers. Furthermore, we prove two decidability...

पूर्ण विवरण

ग्रंथसूची विवरण
मुख्य लेखकों:	Colcombet, T, Ouaknine, J, Semukhin, P, Worrell, J
स्वरूप:	Conference item
प्रकाशित:	Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2019

समान संसाधन

Nonnegativity problems for matrix semigroups
द्वारा: D'Costa, J, और अन्य
प्रकाशित: (2024)

On the Relationship between Reachability Problems in Timed and Counter Automata
द्वारा: Haase, C, और अन्य
प्रकाशित: (2012)

On the relationship between reachability problems in timed and counter automata
द्वारा: Haase, C, और अन्य
प्रकाशित: (2012)

On the decidability of membership in matrix-exponential semigroups
द्वारा: Ouaknine, J, और अन्य
प्रकाशित: (2019)

Vector reachability problem in SL (2, ℤ)
द्वारा: Potapov, I, और अन्य
प्रकाशित: (2016)

Vector and scalar reachability problems in SL(2, Z)
द्वारा: Potapov, I, और अन्य
प्रकाशित: (2018)

The pseudo-reachability problem for diagonalisable linear dynamical systems
द्वारा: D'Costa, J, और अन्य
प्रकाशित: (2022)

On recurrent reachability for continuous linear dynamical systems
द्वारा: Ouaknine, J, और अन्य
प्रकाशित: (2016)

On recurrent reachability for continuous linear dynamical systems
द्वारा: Chonev, V, और अन्य
प्रकाशित: (2016)

Reachability in Succinct and Parametric One−Counter Automata
द्वारा: Haase, C, और अन्य
प्रकाशित: (2009)

Reachability in Succinct and Parametric One-Counter Automata
द्वारा: Haase, C, और अन्य
प्रकाशित: (2009)

On the decidability of reachability in linear time-invariant systems
द्वारा: Fijalkow, N, और अन्य
प्रकाशित: (2019)

On reachability for hybrid automata over bounded time
द्वारा: Brihaye, T, और अन्य
प्रकाशित: (2011)

On matrix powering in low dimensions
द्वारा: Galby, E, और अन्य
प्रकाशित: (2015)

Revisiting reachability in timed automata
द्वारा: Quaas, K, और अन्य
प्रकाशित: (2017)

On LTL model-checking for low-dimensional discrete linear dynamical systems
द्वारा: Karimov, T, और अन्य
प्रकाशित: (2020)

The 2-dimensional constraint loop problem is decidable
द्वारा: Guilmant, Q, और अन्य
प्रकाशित: (2024)

The reachability problem for two-dimensional vector addition systems with states
द्वारा: Blondin, M, और अन्य
प्रकाशित: (2021)

On affine reachability problems
द्वारा: Jaax, S, और अन्य
प्रकाशित: (2020)

On the size of finite rational matrix semigroups
द्वारा: Bumpus, G, और अन्य
प्रकाशित: (2020)

Reachability Matrix Ontology: A Cybersecurity Ontology
द्वारा: Noemi Scarpato, और अन्य
प्रकाशित: (2019-06-01)

Decision Problems for Linear Recurrence Sequences.
द्वारा: Ouaknine, J, और अन्य
प्रकाशित: (2012)

Reachability and escape problems in linear dynamical systems
द्वारा: Dcosta, J
प्रकाशित: (2024)

The Semialgebraic Orbit Problem
द्वारा: Almagor, S, और अन्य
प्रकाशित: (2019)

The polytope-collision problem
द्वारा: Almagor, S, और अन्य
प्रकाशित: (2017)

Solvability of matrix-exponential equations
द्वारा: Ouaknine, J, और अन्य
प्रकाशित: (2016)

Solvability of matrix-exponential equations
द्वारा: Ouaknine, J, और अन्य
प्रकाशित: (2016)

Solvability of matrix-exponential equations
द्वारा: Ouaknine, J, और अन्य
प्रकाशित: (2016)

Reachability problems for linear dynamical systems
द्वारा: Chonev, V
प्रकाशित: (2015)

On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
द्वारा: Bell, P, और अन्य
प्रकाशित: (2019)

On the complexity of the orbit problem
द्वारा: Chonev, V, और अन्य
प्रकाशित: (2016)

On the complexity of the orbit problem
द्वारा: Chonev, V, और अन्य
प्रकाशित: (2016)

On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond
द्वारा: Bell, PC, और अन्य
प्रकाशित: (2021)

The orbit problem in higher dimensions
द्वारा: Chonev, V, और अन्य
प्रकाशित: (2013)

Matrix transformations and generators of analytic semigroups
द्वारा: Medeghri Ahmed, और अन्य
प्रकाशित: (2006-01-01)

Deciding Reachability for 3-Dimensional Multi-Linear Systems
द्वारा: Olga Tveretina, और अन्य
प्रकाशित: (2011-06-01)

Reachability Deficits in Quantum Approximate Optimization of Graph Problems
द्वारा: V. Akshay, और अन्य
प्रकाशित: (2021-08-01)

On the skolem problem for continuous linear dynamical systems
द्वारा: Chonev, V, और अन्य
प्रकाशित: (2016)

On the Skolem Problem for continuous linear dynamical systems
द्वारा: Ouaknine, J, और अन्य
प्रकाशित: (2016)

Decision problems for second-order holonomic sequences
द्वारा: Neumann, E, और अन्य
प्रकाशित: (2021)