The Identity Problem for Matrix Semigroups in SL2(Z) is NP-complete
- Submitting institution
-
The University of Liverpool
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12066
- Type
- E - Conference contribution
- DOI
-
10.1137/1.9781611974782.13
- Title of conference / published proceedings
- Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms
- First page
- 187
- Volume
- 0
- 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
-
2
- Research group(s)
-
-
- Citation count
- 5
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper addresses two open problems on identity and freeness in matrix semigroups (Problems 2 and 3, Section 10.3 in Blondel and Megretski's book "Unsolved Problems in Mathematical Systems and Control Theory"). The new techniques in this paper form the foundation for a series of follow up works by Potapov that are not REF returned, including Fundam. Inform.'18, ICALP'19, and JCSS'19. The techniques have also been used by others, for example, by Jaax and Kiefer (MFCS'20) and Colcombet, Ouaknine, Semukhin, Worrell, Esbelin, Gutan (ICALP'19).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -