Vector Ambiguity and Freeness Problems in SL $$(2,\mathbb {Z})$$

DOI10.1007/978-3-319-55911-7_27zbMath1485.68111OpenAlexW2602284167MaRDI QIDQ2988836

Sang-Ki Ko, Igor Potapov

Publication date: 19 May 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-55911-7_27

zbMATH Keywords

NP-completenessdecidabilitymatrix semigroup\(\mathrm{SL} (2,\mathbb {Z})\)vector ambiguityvector freeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Free semigroups, generators and relations, word problems (20M05) Algebraic systems of matrices (15A30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Relations in the semigroup of 2 × 2 upper-triangular matrices

Cites Work

• 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
• On the equal-subset-sum problem
• On finite semigroups of matrices
• The freeness problem over matrix semigroups and bounded languages
• Two-letter group codes that preserve aperiodicity of inverse finite automata.
• Scalar Ambiguity and Freeness in Matrix Semigroups over Bounded Languages
• 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
• Musical intervals and special linear transformations
• A Second Course in Formal Languages and Automata Theory
• 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
• Vector Reachability Problem in SL(2, Z)
• 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
• Membership Problem for the Modular Group
• Periodic and Infinite Traces in Matrix Semigroups
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS

This page was built for publication: Vector Ambiguity and Freeness Problems in SL $$(2,\mathbb {Z})$$