Abstract
We present a formal model for stratificational linguistics, and examine its properties such as generative power, complexity of recognition and descriptional complexity. By relating stratificational grammars to control grammars and Szilard languages, we obtain a table of language families generated by stratificational grammars under several restrictions of linguistic interest. In the process, we show that context-sensitive control grammars with leftmost derivations are no more powerful than context-free ones, and, using this, resolve two open problems of Ginsburg and Spanier. Throughout the paper, formal results are interpreted in terms of their significance for linguistic theory and practice.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Y. Bar-Hillel,Language and Information, Addison-Wesley, Reading, Mass., 1964.
Y. Bar-Hillel, M. Perles and E. Shamir, “On formal properties of simple phrase structure grammars”,Zeitschrift fur Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14, 143–172 (1961).
R. Book, “Comparing complexity classes”,Journal of Computer and Systems Sciences, 9, 213–229 (1974).
R. V. Book and S. A. Greibach, “Quasi-realtime languages”,Mathematical Systems Theory, 4, 97–111 (1970).
R. Book, M. Nivat and M. Patterson, “Reversal-bounded acceptors and intersections of linear languages”,SIAM Journal of Computing, 3, 283–295 (1974).
A. T. Borgida, “Formal studies of stratificational grammars”, Ph.D. Dissertation, University of Toronto, 1977.
N. Chomsky, “Three models for the description of language”,IRE Transactions on Information Theory, 2, 113–124 (1956).
K. Culik II and C. J. W. Morey, “Formal schemes for language translation”,International Journal of Computer Mathematics, Section A, 3, 17–48 (1971).
F. L. DeRemer, “Transformational grammars”, Chapter 2E ofCompiler Construction — an advanced course (F. L. Bauer and J. Eickel, eds.), Springer Verlag, New York, 1974.
M. M. Geller, H. B. Hunt III, T. G. Szymanski and J. D. Ullman, “Economy of description by parsers, DPDA's and PDA's,Proceedings of 16th Annual Symposium on Foundations of Computer Science, 122–127 (1975).
S. Ginsburg,Algebraic and automata-theoretic properties of formal languages, North Holland, 1975.
S. Ginsburg and E. H. Spanier, “Control sets on grammars”,Mathematical Systems Theory, 2, 159–177 (1968).
H. A. Gleason, Jr., “The organization of language: a stratificational view”,Monograph Series on Language and Linguistics, 17, 75–95 (1964), Georgetown University.
H. A. Gleason, Jr., The architecture of language, unpublished manuscript, University of Toronto, (1973).
S. A. Greibach, “Control sets on context-free grammar forms”,Journal of Computer and Systems Sciences, 15, 35–98 (1975).
G. E. Heidorn, “Natural language inputs to a simulation programming system”, Technical Report NPS-55HD72101A, Naval Postgraduate School, Monterey, CA (1972).
J. E. Hopcroft and J. D. Ullman,Formal languages and their relation to automata, Addison-Wesley, New York, (1966).
S. Lamb,Outline of stratificational grammar, Georgetown University Press, Washington, (1966).
P. M. Lewis II and R. E. Stearns, “Syntax-directed translations”,Journal of the Association for Computing Machinery, 15, 464–488 (1968).
D. G. Lockwood,Introduction to stratificational grammar, Harcourt Brace Jovanovitch Inc., New York, (1972).
B. Monien, “A recursive and a grammatical characterization of the exponential time languages”,Theoretical Computer Science, 3, 61–74 (1975).
E. Moriya, “Associate languages and derivational complexity of formal grammars and languages”,Information and Control, 22, 139–162 (1973).
B. Nash and R. Cohen, “Parallel leveled grammars”,Proceedings of 10th Annual IEEE Symposium on Switching and Automata Theory, 263–276 (1969).
P. S. Peters and R. W. Ritchie, “On the generative power of transformational grammars”,Information Sciences, 6, 49–83 (1973).
P. Pit'ha, “On a new form of Lamb's stratificational grammar”,Slovo a Slovesnost, 35, 208–218 (1974); translated from the original Czech by D. G. Lockwood.
P. Postal, Constituent structure: a study of contemporary models of syntactic description, Indiana University, Bloomington, IN, (1964).
P. A. Reich, “The finiteness of natural language”,Language, 45, 831–843 (1969).
W. C. Rounds, “Complexity of recognition in intermediate level languages”,Proceedings of 14th IEEE Annual Symposium on Switching and Automata Theory, 145–158, (1973).
A. Salomaa,Formal languages, Academic Press, New York, (1973).
G. Sampson,Stratificational grammar: a definition and an example, Janua Linguarum, Series Minor: 88, Mouton, The Hague, (1970).
G. Sampson, “Review of D. Lockwood ‘Introduction to stratificational linguistics’”,Lingua, 34, 235–251 (1974).
S. J. Walljasper, “Left-derivation bounded languages”,Journal of Computer and Systems Sciences, 8, 1–7 (1974).
Author information
Authors and Affiliations
Additional information
This research was supported by the Natural Sciences and Engineering Research Council of Canada.
Rights and permissions
About this article
Cite this article
Borgida, A.T. Some formal results about stratificational grammars and their relevance to linguistics. Math. Systems Theory 16, 29–56 (1983). https://doi.org/10.1007/BF01744567
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01744567