Regular Tree Grammar

In theoretical computer science and formal language theory, a regular tree grammar is a formal grammar that describes a set of directed trees, or terms. A regular word grammar can be seen as a special kind of regular tree grammar, describing a set of single-path trees.

Definition

A regular tree grammar ''G'' is defined by the tuple

''G'' = (''N'', Σ, ''Z'', ''P''),

where

* ''N'' is a finite set of nonterminals,
* Σ is a ranked alphabet (i.e., an alphabet whose symbols have an associated arity) disjoint from ''N'',
* ''Z'' is the starting nonterminal, with , and
* ''P'' is a finite set of productions of the form ''A'' → ''t'', with , and , where ''T''_Σ(''N'') is the associated term algebra, i.e. the set of all trees composed from symbols in according to their arities, where nonterminals are considered nullary.

Derivation of trees

The grammar ''G'' implicitly defines a set of trees: any tree that can be derived from ''Z'' using the rule set ''P'' is said to be described by ''G''.
This set of trees is known as the language of ''G''.
More formally, the relation ⇒_''G'' on the set ''T''_Σ(''N'') is defined as follows:

A tree can be derived in a single step into a tree
(in short: ''t''₁ ⇒_''G'' ''t''₂), if there is a context ''S'' and a production such that:

* ''t''₁ = ''S'' 'A'' and
* ''t''₂ = ''S'' 't''

Here, a ''context'' means a tree with exactly one hole in it; if ''S'' is such a context, ''S'' 't''denotes the result of filling the tree ''t'' into the hole of ''S''.

The tree language generated by ''G'' is the language .

Here, ''T''_Σ denotes the set of all trees composed from symbols of Σ, while ⇒_''G''* denotes successive applications of ⇒_''G''.

A language generated by some regular tree grammar is called a regular tree language.

Examples

Let ''G''₁ = (''N''₁,Σ₁,''Z''₁,''P''₁), where
* ''N''₁ = is our set of nonterminals,
* Σ₁ = is our ranked alphabet, arities indicated by dummy arguments (i.e. the symbol ''cons'' has arity 2),
* ''Z''₁ = ''BList'' is our starting nonterminal, and
* the set ''P''₁ consists of the following productions:
** ''Bool'' → ''false''
** ''Bool'' → ''true''
** ''BList'' → ''nil''
** ''BList'' → ''cons''(''Bool'',''BList'')

An example derivation from the grammar ''G''₁ is

''BList''
⇒ ''cons''(''Bool'',''BList'')
⇒ ''cons''(''false'',''cons''(''Bool'',''BList''))
⇒ ''cons''(''false'',''cons''(''true'',''nil'')).

The image shows the corresponding derivation tree; it is a tree of trees (main picture), whereas a derivation tree in word grammars is a tree of strings (upper left table).

The tree language generated by ''G''₁ is the set of all finite lists of boolean values, that is, ''L''(''G''₁) happens to equal ''T''_Σ1.
The grammar ''G''₁ corresponds to the algebraic data type declarations (in the Standard ML programming language):

datatype Bool
= false
, true
datatype BList
= nil
, cons of Bool * BList

Every member of ''L''(''G''₁) corresponds to a Standard-ML value of type BList.

For another example, let , using the nonterminal set and the alphabet from above, but extending the production set by ''P''₂, consisting of the following productions:
* ''BList'' → ''cons''(''true'',''BList'')
* ''BList'' → ''cons''(''false'',''BList'')
The language ''L''(''G''₂) is the set of all finite lists of boolean values that contain ''true'' at least once. The set ''L''(''G''₂) has no datatype counterpart in Standard ML, nor in any other functional language.
It is a proper subset of ''L''(''G''₁).
The above example term happens to be in ''L''(''G''₂), too, as the following derivation shows:

''BList''
⇒ ''cons''(''false'',''BList'')
⇒ ''cons''(''false'',''cons''(''true'',''BList''))
⇒ ''cons''(''false'',''cons''(''true'',''nil'')).

Language properties

If ''L''₁, ''L''₂ both are regular tree languages, then the tree sets , and ''L''₁ \ ''L''₂ are also regular tree languages, and it is decidable whether , and whether ''L''₁ = ''L''₂.

Alternative characterizations and relation to other formal languages

*Regular tree grammars are a generalization of regular word grammars.
*The regular tree languages are also the languages recognized by bottom-up tree automata and nondeterministic top-down tree automata.
*Rajeev Alur and Parthasarathy Madhusudan related a subclass of regular binary tree languages to nested words and visibly pushdown languages. Sect.4, Theorem 5, Sect.7

Applications

Applications of regular tree grammars include:
* Instruction selection in compiler code generation
* A decision procedure for the first-order logic theory of formulas over equality (=) and set membership (∈) as the only predicates
* Solving constraints about mathematical sets
* The set of all truths expressible in first-order logic about a finite algebra (which is always a regular tree language)
* Graph-search
/ref>

See also

* Set constraint – a generalization of regular tree grammars
* Tree-adjoining grammar

References

Further reading

* Regular tree grammars were already described in 1968 by:
**
**
* A book devoted to tree grammars is:
* Algorithms on regular tree grammars are discussed from an efficiency-oriented view in:
* Given a mapping from trees to weights, Donald Knuth's generalization of Dijkstra's shortest-path algorithm can be applied to a regular tree grammar to compute for each nonterminal the minimum weight of a derivable tree. Based on this information, it is straightforward to enumerate its language in increasing weight order. In particular, any nonterminal with infinite minimum weight produces the empty language. See:
* Regular tree automata have been generalized to admit equality tests between sibling nodes in trees. See:
* Allowing equality tests between deeper nodes leads to undecidability. See:

{{Formal languages and grammars , state=collapsed

Formal languages