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

Blondel, Vincent;Portier, Natacha
(2001) Comptes rendus de l’Académie des sciences - Series I - Mathematics — Vol. 333, n° 12, p. 1127-1130 (2001)

Files

pdfdocument.pdf
  • Restricted Access
  • Adobe PDF
  • 68.2 KB
Request a copy

Details

Authors
  • Blondel, Vincentorcid-logoUCLouvain
    Author
  • Portier, NatachaÉcole normale supérieure de Lyon
    Author
Abstract
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Blondel, V., & Portier, N. (2001). [The minimal realization problem in the max-plus semiring and Pisot’s problem are NP-hard]. Comptes rendus de l’Académie des sciences - Series I - Mathematics, 333(12), 1127-1130. https://doi.org/10.1016/S0764-4442(01)02192-9 (Original work published 2001)