Affordable Access

Elementariness of a finite set of words is co-NP-complete

Publication Date
  • Law


Elementariness of a finite set of words is co-NP-complete INFORMATIQUE THÉORIQUE ET APPLICATIONS JEANNERAUD Elementariness of a finite set of words is co-NP-complete Informatique théorique et applications, tome 24, no 5 (1990), p. 459- 470. <> © AFCET, 1990, tous droits réservés. L’accès aux archives de la revue « Informatique théorique et applications » im- plique l’accord avec les conditions générales d’utilisation (http://www.numdam. org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques Informatique théorique et Applications/Theoretical Informaties and Applications (vol. 24, n° 5, 1990, p. 459 à 470) ELEMENTARINESS OF A FINITE SET OF WORDS IS co-NP-COMPLETE (*) by Jean NERAUD (*) Communicated by J.-E. PIN Abstract. - We defîne the rank of a finite set of words X as the integer: r(X) = min{\Y\:X£Y*\. X is said elementary iff r{X) = \X\ oiherwise X is said simplifiable. We show that deciding whether X is simplifiable and deciding whether r (X) is not greater than a given integer are NP-complete and we consider different related problems. Résumé. - On définit le rang d'un ensemble fini de mots X comme l'entier r(X) = mm{\ Y\:X^ Y*}. X est dit élémentaire ssi r(X) = \X\, sinon X est dit simplifiable. On montre que décider si X est simplifiable et décider si r {X) est majoré par un entier donné sont des problèmes NP-complets, et on examine différents problèmes associés. 1. INTRODUCTION A finite set of words X in a free monoid is simplifiable if there exists another set of words Y of smaller cardinality such that every word of X can be factorized into words of Y, i. e. such that X is included in the submonoid Y* generated by Y. Otherwise X is elementary

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times

More articles like this

The set of minimal braids is co-NP-complete

on Journal of Algorithms Jan 01, 1991

Comparing reductions to NP-complete sets

on Information and Computation Jan 01, 2007

Feedback arc set in bipartite tournaments is NP-co...

on Information Processing Letters Jan 01, 2007

PNP[ O(log n)]and sparse turing-complete sets for...

on Journal of Computer and System... Jan 01, 1989
More articles like this..