TY  - CONF
AU  - Heymans, Stijn
AU  - Korf, Roman
AU  - Erdmann, Michael
AU  - Puehrer, Joerg
AU  - Eiter, Thomas
A2  - 
T1  - F-Logic: Loosely Coupling F-Logic Rules and Ontologies
T2  - Proc. of the 2010 IEEE/WIC/ACM International Conference on Web Intelligence
PB  - 
C1  - 
PY  - 2010/
CY  -  
VL  - 
IS  - 
SP  - 
EP  - 
UR  - http://www.kr.tuwien.ac.at/staff/heymans/priv/publications/wi2010.pdf
DO  - 
KW  - ontologies
KW  - toread
L1  - 
SN  - 
N1  - 
N1  - 
AB  - 
ER  -

TY  - CONF
AU  - Eiter, Thomas
AU  - Ianni, Giovambattista
AU  - Schindlauer, Roman
AU  - Tompits, Hans
A2  - 
T1  - Effective Integration of Declarative Rules with External Evaluations for Semantic-Web Reasoning.
T2  - ESWC
PB  - 
C1  - 
PY  - 2006/
CY  -  
VL  - 
IS  - 
SP  - 273
EP  - 287
UR  - 
DO  - 
KW  - reason
KW  - european
KW  - rules
KW  - proceedings
KW  - 2006
KW  - semantic
KW  - conference
KW  - eswc
KW  - and
KW  - web
L1  - 
SN  - 
N1  - DBLP Record 'conf/esws/EiterIST06'
N1  - 
AB  - 
ER  -

TY  - JOUR
AU  - Eiter, Thomas
AU  - Gottlob, Georg
T1  - Identifying the Minimal Transversals of a Hypergraph and Related Problems
JO  - SIAM J. Comput.
PY  - 1995/
VL  - 24
IS  - 6
SP  - 1278
EP  - 1304
UR  - http://portal.acm.org/citation.cfm?id=219403
DO  - http://dx.doi.org/10.1137/S0097539793250299
KW  - conp
KW  - theory
KW  - hypergraph
KW  - complexity
L1  - 
SN  - 
N1  - 
N1  - 
AB  - The paper considers two decision problems on hypergraphs, hypergraph saturation and recognition of the transversal hypergraph, and discusses their significance for several search problems in applied computer science. Hypergraph saturation (i.e., given a hypergraph $l H$, decide if every subset of vertices is contained in or contains some edge of $l H$) is shown to be co-NP-complete. A certain subproblem of hypergraph saturation, the saturation of simple hypergraphs (i.e., Sperner families), is shown to be under polynomial transformation equivalent to transversal hypergraph recognition; i.e., given two hypergraphs $l H_1, l H_2$, decide if the sets in $l H_2$ are all the minimal transversals of $l H_1$. The complexity of the search problem related to the recognition of the transversal hypergraph, the computation of the transversal hypergraph, is an open problem. This task needs time exponential in the input size; it is unknown whether an output-polynomial algorithm exists. For several important subcases, for instance if an upper or lower bound is imposed on the edge size or for acyclic hypergraphs, output-polynomial algorithms are presented. Computing or recognizing the minimal transversals of a hypergraph is a frequent problem in practice, which is pointed out by identifying important applications in database theory, Boolean switching theory, logic, and artificial intelligence (AI), particularly in model-based diagnosis.
ER  -