On the Identity Problem for Unitriangular Matrices of Dimension Four
| Autor: | Dong, Ruiwen |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Symbolic Computation Discrete Mathematics (cs.DM) matrix semigroups Computing methodologies → Symbolic and algebraic manipulation Symbolic Computation (cs.SC) identity problem unitriangular matrices Computer Science::Information Theory Computer Science - Discrete Mathematics |
| DOI: | 10.4230/lipics.mfcs.2022.43 |
| Popis: | We show that the Identity Problem is decidable in polynomial time for finitely generated sub-semigroups of the group $\mathsf{UT}(4, \mathbb{Z})$ of $4 \times 4$ unitriangular integer matrices. As a byproduct of our proof, we also show the polynomial-time decidability of several subset reachability problems in $\mathsf{UT}(4, \mathbb{Z})$. 28 pages, 2 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|