{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T23:31:50Z","timestamp":1648855910450},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:p> The intersection problem for finite semigroups asks, given a set of regular languages, represented by recognizing morphisms to finite semigroups, whether there exists a word contained in their intersection. In previous work, it was shown that is problem is [Formula: see text]-complete. We introduce compressibility measures as a useful tool to classify the complexity of the intersection problem for certain classes of finite semigroups. Using this framework, we obtain a new and simple proof that for groups and for commutative semigroups, the problem (as well as the variant where the languages are represented by finite automata) is contained in [Formula: see text]. We uncover certain structural and non-structural properties determining the complexity of the intersection problem for varieties of semigroups containing only trivial submonoids. More specifically, we prove [Formula: see text]-hardness for classes of semigroups having a property called unbounded order and for the class of all nilpotent semigroups of bounded order. On the contrary, we show that bounded order and commutativity imply decidability in poly-logarithmic time on alternating random-access Turing machines with a single alternation. We also establish connections to the monoid variant of the problem. <\/jats:p>","DOI":"10.1142\/s0129054120410075","type":"journal-article","created":{"date-parts":[[2020,11,12]],"date-time":"2020-11-12T07:54:28Z","timestamp":1605167668000},"page":"827-842","source":"Crossref","is-referenced-by-count":0,"title":["The Intersection Problem for Finite Semigroups"],"prefix":"10.1142","volume":"31","author":[{"given":"Lukas","family":"Fleischer","sequence":"first","affiliation":[{"name":"FMI, University of Stuttgart, Universit\u00e4tsstra\u00dfe 38, 70569 Stuttgart, Germany"},{"name":"School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada"}]}],"member":"219","published-online":{"date-parts":[[2020,11,11]]},"reference":[{"key":"S0129054120410075BIB001","volume-title":"Finite Semigroups and Universal Algebra","author":"Almeida J.","year":"1994"},{"key":"S0129054120410075BIB002","first-page":"409","volume-title":"STOC 1987, Proceedings","author":"Babai L.","year":"1987"},{"key":"S0129054120410075BIB003","first-page":"229","volume-title":"25th Annual Symposium on Foundations of Computer Science","author":"Babai L.","year":"1984"},{"key":"S0129054120410075BIB004","first-page":"86","volume-title":"Proc. 7th Annual Structure in Complexity Theory Conference","author":"Barrington D. A. M.","year":"1992"},{"issue":"3","key":"S0129054120410075BIB005","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"Barrington D. A. M.","year":"1990","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"S0129054120410075BIB007","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1145\/146637.146661","volume":"39","author":"Beaudry M.","year":"1992","journal-title":"J. ACM"},{"key":"S0129054120410075BIB008","series-title":"LIPIcs","first-page":"25:1","volume-title":"CCC 2018, Proceedings","volume":"102","author":"Fleischer L.","year":"2018"},{"key":"S0129054120410075BIB009","first-page":"30:1","volume-title":"STACS 2018, Proceedings","author":"Fleischer L.","year":"2018"},{"key":"S0129054120410075BIB010","first-page":"36","volume-title":"FOCS 1980, Proceedings","author":"Furst M.","year":"1980"},{"key":"S0129054120410075BIB011","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/12130.12132","volume-title":"Proc. Eighteenth Annual ACM Symposium on Theory of Computing, STOC\u201986","author":"H\u00e5stad J.","year":"1986"},{"key":"S0129054120410075BIB012","first-page":"254","volume-title":"FOCS 1977, Proceedings","author":"Kozen D.","year":"1977"},{"key":"S0129054120410075BIB013","first-page":"169","volume-title":"Proc. Conf. Computational Problems in Abstract Algebra 1967","author":"Sims C. C.","year":"1968"},{"key":"S0129054120410075BIB014","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1142\/9789812776884_0021","volume-title":"Semigroups, Algorithms, Automata and Languages 2001, Proceedings","author":"Tesson P.","year":"2002"},{"key":"S0129054120410075BIB015","first-page":"1","volume-title":"Proc. 26th Annual Symposium on Foundations of Computer Science, FOCS\u201985","author":"Yao A. C.-C.","year":"1985"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120410075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T08:58:31Z","timestamp":1605257911000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120410075"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":14,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.1142\/S0129054120410075"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120410075","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9]]}}}