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

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

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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, 2016 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, 2016 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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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