A Benchmark of Deterministic Automata for ...
Document type :
Pré-publication ou Document de travail
Permalink :
Title :
A Benchmark of Deterministic Automata for Regular XPath Queries
Author(s) :
Al Serhali, Antonio [Auteur]
Linking Dynamic Data [LINKS]
Niehren, Joachim [Auteur]
Linking Dynamic Data [LINKS]
Linking Dynamic Data [LINKS]
Niehren, Joachim [Auteur]

Linking Dynamic Data [LINKS]
English keyword(s) :
XPath
nested words
trees
regular path queries
Automata
nested words
trees
regular path queries
Automata
HAL domain(s) :
Informatique [cs]
English abstract : [en]
We provide a benchmark collection of deterministic automata for regular XPath queries. For this, we select the subcollection of forward navigational XPath queries from a corpus that Lick and Schmitz extracted from real ...
Show more >We provide a benchmark collection of deterministic automata for regular XPath queries. For this, we select the subcollection of forward navigational XPath queries from a corpus that Lick and Schmitz extracted from real world XSLT and XQuery programs, compile them to symbolic stepwise hedge automata (SSHAs) and determinize them. Large blowups by automata determinization are avoided by using schema-based determinization. Therefore, we show how to lift a recent algorithm for schema-based determinization from SHAs to symbolic SHAs. Our collection also provides deterministic symbolic nested word automata, that we obtain by compilation from deterministic symbolic SHAs.Show less >
Show more >We provide a benchmark collection of deterministic automata for regular XPath queries. For this, we select the subcollection of forward navigational XPath queries from a corpus that Lick and Schmitz extracted from real world XSLT and XQuery programs, compile them to symbolic stepwise hedge automata (SSHAs) and determinize them. Large blowups by automata determinization are avoided by using schema-based determinization. Therefore, we show how to lift a recent algorithm for schema-based determinization from SHAs to symbolic SHAs. Our collection also provides deterministic symbolic nested word automata, that we obtain by compilation from deterministic symbolic SHAs.Show less >
Language :
Anglais
Collections :
Source :
Submission date :
2022-03-02T02:00:56Z
Files
- https://hal.inria.fr/hal-03527888v2/document
- Open access
- Access the document