Linear high-order deterministic tree ...
Type de document :
Communication dans un congrès avec actes
Titre :
Linear high-order deterministic tree transducers with regular look-ahead
Auteur(s) :
Gallot, Paul [Auteur]
Linking Dynamic Data [LINKS]
Lemay, Aurélien [Auteur]
Linking Dynamic Data [LINKS]
Salvati, Sylvain [Auteur]
Linking Dynamic Data [LINKS]
Linking Dynamic Data [LINKS]
Lemay, Aurélien [Auteur]
Linking Dynamic Data [LINKS]
Salvati, Sylvain [Auteur]
Linking Dynamic Data [LINKS]
Titre de la manifestation scientifique :
MFCS 2020 : The 45th International Symposium on Mathematical Foundations of Computer Science
Organisateur(s) de la manifestation scientifique :
Andreas Feldmann
Michal Koucky
Anna Kotesovcova
Michal Koucky
Anna Kotesovcova
Ville :
Prague
Pays :
République tchèque
Date de début de la manifestation scientifique :
2020-08-24
Titre de l’ouvrage :
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Date de publication :
2020-08-28
Mot(s)-clé(s) en anglais :
Tree lanuages
λ-calculus
Transducers
and phrases Transducers
Trees 31
λ-calculus
Transducers
and phrases Transducers
Trees 31
Discipline(s) HAL :
Informatique [cs]/Complexité [cs.CC]
Informatique [cs]/Théorie et langage formel [cs.FL]
Informatique [cs]/Théorie et langage formel [cs.FL]
Résumé en anglais : [en]
We introduce the notion of high-order deterministic top-down tree transducers (HODT) whose outputs correspond to simply-typed lambda-calculus formulas. These transducers are natural generalizations of known models of ...
Lire la suite >We introduce the notion of high-order deterministic top-down tree transducers (HODT) whose outputs correspond to simply-typed lambda-calculus formulas. These transducers are natural generalizations of known models of top-tree transducers such as: Deterministic Top-Down Tree Transducers, Macro Tree Transducers, Streaming Tree Transducers... We focus on the linear restriction of high order tree transducers with look-ahead (HODTR lin), and prove this corresponds to tree to tree functional transformations defined by Monadic Second Order (MSO) logic. We give a specialized procedure for the composition of those transducers that uses a flow analysis based on coherence spaces and allows us to preserve the linearity of transducers. This procedure has a better complexity than classical algorithms for composition of other equivalent tree transducers, but raises the order of transducers. However, we also indicate that the order of a HODTR lin can always be bounded by 3, and give a procedure that reduces the order of a HODTR lin to 3. As those resulting HODTR lin can then be transformed into other equivalent models, this gives an important insight on composition algorithm for other classes of transducers. Finally, we prove that those results partially translate to the case of almost linear HODTR: the class corresponds to the class of tree transformations performed by MSO with unfolding (not closed by composition), and provide a mechanism to reduce the order to 3 in this case.Lire moins >
Lire la suite >We introduce the notion of high-order deterministic top-down tree transducers (HODT) whose outputs correspond to simply-typed lambda-calculus formulas. These transducers are natural generalizations of known models of top-tree transducers such as: Deterministic Top-Down Tree Transducers, Macro Tree Transducers, Streaming Tree Transducers... We focus on the linear restriction of high order tree transducers with look-ahead (HODTR lin), and prove this corresponds to tree to tree functional transformations defined by Monadic Second Order (MSO) logic. We give a specialized procedure for the composition of those transducers that uses a flow analysis based on coherence spaces and allows us to preserve the linearity of transducers. This procedure has a better complexity than classical algorithms for composition of other equivalent tree transducers, but raises the order of transducers. However, we also indicate that the order of a HODTR lin can always be bounded by 3, and give a procedure that reduces the order of a HODTR lin to 3. As those resulting HODTR lin can then be transformed into other equivalent models, this gives an important insight on composition algorithm for other classes of transducers. Finally, we prove that those results partially translate to the case of almost linear HODTR: the class corresponds to the class of tree transformations performed by MSO with unfolding (not closed by composition), and provide a mechanism to reduce the order to 3 in this case.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-02902853v2/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02902853v2/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02902853v2/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- MFCS%202020.pdf
- Accès libre
- Accéder au document