scientific article; zbMATH DE number 7204378

DOI10.4230/LIPIcs.MFCS.2017.44zbMath1441.20037MaRDI QIDQ5111259

Igor Potapov, Pavel Semukhin

Publication date: 26 May 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

automatasingular matricesmembership problemgeneral linear groupformal languagesmatrix semigroups

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Linear algebraic groups over finite fields (20G40) Semigroups of transformations, relations, partitions, etc. (20M20) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Algebraic systems of matrices (15A30) Matrices of integers (15B36)

Related Items (7)

Reachability Problems for One-Dimensional Piecewise Affine Maps ⋮ Solving the membership problem for parabolic Möbius monoids ⋮ The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\) ⋮ On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond ⋮ On Reachability Problems for Low-Dimensional Matrix Semigroups ⋮ On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Post correspondence problem for short words
• On undecidability bounds for matrix decision problems
• Mortality for 2 ×2 Matrices Is NP-Hard
• ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS
• Polynomial-time algorithm for the orbit problem
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Decidability of the Membership Problem for 2 × 2 integer matrices
• The Identity Problem for Matrix Semigroups in SL₂(ℤ) is NP-complete
• Vector Reachability Problem in SL(2, Z)
• Some decision problems on integer matrices
• On the Positivity Problem for Simple Linear Recurrence Sequences,
• Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences
• Mathematical Foundations of Computer Science 2004
• Decidable and Undecidable Problems about Quantum Automata
• On Termination of Integer Linear Loops
• Membership Problem for the Modular Group
• Mortality Problem for 2×2 Integer Matrices
• Unsolvability in 3 × 3 Matrices

This page was built for publication: