Query answering with transitive and linear-ordered data

Antoine Amarilli; Michael Benedikt; Pierre Bourhis; Michael Vanden Boom

Query answering with transitive and linear-ordered data

Antoine Amarilli
, Michael Benedikt
, Pierre Bourhis
, Michael Vanden Boom

CNRS LTCI
University of Oxford
University of Lille 1

Résultats de recherche: Contribution à un journal › Article de conférence › Revue par des pairs

12 Citations (Scopus)

Résumé

We consider entailment problems involving powerful constraint languages such as guarded existential rules, in which additional semantic restrictions are put on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural generalizations of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in our conditions lead to undecidability.

langue originale	Anglais
Pages (de - à)	893-899
Nombre de pages	7
journal	IJCAI International Joint Conference on Artificial Intelligence
Volume	2016-January
état	Publié - 1 janv. 2016
Modification externe	Oui
Evénement	25th International Joint Conference on Artificial Intelligence, IJCAI 2016 - New York, États-Unis Durée: 9 juil. 2016 → 15 juil. 2016

Contient cette citation

@article{e5a5b6b550054ba9bfb620147488a8bf,

title = "Query answering with transitive and linear-ordered data",

abstract = "We consider entailment problems involving powerful constraint languages such as guarded existential rules, in which additional semantic restrictions are put on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural generalizations of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in our conditions lead to undecidability.",

author = "Antoine Amarilli and Michael Benedikt and Pierre Bourhis and \{Vanden Boom\}, Michael",

year = "2016",

month = jan,

day = "1",

language = "English",

volume = "2016-January",

pages = "893--899",

journal = "IJCAI International Joint Conference on Artificial Intelligence",

issn = "1045-0823",

publisher = "International Joint Conferences on Artificial Intelligence",

note = "25th International Joint Conference on Artificial Intelligence, IJCAI 2016 ; Conference date: 09-07-2016 Through 15-07-2016",

}

TY - JOUR

T1 - Query answering with transitive and linear-ordered data

AU - Amarilli, Antoine

AU - Benedikt, Michael

AU - Bourhis, Pierre

AU - Vanden Boom, Michael

PY - 2016/1/1

Y1 - 2016/1/1

N2 - We consider entailment problems involving powerful constraint languages such as guarded existential rules, in which additional semantic restrictions are put on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural generalizations of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in our conditions lead to undecidability.

AB - We consider entailment problems involving powerful constraint languages such as guarded existential rules, in which additional semantic restrictions are put on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural generalizations of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in our conditions lead to undecidability.

M3 - Conference article

AN - SCOPUS:85006164454

SN - 1045-0823

VL - 2016-January

SP - 893

EP - 899

JO - IJCAI International Joint Conference on Artificial Intelligence

JF - IJCAI International Joint Conference on Artificial Intelligence

T2 - 25th International Joint Conference on Artificial Intelligence, IJCAI 2016

Y2 - 9 July 2016 through 15 July 2016

ER -

Query answering with transitive and linear-ordered data

Résumé

Empreinte digitale

Contient cette citation