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.
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]
-
Preliminaries
-
The set of parse trees
-
An example: Peano naturals
-
Properties of parse trees
-
The example continued
-
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]