Natacha Portier
Section de mathématique
Université de Liège
ALAPEDES meeting
March 31, 1999
L. J. Meyer and A. R. Stockmeyer proved in 1973 that deciding if a rational expression over a unary alphabet is defining the all language is NP-hard. A consequence of this theorem is the NP-hardness of the following problems: Are there paths of all lengths between two given vertices of a finite directed graph? Are two one-letter rational series in a max-plus algebra different? Is a one-letter rational series in a max-plus algebra equivalent to a rational series of dimension 1? From this last result we infer that the minimal realization problem in max-plus algebra is NP-hard.