L'ensemble des mots minimaux d'un langage algébrique est algèbrique.

J. Berstel, L. Boasson

IBP-Litp 1994/69: Rapport de Recherche Litp / Litp research reports
19 pages - Novembre/November 1994 - French document.

PostScript : Ko /Kb

Titre / Title: L'ensemble des mots minimaux d'un langage algébrique est algèbrique.

Résumé : Soit A un alphabet fini totalement ordonné, et soit ¾ l'ordre lexicographique sur A*. Soit X une partie de A*. Le langage des mots minimaux de X est la partie de X constituée, pour chaque longueur, du mot lexicographiquement minimal de X:
Min(X) = {x OE X Ù w OE X, |w| = |x| Þ x ¾w}
Le but de cet article est de prouver que si L est un langage algébrique, alors Min(L) est un langage algébrique.

Abstract : Let A be a finite, totally ordered alphabet, and let ¾ be the lexicographical ordering on A*. Let X be a subset of A*. The language of minimal words of X is the subset of X composed of the lexicographically minimal word of X for each length:
Min(X) = {x OE X Ù w OE X, |w| = |x| Þ x ¾w}
The aim of this paper is to prove that if L is a context-free language, then the language Min(L) is context-free.

Publications internes Litp 1994 / Litp research reports 1994