LIPIcs-STACS-2018-30.pdf (576.83 kB)
Download file

The intersection problem for finite monoids

Download (576.83 kB)
conference contribution
posted on 22.02.2018, 11:21 by Lukas Fleischer, Manfred Kufleitner
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 Thérien.



  • Science


  • Computer Science

Published in

STACS 2018, Proceedings


FLEISCHER, L. and KUFLEITNER, M., 2018. The intersection problem for finite monoids. IN: Niedermeier, R. and Vallee, B. (eds). 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France, 28 Feb-3 Mar 2018, pp.30:1–30:14.


Schloss Dagstuhl – Leibniz Center for Informatics


VoR (Version of Record)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution 4.0 International (CC BY 4.0) licence. Full details of this licence are available at: by/4.0/

Acceptance date


Publication date



This is a conference paper. It is published under the Creative Commons Attribution 3.0 Unported Licence (CC BY). Full details of this licence are available at:





Book series

Leibniz International Proceedings in Informatics (LIPIcs);96