Although neural methods have been comprehensively applied in different fields,symbolic based logic reasoning is still the main choice for numerous applications based on knowledge graphs.To enhance the efficiency of kn...Although neural methods have been comprehensively applied in different fields,symbolic based logic reasoning is still the main choice for numerous applications based on knowledge graphs.To enhance the efficiency of knowledge graph reasoning,researchers studied how to design parallelalgorithms for reasoning,and take advantage of high-performance architectures,like neural networks.Although parallel algorithms and architectures improve the performance of reasoning to some degree,the task of reasoning is essentially bounded by its computational complexity,i.e.,the PTiMe-Completeness or higher complexities.This means that the task of reasoning is not parallelly tractable.In this work,we investigate the parallel tractability of knowledge graph reasoning from the perspective of parallel complexity.We concentrate on knowledge graphs that are Datalog rewritable.We aim to capture the parallelly tractable classes of knowledge graphs,for which,the task of reasoning falls in the NC complexity.To this end,we employ the computational model of Boolean circuit to formalize knowledge graph reasoning and further obtain all the theoretical results.We then use the results to analyze DHL(Description Horn Logic),a fragment of description logic.We give the properties that ensure the parallel tractability of DHL reasoning.One can utilize our results to check the parallel tractability of real knowledge graphs.In addition,the Boolean circuits proposed in this paper can also be used to construct neural networks to perform knowledge graph reasoning.展开更多
In this paper, the authors continue the researches described in [1], that consists in a comparative study of two methods to eliminate the static hazard from logical functions, by using the form of Product of Sums (POS...In this paper, the authors continue the researches described in [1], that consists in a comparative study of two methods to eliminate the static hazard from logical functions, by using the form of Product of Sums (POS), static hazard “0”. In the first method, it used the consensus theorem to determine the cover term that is equal with the product of the two residual implicants, and in the second method it resolved a Boolean equation system. The authors observed that in the second method the digital hazard can be earlier detected. If the Boolean equation system is incompatible (doesn’t have solutions), the considered logical function doesn’t have the static 1 hazard regarding the coupled variable. Using the logical computations, this method permits to determine the needed transitions to eliminate the digital hazard.展开更多
基金supported by The Natural Science Foundation of the Jiangsu Higher Education Institutions of China under grant number 22KJB520003.The project name is"Research on Representation and Reasoning of Knowledge Graphs based on Semantic Mapping".
文摘Although neural methods have been comprehensively applied in different fields,symbolic based logic reasoning is still the main choice for numerous applications based on knowledge graphs.To enhance the efficiency of knowledge graph reasoning,researchers studied how to design parallelalgorithms for reasoning,and take advantage of high-performance architectures,like neural networks.Although parallel algorithms and architectures improve the performance of reasoning to some degree,the task of reasoning is essentially bounded by its computational complexity,i.e.,the PTiMe-Completeness or higher complexities.This means that the task of reasoning is not parallelly tractable.In this work,we investigate the parallel tractability of knowledge graph reasoning from the perspective of parallel complexity.We concentrate on knowledge graphs that are Datalog rewritable.We aim to capture the parallelly tractable classes of knowledge graphs,for which,the task of reasoning falls in the NC complexity.To this end,we employ the computational model of Boolean circuit to formalize knowledge graph reasoning and further obtain all the theoretical results.We then use the results to analyze DHL(Description Horn Logic),a fragment of description logic.We give the properties that ensure the parallel tractability of DHL reasoning.One can utilize our results to check the parallel tractability of real knowledge graphs.In addition,the Boolean circuits proposed in this paper can also be used to construct neural networks to perform knowledge graph reasoning.
文摘In this paper, the authors continue the researches described in [1], that consists in a comparative study of two methods to eliminate the static hazard from logical functions, by using the form of Product of Sums (POS), static hazard “0”. In the first method, it used the consensus theorem to determine the cover term that is equal with the product of the two residual implicants, and in the second method it resolved a Boolean equation system. The authors observed that in the second method the digital hazard can be earlier detected. If the Boolean equation system is incompatible (doesn’t have solutions), the considered logical function doesn’t have the static 1 hazard regarding the coupled variable. Using the logical computations, this method permits to determine the needed transitions to eliminate the digital hazard.
