Schema-Based Automata Determinization - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

Schema-Based Automata Determinization

Joachim Niehren
Momar Sakho
  • Fonction : Auteur
  • PersonId : 1019942

Résumé

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.
Fichier principal
Vignette du fichier
0.pdf (934.41 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03536045 , version 1 (19-01-2022)
hal-03536045 , version 2 (25-07-2022)

Identifiants

  • HAL Id : hal-03536045 , version 2

Citer

Joachim Niehren, Momar Sakho, Antonio Al Serhali. Schema-Based Automata Determinization. Gandalf 2022: 13th International Symposium on Games, Automata, Logics, and Formal Verification, Sep 2022, Madrid, Spain. ⟨hal-03536045v2⟩
105 Consultations
90 Téléchargements

Partager

Gmail Facebook X LinkedIn More