initial graphs (minimal and negative initial digraphs)
One of the main advantages of MGG over other approaches to graph transformation is its ability to study properties of the grammar independently of the initial state. Thus, it is possible to define an algortihm (productions of a grammar) and analyse some of its properties without taking into account the concrete problem it is going to be applied to.
For a given sequence, one natural question is the minimal (smallest) graph that we have to be given in order to apply the sequence. Recall that MGG is not only able to study the elements that have to be present in order to apply a production, but also those that must not be in the initial graph. The minimal initial digraph (MID) is precisely this smallest graph. The negative initial digraph (NID) specifies those elements that should not appear in the host graph. They both can be explicitely calculated. Sections 4.4 and 5.3 in the MGG book are devoted to this topic. It is interesting that we can use this concepts to contribute to Petri nets (Sec. 8.2).
The main importance of the initial digraphs is that they substitute the host graph in those cases where some initial state is mandatory. For example, when dealing with universal quantifiers in application conditions. Hence, the analysis of the grammar productions can be performed without the need of a concrete host graph.
In previous posts I have commented on non-determinism in MGG, being one of its sources how nodes across productions are related (whether two nodes of the same type in different productions have to be the same node or not). If we have in mind a concrete sequence, as soon as the left hand sides of the productions are matched in the state graph the non-determinism disappears. But the interesting part of the analysis is the one that happens before the productions are matched into the host graph. Recall that this non-determinism is classified as vertical and horizontal. The initial digraphs deal with horizontal non-determinism, so they contribute also to the study of the vertical non-determinism.
Depending on the way completion is carried out, different initial digraphs will be derived, giving rise to the notions of initial digraph set. The horizontal non-determinism needs further research. For some time I tried to address this issue using representation theory, which I will comment on in a future post. There is a fast introduction to representation theory here.
Summarizing, initial digraphs are interesting at least for three reasons: They keep independence in MGG of the analysis with respect to the host graph, they also help in the study of horizontal non-determinism and they answer the question of what is the smallest graph able to fire a sequence.
Today I find myself a bit sarcastic. Normally I choose quotes that are related to the topic of the post in some way, but today I cannot stand including the following phrase from David Hilbert: Some people have got a mental horizon of radius zero and call it their point of view.
sábado, 28 de abril de 2012
martes, 10 de abril de 2012
marking
marking places in the host graph
Non-determinism of MGG is a recurrent topic in this blog. It is a property that MGG shares with the rest of approaches to graph rewriting. However, there are several situations in which determinism is needed, even if we want to have a non-deterministic grammar.
Determinism needs arise naturally in MGG in the following three sample situations: Dangling edges, application conditions and splitting rule actions. The first I briefly explained in a previous post: In order to delete any possible edge we append an epsilon-production. Of course we must assure that both productions are applied to the same nodes (otherwise, dangling edges would not be removed).
I will touch application conditions in some future post. Application conditions are just what their name indicate: Properties that must be fulfilled by the host graph in order to apply the production. It should suffice to say that in MGG it is possible to calculate an equivalent sequence to a given production + application conditions. This sequence extends the production and again it is necessary to guarantee that all relevant productions will be applied to the same nodes. If you are interested in application conditions, they are addressed in Chap. 7 of the MGG book.
At times it is of interest to split a production into subproductions, whose overall effect are equivalent. A good example is reachability (some posts on it in the future). If productions of a certain type are split into two productions (one with the addition of elements and one with deletion of elements), then the state equation can gather more information. Clearly, both productions should be applied in the same elements. For reachability, refer to Chap. 8 of the MGG book.
How is this achieved in MGG?. The idea is quite simple but has some subtleties that I do not address here (see Sec. 5.2 of the MGG book): Just mark all nodes the first production is applied to. To this end, introduce a node of a new type (a type not present in the host graph nor in the LHS or RHS of the productions). Link this node to all nodes where the first production is applied. Alter the second production so, first, its LHS must find this element and its relevant incident edges and, second, it deletes this marking node (not its incident edges). Why the second grammar rule should not delete the incident edges is related to sequential independence and is explained in detail in the MGG book.
Today's quote I have chosen from the great Friedrich Nietzsche: there are no facts, only interpretations. I, as a mathematician, completely agree.
Non-determinism of MGG is a recurrent topic in this blog. It is a property that MGG shares with the rest of approaches to graph rewriting. However, there are several situations in which determinism is needed, even if we want to have a non-deterministic grammar.
Determinism needs arise naturally in MGG in the following three sample situations: Dangling edges, application conditions and splitting rule actions. The first I briefly explained in a previous post: In order to delete any possible edge we append an epsilon-production. Of course we must assure that both productions are applied to the same nodes (otherwise, dangling edges would not be removed).
I will touch application conditions in some future post. Application conditions are just what their name indicate: Properties that must be fulfilled by the host graph in order to apply the production. It should suffice to say that in MGG it is possible to calculate an equivalent sequence to a given production + application conditions. This sequence extends the production and again it is necessary to guarantee that all relevant productions will be applied to the same nodes. If you are interested in application conditions, they are addressed in Chap. 7 of the MGG book.
At times it is of interest to split a production into subproductions, whose overall effect are equivalent. A good example is reachability (some posts on it in the future). If productions of a certain type are split into two productions (one with the addition of elements and one with deletion of elements), then the state equation can gather more information. Clearly, both productions should be applied in the same elements. For reachability, refer to Chap. 8 of the MGG book.
How is this achieved in MGG?. The idea is quite simple but has some subtleties that I do not address here (see Sec. 5.2 of the MGG book): Just mark all nodes the first production is applied to. To this end, introduce a node of a new type (a type not present in the host graph nor in the LHS or RHS of the productions). Link this node to all nodes where the first production is applied. Alter the second production so, first, its LHS must find this element and its relevant incident edges and, second, it deletes this marking node (not its incident edges). Why the second grammar rule should not delete the incident edges is related to sequential independence and is explained in detail in the MGG book.
Today's quote I have chosen from the great Friedrich Nietzsche: there are no facts, only interpretations. I, as a mathematician, completely agree.
lunes, 26 de marzo de 2012
me and the music
A music group called inerKor
Once upon a long ago, two friends of mine (Fernando aka tibu and Javi aka mono) started playing the guitar. They decided to form a group. Soon after I joined them as drum player. Inerkor was born. We tried to include a bassist but after many trials it was not possible. One of our best friends -- Alfonso -- played for a while but unfortunately he left it. So eventually inerkor was a group of three, without bass (who needs it with a double bass drum?).
Our style was influenced by groups like Pantera, Metallica, Napalm Death and many others. Truth is that we spent a lot of time listening to other groups and going to concerts. So you can imagine that our music was pretty noisy, but we introduced certain melodic parts (even with those broken guitars and the double bass drum going full pelt). Really cool.
Our lyrics would have been under a parental advisory label. No doubt. Titles like "suicide time" or "I'd enjoy killing you, motherfucker" say it all. The message was pretty pessimistic, but in line with our feelings and the facts of society we were facing. Even though we really enjoyed, I think anger prevailed in our concerts, music and lyrics. I am not sure anger against what. Looking back I realize that this anger has not faded away, not as that friendship that seems to last forever.
We played for over seven years, giving concerts here and there (one of my dearest memories is our concert in Firenze, Italy), recorded one demo that unfortunately I do not keep (otherwise you could download it from this webpage, be sure) and quit in our best moment I think. I mean that we were good enough to play almost any group and our music was not bad (well, I could not say any other thing).
A few weeks ago, surfing the web, by chance (by a mistake: I introduced the name of the group in the google bar instead of in my gmail account) I discovered a video in which the lead guitar, tibu, was playing kind of celtic music in a collaboration with other people. I have not seen him for over eight years and it was very, very moving. The video is this one.
Many, many things changed in my life at the age of 27/28. Another day, another post, I will tell you about other deep changes. It seems that I got sentimental. Okay, we will return to maths and MGG in the next post. Reading again this post, it does not do Inerkor or my friends justice, so this quote from Gustave Flaubert seems appropriate: writing history is like drinking an ocean and pissing a cupful.
Once upon a long ago, two friends of mine (Fernando aka tibu and Javi aka mono) started playing the guitar. They decided to form a group. Soon after I joined them as drum player. Inerkor was born. We tried to include a bassist but after many trials it was not possible. One of our best friends -- Alfonso -- played for a while but unfortunately he left it. So eventually inerkor was a group of three, without bass (who needs it with a double bass drum?).
Our style was influenced by groups like Pantera, Metallica, Napalm Death and many others. Truth is that we spent a lot of time listening to other groups and going to concerts. So you can imagine that our music was pretty noisy, but we introduced certain melodic parts (even with those broken guitars and the double bass drum going full pelt). Really cool.
Our lyrics would have been under a parental advisory label. No doubt. Titles like "suicide time" or "I'd enjoy killing you, motherfucker" say it all. The message was pretty pessimistic, but in line with our feelings and the facts of society we were facing. Even though we really enjoyed, I think anger prevailed in our concerts, music and lyrics. I am not sure anger against what. Looking back I realize that this anger has not faded away, not as that friendship that seems to last forever.
We played for over seven years, giving concerts here and there (one of my dearest memories is our concert in Firenze, Italy), recorded one demo that unfortunately I do not keep (otherwise you could download it from this webpage, be sure) and quit in our best moment I think. I mean that we were good enough to play almost any group and our music was not bad (well, I could not say any other thing).
A few weeks ago, surfing the web, by chance (by a mistake: I introduced the name of the group in the google bar instead of in my gmail account) I discovered a video in which the lead guitar, tibu, was playing kind of celtic music in a collaboration with other people. I have not seen him for over eight years and it was very, very moving. The video is this one.
Many, many things changed in my life at the age of 27/28. Another day, another post, I will tell you about other deep changes. It seems that I got sentimental. Okay, we will return to maths and MGG in the next post. Reading again this post, it does not do Inerkor or my friends justice, so this quote from Gustave Flaubert seems appropriate: writing history is like drinking an ocean and pissing a cupful.
miércoles, 14 de marzo de 2012
derivations III
derivations and direct derivations. Part III (epsilon-productions)
Today I touch on dangling edges. Let p be a production that specifies the deletion of one node (the LHS -- left hand side -- is made up of a single node and its RHS is empty). Suppose the production is applied to a graph with no isolated nodes. What happens with the edges that are incident to the node that p deletes?
There are two possibilities: Either the production can not be applied or every edge incident to the node that is going to be deleted is also deleted. Let us call those grammars fixed grammars and floating grammars, respectively.
In the categorical approach fixed grammars correspond to the DPO approach and floating grammars to the SPO approach.This is precisely the main difference between them. The pushout construction takes care of dangling edges in the SPO approach and the double pushout construction (DPO approach) does not allow the application of a production if any edge is going to become a dangling edge.
MGG is a floating grammar (this topic is addressed in detail in Sec. 5 of the MGG book). This is achieved using one operator, T. The basic idea is to enlarge the production p in order to include (to delete) any potential dangling edge. As it always happens up to now in MGG, an operator turns out to be equivalent to a certain sequence of productions. In case of dangling edges T(p) is equivalent to a sequence of two productions p;pe , where pe (epsilon-production or e-production) deletes any potential dangling edge (pe is applied before p). If a fixed grammar is preferred, it is enough to make T be the identity operator (compatibility is an application condition that MGG has for free).
It remains to guarantee that p and pe will be applied in the same place of the graph (recall non-determinism). To this end MGG uses marking, which is introduced in Sec. 5.2 of the MGG book.
Today I quote Thales. In my opinon, honesty is a must: I will be sufficiently rewarded if when telling it to others you will not claim the discovery as your own, but will say it was mine.
Today I touch on dangling edges. Let p be a production that specifies the deletion of one node (the LHS -- left hand side -- is made up of a single node and its RHS is empty). Suppose the production is applied to a graph with no isolated nodes. What happens with the edges that are incident to the node that p deletes?
There are two possibilities: Either the production can not be applied or every edge incident to the node that is going to be deleted is also deleted. Let us call those grammars fixed grammars and floating grammars, respectively.
In the categorical approach fixed grammars correspond to the DPO approach and floating grammars to the SPO approach.This is precisely the main difference between them. The pushout construction takes care of dangling edges in the SPO approach and the double pushout construction (DPO approach) does not allow the application of a production if any edge is going to become a dangling edge.
MGG is a floating grammar (this topic is addressed in detail in Sec. 5 of the MGG book). This is achieved using one operator, T. The basic idea is to enlarge the production p in order to include (to delete) any potential dangling edge. As it always happens up to now in MGG, an operator turns out to be equivalent to a certain sequence of productions. In case of dangling edges T(p) is equivalent to a sequence of two productions p;pe , where pe (epsilon-production or e-production) deletes any potential dangling edge (pe is applied before p). If a fixed grammar is preferred, it is enough to make T be the identity operator (compatibility is an application condition that MGG has for free).
It remains to guarantee that p and pe will be applied in the same place of the graph (recall non-determinism). To this end MGG uses marking, which is introduced in Sec. 5.2 of the MGG book.
Today I quote Thales. In my opinon, honesty is a must: I will be sufficiently rewarded if when telling it to others you will not claim the discovery as your own, but will say it was mine.
domingo, 26 de febrero de 2012
derivations II
derivations and direct derivations. Part II (non-determinism)
In a previous post I introduced derivations in MGG. Today I want to give you my personal interpretation of what a direct derivation is. Also, there is one problem that needs to be addressed in order to move forward: Potential dangling edges. MGG takes care of them through so-called epsilon-productions (e-productions). I will address them in the next post.
One question that I find pretty natural is why applying a production to some host graph is so complicated. There are several steps involved. For example, in the categorical approaches (SPO/DPO) we use one pushout construction (or even "worse", two pushout constructions) to define what a direct derivation is. My personal view is that the pushout construction is a device to transform a production into a function. This is not the standard point of view, in which the grammar is/specifies the function.
However, I think that the underlying idea of a production should be that of a function, which is straightforward. Direct derivations as introduced so far in the literature are not (they are not straightforward and they are not functions). Recall that a production applies a single graph into another graph. I think it should rather be a receipt to transform graphs into graphs (production and grammar rule are synonymous; the term rule and receipt are not that far in my opinion).
Nonetheless, my main objection to the pushout construction is its inherent non-determinism. In a more functional style I would say that it defines a multivalued function (one that assigns several different outputs to a single input). This is a far-reaching subject. For example, if SPO was used as a model of computation, e.g. to study the PvsNP problem, we would not get too far. Unfortunately, I think we would not even start because the definition of the complexity class P could not be done. By the way, I am not aware of any attempt to use/study DPO or SPO as a model of computation, even though most of the research in this field is carried out by computer scientists. No doubt, this is an extremely interesting topic.
How can we avoid this non-determinism in the different approaches to graph transformation? In my personal opinion, I think we cannot or at least I do not see how (I mean an easy way). How can we avoid this non-determinism in MGG? Recall that in MGG we can split the dynamics of the production from its statics, so to speak. One possibility are the so-called swaps, which are introduced in this preliminar paper (the full version has been published in the Electronic Journal of Combinatorics).
The obvious drawback of swaps is precisely that we lose non-determinism. Actually, it can be recovered but we shall leave this to a post dedicated solely to swaps.
Today's quote (Johnson Samuel) I do not agree. In fact, I think this is probably the main problem in mathematics and this blog's very initial reason for being: Sir, I have found you an argument. I am not obliged to find you an understanding. It is also possible to illustrate one's opinion using counterexamples...
In a previous post I introduced derivations in MGG. Today I want to give you my personal interpretation of what a direct derivation is. Also, there is one problem that needs to be addressed in order to move forward: Potential dangling edges. MGG takes care of them through so-called epsilon-productions (e-productions). I will address them in the next post.
One question that I find pretty natural is why applying a production to some host graph is so complicated. There are several steps involved. For example, in the categorical approaches (SPO/DPO) we use one pushout construction (or even "worse", two pushout constructions) to define what a direct derivation is. My personal view is that the pushout construction is a device to transform a production into a function. This is not the standard point of view, in which the grammar is/specifies the function.
However, I think that the underlying idea of a production should be that of a function, which is straightforward. Direct derivations as introduced so far in the literature are not (they are not straightforward and they are not functions). Recall that a production applies a single graph into another graph. I think it should rather be a receipt to transform graphs into graphs (production and grammar rule are synonymous; the term rule and receipt are not that far in my opinion).
Nonetheless, my main objection to the pushout construction is its inherent non-determinism. In a more functional style I would say that it defines a multivalued function (one that assigns several different outputs to a single input). This is a far-reaching subject. For example, if SPO was used as a model of computation, e.g. to study the PvsNP problem, we would not get too far. Unfortunately, I think we would not even start because the definition of the complexity class P could not be done. By the way, I am not aware of any attempt to use/study DPO or SPO as a model of computation, even though most of the research in this field is carried out by computer scientists. No doubt, this is an extremely interesting topic.
How can we avoid this non-determinism in the different approaches to graph transformation? In my personal opinion, I think we cannot or at least I do not see how (I mean an easy way). How can we avoid this non-determinism in MGG? Recall that in MGG we can split the dynamics of the production from its statics, so to speak. One possibility are the so-called swaps, which are introduced in this preliminar paper (the full version has been published in the Electronic Journal of Combinatorics).
The obvious drawback of swaps is precisely that we lose non-determinism. Actually, it can be recovered but we shall leave this to a post dedicated solely to swaps.
Today's quote (Johnson Samuel) I do not agree. In fact, I think this is probably the main problem in mathematics and this blog's very initial reason for being: Sir, I have found you an argument. I am not obliged to find you an understanding. It is also possible to illustrate one's opinion using counterexamples...
viernes, 17 de febrero de 2012
derivations I
derivations and direct derivations. Part I
Recall that a production (or grammar rule) specifies how one graph is transformed into another. Following the intuition behind automatas or Turing Machines, we want to establish a procedure to pass from one state of a predetermined system to another, hence simulating its behaviour. In graph grammars, the state of a system is fixed by an associated graph. The idea is very simple: Apply the production to the initial state of the system and derive a new (system) state. This is precisely a direct derivation: The application of some production to some graph. A derivation is just a sequence of direct derivations.
The question that rises naturally is how this application is performed. The answer depends on the chosen approach to graph transformation. For example, in DPO the construction consists in essence of two double pushouts diagrams while in SPO it is a single pushout construction. Whatever the chosen approach is, the following steps are always fulfilled:
1. Select grammar rule.
2. Find occurrence of the grammar rule's left hand side (LHS) in the host (initial) graph.
3. Check application conditions.
4. Remove elements that appear in the left but not in the right hand side (RHS).
5. Glue the elements of the right hand side to the graph of previous step.
MGG also follows more or less these same steps. Let's briefly comment on them. Regarding the selection on rules, there is no standard way (notice that a sequence precisely specifies this order of application). This is a clear source of non-determinism and we shall come back to it when we comment on MGG as a model of computation, sometime in the future.
The occurrence of the LHS is carried out through matching. This is addressed in Chap. 5 in the MGG book. There are two equivalent proposals, one using category theory (similar to the categorical approaches) and the other (novel) defining an operator that enlarges the LHS of the production. The basic remark is that a match is nothing but a production that transforms the LHS into the host graph. Then, we can define an operator that basically performs a continuation of the production (enlarges the production) such that it is perfectly suited for the graph it is going to be applied to.
I will write some posts on application conditions and graph constraints, so I will not touch step 3 here. Steps 4 and 5 are easily addressed through Boolean operations, as explained in this post. As nodes can be deleted, step 4 is potentially unsafe because some edges may dangle. Next post will be on dangling edges and how they are addressed in MGG.
As stated in previous posts, the way MGG handles productions and direct derivations has several advantages, and no real inconvenient as far as I can see. Please, comment if you have a different opinion.
Today I quote Oliver Heaviside. Should I refuse a good dinner simply because I do not understand the process of digestion?
Recall that a production (or grammar rule) specifies how one graph is transformed into another. Following the intuition behind automatas or Turing Machines, we want to establish a procedure to pass from one state of a predetermined system to another, hence simulating its behaviour. In graph grammars, the state of a system is fixed by an associated graph. The idea is very simple: Apply the production to the initial state of the system and derive a new (system) state. This is precisely a direct derivation: The application of some production to some graph. A derivation is just a sequence of direct derivations.
The question that rises naturally is how this application is performed. The answer depends on the chosen approach to graph transformation. For example, in DPO the construction consists in essence of two double pushouts diagrams while in SPO it is a single pushout construction. Whatever the chosen approach is, the following steps are always fulfilled:
1. Select grammar rule.
2. Find occurrence of the grammar rule's left hand side (LHS) in the host (initial) graph.
3. Check application conditions.
4. Remove elements that appear in the left but not in the right hand side (RHS).
5. Glue the elements of the right hand side to the graph of previous step.
MGG also follows more or less these same steps. Let's briefly comment on them. Regarding the selection on rules, there is no standard way (notice that a sequence precisely specifies this order of application). This is a clear source of non-determinism and we shall come back to it when we comment on MGG as a model of computation, sometime in the future.
The occurrence of the LHS is carried out through matching. This is addressed in Chap. 5 in the MGG book. There are two equivalent proposals, one using category theory (similar to the categorical approaches) and the other (novel) defining an operator that enlarges the LHS of the production. The basic remark is that a match is nothing but a production that transforms the LHS into the host graph. Then, we can define an operator that basically performs a continuation of the production (enlarges the production) such that it is perfectly suited for the graph it is going to be applied to.
I will write some posts on application conditions and graph constraints, so I will not touch step 3 here. Steps 4 and 5 are easily addressed through Boolean operations, as explained in this post. As nodes can be deleted, step 4 is potentially unsafe because some edges may dangle. Next post will be on dangling edges and how they are addressed in MGG.
As stated in previous posts, the way MGG handles productions and direct derivations has several advantages, and no real inconvenient as far as I can see. Please, comment if you have a different opinion.
Today I quote Oliver Heaviside. Should I refuse a good dinner simply because I do not understand the process of digestion?
sábado, 28 de enero de 2012
sequences and coherence
A sequence in MGGs (aka concatenation) is just an ordered set of productions (aka grammar rules). In mathematics one usually has a countable amount of ordered elements and studies the limit. However, when studying grammars and languages one usually has a finite number of grammar rules. (The language generated by a grammar is more or less its set of finite sequences.)
I like to think that the importance of sequences stems from the fact that they destroy the non-determinism of "the next rule to apply". A complexity point of view. Recall that there is another source of non-determinism in MGG: The place of the host graph in which the production is applied.
There are some novel concepts related to sequences introduced in the MGG book: Compatibility, coherence, initial graphs and congruence. Today I touch on coherence and possibly the next few posts will brush over the rest.
Productions inside a sequence are applied in order, so it can be the case that one production performs one action that troubles some production that has to be applied later. Coherence guarantees that this is not going to happen. Notice how close coherence is to applicability (the possibility to apply the sequence to some initial graph, thus deriving a new graph: the output of the sequence). In fact, it turns out that a sequence can be applied if and only if it is compatible and coherent.
Today's quote is from Jon Von Neumann, and I would like to dedicate it to my friend Álvaro Iglesias: In mathematics you don't understand things. You just get used to them.
I like to think that the importance of sequences stems from the fact that they destroy the non-determinism of "the next rule to apply". A complexity point of view. Recall that there is another source of non-determinism in MGG: The place of the host graph in which the production is applied.
There are some novel concepts related to sequences introduced in the MGG book: Compatibility, coherence, initial graphs and congruence. Today I touch on coherence and possibly the next few posts will brush over the rest.
Productions inside a sequence are applied in order, so it can be the case that one production performs one action that troubles some production that has to be applied later. Coherence guarantees that this is not going to happen. Notice how close coherence is to applicability (the possibility to apply the sequence to some initial graph, thus deriving a new graph: the output of the sequence). In fact, it turns out that a sequence can be applied if and only if it is compatible and coherent.
Today's quote is from Jon Von Neumann, and I would like to dedicate it to my friend Álvaro Iglesias: In mathematics you don't understand things. You just get used to them.
Suscribirse a:
Entradas (Atom)