Control Language Hierarchy
A more precisely defined hierarchy of languages that correspond to the mildly context-sensitive class was defined by David J. Weir. Based on the work of Nabil A. Khabbaz, Weir's Control Language Hierarchy is a containment hierarchy of countable set of language classes where the Level-1 is defined as context-free, and Level-2 is the class of tree-adjoining and the other three grammars.
Following are some of the properties of Level-k languages in the hierarchy:
- Level-k languages are properly contained in the Level-(k + 1) language class
- Level-k languages can be parsed in time
- Level-k contains the language, but not
- Level-k contains the language, but not
Those properties correspond well (at least for small k > 1) to the conditions of mildly context-sensitive languages imposed by Joshi, and as k gets bigger, the language class becomes, in a sense, less mildly context-sensitive.
Read more about this topic: Mildly Context-sensitive Language
Famous quotes containing the words control, language and/or hierarchy:
“Just as men must give up economic control when their wives share the responsibility for the family’s financial well-being, women must give up exclusive parental control when their husbands assume more responsibility for child care.”
—Augustus Y. Napier (20th century)
“Philosophy is written in this grand book—I mean the universe—
which stands continually open to our gaze, but it cannot be understood unless one first learns to comprehend the language and interpret the characters in which it is written. It is written in the language of mathematics, and its characters are triangles, circles, and other geometrical figures, without which it is humanly impossible to understand a single word of it.”
—Galileo Galilei (1564–1642)
“In a hierarchy every employee tends to rise to his level of incompetence.”
—Laurence J. Peter (1919–1990)