Regular Tree Grammar - Alternative Characterizations and Relation To Other Formal Languages

Alternative Characterizations and Relation To Other Formal Languages

As shown by Rajeev Alur and Parthasarathy Madhusudan the class of regular tree languages coincides with nested words and visibly pushdown languages.

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

Regular tree grammars are a generalization of regular word grammars.

Read more about this topic:  Regular Tree Grammar

Famous quotes containing the words alternative, relation, formal and/or languages:

    It is a secret from nobody that the famous random event is most likely to arise from those parts of the world where the old adage “There is no alternative to victory” retains a high degree of plausibility.
    Hannah Arendt (1906–1975)

    The psychoanalysis of individual human beings, however, teaches us with quite special insistence that the god of each of them is formed in the likeness of his father, that his personal relation to God depends on his relation to his father in the flesh and oscillates and changes along with that relation, and that at bottom God is nothing other than an exalted father.
    Sigmund Freud (1856–1939)

    This is no argument against teaching manners to the young. On the contrary, it is a fine old tradition that ought to be resurrected from its current mothballs and put to work...In fact, children are much more comfortable when they know the guide rules for handling the social amenities. It’s no more fun for a child to be introduced to a strange adult and have no idea what to say or do than it is for a grownup to go to a formal dinner and have no idea what fork to use.
    Leontine Young (20th century)

    It is time for dead languages to be quiet.
    Natalie Clifford Barney (1876–1972)