Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Tuesday, November 16, 2010 - 11:11:57 PM
Last modification on : Thursday, September 20, 2018 - 7:54:02 AM
Long-term archiving on: : Thursday, February 17, 2011 - 3:17:06 AM


Files produced by the author(s)


  • HAL Id : inria-00536823, version 1


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⟩



Record views


Files downloads