GENERIC COMPLEXITY OF THE MEMBERSHIP PROBLEM FOR SEMIGROUPS OF INTEGER MATRICES [О ГЕНЕРИЧЕСКОЙ СЛОЖНОСТИ ПРОБЛЕМЫ ВХОЖДЕНИЯ ДЛЯ ПОЛУГРУПП ЦЕЛОЧИСЛЕННЫХ МАТРИЦ] Full article
| Journal |
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263 |
||
|---|---|---|---|
| Output data | Year: 2022, Number: 55, Pages: 95-101 Pages count : 7 DOI: 10.17223/20710410/55/7 | ||
| Tags | generic complexity; membership problem; semigroups of integer matrices | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0003 |
Abstract:
The membership problem for finitely generated subgroups (subsemigroups) of groups (semigroups) is a classical algorithmic problem, actively studied for many decades. Already for sufficiently simple groups and semigroups, this problem becomes undecidable. For example, K. A. Mikhailova in 1966 proved the undecidability of the membership problem for finitely generated subgroups (hence and for subsemigroups) of a direct product F2 × F2 of two free groups of rank 2. Since, by the well-known Sanov theorem, the group F2 has an exact representation by integer matrices of order 2, the group F2 × F2 is a subgroup of the group GL4(Z) of integer matrices of order 4. It easily implies the undecidability of this problem for the group GLk(Z) for k > 4. Undecidability of the membership problem for finitely generated subsemigroups of semigroups of integer matrices of order > 3 follows from Paterson’s result proved in 1970. In this paper, we propose a strongly generic algorithm deciding the membership problem for semigroups of integer matrices of arbitrary order for inputs from a subset whose sequence of frequencies exponentially fast converges to 1 with increasing size.
Cite:
Rybalov A.N.
GENERIC COMPLEXITY OF THE MEMBERSHIP PROBLEM FOR SEMIGROUPS OF INTEGER MATRICES [О ГЕНЕРИЧЕСКОЙ СЛОЖНОСТИ ПРОБЛЕМЫ ВХОЖДЕНИЯ ДЛЯ ПОЛУГРУПП ЦЕЛОЧИСЛЕННЫХ МАТРИЦ]
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2022. N55. P.95-101. DOI: 10.17223/20710410/55/7 WOS Scopus РИНЦ OpenAlex
GENERIC COMPLEXITY OF THE MEMBERSHIP PROBLEM FOR SEMIGROUPS OF INTEGER MATRICES [О ГЕНЕРИЧЕСКОЙ СЛОЖНОСТИ ПРОБЛЕМЫ ВХОЖДЕНИЯ ДЛЯ ПОЛУГРУПП ЦЕЛОЧИСЛЕННЫХ МАТРИЦ]
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2022. N55. P.95-101. DOI: 10.17223/20710410/55/7 WOS Scopus РИНЦ OpenAlex
Dates:
| Published online: | Mar 16, 2022 |
Identifiers:
| Web of science: | WOS:000780031400007 |
| Scopus: | 2-s2.0-85136282207 |
| Elibrary: | 48164195 |
| OpenAlex: | W4285292692 |