The intersection problem for finite monoids

DOI10.4230/LIPICS.STACS.2018.30zbMATH Open1487.68161arXiv1711.08717OpenAlexW2769638921MaRDI QIDQ3304129FDOQ3304129

Authors: Lukas Fleischer, Manfred Kufleitner 

Publication date: 5 August 2020

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 Therien.

Full work available at URL: https://arxiv.org/abs/1711.08717

Recommendations

• The intersection problem for finite semigroups
• The intersection problem for finite semigroups
• The complexity of intersecting finite automata having few final states
• The complexity of intersecting finite automata having few final states
• Complexity Analysis: Transformation Monoids of Finite Automata

zbMATH Keywords

complexityintersection problemfinite monoidrecognizing morphism

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• The complexity of intersecting finite automata having few final states
• On finite monoids having only trivial subgroups
• Finite-automaton aperiodicity is PSPACE-complete
• Membership testing in commutative transformation semigroups
• The membership problem in aperiodic transformation monoids
• The emptiness problem for intersections of regular languages
• Descriptional and computational complexity of finite automata -- a survey
• Title not available (Why is that?)
• Domino-tiling games
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Membership testing in threshold one transformation monoids

Cited In (13)

• Restriction and intersection theorems -- the nonmonotone case
• An intersection problem for finite automata
• The complexity of intersecting finite automata having few final states
• The complexity of intersecting finite automata having few final states
• On a transport problem and monoids of non-negative integers
• Intersection non-emptiness and hardness within polynomial time
• The intersection problem for finite semigroups
• The intersection problem for finite semigroups
• Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
• Hardness results for intersection non-emptiness
• Title not available (Why is that?)
• The intersection of \(3\)-maximal submonoids
• Deciding FO-definability of regular languages

This page was built for publication: The intersection problem for finite monoids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304129)