STP Approach to Controlled Automata and Applications to DEDS

What is it about?

Discrete event dynamic system (DEDS) is a typical system which can be modelled by a discrete mathematic structure. We introduces the STP, a new powerful matrix analysis tool, into the field of DEDS and models the controlled automata as an algebraic expression of the states, events and control specification. Using such algebraic representation, a necessary and sufficient condition of reachability between any two states of controlled automata is obtained. Based on the condition, an algorithm is established to find all the event strings which can move the controlled automata to one reachable state from another one. Moreover, these results are also suitable to analyze the corresponding problems of finite automata after simply modified, including deterministic finite automaton (DFA) and nondeterministic finite automaton (NFA).

Featured Image

Why is it important?

A new mathematical formulation has been established to deal with the modelling problem of controlled automata and a set of new theoretical results and algorithms have been presented under this formulation. Compared with the existing results on the problems, our method has the following advantages. By our method, the reachability problem of controlled automata can be exactly expressed in an algebraic form of matrices, which is quite different from the existing results. According to our method, to check/determine whether a state is reachable, one only needs to compute a kind of state transition matrix, with which the conclusion can be easily obtained.

Perspectives