Partition-based logical reasoning
From Semantic Portal Wiki
{{#vardefine:category|Publication}}{{#vardefine:templatename|i.publication}}{{#vardefine:package|smwbp_instance_templates}}
| Edit |
Reference: {{#vardefine:pagename|partition-based logical reasoning }}
- [[]]
bibtex
{{#vardefine:pagename|Partition-based logical reasoning }}{{#vardefine:key| }}
abstract: We investigate the problem of reasoning with partitions of related logical axioms. We are motivated by the problem of how to reasoneffectively with multiple knowledge bases that have overlap in content.In this paper, we address the more general problem of how to exploit structure inherent in a set of logical axioms to improve the efficiency of reasoning. To this end, we provide algorithms forreasoning with partitions of axioms in propositional and first-order logic. Craig's interpolation theorem serves as a key to provingcompleteness of these algorithms. We analyze the computational benefit of our algorithms and identify those parameters of a partitioning that influence the efficiency of computation. Theseparameters are the number of symbols shared by a pair of partitions, the size of each partition, and the topology of the overall partitioning. Finally, we provide a greedy algorithm that automatically decomposes a given theory into partitions, trying to optimize the efficiency of reasoning by controlling these parameters.
download:
- paper:
- slides:
| Abstract | We investigate the problem of reasoning wi … We investigate the problem of reasoning with partitions of related logical axioms. We are motivated by the problem of how to reasoneffectively with multiple knowledge bases that have overlap in content.In this paper, we address the more general problem of how to exploit structure inherent in a set of logical axioms to improve the efficiency of reasoning. To this end, we provide algorithms forreasoning with partitions of axioms in propositional and first-order logic. Craig's interpolation theorem serves as a key to provingcompleteness of these algorithms. We analyze the computational benefit of our algorithms and identify those parameters of a partitioning that influence the efficiency of computation. Theseparameters are the number of symbols shared by a pair of partitions, the size of each partition, and the topology of the overall partitioning. Finally, we provide a greedy algorithm that automatically decomposes a given theory into partitions, trying to optimize the efficiency of reasoning by controlling these parameters. reasoning by controlling these parameters. |
| Address | Stanford, CA, USA + |
| Author | Eyal Amir +, and Sheila A. McIlraith + |
| Bibtype | inproceedings + |
| Booktitle | Knowledge Systems, AI Laboratory + |
| Key | KSL-00-02 + |
| Month | February + |
| Note | This paper (without the proofs) also appears in the Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR2000), Breckenridge, USA. April, 2000. + |
| Tag | Computer science + |
| Title | Partition-Based Logical Reasoning + |
| Tr id | KSL-00-02 + |
| Year | 2000 + |
