Re: CFL < ? < CSL

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 aaron@oak.ucsc.edu ...!ucscc!oak!aaron
--

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