6533b873fe1ef96bd12d4d50
RESEARCH PRODUCT
Finite Model Reasoning in Expressive Fragments of First-Order Logic
Lidia Tenderasubject
FOS: Computer and information sciencesComputer Science - Logic in Computer ScienceTheoretical computer scienceComputer sciencelcsh:Mathematicsmedia_common.quotation_subjectModal logicContext (language use)lcsh:QA1-939InfinityTranslation (geometry)lcsh:QA75.5-76.95Logic in Computer Science (cs.LO)First-order logicImage (mathematics)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESFragment (logic)F.4.1lcsh:Electronic computers. Computer scienceAxiommedia_commondescription
Over the past two decades several fragments of first-order logic have been identified and shown to have good computational and algorithmic properties, to a great extent as a result of appropriately describing the image of the standard translation of modal logic to first-order logic. This applies most notably to the guarded fragment, where quantifiers are appropriately relativized by atoms, and the fragment defined by restricting the number of variables to two. The aim of this talk is to review recent work concerning these fragments and their popular extensions. When presenting the material special attention is given to decision procedures for the finite satisfiability problems, as many of the fragments discussed contain infinity axioms. We highlight most effective techniques used in this context, their advantages and limitations. We also mention a few open directions of study.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2017-03-06 | Electronic Proceedings in Theoretical Computer Science |