A matrix-based static approach to analysis of finite state machines

Abstract

Traditional matrix-based approaches in the field of finite state machines construct state transition matrices, and then use the powers of the state transition matrices to represent corresponding dynamic transition processes, which are cornerstones of system analysis. In this study, we propose a static matrix-based approach that revisits a finite state machine from its structure rather than its dynamic transition process, thus avoiding the “explosion of complexity” problem inherent in the existing approaches. Based on the static approach, we reexamine the issues of closed-loop detection and controllability for deterministic finite state machines. In addition, we propose controllable equivalent form and minimal controllable equivalent form concepts and give corresponding algorithms.

Keywords

Logical systems / Finite-valued systems / Semi-tensor product of matrices / Finite state machines / Matrix approaches

RIGHTS & PERMISSIONS

Zhejiang University Press