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

The intersection problem for finite monoids

Download (576.83 kB)
conference contribution
posted on 22.02.2018 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.

History

School

  • Science

Department

  • Computer Science

Published in

STACS 2018, Proceedings

Citation

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.

Publisher

Schloss Dagstuhl – Leibniz Center for Informatics

Version

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: http://creativecommons.org/licenses/ by/4.0/

Acceptance date

06/12/2017

Publication date

2018

Notes

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: http://creativecommons.org/licenses/by/3.0/

ISBN

9783959770620

ISSN

1868-8969

Book series

Leibniz International Proceedings in Informatics (LIPIcs);96

Language

en

Licence

Exports

Logo branding

Licence

Exports