Research articles

Complexity of comparing expressions in max-plus algebra

Expand
  • Department of Automation, Tsinghua University, Beijing 100084, China;

Published date: 05 Dec 2009

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.

Cite this article

Qianchuan ZHAO, . Complexity of comparing expressions in max-plus algebra[J]. Frontiers of Electrical and Electronic Engineering, 2009 , 4(4) : 392 -396 . DOI: 10.1007/s11460-009-0055-5

Outlines

/