Journal of Formalized Mathematics
Volume 5, 1993
University of Bialystok
Copyright (c) 1993 Association of Mizar Users

On Defining Functions on Trees


Grzegorz Bancerek
Polish Academy of Sciences, Institute of Mathematics, Warsaw
Piotr Rudnicki
University of Alberta, Department of Computing Science, Edmonton

Summary.

The continuation of the sequence of articles on trees (see [2], [3], [4], [5]) and on context-free grammars ([13]). We define the set of complete parse trees for a given context-free grammar. Next we define the scheme of induction for the set and the scheme of defining functions by induction on the set. For each symbol of a context-free grammar we define the terminal, the pretraversal, and the posttraversal languages. The introduced terminology is tested on the example of Peano naturals.

This work was partially supported by NSERC Grant OGP9207 while the first author visited University of Alberta, May--June 1993.

MML Identifier: DTCONSTR

The terminology and notation used in this paper have been introduced in the following articles [17] [10] [21] [19] [1] [23] [22] [8] [9] [6] [12] [14] [18] [15] [16] [7] [20] [13] [2] [3] [4] [5] [11]

Contents (PDF format)

  1. Preliminaries
  2. The set of parse trees
  3. An example: Peano naturals
  4. Properties of parse trees
  5. The example continued
  6. Tree traversals and terminal language

Bibliography

[1] Grzegorz Bancerek. The fundamental properties of natural numbers. Journal of Formalized Mathematics, 1, 1989.
[2] Grzegorz Bancerek. Introduction to trees. Journal of Formalized Mathematics, 1, 1989.
[3] Grzegorz Bancerek. K\"onig's Lemma. Journal of Formalized Mathematics, 3, 1991.
[4] Grzegorz Bancerek. Sets and functions of trees and joining operations of trees. Journal of Formalized Mathematics, 4, 1992.
[5] Grzegorz Bancerek. Joining of decorated trees. Journal of Formalized Mathematics, 5, 1993.
[6] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Journal of Formalized Mathematics, 1, 1989.
[7] Czeslaw Bylinski. Binary operations. Journal of Formalized Mathematics, 1, 1989.
[8] Czeslaw Bylinski. Functions and their basic properties. Journal of Formalized Mathematics, 1, 1989.
[9] Czeslaw Bylinski. Functions from a set to a set. Journal of Formalized Mathematics, 1, 1989.
[10] Czeslaw Bylinski. Some basic properties of sets. Journal of Formalized Mathematics, 1, 1989.
[11] Czeslaw Bylinski. Binary operations applied to finite sequences. Journal of Formalized Mathematics, 2, 1990.
[12] Czeslaw Bylinski. Finite sequences and tuples of elements of a non-empty sets. Journal of Formalized Mathematics, 2, 1990.
[13] Patricia L. Carlson and Grzegorz Bancerek. Context-free grammar --- part I. Journal of Formalized Mathematics, 4, 1992.
[14] Agata Darmochwal. Finite sets. Journal of Formalized Mathematics, 1, 1989.
[15] Andrzej Nedzusiak. $\sigma$-fields and probability. Journal of Formalized Mathematics, 1, 1989.
[16] Andrzej Trybulec. Domains and their Cartesian products. Journal of Formalized Mathematics, 1, 1989.
[17] Andrzej Trybulec. Tarski Grothendieck set theory. Journal of Formalized Mathematics, Axiomatics, 1989.
[18] Andrzej Trybulec. Tuples, projections and Cartesian products. Journal of Formalized Mathematics, 1, 1989.
[19] Andrzej Trybulec. Subsets of real numbers. Journal of Formalized Mathematics, Addenda, 2003.
[20] Wojciech A. Trybulec. Binary operations on finite sequences. Journal of Formalized Mathematics, 2, 1990.
[21] Zinaida Trybulec. Properties of subsets. Journal of Formalized Mathematics, 1, 1989.
[22] Edmund Woronowicz. Relations and their basic properties. Journal of Formalized Mathematics, 1, 1989.
[23] Edmund Woronowicz. Relations defined on sets. Journal of Formalized Mathematics, 1, 1989.

Received October 12, 1993

[ Download a postscript version, MML identifier index, Mizar home page]