Title :

Schema-Based Automata Determinization

Author(s) :

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

Conference title :

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

City :

Madrid

Country :

Espagne

Start date of the conference :

2022-09-21

Publisher :

EPTCS

English keyword(s) :

Automata
Nested words
Path queries
Trees
XPath

HAL domain(s) :

Informatique [cs]

English abstract : [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. ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

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

Source :

Harvested from HAL