Abstract
Feature trees generalize first-order trees whereby argument positions become keywords (“features”) from an infinite symbol set F. 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 F 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.
Partially supported by Graduierten-Kolleg Informatik der Universität des Saarlandes.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Hassan Aït-Kaci. An algebraic semantics approach to the effective resolution of type equations. Theoretical Computer Science, 45:293–351, 1986.
Hassan Aït-Kaci and Andreas Podelski. Functional constraints in LIFE. PRL Research Report 13, Digital Equipment Corporation, Paris Research Laboratory, Rueil-Malmaison, France, 1991.
Hassan Aït-Kaci and Andreas Podelski. Towards a meaning of LIFE. In J. Maluszyński and M. Wirsing, editors, Proceedings of the 3rdInlernationalSymposiumon Programming Language Implementation and Logic Programming, Springer LNCS vol. 528, pages 255–274. Springer-Verlag, 1991.
Hassan Aït-Kaci, Andreas Podelski, and Gert Smolka. A feature-based constraint system for logic programming with entailment. In Proceedings of the 5 th International Conference onFiflh Generation Computer Systems, pages 1012–1022, Tokyo, Japan, June 1992. ICOT.
Rolf Backofen and Gert Smolka. A complete and recursive feature theory. Research Report RR-92-30, German Research Center for Artificial Intelligence (DFKI), Stuhlsatzenhausweg 3, 6600 Saarbrücken 11, Germany, September 1992.
Bob Carpenter. The Logic of Typed Feature Structures, volume 32 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, UK, 1992.
Hubert Comon and Catherine Delors. Equational formula with membership constraints,. Rapport de recherche 648, LRI, Universit de Paris Sud, March 1991. To appear in Information and Computation.
Bruno Courcelle. On recognizable sets and tree automata. In Hassan Ait-Kaci and Maurice Nivat, editors, Resolution of Equations in Algebraic Structures, Algebraic Techniques, volume 1, chapter 3, pages 93–126. Academic Press, 1989.
Bruno Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation 85, pages 12–75, 1990.
Bruno Courcelle. Recognizable sets of unrooted trees. In Maurice Nivat and Andreas Podelski, editors, Tree Automata, Advances and Open Problems. Elsevier Science, 1992.
John E. Doner. Tree Acceptors and some of their applications. Journal of Comp. System Sci. 4, pages 406–451, 1970.
Samuel Eilenberg. Automata, Language and Machine, volume A of Applied and Pure Mathematics. Academic Press, 1974.
F. Gécseg and M. Steinby. Tree Automata. Akadémiai Kiadó, Budapest, 1984.
Michael J. Maher. Complete axiomatizations of the algebras of finite, rational and infinite trees. In LICS, pages 348–457, July 1988.
Maurice Nivat. Elements of a theory of tree codes. In Maurice Nivat and Andreas Podelski, editors, Tree Automata, Advances and Open Problems. Elsevier Science, 1992.
William C. Rounds. Set values for unification-based grammar formalisms and logic programming. Report CSLI-88-129, 1988.
Gert Smolka. Feature constraint logics for unification grammars. Journal of Logic Programming, 12:51–87, 1992.
Gert Smolka and Ralf Treinen. Records for logic programming. In Proceedings of the 1992 Joint International Conference and Symposium on Logic Programming, Washington, DC, November 1992. The MIT Press, to appear.
J. W. Thatcher and J. B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory, 2(1):57–81, August 1967. Published by Springer-Verlag NY Inc.
Ralf Treinen. A New Method for Undecidability Proofs of First Order Theories. Journal of Symbolic Compulation, 14:437–457, 1992.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Niehren, J., Podelski, A. (1993). Feature automata and recognizable sets of feature trees. In: Gaudel, M.C., Jouannaud, J.P. (eds) TAPSOFT'93: Theory and Practice of Software Development. CAAP 1993. Lecture Notes in Computer Science, vol 668. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56610-4_76
Download citation
DOI: https://doi.org/10.1007/3-540-56610-4_76
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56610-6
Online ISBN: 978-3-540-47598-9
eBook Packages: Springer Book Archive