Translating between Horn Representations and their Characteristic Models

DSpace/Manakin Repository

Translating between Horn Representations and their Characteristic Models

Citable link to this page

 

 
Title: Translating between Horn Representations and their Characteristic Models
Author: Khardon, Roni
Citation: Khardon, Roni. 1995. Translating between Horn Representations and their Characteristic Models. Harvard Computer Science Group Technical Report TR-03-95.
Full Text & Related Files:
Abstract: Characteristic models are an alternative, model based, representation for Horn expressions. It has been shown that these two representations are incomparable and each has its advantages over the other. It is therefore natural to ask what is the cost of translating, back and forth, between these representations. Interestingly, the same translation questions arise in database theory, where it has applications to the design of relational databases. We study the complexity of these problems and prove some positive and negative results. Our main result is that the two translation problems are equivalent under polynomial reductions, and that they are equivalent to the corresponding decision problem. Namely, translating is equivalent to deciding whether a given set a models is the set of characteristic models for a given Horn expression. We also relate these problems to translating between the CNF and DNF representations of monotone functions, a well known problem for which no polynomial time algorithm is known. It is shown that in general our translation problems are at least as hard as the latter, and in a special case they are equivalent to it.
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:23574651
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters