[The minimal realization problem in the max-plus semiring and Pisot's problem are NP-hard]

We prove the NP-hardness of two problems. The first is the well-known minimal realization problem in the max-plus semiring. The second problem (Pisot's problem) is the problem of determining if a given integer linear recurrent sequence has a zero coefficient. (C) 2001 Academie des sciences/Editions scientifiques et medicales Elsevier SAS