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
Version:
Accepted Manuscript

Actions


Access Document


Files:

Authors


Potapov, I More by this author
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Publisher:
ACM Publisher's website
Pages:
170-186
Series:
28th Annual ACM-SIAM Symposium on Discrete Algorithms
Publication date:
2017
Acceptance date:
2016-10-05
Pubs id:
pubs:834451
URN:
uri:3fc02e4a-9c58-4d0d-b167-50ae0f1d438a
UUID:
uuid:3fc02e4a-9c58-4d0d-b167-50ae0f1d438a
Local pid:
pubs:834451
ISBN:
9781611974782

Terms of use


Metrics



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

TO TOP