Regular Tree Grammar vs. Context-Free Grammar
- From: Eric Wohlstadter <wohlstad@xxxxxxxxx>
- Date: Thu, 07 Dec 2006 15:35:35 -0800
Hello,
I am wondering if anyone can help me with information about the relationship between regular tree grammars and CFGs? In particular do the languages accepted by CFGs include (subsume) the languages accepted by regular tree grammars?
I assume that the languages accepted by a regular tree grammar include (subsume) the languages accepted by regular word grammars, is that correct?
The only information I have so far is that the inclusion problem between regular tree grammars is decidable but the inclusion problem between CFGs is undecidable. This leads be to believe that CFGs are more powerful. Also I see that the set of derivation trees of a CFG is a regular tree grammar. Still, I can't find any other information about their relationship. Thanks in advance for any pointers,
Eric Wohlstadter
Assistant Professor
University of British Columbia
.
- Follow-Ups:
- Re: Regular Tree Grammar vs. Context-Free Grammar
- From: Ben Bacarisse
- Re: Regular Tree Grammar vs. Context-Free Grammar
- Prev by Date: Re: A stupid thought about Hamilton Path problem
- Next by Date: Re: Regular Tree Grammar vs. Context-Free Grammar
- Previous by thread: Quantum Computation By Adiabatic Evolution
- Next by thread: Re: Regular Tree Grammar vs. Context-Free Grammar
- Index(es):