Complexity and Application
Tree-adjoining grammars are often described as mildly context-sensitive, meaning that they possess certain properties that make them more powerful (in terms of weak generative capacity) than context-free grammars, but less powerful than indexed or context-sensitive grammars. Mildly context-sensitive grammars are conjectured to be powerful enough to model natural languages while remaining efficiently parsable in the general case.
A TAG can describe the language of squares (in which some arbitrary string is repeated), and the language . This type of processing can be represented by an embedded pushdown automaton.
Languages with cubes (i.e. triplicated strings) or with more than four distinct character strings of equal length cannot be generated by tree-adjoining grammars.
For these reasons, languages generated by tree-adjoining grammars are referred to as mildly context-sensitive languages.
Read more about this topic: Tree-adjoining Grammar
Famous quotes containing the words complexity and/or application:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)
“Most people, no doubt, when they espouse human rights, make their own mental reservations about the proper application of the word “human.””
—Suzanne Lafollette (1893–1983)