Size, index, and context-sensitivity of controlled partition grammars
Tóm tắt
Controlled partition grammars (CPGs) were designed to apply to certain needs of linguists. General CPGs generate exactly all context-sensitive languages. CPGs have two parameters:size andindex. The partition index of CPGs can be bounded by two, while CPGs with partition index one generate exactly the class of context-free languages. The size (of the partition blocks) of CPGs can be bounded by two, while CPGs of size one generate a class of languages properly contained in the class of contextsensitive languages. If one can eliminate recursive productions of the formA→B in a CPG then deterministic and nondeterministic lba's are equivalent.
Tài liệu tham khảo
S. Abraham, Some Questions of Phrase Structure Grammars,Computational Linguistics 4 (1965), 61–70.
A. Aho, Indexed Grammars, an Extension of Context-Free Grammars,JACM 15 (October 1968), 647–671.
N. Chomsky, On Certain Formal Properties of Grammars,Information and Control 2 (June 1959), 137–167.
N. Chomsky,Aspects of the Theory of Syntax, The MIT Press, Cambridge, Mass. 1965.
A. B. Cremers, Normal Forms for Context-Sensitive Grammars,Acta Informatica 3 (1973), 59–73.
A. B. Cremers andO. Mayer, On Matrix Languages,Information and Control 23 (1973), 86–96.
A. B. Cremers andO. Mayer, On Vector Languages,J. Computer and System Sciences 8 (1974), 158–166.
A. B. Cremers, H. A. Maurer, andO. Mayer, A Note on Leftmost Restricted Random Context Grammars,Information Processing Letters 2 (1973), 31–33.
I. Fris, Grammars with Partial Ordering of the Rules,Information and Control 12 (1968), 415–425.
S. Ginsburg andB. H. Partee, A Mathematical Model of Transformational Grammars,Information and Control 15 (October 1969), 297–334.
S. Ginsburg andE. H. Spanier, Control Sets on Grammars,Math. Systems Theory 2 (1968), 159–177.
S. A. Greibach andJ. E. Hopcroft, Scattered Context Grammars,J. Computer and System Sciences 3 (1969), 233–247.
J. E. Hopcroft andJ. D. Ullman,Formal Languages and their Relation to Automata, Reading, Mass., Addison-Wesley, 1969.
T. Kasai, An Hierarchy Between Context-Free and Context-Sensitive Languages,J. Computer and System Sciences 4 (1970), 492–508.
S.-Y. Kuroda, Classes of Languages and Linear-Bounded Automata,Information and Control 7 (1964), 207–223.
H. A. Maurer, Simple Matrix Languages with a Leftmost Restriction,Information and Control 23 (1973), 128–139.
O. Mayer, Some Restrictive Devices for Context-Free Grammars,Information and Control 20 (1972), 69–92.
D. L. Milgram andA. Rosenfeld, A Note on Scattered Context Grammars,Information Processing Letters 1 (1971), 47–50.
B. O. Nash, Context-Free Parallel-Levelled Grammars, Ph.D. Thesis, University of Waterloo, Ontario 1970.
S. Peters andR. Ritchie, On the Generative Power of Transformational Grammar,Information Sciences 6 (1973), 49–83.
G. Rozenberg, Direction Controlled Programmed Grammars,Acta Informatica 1 (1972), 242–252.
D. J. Rosenkrantz, Programmed Grammars and Classes of Formal Languages,JACM 16 (1969), 107–131.
A. Salomaa, Periodically Time-Variant Context-Free Grammars,Information and Control 17 (1970), 294–311.
A. Salomaa, Matrix Grammars with a Leftmost Restriction,Information and Control 20 (1972), 143–149.
A. Salomaa,Formal Languages, New York, Academic Press, 1973.
W. Savitch, Relationships Between Nondeterministic and Deterministic Tape Complexities,J. Computer and System Sciences 4 (1970), 177–192.
J. van Leeuwen, A Partial Solution to the Reachability Problem for Vector Addition Systems,6th Ann. ACM Symp. on Theory of Computing (May 1974), 303–309.
E.-M. M. Wotschke, Ordered Grammars with Equivalence Classes: Some Formal and Linguistic Aspects, Ph.D. Thesis, University of California, Los Angeles, 1975.