On the disjunctive set problem

A monoid M is called syntactic if it has a disjunctive subset, the latter being defined as a part PCM which is not a union of classes of a non-equality congruence on M, The SYNTACTIC MONOID problem asks to decide, for an arbitrary finite monoid M, whether or not M is syntactic. Our contribution to this problem is twofold: (1) We give an algorithm solving SYNTACTIC MONOID for a large class of finite monoids in O(\M\(3)) time (in O(\M\(2)) if D = H). (2) We show that a slight generalization of SYNTACTIC MONOID is NP-complete. This leaves us with the SYNTACTIC MONOID problem still open, but with its 'hard core' better circumscribed. (C) 1998-Elsevier Science B.V. All rights reserved.