1967 · 36 citations · 9 references
ComputingComputer ScienceAlgorithmsProgramming LanguagesSyntaxAutomata TheoryContext-free LanguagesFinite AutomataGrammarPushdown AutomataSyntax AnalysisClosure PropertiesContext-free GrammarsContext-sensitive LanguagesDecidabilityIndexed GrammarsLanguage Closure PropertiesNested Stack AutomataStack Automata
A new type of grammar, called an indexed grammar, is defined. The language generated by an indexed grammar is called an indexed language. The class of indexed languages properly includes the class of context free languages and is a proper subset of the class of context sensitive languages. The closure properties and decidability results for the class of indexed languages are similar to those for the class of context free languages. An exact characterization of this new class of languages is provided by a new recognition device called a nested stack automaton. Special cases of the nested stack automaton include the pushdown automaton, the stack automaton, and the reading pushdown automaton. The class of indexed languages seems to be a closer approximation to the class of algorithmic programming languages than either the class of context free languages or the class of context sensitive languages.
9
The mathematical theory of context-free languages
H. P. Edmundson · Information Storage and Retrieval · 1967 · 738 citations
Classes of languages and linear-bounded automata
S.-Y. Kuroda · Information and Control · 1964 · 271 citations
Seymour Ginsburg, Sheila A. Greibach, Michael A. Harrison · Journal of the ACM · 1967 · 225 citations · Full text
Abstract families of languages
Seymour Ginsburg, Sheila A. Greibach · 1967 · 201 citations
Language Studies, Computer Science, Computational Linguistics +7
Seymour Ginsburg, Sheila A. Greibach, Michael A. Harrison · Journal of the ACM · 1967 · 141 citations · Full text