The presence of a zero in an integer linear recurrent sequence is NP-hard to decide

DOI10.1016/S0024-3795(01)00466-9zbMath1007.93047MaRDI QIDQ1611897

Blondel, Vincent D., Natacha Portier

Publication date: 28 August 2002

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

zbMATH Keywords

minimal realization; NP-hard; discrete event systems; max-plus rational series; Pisot's problem

Mathematics Subject Classification ID

93C65: Discrete event control/observation systems

93B20: Minimal systems representations

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

A survey of computational complexity results in systems and control, The continuous Skolem-Pisot problem, The set of realizations of a max-plus linear sequence is semi-polyhedral, Explicit test sets for iterated morphisms in free monoids and metabelian groups, Orbits of Linear Maps and Regular Languages, Reachability in Linear Dynamical Systems, D0L sequence equivalence is inPfor fixed alphabets

Cites Work

• Suites récurrentes linéaires. Propriétés algébriques et arithmétiques. (Linear recurrent sequences. Algebraic and arithmetic properties)
• Minimal realization in the max algebra is an extended linear complementarity problem
• The set of realizations of a max-plus linear sequence is semi-polyhedral
• Zeros of Z-rational functions and DOL equivalence
• The complexity of some reachability problems for a system on a finite group
• On the boolean minimal realization problem in the max-plus algebra
• Complexity of stability and controllability of elementary hybrid systems
• Discrete-event dynamic systems: The strictly convex case
• Automata Studies. (AM-34)
• On the definition of a family of automata
• Minimal (max,+) Realization of Convex Sequences
• Methods and applications of (max,+) linear algebra
• A survey of computational complexity results in systems and control
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item