Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.30
URN: urn:nbn:de:0030-drops-85079
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8507/
Fleischer, Lukas ; Kufleitner, Manfred
The Intersection Problem for Finite Monoids
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{fleischer_et_al:LIPIcs:2018:8507,
author = {Lukas Fleischer and Manfred Kufleitner},
title = {{The Intersection Problem for Finite Monoids}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {30:1--30:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-062-0},
ISSN = {1868-8969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8507},
URN = {urn:nbn:de:0030-drops-85079},
doi = {10.4230/LIPIcs.STACS.2018.30},
annote = {Keywords: intersection problem, finite monoid, recognizing morphism, complexity}
}
| Keywords: | intersection problem, finite monoid, recognizing morphism, complexity | |
| Seminar: | 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 27.02.2018 |
