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

DOI10.1016/S0764-4442(01)02192-9zbMATH Open1016.68048MaRDI QIDQ2778041FDOQ2778041

Authors: Vincent D. Blondel, Natacha Portier 

Publication date: 13 March 2002

Published in: Comptes Rendus de l'Académie des Sciences. Série I. Mathématique (Search for Journal in Brave)

Recommendations

• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
• New NP-hard and NP-complete polynomial and integer divisibility problems
• Complexity of the Frobenius problem
• The balance problem of min-max systems is co-nNP hard
• Several NP-hard problems arising in robust stability analysis

zbMATH Keywords

NP-hardnessmax-plus semiringminimal realization problemPisot's problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Generalizations (16Y99)

Cited In (3)

• MPF problem over modified medial semigroup is NP-complete
• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
• On the boolean minimal realization problem in the max-plus algebra

This page was built for publication: The minimal realization problem in the max-plus semiring and Pisot's problem are \(NP\)-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2778041)