3 citations · 8 across the 9 of their papers we have counts for
5 papers · 1 filter
On the Complexity of Properties of Transformation Semigroups
Lukas Fleischer, Trevor Jack
We investigate the computational complexity for determining various properties of a finite transformation semigroup given by generators. We introduce a simple framework to describe…
Efficient Membership Testing for Pseudovarieties of Finite Semigroups
Lukas Fleischer
We consider the complexity of deciding membership of a given finite semigroup to a fixed pseudovariety. While it is known that there exist pseudovarieties with NP-complete or even…
The Intersection Problem for Finite Semigroups
Lukas Fleischer
We investigate the intersection problem for finite semigroups, which asks for a given set of regular languages, represented by recognizing morphisms to finite semigroups, whether t…
Testing Simon's congruence
Lukas Fleischer, Manfred Kufleitner
Piecewise testable languages are a subclass of the regular languages. There are many equivalent ways of defining them; Simon's congruence is one of the most classical appr…
On the Complexity of the Cayley Semigroup Membership Problem
Lukas Fleischer
We investigate the complexity of deciding, given a multiplication table representing a semigroup S, a subset X of S and an element t of S, whether t can be expressed as a product o…