Regular tree grammar

In theoretical computer science and formal language theory, a regular tree grammar (RTG) is a formal grammar that describes a set of directed trees, or terms.[1] 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

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 t1TΣ(N) can be derived in a single step into a tree t2TΣ(N) (in short: t1G t2), if there is a context S and a production (At) ∈ P such that:

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 L(G) = { tTΣ | ZG* t }.

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

Example derivation tree from G1 in linear (upper left table) and graphical (main picture) notation

Let G1 = (N11,Z1,P1), where

An example derivation from the grammar G1 is

BListcons(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 G1 is the set of all finite lists of boolean values, that is, L(G1) happens to equal TΣ1. The grammar G1 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(G1) corresponds to a Standard-ML value of type BList.

For another example, let G2 = (N11,BList1,P1P2), using the nonterminal set and the alphabet from above, but extending the production set by P2, consisting of the following productions:

The language L(G2) is the set of all finite lists of boolean values that contain true at least once. The set L(G2) has no datatype counterpart in Standard ML, nor in any other functional language. It is a proper subset of L(G1). The above example term happens to be in L(G2), too, as the following derivation shows:

BList1cons(false,BList1) ⇒ cons(false,cons(true,BList)) ⇒ cons(false,cons(true,nil)).

Language properties

If L1, L2 both are regular tree languages, then the tree sets L1L2, L1L2, and L1 \ L2 are also regular tree languages, and it is decidable whether L1L2, and whether L1 = L2.

Alternative characterizations and relation to other formal languages

Rajeev Alur and Parthasarathy Madhusudan related a subclass of regular binary tree languages to nested words and visibly pushdown languages.[2][3]

The regular tree languages are also the languages recognized by bottom-up tree automata and nondeterministic top-down tree automata.[4]

Regular tree grammars are a generalization of regular word grammars.

Applications

Applications of regular tree grammars include:

See also

References

  1. "Regular tree grammars as a formalism for scope underspecification". CiteSeerX: 10.1.1.164.5484.
  2. Alur, R.; Madhusudan, P. (2004). "Visibly pushdown languages" (PDF). Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04. pp. 202–211. doi:10.1145/1007352.1007390. ISBN 1581138520. Sect.4, Theorem 5,
  3. Alur, R.; Madhusudan, P. (2009). "Adding nesting structure to words" (PDF). Journal of the ACM 56 (3): 1–43. doi:10.1145/1516512.1516518. Sect.7
  4. Comon, Hubert; Dauchet, Max; Gilleron, Remi; Löding, Christof; Jacquemard, Florent; Lugiez, Denis; Tison, Sophie; Tommasi, Marc (12 October 2007). "Tree Automata Techniques and Applications". Retrieved 25 January 2016.
  5. Emmelmann, Helmut (1991). "Code Selection by Regularly Controlled Term Rewriting". Code Generation - Concepts, Tools, Techniques. Workshops in Computing. Springer. pp. 3–29.
  6. Comon, Hubert (1990). "Equational Formulas in Order-Sorted Algebras". Proc. ICALP.
  7. Gilleron, R.; Tison, S.; Tommasi, M. (1993). "Solving Systems of Set Constraints using Tree Automata". 10th Annual Symposium on Theoretical Aspects of Computer Science. LNCS. Springer. pp. 505–514.
  8. Burghardt, Jochen (2002). "Axiomatization of Finite Algebras" (PDF). Advances in Artificial Intelligence. LNAI. Springer. pp. 222–234. ISBN 3-540-44185-9.

Further reading

This article is issued from Wikipedia - version of the Monday, January 25, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.