tree language

A Dictionary of Computing | 2004 | 674 words | Copyright

tree language (term language) In formal language theory, a generalization of the notion of language, applying to trees (often called terms in this context) rather than strings. Alphabets are extended to give each symbol an arity, the arity of each symbol dictating the number of subterms, or descendants in the tree, that it has.

For example, let Σ be the alphabet {f,g,a,b} and give arities 2,1,0,0 to f,g,a,b respectively. Then examples of Σ-trees and their equivalent representations as Σ-terms (or well-formed expressions over Σ) are shown in the diagram. A Σ-language is now any set of Σ-terms. See also tree grammar, tree automaton.

Cite this article
Pick a style below, and copy the text for your bibliography.

MLA
Chicago
APA

JOHN DAINTITH. "tree language." A Dictionary of Computing. 2004. Encyclopedia.com. 27 May. 2012 <http://www.encyclopedia.com>.

JOHN DAINTITH. "tree language." A Dictionary of Computing. 2004. Encyclopedia.com. (May 27, 2012). http://www.encyclopedia.com/doc/1O11-treelanguage.html

JOHN DAINTITH. "tree language." A Dictionary of Computing. 2004. Retrieved May 27, 2012 from Encyclopedia.com: http://www.encyclopedia.com/doc/1O11-treelanguage.html

Learn more about citation styles