Conference item icon

Conference item

Decidability of the membership problem for 2 x 2 integer matrices

Abstract:

The main result of this paper is the decidability of the membership problem for 2 × 2 nonsingular integer matrices. Namely, we will construct the first algorithm that for any nonsingular 2 × 2 integer matrices M1 : : : Mn and M decides whether M belongs to the semigroup generated by fM1 : : : Mng. Our algorithm relies on a translation of nu- merical problems on matrices into combinatorial problems on words. It also makes use of some algebraic properties of well-known subgroups of GL(2; Z) and...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Publisher:
ACM Publisher's website
Journal:
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms Journal website
Pages:
170-186
Series:
28th Annual ACM-SIAM Symposium on Discrete Algorithms
Host title:
SODA '17 Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
Publication date:
2017-01-01
Acceptance date:
2016-10-05
Event location:
Barcelona, Spain
Source identifiers:
834451
ISBN:
9781611974782
Pubs id:
pubs:834451
UUID:
uuid:3fc02e4a-9c58-4d0d-b167-50ae0f1d438a
Local pid:
pubs:834451
Deposit date:
2018-09-06

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP