2017/11/23 by Lukas Fleischer, Fleischer, Lukas, Manfred Kufleitner +1
Computer Science · Mathematics · #F.2.2 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Geometric and Algebraic Topology #Logic, programming, and type systems #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1711.08717
Extended version of a paper accepted to STACS 2018
openalex publication_date 2017/11/23 · arxiv created 2018/02/02 · arxiv updated 2018/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the intersection problem for finite monoids, which asks for a given set of regular languages, represented by recognizing morphisms to finite monoids from a variety V, whether there exists a word contained in their intersection. Our main result is that the problem is PSPACE-complete if V is contained in DS and NP-complete if V is non-trivial and contained in DO. Our NP-algorithm for the case that V is contained in DO uses novel methods, based on compression techniques and combinatorial properties of DO. We also show that the problem is log-space reducible to the intersection problem for deterministic finite automata (DFA) and that a variant of the problem is log-space reducible to the membership problem for transformation monoids. In light of these reductions, our hardness results can be seen as a generalization of both a classical result by Kozen and a theorem by Beaudry, McKenzie and Therien.