Feature Automata and Recognizable Sets of Feature Trees

Abstract : 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.
Type de document :
Communication dans un congrès
Marie-Claude Gaudel and Jean-Pierre Jouannaud. TAPSOFT: Theory and Practice of Software Development: Joint International Conference CAAP/FASE/TOOLS., 1993, Orsay, France. Springer, 668, pp.356--375, 1993, Lecture Notes on Computer Science
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00536823
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 23:11:57
Dernière modification le : lundi 20 novembre 2017 - 15:14:01
Document(s) archivé(s) le : jeudi 17 février 2011 - 03:17:06

Fichiers

CAAP1993.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536823, version 1

Citation

Joachim Niehren, Andreas Podelski. Feature Automata and Recognizable Sets of Feature Trees. Marie-Claude Gaudel and Jean-Pierre Jouannaud. TAPSOFT: Theory and Practice of Software Development: Joint International Conference CAAP/FASE/TOOLS., 1993, Orsay, France. Springer, 668, pp.356--375, 1993, Lecture Notes on Computer Science. 〈inria-00536823〉

Partager

Métriques

Consultations de la notice

94

Téléchargements de fichiers

98