4
$\begingroup$

$\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

$\endgroup$
  • $\begingroup$ Do you mean $M \subset \lambda M$ in (c)? $\endgroup$ – Yuval Filmus Feb 19 '16 at 13:07
  • $\begingroup$ Please update your question accordingly. $\endgroup$ – Yuval Filmus Feb 21 '16 at 19:17
  • $\begingroup$ Before updating, please first check the source paper you link, see my answer below. $\endgroup$ – Hendrik Jan Feb 21 '16 at 21:35
4
$\begingroup$

The paper you link (Grammars with Regulated Rewriting, Jürgen Dassow, manuscript, 2006) gives more hints. Look at Theorem 2. The four types of matrix grammars are equivalent to the (slightly more general) four classes of regularly controlled grammars.

The fact that grammars without appearance checking are strictly less powerful than those with ac seems to have been obtained by Hauschildt and Jantzen. It is a consequence that without ac the languages over a single letter alphabet are regular. Dassow: "Since the known proofs for statement [..] use deep results from the theory of Petri nets [..] we omit a proof".

This should prove strict inclusions in (a) and (b). The inclusion in (c) is perhaps not known to be strict? It is just inclusion in Theorem 1 (iii).

D. Hauschildt, M. Jantzen, Petri net algorithms in the theory of matrix grammars. Acta Informatica 31 (1994) 719–728. doi 10.1007/BF01178731

Abstract. This paper shows that the languages over a one-letter alphabet generated by context-free matrix grammars are always regular. Moreover we give a decision procedure for the question of whether a context-free matrix language is finite. Hereby we strengthen a result of [Mäkinen, E.: On the generative capacity of context-free matrix grammars over one-letter alphabet 92] and settle a number of open questions in [Dassow, J., Pâun, G.: Regular rewriting in formal language theory 89]. Both results are obtained by a reduction to Petri net problems.

$\endgroup$
  • $\begingroup$ I've never thought to look into Petri Nets paper because didn't know they are related with matrix grammar and the answer is there. This is such a tremendous help, thanks so much! $\endgroup$ – kate Feb 24 '16 at 11:35
  • 1
    $\begingroup$ @kate Neither did I, but the authors solved this long standing open problem by linking them. For the single letter case as far as I know. $\endgroup$ – Hendrik Jan Feb 27 '16 at 10:21
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you so much for the articles and links. These'll be great help! $\endgroup$ – kate Jun 26 '16 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.