2001 • Journal Article
[The minimal realization problem in the max-plus semiring and Pisot's problem are NP-hard]
Authors:
Blondel, Vincent ,
Portier, N
Published in:
Comptes rendus de l'Académie des sciences - Series I - Mathematics
Volume: 333 • Number: 12 • Pages: 1127-1130
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.