Portal de Periódicos da CAPES

On the disjunctive set problem

1998; Elsevier BV; Volume: 204; Issue: 1-2 Linguagem: Francês

10.1016/s0304-3975(98)00034-6

1879-2294

P. Goralčík, Vácłav Koubek,

Computability, Logic, AI Algorithms

A monoid M is called syntactic if it has a disjunctive subset, the latter being defined as a part P ⊆ M 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) /oD = /oH). (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. On appelle un monoïde M syntaxique s'il admet une partie disjunctive, cette dernière étant définie comme une partie P ⊆ M qui n'est pas une réunion de classes d'une congruence sur M distincte de l'égalité. Le problème SYNTACTIC MONOID demande de décider, pour un monoïde fini M quqelconque, si oui ou non M est syntaxique. Notre contribution à ce problème est double: (1) Nous proposons un algorithme qui résout le SYNTACTIC MONOID pour une large classe de monoïdes finis en temps O(¦M¦2) (en O(¦M¦2) si /oD = /oH). (2) Nous montrons qu'une faible généralisation du SYNTACTIC MONOID est un problème NP-complet. Cela nous laisse avec le SYNTACTIC MONOID toujours ouvert, mais avec son ‘noyau dur’ mieux cerné.