patternMinor
What is examples of languages to prove the inclusions between families of languages generated by matrix grammars?
Viewed 0 times
generatedthewhatlanguagesgrammarsexamplesfamiliesproveinclusionsbetween
Problem
$\lambda M_{ac}$ = family of languages generated by matrix grammar with appearance checking and with erasing rules
$\lambda M$ = family of languages generated by matrix grammar without appearance checking and with erasing rules
$M_{ac}$ = family of languages generated by matrix grammar with appearance checking and without erasing rules
$M$ = family of languages generated by matrix grammar without appearance checking and without erasing rules
$RE$ = family of recursive enumerable languages
It is stated in [1] that
(a) $\lambda M \subset \lambda M_{ac} = RE$,
(b) $M \subset M_{ac} \subset CS$,
(c) $M \subseteq \lambda M$.
$M_{ac}$ can generate the language $L = \{a^{2^m} : m \geq 0 \}$, but $M$ probably cannot (if I'm not mistaken). Thus this yield the (b) above.
What are the examples of languages that can be used to prove the (a) and (c)?
Your shared wisdom, advice or hints are very appreciated.
[1] http://aleteya.cs.buap.mx/~jlavalle/papers/rewriting/tarraphd.pdf
$\lambda M$ = family of languages generated by matrix grammar without appearance checking and with erasing rules
$M_{ac}$ = family of languages generated by matrix grammar with appearance checking and without erasing rules
$M$ = family of languages generated by matrix grammar without appearance checking and without erasing rules
$RE$ = family of recursive enumerable languages
It is stated in [1] that
(a) $\lambda M \subset \lambda M_{ac} = RE$,
(b) $M \subset M_{ac} \subset CS$,
(c) $M \subseteq \lambda M$.
$M_{ac}$ can generate the language $L = \{a^{2^m} : m \geq 0 \}$, but $M$ probably cannot (if I'm not mistaken). Thus this yield the (b) above.
What are the examples of languages that can be used to prove the (a) and (c)?
Your shared wisdom, advice or hints are very appreciated.
[1] http://aleteya.cs.buap.mx/~jlavalle/papers/rewriting/tarraphd.pdf
Solution
To my knowledge, it is an open problem whether the inclusion (c) above
is strict. Some (baby) steps toward solving this problem can be found in
"Toward Understanding the Generative Capacity of Erasing Rules in Matrix Grammars", IJFCS 2011, http://dx.doi.org/10.1142/S0129054111008118
"On Erasing Productions in Random Context Grammars", ICALP 2010, http://dx.doi.org/10.1007/978-3-642-14162-1_15
"A Sufficient Condition for Erasing Productions to Be Avoidable", DLT 2011.
http://link.springer.com/chapter/10.1007%2F978-3-642-22321-1_39
is strict. Some (baby) steps toward solving this problem can be found in
"Toward Understanding the Generative Capacity of Erasing Rules in Matrix Grammars", IJFCS 2011, http://dx.doi.org/10.1142/S0129054111008118
"On Erasing Productions in Random Context Grammars", ICALP 2010, http://dx.doi.org/10.1007/978-3-642-14162-1_15
"A Sufficient Condition for Erasing Productions to Be Avoidable", DLT 2011.
http://link.springer.com/chapter/10.1007%2F978-3-642-22321-1_39
Context
StackExchange Computer Science Q#53340, answer score: 5
Revisions (0)
No revisions yet.