The balance problem of min-max systems is co-nNP hard

DOI10.1016/j.sysconle.2004.05.009zbMath1157.93445OpenAlexW2037055460MaRDI QIDQ2503672

Ke Yang, Qian-Chuan Zhao

Publication date: 21 September 2006

Published in: Systems \& Control Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.sysconle.2004.05.009

zbMATH Keywords

Discrete event systemsmin-max systemsCycle timeco-NP hardMonotone Boolean functionsBalance condition

Mathematics Subject Classification ID

Discrete event control/observation systems (93C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

A unified approach to nonlinear Perron-Frobenius theory ⋮ A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors ⋮ Ergodicity conditions for zero-sum games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Eigenvalues of dynamic max-min systems
• Minimax algebra
• Min-max functions
• Conditions for the structural existence of an eigenvalue of a bipartite \((\min,\max,+)\)-system.
• Analytic expansions of max-plus Lyapunov exponents.
• The duality theorem for min-max functions
• Structure properties of min-max systems and existence of global cycle time
• The Perron-Frobenius theorem for homogeneous, monotone functions
• A constructive fixed point theorem for min-max functions
• A Remark on Inseparability of Min–Max Systems

This page was built for publication: The balance problem of min-max systems is co-nNP hard