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

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

Natacha Portier, Blondel, Vincent D.

Publication date: 28 August 2002

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

Full work available at URL: https://doi.org/10.1016/s0024-3795(01)00466-9

zbMATH Keywords

minimal realizationNP-harddiscrete event systemsmax-plus rational seriesPisot's problem

Mathematics Subject Classification ID

Discrete event control/observation systems (93C65) Minimal systems representations (93B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Effective results on the Skolem problem for linear recurrence sequences, Minimal positive realizations: A survey, Compound matrices in systems and control theory: a tutorial, Analyzing ultimate positivity for solvable systems, Reachability in Linear Dynamical Systems, Decision Questions for Probabilistic Automata on Small Alphabets, D0L sequence equivalence is inPfor fixed alphabets, On recurrences converging to the wrong limit in finite precision and some new examples, Unnamed Item, Orbits of Linear Maps and Regular Languages, Scalable control of positive systems, A survey of computational complexity results in systems and control, Explicit test sets for iterated morphisms in free monoids and metabelian groups, The continuous Skolem-Pisot problem, The set of realizations of a max-plus linear sequence is semi-polyhedral, On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond, Semicomputable points in Euclidean spaces, On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond, Variation diminishing linear time-invariant systems, Complexity of Restricted Variants of Skolem and Related Problems, On the multiplicities of Padovan-type sequences, On Second-Order Cone Positive Systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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