Affordable Access

A more efficient notion of zigzag stability

Authors
Publication Date
Disciplines
  • Mathematics

Abstract

A more efficient notion of zigzag stability INFORMATIQUE THÉORIQUE ET APPLICATIONS B. LE SAËC I. LITOVSKY B. PATROU Amore efficient notion of zigzag stability Informatique théorique et applications, tome 30, no 3 (1996), p. 181- 194. <http://www.numdam.org/item?id=ITA_1996__30_3_181_0> © AFCET, 1996, 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 http://www.numdam.org/ Informatique théorique et Applications/Theoretical Informaties and Applications (vol. 30, n° 3, 1996, pp. 181-194) A MORE EFFICIENT NOTION OF ZIGZAG STABILITY (*) by B. LE SAËC (*), I. LITOVSKY (2) and B. PATROU C1) Communicated by J. BERSTEL Abstract. — In [6] a définition of zigzag stability for zigzag submonoids is given. We give hère a new définition of zigzag stability, which is simpler and very close to the usual définition of stability for ordinary submonoids. We give a short proof that zigzag stability is decidable in the rational case. Moreover this notion of zigzag stability enables one to obtain an algorithm to décide whether a rational language is a zigzag code. Despite being in exponential time, the complexity of this algorithm is better than that of every other known algorithm [3], [8], [6J. Résumé. - Dans [6] une première définition de stabilité zigzag pour les sous-monoïdes zigzag est donnée. Nous donnons ici une autre définition de stabilité zigzag qui est plus simple et plus proche de la définition habituelle de stabilité pour les sous-monoïdes ordinaires. Par une preuve très courte, on montre que cette stabilité zigzag est decidable dans le cas rationnel En

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