Titre :

Schema-Based Automata Determinization

Auteur(s) :

Niehren, Joachim [Auteur]
Linking Dynamic Data [LINKS]
Sakho, Momar [Auteur]
Linking Dynamic Data [LINKS]
Université de Lille
Al Serhali, Antonio [Auteur]
Linking Dynamic Data [LINKS]
Université de Lille

Titre de la manifestation scientifique :

Gandalf 2022: 13th International Symposium on Games, Automata, Logics, and Formal Verification

Ville :

Madrid

Pays :

Espagne

Date de début de la manifestation scientifique :

2022-09-21

Éditeur :

EPTCS

Mot(s)-clé(s) en anglais :

Automata
Nested words
Path queries
Trees
XPath

Discipline(s) HAL :

Informatique [cs]

Résumé en anglais : [en]

We propose an algorithm for schema-based determinization of finite automata on words and of stepwise hedge automata on nested words. The idea is to integrate schema-based cleaning directly into automata determinization. ...
Lire la suite >We propose an algorithm for schema-based determinization of finite automata on words and of stepwise hedge automata on nested words. The idea is to integrate schema-based cleaning directly into automata determinization. We prove the correctness of our new algorithm and show that it is always more efficient than standard determinization followed by schema-based cleaning. Our implementation permits to obtain a small deterministic automaton for an example of an XPath query, where standard determinization yields a huge stepwise hedge automaton for which schema-based cleaning runs out of memory.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL