Back to Search Start Over

Model Representation over Finite and Infinite Signatures.

Authors :
Fisher, Michael
Hoek, Wiebe
Konev, Boris
Lisitsa, Alexei
Fermüller, Christian G.
Pichler, Reinhard
Source :
Logics in Artificial Intelligence; 2006, p164-176, 13p
Publication Year :
2006

Abstract

Computationally adequate representation of models is a topic arising in various forms in logic and AI. Two fundamental decision problems in this area are: (1) to check whether a given clause is true in a represented model, and (2) to decide whether two representations of the same type represent the same model. ARMs, contexts and DIGs are three important examples of model representation formalisms. The complexity of the mentioned decision problems has been studied for ARMs only for finite signatures, and for contexts and DIGs only for infinite signatures, so far. We settle the remaining cases. Moreover we show that, similarly to the case for infinite signatures, contexts and DIGs allow one to represent the same classes of models also over finite signatures; however DIGs may be exponentially more succinct than all equivalent contexts. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISBNs :
9783540396253
Database :
Complementary Index
Journal :
Logics in Artificial Intelligence
Publication Type :
Book
Accession number :
32905305
Full Text :
https://doi.org/10.1007/11853886_15