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.
lunes, 26 de marzo de 2012
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.
miércoles, 11 de enero de 2012
the very basics III
The very basics of graph dynamics: the nihilation matrix.
Today I touch on the nihilation or nihil matrix. Recall that a production transforms one graph (L) into another (R). When a production is applied to some host graph G (which represents the state of the system under study), L is found in G and substituted by R to derive graph H (which is the new state of the system).
Notice that the left hand side of the productions (L) specifies what elements must be present in any host graph in order to apply the production. The nihilation matrix specifies what edges must not be present in order to apply the production. It is represented by K. There are two sets of edges that should not appear: Those incident to nodes that are deleted by the production and those that are going to be added by the production.
It is important to notice that the nihilation matrix only makes explicit some implicit information. Then, what is it good for? Actually it is extremely useful. First of all, it can be used to characterize compatibility (closedness of the set of graphs with respect to productions of the grammar). Second, together with L and R, they define the natural framework to study application conditions and graph constraints. Most importantly, nihilation matrices are the key idea to relate MGGs and complex analysis, swaps, etcetera (an introduction here).
I have said that the nihilation matrix just makes explicit some implicit information. We know that a production p transforms L into R. So in principle we should have all ingredients to know which are the forbidden elements in the image of the host graph G. Interestingly, the image of the nihil matrix K (which I will represent as Q) evolves according to the inverse of the production:
More on nihilation matrices can be found in Secs. 4.4 and 7.4 of the MGG book. Let's finish today with a nice cite from Karl Friedrich Gauss: It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
Today I touch on the nihilation or nihil matrix. Recall that a production transforms one graph (L) into another (R). When a production is applied to some host graph G (which represents the state of the system under study), L is found in G and substituted by R to derive graph H (which is the new state of the system).
Notice that the left hand side of the productions (L) specifies what elements must be present in any host graph in order to apply the production. The nihilation matrix specifies what edges must not be present in order to apply the production. It is represented by K. There are two sets of edges that should not appear: Those incident to nodes that are deleted by the production and those that are going to be added by the production.
It is important to notice that the nihilation matrix only makes explicit some implicit information. Then, what is it good for? Actually it is extremely useful. First of all, it can be used to characterize compatibility (closedness of the set of graphs with respect to productions of the grammar). Second, together with L and R, they define the natural framework to study application conditions and graph constraints. Most importantly, nihilation matrices are the key idea to relate MGGs and complex analysis, swaps, etcetera (an introduction here).
I have said that the nihilation matrix just makes explicit some implicit information. We know that a production p transforms L into R. So in principle we should have all ingredients to know which are the forbidden elements in the image of the host graph G. Interestingly, the image of the nihil matrix K (which I will represent as Q) evolves according to the inverse of the production:
More on nihilation matrices can be found in Secs. 4.4 and 7.4 of the MGG book. Let's finish today with a nice cite from Karl Friedrich Gauss: It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
domingo, 25 de diciembre de 2011
the very basics II
The very basics of graph dynamics: completion and compatibility
A production in MGG specifies some Boolean matrix operations. The first thing to do is to "complete" the matrices so the Boolean operations make sense. This is not a trivial fact because not only the number of elements in the matrices may differ but also their ordering. Somehow it has to be decided which nodes are the same in different graphs, respecting types. Notice that this is one source of non-determinism unless all types are different.
This property is closely related to the matching problem: Given a host graph (initial state to which the grammar is going to be applied), select the places where the productions are going to be applied.
Notice there is still another source of non-determinism in MGGs: A means to select the following production to be applied. This sort of non-determinism is avoided by providing a sequence of productions, which is nothing but a set of productions to be applied in a given order.
Completion is necessary to perform the algebraic operations and we will always assume in MGGs that it has been performed somehow. More on this in Sec. 4.2 of the MGG book. The two sources of non-determinism commented above are relevant if we consider MGG as a model of computation, which I will do in future posts.
Another algebraic need is compatibility. We give the adjacency matrix to specify the edges of a graph, which implicitly contains the nodes of the graphs. As productions may act on nodes independently, a vector of nodes is also given and we have to be sure that the adjacency matrix and the vector of nodes are compatible, i.e. they have the same nodes (no edge is incident to a node that does not belong to the graph). A production is said to be compatible if it outputs a compatible graph starting out of a compatible graph. A similar definition of compatibility is given for sequences in the MGG book (intermediate states have to be compatible).
Compatibility is in essence well-formedness of graphs.
I finish today with a quote from Richard Feynman: "The worthwhile problems are the ones you can really solve or help solve, the ones you can really contribute something to. ... No problem is too small or too trivial if we can really do something about it."
A production in MGG specifies some Boolean matrix operations. The first thing to do is to "complete" the matrices so the Boolean operations make sense. This is not a trivial fact because not only the number of elements in the matrices may differ but also their ordering. Somehow it has to be decided which nodes are the same in different graphs, respecting types. Notice that this is one source of non-determinism unless all types are different.
This property is closely related to the matching problem: Given a host graph (initial state to which the grammar is going to be applied), select the places where the productions are going to be applied.
Notice there is still another source of non-determinism in MGGs: A means to select the following production to be applied. This sort of non-determinism is avoided by providing a sequence of productions, which is nothing but a set of productions to be applied in a given order.
Completion is necessary to perform the algebraic operations and we will always assume in MGGs that it has been performed somehow. More on this in Sec. 4.2 of the MGG book. The two sources of non-determinism commented above are relevant if we consider MGG as a model of computation, which I will do in future posts.
Another algebraic need is compatibility. We give the adjacency matrix to specify the edges of a graph, which implicitly contains the nodes of the graphs. As productions may act on nodes independently, a vector of nodes is also given and we have to be sure that the adjacency matrix and the vector of nodes are compatible, i.e. they have the same nodes (no edge is incident to a node that does not belong to the graph). A production is said to be compatible if it outputs a compatible graph starting out of a compatible graph. A similar definition of compatibility is given for sequences in the MGG book (intermediate states have to be compatible).
Compatibility is in essence well-formedness of graphs.
I finish today with a quote from Richard Feynman: "The worthwhile problems are the ones you can really solve or help solve, the ones you can really contribute something to. ... No problem is too small or too trivial if we can really do something about it."
Suscribirse a:
Entradas (Atom)