25 Jan 1997 21:58:19 -0500

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) |

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.