Re: Between Regular and Context Free Languages

Leif Nixon <nixon@softlab.se>
25 Jan 1997 21:58:19 -0500

          From comp.compilers
Related articles
Between Regular and Context Free Languages loewe@ipd.info.uni-karlsruhe.de (Welf Loewe) (1997-01-22)
Re: Between Regular and Context Free Languages torbenm@diku.dk (1997-01-25)
Re: Between Regular and Context Free Languages nixon@softlab.se (Leif Nixon) (1997-01-25)
| List of all articles for this month |
From: Leif Nixon <nixon@softlab.se>
Newsgroups: comp.compilers
Date: 25 Jan 1997 21:58:19 -0500
Organization: Ericsson
References: 97-01-176
Keywords: parse, theory

Welf Loewe <loewe@ipd.info.uni-karlsruhe.de> writes:


> Are there classes of languages R* with
>
> Regular Languages \subset R* \subset context free languages
>
> such that
>
> L, L' \in R* ==> L \subset L' is decidable?
> L, L' \in R* ==> L \subset L' is efficiently computable?
>
> Can anyone point me to references on Dyck languages
> and on (regular) tree languages. Are these classes of
> languages candidates for R*?


Regular tree languages, AKA regular term languages, do
indeed fulfil your criteria. A very nice paper describing
algorithms for performing the ordinary set operations on
regular term languges is:


R. Topor, J. Zobel: Operations on regular term grammars.
    Technical Report 44, Key Centre for Knowledge Based Systems,
    University of Melbourne and RMIT, Australia, 1991.




Leif Nixon SoftLab AB
-------------------------------------------------
E-mail: nixon@softlab.se Phone: +46 13 23 57 61
--

Post a followup to this message

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