The theory of the concept lattice is an efficient tool for knowledge representation and knowledge discovery, and is applied to many fields successfully. One focus of knowledge discovery is knowledge reduction. This pa...The theory of the concept lattice is an efficient tool for knowledge representation and knowledge discovery, and is applied to many fields successfully. One focus of knowledge discovery is knowledge reduction. This paper proposes the theory of attribute reduction in the concept lattice, which extends the theory of the concept lattice. In this paper, the judgment theorems of consistent sets are examined, and the discernibility matrix of a formal context is introduced, by which we present an approach to attribute reduction in the concept lattice. The characteristics of three types of attributes are analyzed.展开更多
The theory of concept lattices is an efficient tool for knowledge representation and knowledge discovery, and is applied to many fields successfully. One focus of knowledge discovery is knowledge reduction. Based on t...The theory of concept lattices is an efficient tool for knowledge representation and knowledge discovery, and is applied to many fields successfully. One focus of knowledge discovery is knowledge reduction. Based on the reduction theory of classical formal context, this paper proposes the definition of decision formal context and its reduction theory, which extends the reduction theory of concept lattices. In this paper, strong consistence and weak consistence of decision formal context are defined respectively. For strongly consistent decision formal context, the judgment theorems of consistent sets are examined, and approaches to reduction are given. For weakly consistent decision formal context, implication mapping is defined, and its reduction is studied. Finally, the relation between reducts of weakly consistent decision formal context and reducts of implication mapping is discussed.展开更多
The loop invariants take a very important role in the design,proof and derivation of the algorithmic program.We point out the limitations of the traditional standard strategy for developing loop invariants, and propos...The loop invariants take a very important role in the design,proof and derivation of the algorithmic program.We point out the limitations of the traditional standard strategy for developing loop invariants, and propose two new strategies for proving the existing algorithmic program and developing new ones. The strategies use recurrence as vehicle and integrate some effective methods of designing algorithms, e.g.Dynamic Programming,Greedy and Divide Conquer,into the recurrence relation of problem solving sequence.This lets us get straightforward an approach for solving a variety of complicated prob- lems,and makes the standard proof and formal derivation of their algorithmic programs possible.We show the method and advantages of applying the strategies with several typical nontrivial examples.展开更多
Automatic discovery and composition of Web services is an important research area in Web service technology, in which the specification of Web services is a key issue. This paper presents a Web service capability desc...Automatic discovery and composition of Web services is an important research area in Web service technology, in which the specification of Web services is a key issue. This paper presents a Web service capability description framework based on the environment ontology. This framework depicts Web services capability in two aspects： the operable environment and the environment changes resulting from behaviors of the Web service. On the basis of the framework, a requirement-driven Web service composition model has been constructed. This paper brings forward the formalization of Web service interactions with π calculus. And an automatic mechanism converting conceptual capability description to the formal process expression has been built. This kind of formal specification assists in verifying whether the composite Web service model matches the requirement.展开更多
Cellular automata are the discrete dynamical systems of simple construction but with complex and varied behaviors.In this paper,the elementary cellular automaton of rule 22 is studied by the tools of formal language t...Cellular automata are the discrete dynamical systems of simple construction but with complex and varied behaviors.In this paper,the elementary cellular automaton of rule 22 is studied by the tools of formal language theory and symbolic dynamics.Its temporal evolution orbits are coarse grained into evolution sequences and the evolution languages are defined.It is proved that for every n ≥2 its width n evolution language is not regular.展开更多
In this paper, the fluid flow differential equation based on the homogenous reservoirs model is first reviewed. Then a theorem about the formal similarity of solutions in the Laplace space with outer boundary conditio...In this paper, the fluid flow differential equation based on the homogenous reservoirs model is first reviewed. Then a theorem about the formal similarity of solutions in the Laplace space with outer boundary conditions and inner boundary condition is presented and proved. Lastly, a corollary of our theorem is given particularly on inner boundary. The obtained results are very helpful for understanding inherent laws of relevant engineering science and designing practical analysis software.展开更多
A great disturbance was raised by the report of Elkan entitled 'The Paradoxical Success of Fuzzy Logic' at the llth Annual Conference on Artificial Intelligence held in the United States in July, 1993. 15 famo...A great disturbance was raised by the report of Elkan entitled 'The Paradoxical Success of Fuzzy Logic' at the llth Annual Conference on Artificial Intelligence held in the United States in July, 1993. 15 famous experts working in artificial intelligence and fuzzy systems refuted the opinion. Elkan then gave another report entitled 'The Paradoxical Controversy over Fuzzy Logic' as a reply to the refutations mentioned above. Prof. Wu gave a detailed analysis on the controversy (see ref. [3]). This shows that there is no rigid logic foundation for fuzzy propositional calculus. In this note we first point out that it is impossible to keep all classical theorems as tautologies in the field of fuzzy propositional calculus. Then we introduce a formal deductive system in fuzzy propositional calculus by giving up certain classical axioms, and the corresponding soundness theorem is proved.展开更多
Since the formal deductive system (?) was built up in 1997, it has played important roles in the theoretical and applied research of fuzzy logic and fuzzy reasoning. But, up to now, the completeness problem of the sys...Since the formal deductive system (?) was built up in 1997, it has played important roles in the theoretical and applied research of fuzzy logic and fuzzy reasoning. But, up to now, the completeness problem of the system (?) is still an open problem. In this paper, the properties and structure of R0 algebras are further studied, and it is shown that every tautology on the R0 interval [0,1] is also a tautology on any R0 algebra. Furthermore, based on the particular structure of (?) -Lindenbaum algebra, the completeness and strong completeness of the system (?) are proved. Some applications of the system (?) in fuzzy reasoning are also discussed, and the obtained results and examples show that the system (?) is suprior to some other important fuzzy logic systems.展开更多
More and more cryptographic protocols have been used to achieve various security requirements of distributed systems in the open network environment. However cryptographic protocols are very difficult to design and an...More and more cryptographic protocols have been used to achieve various security requirements of distributed systems in the open network environment. However cryptographic protocols are very difficult to design and analyze due to the complexity of the cryptographic protocol execution, and a large number of problems are unsolved that range from the theory framework to the concrete analysis technique. In this paper, we build a new algebra called cryptographic protocol algebra (CPA) for describing the message operations with many cryptographic primitives, and proposed a new algebra model for cryptographic protocols based on the CPA. In the model, expanding processes of the participants knowledge on the protocol runs are characterized with some algebraic notions such as subalgebra, free generator and polynomial algebra, and attack processes are modeled with a new notion similar to that of the exact sequence used in homological algebra. Then we develope a mathematical approach to the cryptographic protocol security analysis. By using algebraic techniques, we have shown that for those cryptographic protocols with some symmetric properties, the execution space generated by an arbitrary number of participants may boil down to a smaller space generated by several honest participants and attackers. Furthermore we discuss the composability problem of cryptographic protocols and give a sufficient condition under which the protocol composed of two correct cryptographic protocols is still correct, and we finally offer a counterexample to show that the statement may not be true when the condition is not met.展开更多
Translation validation was invented in the 90＇s by Pnueli et al. as a technique to formally verify the correctness of code generators. Rather than certifying the code generator or exhaustively qualifying it, translat...Translation validation was invented in the 90＇s by Pnueli et al. as a technique to formally verify the correctness of code generators. Rather than certifying the code generator or exhaustively qualifying it, translation validators attempt to verify that program transformations preserve semantics. In this work, we adopt this approach to formally verify that the clock semantics and data dependence are preserved during the compilation of the Signal compiler. Translation valida- tion is implemented for every compilation phase from the initial phase until the latest phase where the executable code is generated, by proving the transformation in each phase of the compiler preserves the semantics. We represent the clock semantics, the data dependence of a program and its trans- formed counterpart as first-order formulas which are called clock models and synchronous dependence graphs （SDGs）, respectively. We then introduce clock refinement and depen- dence refinement relations which express the preservations of clock semantics and dependence, as a relation on clock mod- els and SDGs, respectively. Our validator does not require any instrumentation or modification of the compiler, nor any rewriting of the source program.展开更多
基金This work was supported by the National 973 Program of China(Grant No．2002CB3 1 2200)the National Natural Science Foundation of China(Grant No．60373038) the Natural Scientific Research Project ofthe Education Department ofShaanxi Province in China(Grant No．04JK131)．
文摘The theory of the concept lattice is an efficient tool for knowledge representation and knowledge discovery, and is applied to many fields successfully. One focus of knowledge discovery is knowledge reduction. This paper proposes the theory of attribute reduction in the concept lattice, which extends the theory of the concept lattice. In this paper, the judgment theorems of consistent sets are examined, and the discernibility matrix of a formal context is introduced, by which we present an approach to attribute reduction in the concept lattice. The characteristics of three types of attributes are analyzed.
基金the National 973 Program of China (Grant No.2002CB312200)the National Natural Science Foundation of China (Grant Nos.60703117, 60433010 and 60673096)the Doctor Research Fund of Northwest University in China
文摘The theory of concept lattices is an efficient tool for knowledge representation and knowledge discovery, and is applied to many fields successfully. One focus of knowledge discovery is knowledge reduction. Based on the reduction theory of classical formal context, this paper proposes the definition of decision formal context and its reduction theory, which extends the reduction theory of concept lattices. In this paper, strong consistence and weak consistence of decision formal context are defined respectively. For strongly consistent decision formal context, the judgment theorems of consistent sets are examined, and approaches to reduction are given. For weakly consistent decision formal context, implication mapping is defined, and its reduction is studied. Finally, the relation between reducts of weakly consistent decision formal context and reducts of implication mapping is discussed.
基金Research supported by the National Natural Science Foundation of China.
文摘The loop invariants take a very important role in the design,proof and derivation of the algorithmic program.We point out the limitations of the traditional standard strategy for developing loop invariants, and propose two new strategies for proving the existing algorithmic program and developing new ones. The strategies use recurrence as vehicle and integrate some effective methods of designing algorithms, e.g.Dynamic Programming,Greedy and Divide Conquer,into the recurrence relation of problem solving sequence.This lets us get straightforward an approach for solving a variety of complicated prob- lems,and makes the standard proof and formal derivation of their algorithmic programs possible.We show the method and advantages of applying the strategies with several typical nontrivial examples.
基金This work was partly supported by the National Natural Science Foundation of China （Grant Nos. 60233010 and 60496324） the National Key Research and Development Program of China （Grant No. 2002CB312004） the Knowledge Innovation Program of the Chinese Academy of Sciences and MADIS of the Chinese Academy of Sciences.
文摘Automatic discovery and composition of Web services is an important research area in Web service technology, in which the specification of Web services is a key issue. This paper presents a Web service capability description framework based on the environment ontology. This framework depicts Web services capability in two aspects： the operable environment and the environment changes resulting from behaviors of the Web service. On the basis of the framework, a requirement-driven Web service composition model has been constructed. This paper brings forward the formalization of Web service interactions with π calculus. And an automatic mechanism converting conceptual capability description to the formal process expression has been built. This kind of formal specification assists in verifying whether the composite Web service model matches the requirement.
基金National Natural Science Foundation of China (1 0 1 0 1 0 1 6) Tian Yuan Founda-tion(1 0 1 2 60 2 0 )
文摘Cellular automata are the discrete dynamical systems of simple construction but with complex and varied behaviors.In this paper,the elementary cellular automaton of rule 22 is studied by the tools of formal language theory and symbolic dynamics.Its temporal evolution orbits are coarse grained into evolution sequences and the evolution languages are defined.It is proved that for every n ≥2 its width n evolution language is not regular.
文摘In this paper, the fluid flow differential equation based on the homogenous reservoirs model is first reviewed. Then a theorem about the formal similarity of solutions in the Laplace space with outer boundary conditions and inner boundary condition is presented and proved. Lastly, a corollary of our theorem is given particularly on inner boundary. The obtained results are very helpful for understanding inherent laws of relevant engineering science and designing practical analysis software.
文摘A great disturbance was raised by the report of Elkan entitled 'The Paradoxical Success of Fuzzy Logic' at the llth Annual Conference on Artificial Intelligence held in the United States in July, 1993. 15 famous experts working in artificial intelligence and fuzzy systems refuted the opinion. Elkan then gave another report entitled 'The Paradoxical Controversy over Fuzzy Logic' as a reply to the refutations mentioned above. Prof. Wu gave a detailed analysis on the controversy (see ref. [3]). This shows that there is no rigid logic foundation for fuzzy propositional calculus. In this note we first point out that it is impossible to keep all classical theorems as tautologies in the field of fuzzy propositional calculus. Then we introduce a formal deductive system in fuzzy propositional calculus by giving up certain classical axioms, and the corresponding soundness theorem is proved.
文摘Since the formal deductive system (?) was built up in 1997, it has played important roles in the theoretical and applied research of fuzzy logic and fuzzy reasoning. But, up to now, the completeness problem of the system (?) is still an open problem. In this paper, the properties and structure of R0 algebras are further studied, and it is shown that every tautology on the R0 interval [0,1] is also a tautology on any R0 algebra. Furthermore, based on the particular structure of (?) -Lindenbaum algebra, the completeness and strong completeness of the system (?) are proved. Some applications of the system (?) in fuzzy reasoning are also discussed, and the obtained results and examples show that the system (?) is suprior to some other important fuzzy logic systems.
文摘More and more cryptographic protocols have been used to achieve various security requirements of distributed systems in the open network environment. However cryptographic protocols are very difficult to design and analyze due to the complexity of the cryptographic protocol execution, and a large number of problems are unsolved that range from the theory framework to the concrete analysis technique. In this paper, we build a new algebra called cryptographic protocol algebra (CPA) for describing the message operations with many cryptographic primitives, and proposed a new algebra model for cryptographic protocols based on the CPA. In the model, expanding processes of the participants knowledge on the protocol runs are characterized with some algebraic notions such as subalgebra, free generator and polynomial algebra, and attack processes are modeled with a new notion similar to that of the exact sequence used in homological algebra. Then we develope a mathematical approach to the cryptographic protocol security analysis. By using algebraic techniques, we have shown that for those cryptographic protocols with some symmetric properties, the execution space generated by an arbitrary number of participants may boil down to a smaller space generated by several honest participants and attackers. Furthermore we discuss the composability problem of cryptographic protocols and give a sufficient condition under which the protocol composed of two correct cryptographic protocols is still correct, and we finally offer a counterexample to show that the statement may not be true when the condition is not met.
文摘Translation validation was invented in the 90＇s by Pnueli et al. as a technique to formally verify the correctness of code generators. Rather than certifying the code generator or exhaustively qualifying it, translation validators attempt to verify that program transformations preserve semantics. In this work, we adopt this approach to formally verify that the clock semantics and data dependence are preserved during the compilation of the Signal compiler. Translation valida- tion is implemented for every compilation phase from the initial phase until the latest phase where the executable code is generated, by proving the transformation in each phase of the compiler preserves the semantics. We represent the clock semantics, the data dependence of a program and its trans- formed counterpart as first-order formulas which are called clock models and synchronous dependence graphs （SDGs）, respectively. We then introduce clock refinement and depen- dence refinement relations which express the preservations of clock semantics and dependence, as a relation on clock mod- els and SDGs, respectively. Our validator does not require any instrumentation or modification of the compiler, nor any rewriting of the source program.
