Feature Automata and Recognizable Sets of Feature Trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 1993

Feature Automata and Recognizable Sets of Feature Trees

Résumé

Feature trees generalize first-order trees whereby argument positions become keywords (features) from an infinite symbol set . Constructor symbols can occur with any argument positions, in any finite number. Feature trees are used to model flexible records; the assumption on the infiniteness of accounts for dynamic record field updates. We develop a universal algebra framework for feature trees. We introduce the classical set-defining notions: automata, regular expressions and equational systems, and show that they coincide. This extension of the regular theory of trees requires new notions and proofs. Roughly, a feature automaton reads a feature tree in two directions: along its branches and along the fan-out of each node. We illustrate the practical motivation of our regular theory of feature trees by pointing out an application on the programming language LIFE.
Fichier principal
Vignette du fichier
CAAP1993.pdf (296.52 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00536823 , version 1 (16-11-2010)

Identifiants

  • HAL Id : inria-00536823 , version 1

Citer

Joachim Niehren, Andreas Podelski. Feature Automata and Recognizable Sets of Feature Trees. TAPSOFT: Theory and Practice of Software Development: Joint International Conference CAAP/FASE/TOOLS., 1993, Orsay, France. pp.356--375. ⟨inria-00536823⟩
60 Consultations
159 Téléchargements

Partager

Gmail Facebook X LinkedIn More