|
|
|
Complexity of comparing expressions in max-plus
algebra |
| Qianchuan ZHAO, |
| Department of Automation,
Tsinghua University, Beijing 100084, China; |
|
|
|
|
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
|
|
Issue Date: 05 December 2009
|
|
|
Baccelli F, Cohen G, Olsder G J, Quadrat J P. Synchronization and Linearity. Wiley, 1992
|
|
De Schutter B, De Moor B. A method to find all solutionsof a system of multivariate polynomial equalities and inequalitiesin the max algebra. Theory and Applicationof Discrete Event Dynamic Systems, 1996, 6(2): 115―138
doi: 10.1007/BF01797235
|
|
Cook S A. The complexity of theorem-proving procedures. In: Proceedings of the Third ACM Symposium on Theory of Computing. 1971, 151―158
|
|
Garey M R, Johnson D S. Computers and Intractability:A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman andCompany, 1979
|
|
McMillan K L, Dill D L. Algorithms for interfacetiming verification. In: Proceedings ofthe IEEE International Conference on Computer Design: VLSI in Computersand Processors, 1992, 48―51
|
|
Zhao Q C, Zheng D Z. On robustness of event-orderof DEDS. Acta Automatica Sinica, 1997, 23(4): 433―438 (in Chinese)
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
