Re: CFL < ? < CSL

oak! (Aaron Emigh)
4 Jul 91 09:40:30 GMT

          From comp.compilers

Related articles
CFL < ? < CSL (1991-06-25)
Re: CFL < ? < CSL oak! (1991-07-04)
| List of all articles for this month |

Newsgroups: comp.theory,comp.compilers
From: oak! (Aaron Emigh)
Followup-To: comp.theory
Summary: indexed languages
Keywords: parse, indexed languages
Organization: University of California, Santa Cruz
References: 91-07-005
Date: 4 Jul 91 09:40:30 GMT

Amr Sabry writes:
>My question is whether there exists a class of languages lying properly
>between context-free languages and context-sensitive languages and that is
>"efficiently" recognizable.

It depends on what you mean by "efficiently" -- most people would say
that context-free languages cannot be recognized efficiently enough to
use, for example, a general context-free parser in a compiler.

The most noteworthy class of languages lying properly between CFLs and
CSLs with which I am aware is the class of indexed grammars. The basic
reference on this is Aho '68; there are some others too (and I'm sure I
don't have them all here).

Alfred Aho, "Indexed Grammars," JACM 15:4 (1968), 647-671.
Alfred Aho, "Nested Stack Automata," JACM 16:3 (1969), 383-406.
S. A. Greibach, "Full AFL's and Nested Iterated Substitution,"
Information and Control 16:1 (1970), 7-35.
Takeshi Hayashi, "On Derivation Trees of Indexed Grammars..." Pub. RIMS
(Kyoto University) 9:1 (1973), 61-92.
T. S. E. Maibaum, "A Generalized Approach to Formal Languages," J.
Computer and Systems Science 8:3 (1974), 409-439.
Parchmann, Duske, Specht, "On Deterministic Indexed Languages,"
Information and Control 45 (1980), 48-67.
Parchmann, Duske, Specht, "Closure Properties of Deterministic Indexed
Languages," Information and Control 46 (1980), 200-218.

Aaron Emigh ...!ucscc!oak!aaron

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.