The Problems of Transition Predicates Construction in Hierarchical Concurrent Controllers

The paper presents a problem of a transition predicates construction in hierarchical concurrent state oriented notation. The notation, called statechart diagrams or state machine, serves as a very convenient formalism for specification of a complex behavior of the embedded systems control unit. The controller specified in this way is discrete, deterministic and synchronous system which operates on binary values and can be implemented in programmable devices as a digital circuit. Well designed controller has conflict-free transitions and its concurrent transitions should be independent. In order to meet this requirements transition predicates must be pairwise both orthogonal and non-implicative. Computational complexities of the problems is equal to classic clique problem. The paper also suggests some statecharts syntactic structures solving these problems.