2018/07/15 by Özlem Salehi, Salehi, Özlem, A. C. Cem Say +2
Computer Science · Mathematics · #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Geometric and Algebraic Topology #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1807.05516
NCMA2018 Short Paper
arxiv created 2018/07/15 · openalex publication_date 2018/07/15 · arxiv updated 2018/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We make a connection between the subgroup membership and identity problems for matrix groups and extended finite automata. We provide an alternative proof for the decidability of the subgroup membership problem for 2 × 2 integer matrices. We show that the emptiness problem for extended finite automata over 4 × 4 integer matrix semigroups is undecidable. We prove that the decidability of the universe problem for extended finite automata is a sufficient condition for the decidability of the subgroup membership and identity problems.