@article{BlondelPortier:LAA:2002,
    Abstract = {We show that the problem of determining if a given integer linear recurrent sequence has a zero---a problem that is known as ``Pisot's problem''---is NP-hard. With a similar argument we show that the problem of finding the minimal realization dimension of a one-letter max-plus rational series is NP-hard. This last result answers a folklore question raised in the control literature on the max-plus approach to discrete event systems. Our results are simple consequences of a construction due to Stockmeyer and Meyer.},
    Author = {Blondel, Vincent D. and Portier, Natacha},
    File = {The presence of a zero in an integer linear recurrent sequence is NP-hard to decide - 1-s2.0-S0024379501004669-main - a - k.pdf},
    ISSN = {0024-3795},
    Journal = {Linear Algebra and its Applications},
    Keywords = {Pisot's problem, Linear recurrent sequence, Minimal realization, Max-plus rational series},
    Note = {Fourth Special Issue on Linear Systems and Control},
    Pages = {91--98},
    Title = {The presence of a zero in an integer linear recurrent sequence is NP-hard to decide},
    URL = {http://www.sciencedirect.com/science/article/pii/S0024379501004669},
    Volume = {351--352},
    Year = {2002},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0024379501004669},
    bdsk-url-2 = {https://doi.org/10.1016/S0024-3795(01)00466-9},
    date-added = {2020-04-25 11:43:54 +0200},
    date-modified = {2021-01-18 19:07:32 +0100},
    doi = {10.1016/S0024-3795(01)00466-9}
}

@article{BlondelPortier:LAA:2002, Abstract = {We show that the problem of determining if a given integer linear recurrent sequence has a zero---a problem that is known as ``Pisot's problem''---is NP-hard. With a similar argument we show that the problem of finding the minimal realization dimension of a one-letter max-plus rational series is NP-hard. This last result answers a folklore question raised in the control literature on the max-plus approach to discrete event systems. Our results are simple consequences of a construction due to Stockmeyer and Meyer.}, Author = {Blondel, Vincent D. and Portier, Natacha}, File = {The presence of a zero in an integer linear recurrent sequence is NP-hard to decide - 1-s2.0-S0024379501004669-main - a - k.pdf}, ISSN = {0024-3795}, Journal = {Linear Algebra and its Applications}, Keywords = {Pisot's problem, Linear recurrent sequence, Minimal realization, Max-plus rational series}, Note = {Fourth Special Issue on Linear Systems and Control}, Pages = {91--98}, Title = {The presence of a zero in an integer linear recurrent sequence is NP-hard to decide}, URL = {http://www.sciencedirect.com/science/article/pii/S0024379501004669}, Volume = {351--352}, Year = {2002}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0024379501004669}, bdsk-url-2 = {https://doi.org/10.1016/S0024-3795(01)00466-9}, date-added = {2020-04-25 11:43:54 +0200}, date-modified = {2021-01-18 19:07:32 +0100}, doi = {10.1016/S0024-3795(01)00466-9} }