Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$

DOI10.1007/978-3-319-51963-0_21zbMath1444.20034arXiv1610.09834OpenAlexW2569236261MaRDI QIDQ2971140

Sang-Ki Ko, Igor Potapov

Publication date: 4 April 2017

Published in: SOFSEM 2017: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.09834

zbMATH Keywords

computational complexitydecision problemsdecidabilityfreenessmatrix semigroups

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Vector Ambiguity and Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\) ⋮ Freeness Problem for Matrix Semigroups of Parikh Matrices

Cites Work

• 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
• On the equal-subset-sum problem
• On finite semigroups of matrices
• The freeness problem over matrix semigroups and bounded languages
• On the problem of freeness of multiplicative matrix semigroups
• On the decidability of semigroup freeness
• Mortality for 2 ×2 Matrices Is NP-Hard
• Composition Problems for Braids
• Elliptic Modular Forms and Their Applications
• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS
• Musical intervals and special linear transformations
• A Second Course in Formal Languages and Automata Theory
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• 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
• Membership Problem for the Modular Group
• Periodic and Infinite Traces in Matrix Semigroups
• Developments in Language Theory
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS

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