In Computer Science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, a regular tree grammar (RTG) is a formal grammar

Formal grammar

A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...

 that describes a set of directed trees

Tree (graph theory)

In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...

.

Definition

A regular tree grammar is defined by the tuple

,

where

• is a set of nonterminals,
• is a ranked alphabet (i.e., an alphabet whose symbols have an associated arity
  Arity
  In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...
  
  ) disjoint from ,
• is the starting nonterminal, with , and
• is a set of productions of the form , where , and , where is the associated term algebra.

Derivation of Trees

The grammar implicitly defines a set of trees: any
tree that can be derived from using the rule set is said to be described by .
This set of trees is known as the language

Formal language

A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

 of .
To express this more formally,
we define the relation on the set as follows:

For every , if there is a context and a production such that:

• , and
• .

The tree language generated by is the language

.

Where denotes successive applications of . Such languages are called Tree languages.

Relation to other formal languages

As shown by Rajeev Alur and Parthasarathy Madhusudan the class of regular tree languages coincides with nested word

Nested word

In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of ordered unranked trees, as traditionally used for...

s and visibly pushdown languages.