The FaCT System
Lecture notes in computer sciencePublished 1 January 1998
Ian Horrocks
Citations288
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
FaCT is a Description Logic classifier which has been implemented as a test-bed for a highly optimised tableaux satisfiability (subsumption) testing algorithm.
Abstract
FaCT is a Description Logic classifier which has been implemented as a test-bed for a highly optimised tableaux satisfiability (subsumption) testing algorithm. The correspondence between modal and description logics also allows FaCT to be used as a theorem prover for the propositional modal logics K, KT, K4 and S4. Empirical tests have demonstrated the effectiveness of the optimised implementation and, in particular, of the dependency directed backtracking optimisation.
Keywords
Computer Science
Communications of the ACMA machine program for theorem-proving
3,191 Citations1962Martin Davis, George Logemann +1 more
The programming of a proof procedure is discussed in connection with trial runs and possible improvements.
Artificial IntelligenceAttributive concept descriptions with complements
964 Citations1991Manfred Schmidt-Schauß, Gert Smolka
It is shown that deciding coherence and subsumption of such descriptions are PSPACE-complete problems that can be decided with linear space.
A correspondence theory for terminological logics: preliminary report
466 Citations1991Klaus Schild
It is proved that universal implications can be expressed within TSC, and it is shown that features correspond to deterministic programs in dynamic logic preserves decidability, although violates its finite model property.
ScholarlyCommons (University of Pennsylvania)Improvements to propositional satisfiability search algorithms
258 Citations1995Jon Freeman
This dissertation examines complete search algorithms for SAT, the satisfiability problem for propositional formulas in conjunctive normal form, and argues that any efficient SAT search algorithm should perform only a few key technique at each node of the search tree.
SciDok (Saarland University and State Library)Decidable reasoning in terminological knowledge representation systems
190 Citations1993Martin Buchheit, Francesco M. Donini +1 more
The decidability of a number of desirable TKRS-deduction services are proved through a sound, complete and terminating calculus for reasoning in ALCNR-knowledge bases, and the result that inclusion statements in A LCNR can be simulated by terminological cycles, if descriptive semantics is adopted.
SciDok (Saarland University and State Library)An empirical analysis of optimization techniques for terminological representation systems : or: 'Making KRIS get a move on'
180 Citations1993Franz Baader, Bernhard Hollunder +3 more
Different methods of optimizing the classification process of terminological representation systems are considered, and their effect on three different types of test data is evaluated.
Lecture notes in computer scienceBuilding decision procedures for modal logics from propositional decision procedures — The case study of modal K
114 Citations1996Fausto Giunchiglia, Roberto Sebastiani
The goal of this paper is to propose a new technique for developing decision procedures for propositional modal logics, based on an implementation of the Davis-Putnam-Longemann-Loveland procedure, which tests satisfiability in modal K.
Journal of Artificial Intelligence ResearchDecidable Reasoning in Terminological Knowledge Representation Systems
109 Citations1993Martin Buchheit, Francesco M. Donini +1 more
Artificial IntelligenceCardinality restrictions on concepts
105 Citations1996Franz Baader, Martin Buchheit +1 more
ACM SIGART BulletinKRIS
94 Citations1991Franz Baader, Bernhard Hollunder
It turned out that almost all implemented KL-ONE systems such as BACK, KL-TWO, LOOM, NIKL, SB-ONE use sound but incomplete algorithms.
Journal of Automated ReasoningHARP: A tableau-based theorem prover
90 Citations1988Franz Oppacher, E. Suen
HARP's architecture-and the concomitant ready extensibility of its control structure by declarative heuristic rules-renders it easy to let extralogical information, e.g. semantic and world knowledge, guide the search for proofs and help eliminate irrelevant premisses.
Lecture notes in computer scienceA concept language extended with different kinds of transitive roles
88 Citations1996Ulrike Sattler
Insight is given into the diverse alternatives for the representation of transitive relations such as part-whole relations, family relations or partial orders in general in terminological knowledge representation systems.
Journal of Automated ReasoningA Benchmark Method for the Propositional Modal Logics K, KT, S4
74 Citations2000Peter Balsiger, Alain Heuerding +1 more
A set of benchmark formulas for proof search in propositional modal logics K, KT, and S4 are presented and the discussion of postulates concerning ATP benchmark helps to obtain improved benchmark methods for other logics, too.
SciDok (Saarland University and State Library)Terminological knowledge representation : a proposal for a terminological logic
73 Citations1990Franz Baader, Hans-Jürgen Bürckert +6 more
A roller particularly adapted for driving sheet material through a folding machine, which sheet material is folded by the folding machine.
Intelligent backtracking on constraint satisfaction problems: experimental and theoretical results
72 Citations1995Andrew B. Baker
It is shown that for a large class of constraint satisfaction algorithms, there is a trade-off in intelligent backtracking between space and time, and whether it is possible for a polynomial-space algorithm to be exponential in the induced width is shown.
A SAT-based decision procedure for ALC
60 Citations1996Fausto Giunchiglia, Roberto Sebastiani
The goal of this paper is to describe and thoroughly test a decision procedure, called KSAT, checking satisfiability in the terminological logic A£C, and highlight an intrinsic weakeness that tableau- based decision procedures have with respect to SATbased decision procedures.
Artificial IntelligenceHard random 3-SAT problems and the Davis-Putnam procedure
38 Citations1996Jon Freeman
This paper uses a highly optimized version of DPL to plot the average number of remaining variables versus search tree depth for several nontrivial sizes of critically constrained, under Constrained, and overconstrained problems, and experimentally determines how their complexity decreases as the depth of their associated search trees increases.
Implementing and Testing Expressive Description Logics: a Preliminary Report
33 Citations1995Paolo Bresciani, Enrico Franconi +1 more
The aim of the crack project is the research and the development of a knowledge representation architecture based on description logics, characterized by an order parameter generating phase transitions in the satis ability probability space.