Publication details

Saarland University Computer Science

Feature Automata and Recognizable Sets of Feature Trees

Joachim Niehren, Andreas Podelski

Theory and Practice of Software Development, International Joint Conference CAAP/FASE/TOOLS, Vol. 1214 of LNCS, pp. 356--375, springer, 1993

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.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009