In this paper a comprehensive introduction for modeling and control of networked evolutionary games （NEGs） via semi-tensor product （STP） approach is presented. First, we review the mathematical model of an NEG, wh...In this paper a comprehensive introduction for modeling and control of networked evolutionary games （NEGs） via semi-tensor product （STP） approach is presented. First, we review the mathematical model of an NEG, which consists of three ingredients： network graph, fundamental network game, and strategy updating rule. Three kinds of network graphs are considered, which are i） undirected graph for symmetric games; ii） directed graph for asymmetric games, and iii） d-directed graph for symmetric games with partial neighborhood information. Three kinds of fundamental evolutionary games （FEGs） are discussed, which are i） two strategies and symmetric （S-2）; ii） two strategies and asymmetric （A-2）; and iii） three strategies and symmetric （S-3）. Three strategy updating rules （SUR） are introduced, which are i） Unconditional Imitation （UI）; ii） Fermi Rule（FR）; iii） Myopic Best Response Adjustment Rule （MBRA）. First, we review the fundamental evolutionary equation （FEE） and use it to construct network profile dynamics （NPD）of NEGs. To show how the dynamics of an NEG can be modeled as a discrete time dynamics within an algebraic state space, the fundamental evolutionary equation （FEE） of each player is discussed. Using FEEs, the network strategy profile dynamics （NSPD） is built by providing efficient algorithms. Finally, we consider three more complicated NEGs： i） NEG with different length historical information, ii） NEG with multi-species, and iii） NEG with time-varying payoffs. In all the cases, formulas are provided to construct the corresponding NSPDs. Using these NSPDs, certain properties are explored. Examples are presented to demonstrate the model constructing method, analysis and control design technique, and to reveal certain dynamic behaviors of NEGs.展开更多
This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product, and presents a number of new results and algorithms. First, usin...This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product, and presents a number of new results and algorithms. First, using the matrix semi-tensor product, the robust graph coloring is expressed into a kind of optimization problem taking in an algebraic form of matrices, based on which an algorithm is designed to find all the most robust coloring schemes for any simple graph. Second, an equivalent problem of robust graph coloring is studied, and a necessary and sufficient condition is proposed, from which a new algorithm to find all the most robust coloring schemes is established. Third, a kind of examination timetabling is discussed by using the obtained results, and a method to design a practicable timetabling scheme is presented. Finally, the effectiveness of the results/algorithms presented in this paper is shown by two illustrative examples.展开更多
The kernel function method in support vector machine(SVM)is an excellent tool for nonlinear classification.How to design a kernel function is difficult for an SVM nonlinear classification problem,even for the polynomi...The kernel function method in support vector machine(SVM)is an excellent tool for nonlinear classification.How to design a kernel function is difficult for an SVM nonlinear classification problem,even for the polynomial kernel function.In this paper,we propose a new kind of polynomial kernel functions,called semi-tensor product kernel(STP-kernel),for an SVM nonlinear classification problem by semi-tensor product of matrix(STP)theory.We have shown the existence of the STP-kernel function and verified that it is just a polynomial kernel.In addition,we have shown the existence of the reproducing kernel Hilbert space(RKHS)associated with the STP-kernel function.Compared to the existing methods,it is much easier to construct the nonlinear feature mapping for an SVM nonlinear classification problem via an STP operator.展开更多
This paper investigates the networked evolutionary model based on snow-drift game with the strategy of rewards and penalty. Firstly, by using the semi-tensor product of matrices approach, the mathematical model of the...This paper investigates the networked evolutionary model based on snow-drift game with the strategy of rewards and penalty. Firstly, by using the semi-tensor product of matrices approach, the mathematical model of the networked evolutionary game is built. Secondly, combined with the matrix expression of logic, the mathematical model is expressed as a dynamic logical system and next converted into its evolutionary dynamic algebraic form. Thirdly, the dynamic evolution process is analyzed and the final level of cooperation is discussed. Finally, the effects of the changes in the rewarding and penalty factors on the level of cooperation in the model are studied separately, and the conclusions are verified by examples.展开更多
This paper deals with the dynamic output feedback stabilization problem of deterministic finite automata(DFA).The static form of this problem is defined and solved in previous studies via a set of equivalent condition...This paper deals with the dynamic output feedback stabilization problem of deterministic finite automata(DFA).The static form of this problem is defined and solved in previous studies via a set of equivalent conditions.In this paper,the dynamic output feedback(DOF)stabilization of DFAs is defined in which the controller is supposed to be another DFA.The DFA controller will be designed to stabilize the equilibrium point of the main DFA through a set of proposed equivalent conditions.It has been proven that the design problem of DOF stabilization is more feasible than the static output feedback(SOF)stabilization.Three simulation examples are provided to illustrate the results of this paper in more details.The first example considers an instance DFA and develops SOF and DOF controllers for it.The example explains the concepts of the DOF controller and how it will be implemented in the closed-loop DFA.In the second example,a special DFA is provided in which the DOF stabilization is feasible,whereas the SOF stabilization is not.The final example compares the feasibility performance of the SOF and DOF stabilizations through applying them to one hundred random-generated DFAs.The results reveal the superiority of the DOF stabilization.展开更多
In this paper, the solution of the matrix second semi-tensor product equation A∘lX∘lB=Cis studied. Firstly, the solvability of the matrix-vector second semi-tensor product equation is investigated. At the same time,...In this paper, the solution of the matrix second semi-tensor product equation A∘lX∘lB=Cis studied. Firstly, the solvability of the matrix-vector second semi-tensor product equation is investigated. At the same time, the compatibility conditions, the sufficient and necessary conditions and the specific solution methods for the matrix solution are given. Secondly, we further consider the solvability of the second semi-tensor product equation of the matrix. For each part, several examples are given to illustrate the validity of the results.展开更多
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 fuzz...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.展开更多
Multi-objective games(MOGs)have received much attention in recent years as a class of games with vector payoffs.Based on the semi-tensor product(STP),this paper discusses the MOG,including the existence,finite-step re...Multi-objective games(MOGs)have received much attention in recent years as a class of games with vector payoffs.Based on the semi-tensor product(STP),this paper discusses the MOG,including the existence,finite-step reachability,and finite-step controllability of Pareto equilibrium of this model,from both static and dynamic perspectives.First,the MOG concept is presented using multi-layer graphs,and STP is used to convert the payoff function into its algebraic form.Then,from the static perspective,two necessary and sufficient conditions are proposed to verify whether all players can meet their expectations and whether the strategy profile is a Pareto equilibrium,separately.Furthermore,from the dynamic perspective,a strategy updating rule is designed to investigate the finite-step reachability of the evolutionary MOG.Finally,the finite-step controllability of the evolutionary MOG is analyzed by adding pseudo-players,and a backward search algorithm is provided to find the shortest evolutionary process and control sequence.展开更多
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 ...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）.展开更多
Semi-tensor product of matrices is a generalization of conventional matrix product for the case when the two factor matrices do not meet the dimension matching condition. It was firstly proposed about ten years ago. S...Semi-tensor product of matrices is a generalization of conventional matrix product for the case when the two factor matrices do not meet the dimension matching condition. It was firstly proposed about ten years ago. Since then it has been developed and applied to several different fields. In this paper we will first give a brief introduction. Then give a survey on its applications to dynamic systems, to logic, to differential geometry, to abstract algebra, respectively.展开更多
Abstract The left semi-tensor product of matrices was proposed in [2]. In this paper the right semi-tensor product is introduced first. Some basic properties are presented and compared with those of the left semi-tens...Abstract The left semi-tensor product of matrices was proposed in [2]. In this paper the right semi-tensor product is introduced first. Some basic properties are presented and compared with those of the left semi-tensor product.Then two new applications are investigated. Firstly, its applications to connection, an important concept in differential geometry, is considered. The structure matrix and the Christoffel matrix are introduced. The transfer formulas under coordinate transformation are expressed in matrix form. Certain new results are obtained. Secondly, the structure of finite dimensional Lie algebra, etc. are investigated under the matrix expression.These applications demonstrate the usefulness of the new matrix products.展开更多
This paper proposes a new matrix product, namely, semi-tensor product. It is a general-ization of the conventional matrix product. Meanwhile, it is also closely related to Kronecker (tensor) product of matrices. The p...This paper proposes a new matrix product, namely, semi-tensor product. It is a general-ization of the conventional matrix product. Meanwhile, it is also closely related to Kronecker (tensor) product of matrices. The purpose of introducing this product is twofold: (i) treat multi-dimensional da-ta; (ii) treat nonlinear problems in a linear way. Then the computer and numerical methods can be easily used for solving nonlinear problems. Properties and formulas are deduced. As an application, the Morgan's problem for control systems is formulated as a numerically solvable problem.展开更多
Using the semi-tensor product of matrices, this paper investigates the computation of purestrategy Nash equilibrium （PNE） for fashion games, and presents several new results. First, a formal fashion game model on a ...Using the semi-tensor product of matrices, this paper investigates the computation of purestrategy Nash equilibrium （PNE） for fashion games, and presents several new results. First, a formal fashion game model on a social network is given. Second, the utility function of each player is converted into an Mgebraic form via the semi-tensor product of matrices, based on which the case of two-strategy fashion game is studied and two methods are obtained for the case to verify the existence of PNE. Third, the multi-strategy fashion game model is investigated and an algorithm is established to find all the PNEs for the general case. Finally, two kinds of optimization problems, that is, the so-called social welfare and normalized satisfaction degree optimization problems are investigated and two useful results are given. The study of several illustrative examples shows that the new results obtained in this paper are effective.展开更多
This paper investigates the observabihty of free Boolean networks by using the semi-tensor product method,and presents some new results.First,the concept of observability for free Boolean networks is proposed,based on...This paper investigates the observabihty of free Boolean networks by using the semi-tensor product method,and presents some new results.First,the concept of observability for free Boolean networks is proposed,based on which and the algebraic form of Boolean networks,a kind of observabihty matrix is constructed.Second,by the observability matrix,a new necessary and sufficient condition is given for the observability of Boolean networks.Third,the concept of observabihty index for observable Boolean networks is defined,and an algorithm is established to calculate the observability index.Finally,a practical example of D.Melanogaster segmentation polarity gene networks is studied to support our new results.The study of the illustrative example shows that the new results obtained in this paper are very effective in investigating the observability of free Boolean networks.展开更多
Boolean satisfiability (SAT) is widely used as a solver engine in electronic design automation (EDA). Typically, SAT is used to determine whether one or more groups of variables can be combined to form a true formula....Boolean satisfiability (SAT) is widely used as a solver engine in electronic design automation (EDA). Typically, SAT is used to determine whether one or more groups of variables can be combined to form a true formula. All solutions SAT (AllSAT) is a variant of the SAT problem. In the fields of formal verification and pattern generation, AllSAT is particularly useful because it efficiently enumerates all possible solutions. In this paper, a semi-tensor product (STP) based AllSAT solver is proposed. The solver can solve instances described in both the conjunctive normal form (CNF) and circuit form. The implementation of our method differs from incremental enumeration because we do not add blocking conditions for existing solutions, but rather compute the matrices to obtain all the solutions in one pass. Additionally, the logical matrices support a variety of logic operations. Results from experiments with MCNC benchmarks using CNF-based and circuit-based forms show that our method can accelerate CPU time by 8.1x (238x maximum) and 19.9x (72x maximum), respectively.展开更多
The reachability problem of synchronizing transitions bounded Petri net systems （BPNSs） is investigated in this paper by constructing a mathematical model for dynamics of BPNS. Using the semi-tensor product （STP） ...The reachability problem of synchronizing transitions bounded Petri net systems （BPNSs） is investigated in this paper by constructing a mathematical model for dynamics of BPNS. Using the semi-tensor product （STP） of matrices, the dynamics of BPNSs, which can be viewed as a combination of several small bounded subnets via synchronizing transitions, are described by an algebraic equation. When the algebraic form for its dynamics is established, we can present a necessary and sufficient condition for the reachability between any marking （or state） and initial marking. Also, we give a corresponding algorithm to calculate all of the transition paths between initial marking and any target marking. Finally, an example is shown to illustrate proposed results. The key advantage of our approach, in which the set of reachable markings of BPNSs can be expressed by the set of reachable markings of subnets such that the big reachability set of BPNSs do not need generate, is partly avoid the state explosion problem of Petri nets （PNs）.展开更多
The compatible-invariant subset of deterministic finite automata（ DFA） is investigated to solve the problem of subset stabilization under the frameworks of semi-tensor product（ STP） of matrices. The concepts of co...The compatible-invariant subset of deterministic finite automata（ DFA） is investigated to solve the problem of subset stabilization under the frameworks of semi-tensor product（ STP） of matrices. The concepts of compatibleinvariant subset and largest compatible-invariant subset are introduced inductively for Moore-type DFA,and a necessary condition for the existence of largest compatible-invariant subset is given. Meanwhile,by using the STP of matrices,a compatible feasible event matrix is defined with respect to the largest compatible-invariant subset.Based on the concept of compatible feasible event matrix,an algorithm to calculate the largest compatible-invariant subset contained in a given subset is proposed. Finally,an illustrative example is given to validate the results.展开更多
In 2011,Liu,et al.investigated the structural controllability of directed networks.They proved that the minimum number of input signals,driver nodes,can be determined by seeking a maximum matching in the directed netw...In 2011,Liu,et al.investigated the structural controllability of directed networks.They proved that the minimum number of input signals,driver nodes,can be determined by seeking a maximum matching in the directed network.Thus,the algorithm for seeking a maximum matching is the key to solving the structural controllability problem of directed networks.In this study,the authors provide algebraic expressions for matchings and maximum matchings proposed by Liu,et al.(2011)via a new matrix product called semi-tensor product,based on which the corresponding algorithms are established to seek matchings and maximum matchings in digraphs,which make determining the number of driver nodes tractable in computer.In addition,according to the proposed algorithm,the authors also construct an algorithm to distinguish critical arcs,redundant arcs and ordinary arcs of the directed network,which plays an important role in studying the robust control problem.An example of a small network from Liu’s paper is used for algorithm verification.展开更多
This paper uses the semi-tensor product(STP)of matrices and adopts algebraic methods to study the controllability,reachability,and stabilizability of extended finite state machines(EFSMs).First,we construct the biline...This paper uses the semi-tensor product(STP)of matrices and adopts algebraic methods to study the controllability,reachability,and stabilizability of extended finite state machines(EFSMs).First,we construct the bilinear dynamic system model of the EFSM,laying the foundation for further research.Second,combined with this bilinear dynamic system model,we propose theorems for the controllability,reachability,and stabilizability of the bilinear dynamic system model of the EFSM.Finally,we design an algorithm to determine the controllability and stabilizability of the EFSM.The correctness of the main results is verified through examples.展开更多
Using the semi-tensor product of matrices, this paper investigates cycles of graphs with application to cut-edges and the minimum spanning tree, and presents a number of new results and algorithms. Firstly, by definin...Using the semi-tensor product of matrices, this paper investigates cycles of graphs with application to cut-edges and the minimum spanning tree, and presents a number of new results and algorithms. Firstly, by defining a characteristic logical vector and using the matrix expression of logical functions, an algebraic description is obtained for cycles of graph, based on which a new necessary and sufficient condition is established to find all cycles for any graph. Secondly, using the necessary and sufficient condition of cycles, two algorithms are established to find all cut-edges and the minimum spanning tree, respectively. Finally, the study of an illustrative example shows that the results/algorithms presented in this paper are effective.展开更多
基金This work was partially supported by National Natural Science Foundation of China （Nos. 61273013, 61333001, 61104065, 61322307）.
文摘In this paper a comprehensive introduction for modeling and control of networked evolutionary games （NEGs） via semi-tensor product （STP） approach is presented. First, we review the mathematical model of an NEG, which consists of three ingredients： network graph, fundamental network game, and strategy updating rule. Three kinds of network graphs are considered, which are i） undirected graph for symmetric games; ii） directed graph for asymmetric games, and iii） d-directed graph for symmetric games with partial neighborhood information. Three kinds of fundamental evolutionary games （FEGs） are discussed, which are i） two strategies and symmetric （S-2）; ii） two strategies and asymmetric （A-2）; and iii） three strategies and symmetric （S-3）. Three strategy updating rules （SUR） are introduced, which are i） Unconditional Imitation （UI）; ii） Fermi Rule（FR）; iii） Myopic Best Response Adjustment Rule （MBRA）. First, we review the fundamental evolutionary equation （FEE） and use it to construct network profile dynamics （NPD）of NEGs. To show how the dynamics of an NEG can be modeled as a discrete time dynamics within an algebraic state space, the fundamental evolutionary equation （FEE） of each player is discussed. Using FEEs, the network strategy profile dynamics （NSPD） is built by providing efficient algorithms. Finally, we consider three more complicated NEGs： i） NEG with different length historical information, ii） NEG with multi-species, and iii） NEG with time-varying payoffs. In all the cases, formulas are provided to construct the corresponding NSPDs. Using these NSPDs, certain properties are explored. Examples are presented to demonstrate the model constructing method, analysis and control design technique, and to reveal certain dynamic behaviors of NEGs.
基金This work was supported by the National Natural Science Foundation of China （Nos. G61374065, G61034007, G61374002） the Fund for the Taishan Scholar Project of Shandong Province, the Natural Science Foundation of Shandong Province （No. ZR2010FM013） the Scientific Research and Development Project of Shandong Provincial Education Department （No. J11LA01 ）
文摘This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product, and presents a number of new results and algorithms. First, using the matrix semi-tensor product, the robust graph coloring is expressed into a kind of optimization problem taking in an algebraic form of matrices, based on which an algorithm is designed to find all the most robust coloring schemes for any simple graph. Second, an equivalent problem of robust graph coloring is studied, and a necessary and sufficient condition is proposed, from which a new algorithm to find all the most robust coloring schemes is established. Third, a kind of examination timetabling is discussed by using the obtained results, and a method to design a practicable timetabling scheme is presented. Finally, the effectiveness of the results/algorithms presented in this paper is shown by two illustrative examples.
基金supported by the National Natural Science Foundation of China(61573288)the Key Programs in Shaanxi Province of China(2021JZ-12)and the Yulin Science and Technology Bureau project(2019-89-2).
文摘The kernel function method in support vector machine(SVM)is an excellent tool for nonlinear classification.How to design a kernel function is difficult for an SVM nonlinear classification problem,even for the polynomial kernel function.In this paper,we propose a new kind of polynomial kernel functions,called semi-tensor product kernel(STP-kernel),for an SVM nonlinear classification problem by semi-tensor product of matrix(STP)theory.We have shown the existence of the STP-kernel function and verified that it is just a polynomial kernel.In addition,we have shown the existence of the reproducing kernel Hilbert space(RKHS)associated with the STP-kernel function.Compared to the existing methods,it is much easier to construct the nonlinear feature mapping for an SVM nonlinear classification problem via an STP operator.
文摘This paper investigates the networked evolutionary model based on snow-drift game with the strategy of rewards and penalty. Firstly, by using the semi-tensor product of matrices approach, the mathematical model of the networked evolutionary game is built. Secondly, combined with the matrix expression of logic, the mathematical model is expressed as a dynamic logical system and next converted into its evolutionary dynamic algebraic form. Thirdly, the dynamic evolution process is analyzed and the final level of cooperation is discussed. Finally, the effects of the changes in the rewarding and penalty factors on the level of cooperation in the model are studied separately, and the conclusions are verified by examples.
文摘This paper deals with the dynamic output feedback stabilization problem of deterministic finite automata(DFA).The static form of this problem is defined and solved in previous studies via a set of equivalent conditions.In this paper,the dynamic output feedback(DOF)stabilization of DFAs is defined in which the controller is supposed to be another DFA.The DFA controller will be designed to stabilize the equilibrium point of the main DFA through a set of proposed equivalent conditions.It has been proven that the design problem of DOF stabilization is more feasible than the static output feedback(SOF)stabilization.Three simulation examples are provided to illustrate the results of this paper in more details.The first example considers an instance DFA and develops SOF and DOF controllers for it.The example explains the concepts of the DOF controller and how it will be implemented in the closed-loop DFA.In the second example,a special DFA is provided in which the DOF stabilization is feasible,whereas the SOF stabilization is not.The final example compares the feasibility performance of the SOF and DOF stabilizations through applying them to one hundred random-generated DFAs.The results reveal the superiority of the DOF stabilization.
文摘In this paper, the solution of the matrix second semi-tensor product equation A∘lX∘lB=Cis studied. Firstly, the solvability of the matrix-vector second semi-tensor product equation is investigated. At the same time, the compatibility conditions, the sufficient and necessary conditions and the specific solution methods for the matrix solution are given. Secondly, we further consider the solvability of the second semi-tensor product equation of the matrix. For each part, several examples are given to illustrate the validity of the results.
基金This work was partially supported by the Natural Science Foundation of China （No. 611 74094） the Tianjin Natural Science Foundation of China （No. 13JCYBJC1 7400） the Program for New Century Excellent Talents in University of China （No. NCET-10-0506）.
文摘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.
基金Project supported by the National Natural Science Foundation of China(Nos.62273201 and 62350037)the Taishan Scholar Project of Shandong Province of China(No.TSTP20221103)。
文摘Multi-objective games(MOGs)have received much attention in recent years as a class of games with vector payoffs.Based on the semi-tensor product(STP),this paper discusses the MOG,including the existence,finite-step reachability,and finite-step controllability of Pareto equilibrium of this model,from both static and dynamic perspectives.First,the MOG concept is presented using multi-layer graphs,and STP is used to convert the payoff function into its algebraic form.Then,from the static perspective,two necessary and sufficient conditions are proposed to verify whether all players can meet their expectations and whether the strategy profile is a Pareto equilibrium,separately.Furthermore,from the dynamic perspective,a strategy updating rule is designed to investigate the finite-step reachability of the evolutionary MOG.Finally,the finite-step controllability of the evolutionary MOG is analyzed by adding pseudo-players,and a backward search algorithm is provided to find the shortest evolutionary process and control sequence.
基金Acknowledgements This work was supported by the National Natural Science Foundation of China （Grant No. 61174094）, and the Tianjin Natural Science Foundation of China under （14JCYBJC18700 and 13JCY- BJC17400）.
文摘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）.
基金Supported partly by National Natural Science Foundation of China under Grant No. 60221301 and 60334040 .Dedicated to Academician Han-Fu Chen on the occasion of his 70th birthday.
文摘Semi-tensor product of matrices is a generalization of conventional matrix product for the case when the two factor matrices do not meet the dimension matching condition. It was firstly proposed about ten years ago. Since then it has been developed and applied to several different fields. In this paper we will first give a brief introduction. Then give a survey on its applications to dynamic systems, to logic, to differential geometry, to abstract algebra, respectively.
基金Partially supported by the National Science Foundation (G.59837270)the National Key Project (G.1998020308) of China.
文摘Abstract The left semi-tensor product of matrices was proposed in [2]. In this paper the right semi-tensor product is introduced first. Some basic properties are presented and compared with those of the left semi-tensor product.Then two new applications are investigated. Firstly, its applications to connection, an important concept in differential geometry, is considered. The structure matrix and the Christoffel matrix are introduced. The transfer formulas under coordinate transformation are expressed in matrix form. Certain new results are obtained. Secondly, the structure of finite dimensional Lie algebra, etc. are investigated under the matrix expression.These applications demonstrate the usefulness of the new matrix products.
基金This work was supported by the National Natural Science Foundation of China ( Grant Nos. G69774008, G59837270) National 973 Project (Grant No. G1998020308) National Key Project of China.
文摘This paper proposes a new matrix product, namely, semi-tensor product. It is a general-ization of the conventional matrix product. Meanwhile, it is also closely related to Kronecker (tensor) product of matrices. The purpose of introducing this product is twofold: (i) treat multi-dimensional da-ta; (ii) treat nonlinear problems in a linear way. Then the computer and numerical methods can be easily used for solving nonlinear problems. Properties and formulas are deduced. As an application, the Morgan's problem for control systems is formulated as a numerically solvable problem.
基金supported by the National Natural Science Foundation of China under Grant No.61374065the Research Fund for the Taishan Scholar Project of Shandong Province
文摘Using the semi-tensor product of matrices, this paper investigates the computation of purestrategy Nash equilibrium （PNE） for fashion games, and presents several new results. First, a formal fashion game model on a social network is given. Second, the utility function of each player is converted into an Mgebraic form via the semi-tensor product of matrices, based on which the case of two-strategy fashion game is studied and two methods are obtained for the case to verify the existence of PNE. Third, the multi-strategy fashion game model is investigated and an algorithm is established to find all the PNEs for the general case. Finally, two kinds of optimization problems, that is, the so-called social welfare and normalized satisfaction degree optimization problems are investigated and two useful results are given. The study of several illustrative examples shows that the new results obtained in this paper are effective.
基金supported by the National Natural Science Foundation of China under Grant Nos.61034007,61174036,and 61374065the Research Fund for the Taishan Scholar Project of Shandong Province of China
文摘This paper investigates the observabihty of free Boolean networks by using the semi-tensor product method,and presents some new results.First,the concept of observability for free Boolean networks is proposed,based on which and the algebraic form of Boolean networks,a kind of observabihty matrix is constructed.Second,by the observability matrix,a new necessary and sufficient condition is given for the observability of Boolean networks.Third,the concept of observabihty index for observable Boolean networks is defined,and an algorithm is established to calculate the observability index.Finally,a practical example of D.Melanogaster segmentation polarity gene networks is studied to support our new results.The study of the illustrative example shows that the new results obtained in this paper are very effective in investigating the observability of free Boolean networks.
基金supported in part by the National Natural Science Foundation of China under Grant No.61871242in part by the State Key Laboratory of ASIC(Application Specific Integrated Circuit)&System of China under Grant No.2021KF008.
文摘Boolean satisfiability (SAT) is widely used as a solver engine in electronic design automation (EDA). Typically, SAT is used to determine whether one or more groups of variables can be combined to form a true formula. All solutions SAT (AllSAT) is a variant of the SAT problem. In the fields of formal verification and pattern generation, AllSAT is particularly useful because it efficiently enumerates all possible solutions. In this paper, a semi-tensor product (STP) based AllSAT solver is proposed. The solver can solve instances described in both the conjunctive normal form (CNF) and circuit form. The implementation of our method differs from incremental enumeration because we do not add blocking conditions for existing solutions, but rather compute the matrices to obtain all the solutions in one pass. Additionally, the logical matrices support a variety of logic operations. Results from experiments with MCNC benchmarks using CNF-based and circuit-based forms show that our method can accelerate CPU time by 8.1x (238x maximum) and 19.9x (72x maximum), respectively.
基金supported by the National Natural Science Foundation of China(61573199,61573200)the Tianjin Natural Science Foundation(14JCYBJC18700)
文摘The reachability problem of synchronizing transitions bounded Petri net systems （BPNSs） is investigated in this paper by constructing a mathematical model for dynamics of BPNS. Using the semi-tensor product （STP） of matrices, the dynamics of BPNSs, which can be viewed as a combination of several small bounded subnets via synchronizing transitions, are described by an algebraic equation. When the algebraic form for its dynamics is established, we can present a necessary and sufficient condition for the reachability between any marking （or state） and initial marking. Also, we give a corresponding algorithm to calculate all of the transition paths between initial marking and any target marking. Finally, an example is shown to illustrate proposed results. The key advantage of our approach, in which the set of reachable markings of BPNSs can be expressed by the set of reachable markings of subnets such that the big reachability set of BPNSs do not need generate, is partly avoid the state explosion problem of Petri nets （PNs）.
基金supported by the National Natural Science Foundation of China(61573199,61573200)
文摘The compatible-invariant subset of deterministic finite automata（ DFA） is investigated to solve the problem of subset stabilization under the frameworks of semi-tensor product（ STP） of matrices. The concepts of compatibleinvariant subset and largest compatible-invariant subset are introduced inductively for Moore-type DFA,and a necessary condition for the existence of largest compatible-invariant subset is given. Meanwhile,by using the STP of matrices,a compatible feasible event matrix is defined with respect to the largest compatible-invariant subset.Based on the concept of compatible feasible event matrix,an algorithm to calculate the largest compatible-invariant subset contained in a given subset is proposed. Finally,an illustrative example is given to validate the results.
基金supported by the National Natural Science Foundation of China under Grant Nos.61573288,12071370,U1803263,71973103Key Programs in Shaanxi Province of China under Grant No.2021JZ-12。
文摘In 2011,Liu,et al.investigated the structural controllability of directed networks.They proved that the minimum number of input signals,driver nodes,can be determined by seeking a maximum matching in the directed network.Thus,the algorithm for seeking a maximum matching is the key to solving the structural controllability problem of directed networks.In this study,the authors provide algebraic expressions for matchings and maximum matchings proposed by Liu,et al.(2011)via a new matrix product called semi-tensor product,based on which the corresponding algorithms are established to seek matchings and maximum matchings in digraphs,which make determining the number of driver nodes tractable in computer.In addition,according to the proposed algorithm,the authors also construct an algorithm to distinguish critical arcs,redundant arcs and ordinary arcs of the directed network,which plays an important role in studying the robust control problem.An example of a small network from Liu’s paper is used for algorithm verification.
基金Project supported by the National Natural Science Foundation of China(Nos.U1804150 and 62073124)。
文摘This paper uses the semi-tensor product(STP)of matrices and adopts algebraic methods to study the controllability,reachability,and stabilizability of extended finite state machines(EFSMs).First,we construct the bilinear dynamic system model of the EFSM,laying the foundation for further research.Second,combined with this bilinear dynamic system model,we propose theorems for the controllability,reachability,and stabilizability of the bilinear dynamic system model of the EFSM.Finally,we design an algorithm to determine the controllability and stabilizability of the EFSM.The correctness of the main results is verified through examples.
基金Supported by the Natural Science Foundation of Hebei Province(61203142)
文摘Using the semi-tensor product of matrices, this paper investigates cycles of graphs with application to cut-edges and the minimum spanning tree, and presents a number of new results and algorithms. Firstly, by defining a characteristic logical vector and using the matrix expression of logical functions, an algebraic description is obtained for cycles of graph, based on which a new necessary and sufficient condition is established to find all cycles for any graph. Secondly, using the necessary and sufficient condition of cycles, two algorithms are established to find all cut-edges and the minimum spanning tree, respectively. Finally, the study of an illustrative example shows that the results/algorithms presented in this paper are effective.
