The possibility of developing a complete graph invariant computable in polynomial time remains an open question. Consequently, creating efficient algorithms to verify non-isomorphism, including heuristic approaches, i...The possibility of developing a complete graph invariant computable in polynomial time remains an open question. Consequently, creating efficient algorithms to verify non-isomorphism, including heuristic approaches, is essential. Effective implementation of these heuristics necessitates both the adaptation of existing graph invariants and the invention of novel ones, which continues to be a relevant challenge. Numerous current invariants are capable of distinguishing a significant number of graphs rapidly in real-time scenarios. In this study, we present an invariant tailored for tournaments, a specific class of directed graphs. Tournaments are particularly intriguing because the count of distinct tournaments for a given number of vertices aligns with that of undirected graphs of the same size. The introduced invariant evaluates all possible tournament subsets derived from the original digraph that share the identical arc set. For each subset tournament, standard rankings are computed and aggregated to produce the final vertex scores, which serve as the new invariant. Our analysis indicates that this newly proposed invariant diverges from the most straightforward tournament invariant, which typically assigns scores to each participant. Preliminary computational tests demonstrate that the minimal correlation between the sequences generated by these two invariants occurs at a vertex count of 15.展开更多
Due to limitations to extract invariant features for recognition when the aircraft presents various poses and lacks enough samples for training, a novel algorithm called Weighted Marginal Fisher Analysis with Spatiall...Due to limitations to extract invariant features for recognition when the aircraft presents various poses and lacks enough samples for training, a novel algorithm called Weighted Marginal Fisher Analysis with Spatially Smooth （WMFA-SS） for extracting invariant features in aircraft rec- ognition is proposed. According to the Graph Embedding （GE） framework, Heat Kernel function is firstly introduced to characterize the interclass separability when choosing the weights of penalty graph. Furthermore, Laplacian penalty is applied to constraining the coefficients to be spatially smooth in this algorithm. Laplacian penalty is able to incorporate the prior information that neigh- boring pixels are correlated. Besides, using a Laplacian penalty can also avoid the singularity of Laplacian matrix of intrinsic graph. Once compact representations of the images are obtained, it can be considered as invariant features and then be performed in classification to recognize different patterns of aircraft. Real aircraft recognition experiments show the superiority of our proposed WMFA-SS in comparison to other GE algorithms and the current aircraft recognition algorithm; the accuracy rate of our proposed method is 90.00% for dataset BH-AIR1.0 and 99.25% for dataset BH-AIR2.0.展开更多
In this exposition, we show that the Hamiltonian is always constant on a compact invariant connected subset which lies in a Lagrangian graph provided that the Hamiltonian and the graph are sufficiently smooth. We also...In this exposition, we show that the Hamiltonian is always constant on a compact invariant connected subset which lies in a Lagrangian graph provided that the Hamiltonian and the graph are sufficiently smooth. We also provide some counterexamples to show that if the Hamiltonian function is not smooth enough, then it may be non-constant on a compact invariant connected subset which lies in a Lagrangian graph.展开更多
Observability is a fundamental property of a partially observed dynamical system,which means whether one can use an input sequence and the corresponding output sequence to determine the initial state.Observability pro...Observability is a fundamental property of a partially observed dynamical system,which means whether one can use an input sequence and the corresponding output sequence to determine the initial state.Observability provides bases for many related problems,such as state estimation,identification,disturbance decoupling,controller synthesis,etc.Until now,fundamental improvement has been obtained in observability of Boolean control networks(BCNs)mainly based on two methods-Edward F.Moore's partition and our observability graph or their equivalent representations found later based on the semitensor product(STP)of matrices(where the STP was proposed by Daizhan Cheng),including necessary and sufficient conditions for different types of observability,extensions to probabilistic Boolean networks(PBNs)and singular BCNs,even to nondeterministic finite-transition systems(NFTSs);and the development(with the help of the STP of matrices)in related topics,such as com-putation of smallest invariant dual subspaces of BNs containing a set of Boolean functions,multiple-experiment observability verification/decomposition in BCNs,disturbance decoupling in BCNs,etc.This paper provides a thorough survey for these topics.The contents of the paper are guided by the above two methods.First,we show that Moore's partition-based method closely relates the following problems:computation of smallest invariant dual subspaces of BNs,multiple-experiment observ-ability verification/decomposition in BCNs,and disturbance decoupling in BCNs.However,this method does not apply to other types of observability or nondeterministic systems.Second,we show that based on our observability graph,four different types of observability have been verified in BCNs,verification results have also been extended to PBNs,singular BCNs,and NFTSs.In addition,Moore's partition also shows similarities between BCNs and linear time-invariant(LTI)control systems,e.g.,smallest invariant dual subspaces of BNs containing a set of Boolean functions in BCNs vs unobservable subspaces 展开更多
文摘The possibility of developing a complete graph invariant computable in polynomial time remains an open question. Consequently, creating efficient algorithms to verify non-isomorphism, including heuristic approaches, is essential. Effective implementation of these heuristics necessitates both the adaptation of existing graph invariants and the invention of novel ones, which continues to be a relevant challenge. Numerous current invariants are capable of distinguishing a significant number of graphs rapidly in real-time scenarios. In this study, we present an invariant tailored for tournaments, a specific class of directed graphs. Tournaments are particularly intriguing because the count of distinct tournaments for a given number of vertices aligns with that of undirected graphs of the same size. The introduced invariant evaluates all possible tournament subsets derived from the original digraph that share the identical arc set. For each subset tournament, standard rankings are computed and aggregated to produce the final vertex scores, which serve as the new invariant. Our analysis indicates that this newly proposed invariant diverges from the most straightforward tournament invariant, which typically assigns scores to each participant. Preliminary computational tests demonstrate that the minimal correlation between the sequences generated by these two invariants occurs at a vertex count of 15.
基金co-supported by the National Key Scientific Instrument and Equipment Development Project (No.2012YQ140032)
文摘Due to limitations to extract invariant features for recognition when the aircraft presents various poses and lacks enough samples for training, a novel algorithm called Weighted Marginal Fisher Analysis with Spatially Smooth （WMFA-SS） for extracting invariant features in aircraft rec- ognition is proposed. According to the Graph Embedding （GE） framework, Heat Kernel function is firstly introduced to characterize the interclass separability when choosing the weights of penalty graph. Furthermore, Laplacian penalty is applied to constraining the coefficients to be spatially smooth in this algorithm. Laplacian penalty is able to incorporate the prior information that neigh- boring pixels are correlated. Besides, using a Laplacian penalty can also avoid the singularity of Laplacian matrix of intrinsic graph. Once compact representations of the images are obtained, it can be considered as invariant features and then be performed in classification to recognize different patterns of aircraft. Real aircraft recognition experiments show the superiority of our proposed WMFA-SS in comparison to other GE algorithms and the current aircraft recognition algorithm; the accuracy rate of our proposed method is 90.00% for dataset BH-AIR1.0 and 99.25% for dataset BH-AIR2.0.
基金supported by National Natural Science Foundation of China (Grant No. 10801071)research fellowship for postdoctoral researchers from Alexander von Humboldt Foundation
文摘In this exposition, we show that the Hamiltonian is always constant on a compact invariant connected subset which lies in a Lagrangian graph provided that the Hamiltonian and the graph are sufficiently smooth. We also provide some counterexamples to show that if the Hamiltonian function is not smooth enough, then it may be non-constant on a compact invariant connected subset which lies in a Lagrangian graph.
文摘Observability is a fundamental property of a partially observed dynamical system,which means whether one can use an input sequence and the corresponding output sequence to determine the initial state.Observability provides bases for many related problems,such as state estimation,identification,disturbance decoupling,controller synthesis,etc.Until now,fundamental improvement has been obtained in observability of Boolean control networks(BCNs)mainly based on two methods-Edward F.Moore's partition and our observability graph or their equivalent representations found later based on the semitensor product(STP)of matrices(where the STP was proposed by Daizhan Cheng),including necessary and sufficient conditions for different types of observability,extensions to probabilistic Boolean networks(PBNs)and singular BCNs,even to nondeterministic finite-transition systems(NFTSs);and the development(with the help of the STP of matrices)in related topics,such as com-putation of smallest invariant dual subspaces of BNs containing a set of Boolean functions,multiple-experiment observability verification/decomposition in BCNs,disturbance decoupling in BCNs,etc.This paper provides a thorough survey for these topics.The contents of the paper are guided by the above two methods.First,we show that Moore's partition-based method closely relates the following problems:computation of smallest invariant dual subspaces of BNs,multiple-experiment observ-ability verification/decomposition in BCNs,and disturbance decoupling in BCNs.However,this method does not apply to other types of observability or nondeterministic systems.Second,we show that based on our observability graph,four different types of observability have been verified in BCNs,verification results have also been extended to PBNs,singular BCNs,and NFTSs.In addition,Moore's partition also shows similarities between BCNs and linear time-invariant(LTI)control systems,e.g.,smallest invariant dual subspaces of BNs containing a set of Boolean functions in BCNs vs unobservable subspaces
