Vector ambiguity and freeness problems in SL (2, Z)

DOI10.1007/978-3-319-55911-7_27MaRDI QIDQ2988836zbMATH OpenOpenAlexFDO

Authors 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

\(\mathrm{SL} (2,\mathbb {Z})\)decidabilitymatrix semigroupNP-completenessvector ambiguityvector freeness

Mathematics Subject Classification ID

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

Recommendations

• Vector Ambiguity and Freeness Problems in SL(2, ℤ)
• Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
• The identity problem for matrix semigroups in \(\mathrm{SL}_2(\mathbb{Z})\) is NP-complete
• Vector reachability problem in \(\operatorname{SL}(2,\mathbb{Z})\)
• Some decision problems on integer matrices

Cites work

• A Second Course in Formal Languages and Automata Theory
• Arithmetic Applications of the Hyperbolic Lattice Point Theorem
• Composition problems for braids
• Decidability of the membership problem for \(2\times 2\) integer matrices
• Elliptic modular forms and their applications
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 2232304 (Why is no real title available?)
• Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
• Membership Problem for the Modular Group
• Mortality for 2 2 matrices is NP-hard
• Musical intervals and special linear transformations
• Non-Euclidean visibility problems
• On finite semigroups of matrices
• On the computational complexity of matrix semigroup problems
• On the equal-subset-sum problem
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• Periodic and Infinite Traces in Matrix Semigroups
• Reachability problems in quaternion matrix and rotation semigroups
• Scalar ambiguity and freeness in matrix semigroups over bounded languages
• SL(2, Z) symmetries, supermembranes and symplectic torus bundles
• Some decision problems on integer matrices
• Stable mixing for cat maps and quasi-morphisms of the modular group
• The freeness problem over matrix semigroups and bounded languages
• The identity problem for matrix semigroups in \(\mathrm{SL}_2(\mathbb{Z})\) is NP-complete
• Two-letter group codes that preserve aperiodicity of inverse finite automata.
• Vector reachability problem in \(\operatorname{SL}(2,\mathbb{Z})\)

Cited in

(6)

• Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)
• Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
• The identity problem for matrix semigroups in \(\mathrm{SL}_2(\mathbb{Z})\) is NP-complete
• Vector reachability problem in \(\operatorname{SL}(2,\mathbb{Z})\)
• Vector Ambiguity and Freeness Problems in SL(2, ℤ)
• Relations in the semigroup of \(2\times 2\) upper-triangular matrices

This page was built for publication: Vector ambiguity and freeness problems in \(\mathrm{SL} (2,\mathbb {Z})\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988836)