Decidability of the membership problem for 2 × 2 integer matrices
- Submitting institution
-
The University of Liverpool
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12034
- Type
- E - Conference contribution
- DOI
-
10.1137/1.9781611974782.12
- Title of conference / published proceedings
- Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms
- First page
- 170
- Volume
- 2017
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- January
- Year of publication
- 2017
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
-
- Citation count
- 7
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- As noted by AMS fellow John Stillwell in "Elements of Mathematics: From Euclid to Goedel, 2018", "noncommutative semigroups are hard to understand". The membership decidability proof for nonsingular integer 2×2 matrix semigroup in this paper is the first significant result on noncommutative matrices since the work of Babai (SODA'96) and Gurevich and Schupp (SIAM J. Comput. 2007). This result was characterised by Hrushovski, Ouaknine, Pouly, and Worrell (LICS'18) as a breakthrough in the field. It was used by the authors to prove further decidability results (ISSAC'20), not REF returned.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -