The intersection problem for finite monoids

DOI10.4230/LIPICS.STACS.2018.30MaRDI QIDQ3304129zbMATH OpenOpenAlexFDO

Authors Lukas Fleischer, Manfred Kufleitner

Publication date 5 August 2020

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 176769 (Why is no real title available?)
• scientific article; zbMATH DE number 1134629 (Why is no real title available?)
• scientific article; zbMATH DE number 1944133 (Why is no real title available?)
• scientific article; zbMATH DE number 798167 (Why is no real title available?)
• Descriptional and computational complexity of finite automata -- a survey
• Domino-tiling games
• Finite-automaton aperiodicity is PSPACE-complete
• Membership testing in commutative transformation semigroups
• Membership testing in threshold one transformation monoids
• On finite monoids having only trivial subgroups
• The complexity of intersecting finite automata having few final states
• The emptiness problem for intersections of regular languages
• The membership problem in aperiodic transformation monoids

Cited in

(13)

• Restriction and intersection theorems -- the nonmonotone case
• The complexity of intersecting finite automata having few final states
• An intersection problem for finite automata
• 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
• scientific article; zbMATH DE number 5953970 (Why is no real title available?)
• 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)