Expressive Logical Combinators for Free

Pierre Genevès 1 Alan Schmitt 2
1 TYREX - Types and Reasoning for the Web
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 CELTIQUE - Software certification with semantic analysis
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : A popular technique for the analysis of web query languages relies on the translation of queries into logical formulas. These formulas are then solved for satisfiability using an off-the-shelf satisfiabil-ity solver. A critical aspect in this approach is the size of the obtained logical formula, since it constitutes a factor that affects the combined complexity of the global approach. We present logical combi-nators whose benefit is to provide an exponential gain in succinctness in terms of the size of the logical representation. This opens the way for solving a wide range of problems such as satisfiability and containment for expressive query languages in exponential-time, even though their direct formulation into the underlying logic results in an exponential blowup of the formula size, yielding an incorrectly presumed two-exponential time complexity. We illustrate this from a practical point of view on a few examples such as numerical occurrence constraints and tree frontier properties which are concrete problems found with semi-structured data.
Type de document :
Communication dans un congrès
International Joint Conference on Artificial Intelligence (IJCAI 2015), Jul 2015, Buenos Aires, Argentina
Liste complète des métadonnées


https://hal.inria.fr/hal-00868724
Contributeur : Tyrex Equipe <>
Soumis le : mercredi 6 mai 2015 - 17:06:38
Dernière modification le : mercredi 12 juillet 2017 - 01:14:23
Document(s) archivé(s) le : dimanche 16 avril 2017 - 09:30:18

Fichier

Lean-ijcai15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00868724, version 4

Citation

Pierre Genevès, Alan Schmitt. Expressive Logical Combinators for Free. International Joint Conference on Artificial Intelligence (IJCAI 2015), Jul 2015, Buenos Aires, Argentina. <hal-00868724v4>

Partager

Métriques

Consultations de
la notice

542

Téléchargements du document

160