The intersection problem for finite monoids

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

Full description

Saved in:
Bibliographic Details
Main Authors: Lukas Fleischer, Manfred Kufleitner
Format: Default Conference proceeding
Published: 2018
Subjects:
Other information and computing sciences not elsewhere classified
Intersection problem
Finite monoid
Recognizing morphism
Complexity
Information and Computing Sciences not elsewhere classified
Online Access:https://hdl.handle.net/2134/31943
Tags: Add Tag
No Tags, Be the first to tag this record!

Similar Items