Schema-Based Automata Determinization
Document type :
Communication dans un congrès avec actes
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]
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
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 >
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 :
Source :
Files
- https://hal.inria.fr/hal-03536045v2/document
- Open access
- Access the document
- https://hal.inria.fr/hal-03536045v2/document
- Open access
- Access the document
- https://hal.inria.fr/hal-03536045v2/document
- Open access
- Access the document
- document
- Open access
- Access the document
- 0.pdf
- Open access
- Access the document