Complexity of comparing expressions in max-plus algebra

Front. Electr. Electron. Eng. ›› 2009, Vol. 4 ›› Issue (4) : 392 -396.

PDF (107KB)
Front. Electr. Electron. Eng. ›› 2009, Vol. 4 ›› Issue (4) : 392 -396. DOI: 10.1007/s11460-009-0055-5
Research articles
Research articles

Complexity of comparing expressions in max-plus algebra

Author information +
History +
PDF (107KB)

Abstract

Max-plus algebra has been widely used in the study of discrete-event dynamic systems. Using max-plus algebra makes it easy to specify safety constraints on events since they can be described as a set of inequalities of state variables, i.e., firing times of relevant events. This paper proves that the problem of solving max-plus inequalities in a cube (MAXINEQ) is nondeterministic polynomial-time hard (NP-hard) in strong sense and the problem of verifying max-plus inequalities (VERMAXINEQ) is co-NP. As a corollary, the problem of solving a system of multivariate max-algebraic polynomial equalities and inequalities (MPEI) is shown to be NP-hard in strong sense. The results indicate the difficulties in comparing max-plus formulas in general. Problem structures of specific systems have to be explored to enable the development of efficient algorithms.

Keywords

max-plus algebra / NP-hard / discrete event dynamic systems

Cite this article

Download citation ▾
null. Complexity of comparing expressions in max-plus algebra. Front. Electr. Electron. Eng., 2009, 4(4): 392-396 DOI:10.1007/s11460-009-0055-5

登录浏览全文

4963

注册一个新账户 忘记密码

References

AI Summary AI Mindmap
PDF (107KB)

867

Accesses

0

Citation

Detail

Sections
Recommended

AI思维导图

/