Semi-tensor product approach to controllability and stabilizability of finite automata

Using semi-tensor product of matrices, the controllability and stabilizability of finite automata are investigated. By expressing the states, inputs, and outputs in vector forms, the transition and output functions are represented in matrix forms.Based on this algebraic description, a necessary and sufficient condition is proposed for checking whether a state is controllable to another one. By this condition, an algorithm is established to find all the control sequences of an arbitrary length. Moreover, the stabilizability of finite automata is considered, and a necessary and sufficient condition is presented to examine whether some states can be stabilized. Finally, the study of illustrative examples verifies the correctness of the presented results/algorithms.

Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition

This paper investigates the transition function and the reachability conditions of finite automata by using a semitensor product of matrices, which is a new powerful matrix analysis tool. The states and input symbols are first expressed in vector forms, then the transition function is described in an algebraic form. Using this algebraic representation, a sufficient and necessary condition of the reachability of any two states is proposed, based on which an algorithm is developed for discovering all the paths from one state to another. Furthermore, a mechanism is established to recognize the language acceptable by a finite automaton. Finally, illustrative examples show that the results/algorithms presented in this paper are suitable for both deterministic finite automata （DFA） and nondeterministic finite automata （NFA）.

Solving type-2 fuzzy relation equations via semi-tensor product of matrices

The problem of solving type-2 fuzzy relation equations is investigated. In order to apply semi-tensor product of matrices, a new matrix analysis method and tool, to solve type-2 fuzzy relation equations, a type-2 fuzzy relation is decomposed into two parts as principal sub-matrices and secondary sub-matrices; an r-ary symmetrical-valued type-2 fuzzy relation model and its corresponding symmetrical-valued type-2 fuzzy relation equation model are established. Then, two algorithms are developed for solving type-2 fuzzy relation equations, one of which gives a theoretical description for general type-2 fuzzy relation equations; the other one can find all the solutions to the symmetrical-valued ones. The results can improve designing type-2 fuzzy controllers, because it provides knowledge to search the optimal solutions or to find the reason if there is no solution. Finally some numerical examples verify the correctness of the results/algorithms.

Algebraic criteria for finite automata understanding of regular language

1 Introduction and main contributions Finite automata are dynamical systems with discrete inputs and outputs, which belong to the domain of logical systems and have a wide range of applications. In engineering, due to the excellent hardware qualities of simple structure, low power consumption and low electromagnetic noise, etc., finite automata are used in avionics and nuclear engineering, where the environment is bad and require strict safety. In science, finite automata serve as one of the main molding tools for discrete event dynamic systems (DEDS)(others are Petri nets, Markov chains and queuing networks, etc.). Studying DEDS is one of the major ways to study the cyber physical systems (CPS) which is the core content of Industry 4.0.

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

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.

Algebraic state space approach to model and control combined automata

A new modeling tool, algebraic state space approach to logical dynamic systems, which is developed recently based on the theory of semi-tensor product of matrices （STP）, is applied to the automata field. Using the STE this paper investigates the modeling and controlling problems of combined automata constructed in the ways of parallel, serial and feedback. By representing the states, input and output symbols in vector forms, the transition and output functions are expressed as algebraic equations of the states and inputs. Based on such algebraic descriptions, the control problems of combined automata, including output control and state control, are considered, and two necessary and sufficient conditions are presented for the controllability, by which two algorithms are established to find out all the control strings that make a combined automaton go to a target state or produce a desired output. The results are quite different from existing methods and provide a new angle and means to understand and analyze the dynamics of combined automata.

State space optimization of finite state machines from the viewpoint of control theory

Motivated by the inconvenience or even inability to explain the mathematics of the state space optimization of finite state machines(FSMs)in most existing results,we consider the problem by viewing FSMs as logical dynamic systems.Borrowing ideas from the concept of equilibrium points of dynamic systems in control theory,the concepts of t-equivalent states and t-source equivalent states are introduced.Based on the state transition dynamic equations of FSMs proposed in recent years,several mathematical formulations of t-equivalent states and t-source equivalent states are proposed.These can be analogized to the necessary and sufficient conditions of equilibrium points of dynamic systems in control theory and thus give a mathematical explanation of the optimization problem.Using these mathematical formulations,two methods are designed to find all the t-equivalent states and t-source equivalent states of FSMs.Further,two ways of reducing the state space of FSMs are found.These can be implemented without computers but with only pen and paper in a mathematical manner.In addition,an open question is raised which can further improve these methods into unattended ones.Finally,the correctness and effectiveness of the proposed methods are verified by a practical language model.