main problems III

Other interesting problems

There are other interesting problems that can be studied. I introduce in this post some of them, which I hopefully will try to address in future contributions.

One that I think is very interesting and that I call redundancy can be stated as follows. For a given MGG (matrix graph grammar) decide whether there are redundant productions. A redundant production is one that can be written as a sequence of some of the other productions in the grammar. This is inspired by the notion of base in vector spaces. In essence we are asking to find minimal grammars to express some given language. 

Liveness is a notion from Petri nets, and asks for the (potential) applicability of some production. In fact it can be used as a halting condition for matrix graph grammars, in particular when they are extended using affine productions (a post to come on this). Other concpets can be of interest, also taken from Petri nets, such as boundedness. Enough for today.

Today's quote's from Billy Connely: I have been made redundant before and it is a terrible blow; redundant is a rotten word because it makes you think you are useless.