Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)

DOI10.1016/j.jcss.2018.09.003zbMath1421.68095OpenAlexW2890141802MaRDI QIDQ1740664

Pavel Semukhin, Igor Potapov

Publication date: 2 May 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2018.09.003

zbMATH Keywords

linear fractional transformationspecial linear groupautomata and formal languagesmatrix semigroupscalar reachability problemvector reachability problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Algebraic systems of matrices (15A30)

Related Items

On Reachability Problems for Low-Dimensional Matrix Semigroups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• SL(2, Z) symmetries, supermembranes and symplectic torus bundles
• Reachability problems in quaternion matrix and rotation semigroups
• Non-Euclidean visibility problems
• The freeness problem over matrix semigroups and bounded languages
• On undecidability bounds for matrix decision problems
• On the decidability of semigroup freeness
• Mortality for 2 ×2 Matrices Is NP-Hard
• Composition Problems for Braids
• Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$
• Elliptic Modular Forms and Their Applications
• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• Musical intervals and special linear transformations
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Decidability of the Membership Problem for 2 × 2 integer matrices
• The Identity Problem for Matrix Semigroups in SL₂(ℤ) is NP-complete
• Stable mixing for cat maps and quasi-morphisms of the modular group
• Some decision problems on integer matrices
• Arithmetic Applications of the Hyperbolic Lattice Point Theorem
• On the Positivity Problem for Simple Linear Recurrence Sequences,
• Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences
• Mathematical Foundations of Computer Science 2004
• Decidable and Undecidable Problems about Quantum Automata
• On Termination of Integer Linear Loops
• Membership Problem for the Modular Group