Improvements on graph path queries : expression, evaluation, and minimum-weight satisfiability
Nous traitons trois problèmes liés aux requêtes de chemin en graphes. La plupart des langages de requête en graphes actuels prennent en charge les requêtes de chemins réguliers. Cependant, certaines applications telles que l analyse du code source et la génétique nécessitent des requêtes de chemins...
Kaydedildi:
| Yazar: | |
|---|---|
| Diğer Yazarlar: | , , , , , , , |
| Materyal Türü: | Thèse numérique |
| Dil: | Anglais |
| Baskı/Yayın Bilgisi: |
2022.
|
| Konular: | |
| Online Erişim: | Accès au texte intégral https://theses.univ-orleans.fr/public/2022ORLE1038_va.pdf http://www.theses.fr/2022ORLE1038/abes https://theses.hal.science/tel-04186027 |
| Not: |
Thèse soutenue en co-tutelle Titre provenant de l'écran-titre Ecole(s) Doctorale(s) : École doctorale Mathématiques, Informatique, Physique Théorique et Ingénierie des Systèmes (Centre-Val de Loire ; 2012-....) Partenaire(s) de recherche : Laboratoire d'informatique fondamentale d'Orléans (Orléans ; 1987-....) (Laboratoire) Autre(s) contribution(s) : Nicolas Travers (Président du jury) ; Mathieu Liedloff, Farouk Toumani, Elizabeth Goldbarg (Membre(s) du jury) ; Carmem Satie Hara, Nora Reyes (Rapporteur(s)) |
| Autres localisations: | Voir dans le Sudoc |
| Variante du titre: | Améliorations de requêtes de chemin dans les graphes :, expression, évaluation et satisfiabilité de coût minimal |
| LEADER | 04838nam a22005057a 4500 | ||
|---|---|---|---|
| 001 | 1076264 | ||
| 008 | 230823s2022 xxe ||| |||| 00| 0 eng d | ||
| 009 | PPN271482842 | ||
| 041 | 0 | |a eng |b fre |b eng | |
| 084 | |a 004 | ||
| 084 | |a 510 | ||
| 100 | 1 | |a Morais Medeiros, Ciro, |d 1994- | |
| 240 | 1 | 0 | |a Améliorations de requêtes de chemin dans les graphes : |b expression, évaluation et satisfiabilité de coût minimal |
| 245 | 1 | 0 | |a Improvements on graph path queries : |b expression, evaluation, and minimum-weight satisfiability |c Ciro Morais Medeiros ; sous la direction de Mírian Halfeld Ferrari Alves et de Martin Musicante. |
| 256 | |a Données textuelles | ||
| 260 | |c 2022. | ||
| 500 | |a Thèse soutenue en co-tutelle | ||
| 500 | |a Titre provenant de l'écran-titre | ||
| 500 | |a Ecole(s) Doctorale(s) : École doctorale Mathématiques, Informatique, Physique Théorique et Ingénierie des Systèmes (Centre-Val de Loire ; 2012-....) | ||
| 500 | |a Partenaire(s) de recherche : Laboratoire d'informatique fondamentale d'Orléans (Orléans ; 1987-....) (Laboratoire) | ||
| 500 | |a Autre(s) contribution(s) : Nicolas Travers (Président du jury) ; Mathieu Liedloff, Farouk Toumani, Elizabeth Goldbarg (Membre(s) du jury) ; Carmem Satie Hara, Nora Reyes (Rapporteur(s)) | ||
| 502 | |a Thèse de doctorat. Informatique. Orléans. 2022 | ||
| 502 | |a Thèse de doctorat. Informatique. Universidade federal do Rio Grande do Norte (Natal, Brésil). 2022 | ||
| 520 | |a Nous traitons trois problèmes liés aux requêtes de chemin en graphes. La plupart des langages de requête en graphes actuels prennent en charge les requêtes de chemins réguliers. Cependant, certaines applications telles que l analyse du code source et la génétique nécessitent des requêtes de chemins hors-contexte. Les requêtes de chemins hors-contexte utilisent des langages hors-contexte. Il n y a pas de notation standard pour les langages hors-contexte plus simple que les grammaires hors-contexte. L évaluation d une requête de chemins hors-contexte est plus complexe qu une requête de chemins réguliers. Encore, dans certaines applications, on souhaite avoir le graphe minimum qui préserve les réponses à une requête de chemins donnée. Pour résoudre chacun de ces problèmes, nous : (1) développons une notation alternative pour exprimer des langages hors-contexte ; (2) développons et expérimentons un algorithme d évaluation de requête de chemins hors-contexte ; et (3) formalisons le problème de minimisation de graphes contrainte par un langage formel,pour lequel nous développons des solutions pour les cas où le langage formel est régulier ou hors-contexte. | ||
| 520 | |a We deal with three problems related to graph path queries. Most current graph query languages support regular path queries. However, some applications such as source-code analysis and genetics require context-free path queries. Context-free path queries use context-free languages. There is no standard notation for context-free languages simpler than context-free grammars. The evaluation of a context-free path query is more complex than a regular path query. Moreover, in some applications, it is desired to have the minimum graph that preserves answers to a given path query. To address each of those problems, we: (1) develop an alternative notation for expressing context-free languages;(2) design, implement and experiment with a context-free path query evaluation algorithm; and (3) formalize the formal-language-constrained graph minimization problem, for which we design solutions for the cases where the formal language is regular or context-free. | ||
| 538 | |a Configuration requise : un logiciel capable de lire un fichier au format : PDF | ||
| 650 | |a Chemins et cycles (théorie des graphes) | ||
| 650 | |a Bases de données |x Interrogation | ||
| 650 | |a Langages d'interrogation | ||
| 650 | |a Langages rationnels | ||
| 650 | |a Thèses et écrits académiques | ||
| 700 | 1 | |a Halfeld Ferrari Alves, Mírian, |d 1962- |4 ths | |
| 700 | 1 | |a Musicante, Martin, |d 19..- |4 ths | |
| 700 | 1 | |a Travers, Nicolas, |d 1979-...., |c chercheur en informatique. | |
| 700 | 1 | |a Hara, Carmem Satie, |d 19..- | |
| 700 | 1 | |a Reyes, Nora, |d 19..- | |
| 700 | 1 | |a Liedloff, Mathieu, |d 1980- |4 opn | |
| 700 | 1 | |a Toumani, Farouk, |d 19..- |4 opn | |
| 700 | 1 | |a Goldbarg, Elizabeth, |d 19..- |4 opn | |
| 710 | 2 | |a Université d'Orléans. |4 dgg | |
| 856 | 4 | |q PDF |s 1739959 |u http://www.theses.fr/2022ORLE1038/document |z Accès au texte intégral | |
| 856 | 4 | |u https://theses.univ-orleans.fr/public/2022ORLE1038_va.pdf | |
| 856 | 4 | |u http://www.theses.fr/2022ORLE1038/abes | |
| 856 | 4 | |u https://theses.hal.science/tel-04186027 | |
| 997 | |0 1076264 |1 Thèse numérique |a Ressource numérique |b INSA |b ENSA |c 0/Bibliothèque numérique/ |c 1/Bibliothèque numérique/Autre ressource numérique/ | ||