Main problems: Applicability, sequential independence and reachability
After several weeks of contributions to this blog I realize I have not touched on the driving forces that guide my research. Normally I have some question in my mind that I would like to solve. At times they are problems as general as those that I am about to comment and at times they are much more simple. For me, a general problem is e.g. sequential independence. A more concrete problem is e.g. how to associate a function to a production.
Both general and concrete problems are important. General problems set broad objectives, lead long term research and structure my research. I think it is helpful to have a long term objective and, more important, this objective should be difficult. However, in everyday research, one should have more humble objectives. Otherwise frustration might be just about to knock.
I would like to say that I find some concrete problems as relevant as general ones, and at times even more. For example, the one that I mention above (how to associate a function to a production) seems of capital importance to me. It might open new research directions by bringing in new branches of mathematics or by fitting previous unrelated results into a coherent body of theorems and propositions.
In the MGG book I have addressed and characterized applicability, sequential independence and reachability which are related among them, in my opinion complementing one to each other.
Applicability. Let a sequence be given with productions in some fixed MGG and a simple digraph G. Is it possible to apply the sequence to G?
Note that applicability is the essence of graph dynamics because a new graph is derived if the sequence can be applied. For a given grammar and an initial host graph, some sequences can be applied and others can not be applied. These are the languages associated to a graph grammar.
Two characterizations are given in the MGG book. One using coherence and the other congruence and initial digraphs (compatibility is needed in both).
Sequential independence. Do the derivations f and g = s(f) -- where s is a permutation -- applicable to the same initial graph G reach the same state H, i.e. f(G) = H = g(G)?
Sequential independence is a particular case of what I have called the independence problem which states something similar but without one being a permutation of the other. This problem is characterized in the MGG book (Sec. 6.2) using compatibility, coherence and congruence, with explicit formulas for the case of advancement and delay of a production a finite number of positions inside a sequence.
Reachability. Let two graphs and a graph grammar be given. Does there exist a sequence made up of productions in the graph grammar that transforms the first graph into the second?
The problem is partially solved by extending techniques from Petri nets theory to MGG. In the meanwhile, Petri nets are characterized as a proper subset of MGGs and MGG techniques are applied to them. The relations among them are studied in the MGG book, though not in detail. Applicability, sequential independence and reachability organize all the MGG book except Chap. 7 on graph constraints and application conditions (they are a generalization of productions and are somewhat unrelated to these problems).
In the next post I will write on three more problems that I find very interesting: confluence, termination and complexity. The following quote of Alan Turing seems to fit well with today's post: We can only see a short distance ahead, but we can see plenty there that needs to be done.
domingo, 9 de septiembre de 2012
miércoles, 22 de agosto de 2012
what are mathematics good for?
Convince me that I have to study maths, dad
Servando Arbolí sent me the drawing that you can find below. It was taken from here. The question is: Why should I learn maths? Or, otherwise stated, why is maths important? To tell you the truth, I have never thought about it. Fortunately nobody asked me before.
Before thinking, it is always a good idea to google for an answer: Root of all science (sounds to me kinda "root of all evil"), good for training your brain (as exercise for training your body, possibly other brain exercises are easier and more effective), etc. I have not found any convincing answer and I do not have a better one. They are good for me because I enjoy maths, I have a good time reading and doing maths. One of my great experiences was reading Riemann's paper on the distribution of prime numbers. I suppose I simply liked it since I was a boy (possibly due to its exacteness, at a first glance at least) and I suppose I'll stop as soon as it is not fun anymore.
A related recurrent question is: Why all sciences seem to be based on maths? To me, the answer is that we humans use languages to communicate. Any coherent and exact-to.some.extent language lies in the realms of maths (is maths to me). Hence, ...
Despite my atheism, I shall quote Sir James Jeans: From the intrinsic evidence of his creation, the great architect of the universe now begins to appear as a pure mathematician.
Servando Arbolí sent me the drawing that you can find below. It was taken from here. The question is: Why should I learn maths? Or, otherwise stated, why is maths important? To tell you the truth, I have never thought about it. Fortunately nobody asked me before.
Before thinking, it is always a good idea to google for an answer: Root of all science (sounds to me kinda "root of all evil"), good for training your brain (as exercise for training your body, possibly other brain exercises are easier and more effective), etc. I have not found any convincing answer and I do not have a better one. They are good for me because I enjoy maths, I have a good time reading and doing maths. One of my great experiences was reading Riemann's paper on the distribution of prime numbers. I suppose I simply liked it since I was a boy (possibly due to its exacteness, at a first glance at least) and I suppose I'll stop as soon as it is not fun anymore.
A related recurrent question is: Why all sciences seem to be based on maths? To me, the answer is that we humans use languages to communicate. Any coherent and exact-to.some.extent language lies in the realms of maths (is maths to me). Hence, ...
Despite my atheism, I shall quote Sir James Jeans: From the intrinsic evidence of his creation, the great architect of the universe now begins to appear as a pure mathematician.
sábado, 4 de agosto de 2012
application conditions II
application conditions and sequences
When an application condition (AC) is defined, we may face some problems. These problems can be described informally as follows: There is at least one graph that satisfies the AC (the AC is consistent); the AC is not a fallacy, i.e. false in all possible escenarios (the AC is coherent) and the AC describes some simple digraph (the AC is compatible).
Coherence typically fails because the AC asks for some element to be present and not to be present in the host graph (the graph the production is going to be applied to). Non-compatibility deals with internal structural inconsistencies. Consistency is concerned with applicability. It is proved in Chap. 7 of the MGG book that consistency is equivalent to compatibility plus coherence.
It is possible to use two operators (closure and decomposition) to transform any application condition into an equivalent sequence or set of sequences. In my opinion this is the main (unexpected) result of Chap. 7. This theorem has important consequences:
From a more practical point of view, ACs can be used to allow MGG to tackle with multidigraphs with no major modification of the theory. This solves one of the main practical drawbacks of MGG (the other one being relabelling, which I will address in a future post). They can also be used to study other models of computation as particular cases of MGG, such as Turing Machines and Boolean Circuits.
I cite Aristotle today: The whole is more than the sum of its parts.
When an application condition (AC) is defined, we may face some problems. These problems can be described informally as follows: There is at least one graph that satisfies the AC (the AC is consistent); the AC is not a fallacy, i.e. false in all possible escenarios (the AC is coherent) and the AC describes some simple digraph (the AC is compatible).
Coherence typically fails because the AC asks for some element to be present and not to be present in the host graph (the graph the production is going to be applied to). Non-compatibility deals with internal structural inconsistencies. Consistency is concerned with applicability. It is proved in Chap. 7 of the MGG book that consistency is equivalent to compatibility plus coherence.
It is possible to use two operators (closure and decomposition) to transform any application condition into an equivalent sequence or set of sequences. In my opinion this is the main (unexpected) result of Chap. 7. This theorem has important consequences:
- All the machinery developed for sequences can now be applied to graph constraints and ACs.
- Through sequential independence, preconditions can be transformed into equivalent postconditions and viceversa.
- It is another example of an operator equivalent to a (set of) sequence(s). Other examples are the marking operator, the matching and the operator dealing with epsilon-productions.
From a more practical point of view, ACs can be used to allow MGG to tackle with multidigraphs with no major modification of the theory. This solves one of the main practical drawbacks of MGG (the other one being relabelling, which I will address in a future post). They can also be used to study other models of computation as particular cases of MGG, such as Turing Machines and Boolean Circuits.
I cite Aristotle today: The whole is more than the sum of its parts.
viernes, 27 de julio de 2012
application conditions I
application conditions and graph constraints
Graph constraints and application conditions are restrictions set on the host graph and on the applicability of a production, respectively. Conceptually, what we try to address is the especification of properties. For example, is a (host) graph three-colorable?, or, is every node of type 1 linked to one of type 2? This topic is important both from the theoretical and the practical points of view. It si addressed in Chap. 7 of the MGG book in full detail.
If we try to describe properties of a single graph, they are known as graph constraints; if there is a production involved they are known as application conditions. Application conditions can be set on the left hand side of the production (precondition) or on the right hand side (postcondition), or on both.
The proposal in MGG generalizes any previous approach to the topic. In essence, a graph constraint consists of a diagram (made up of graphs and morphisms between them) and a logical formula (monadic second order, to be concrete). The diagram specifies the graphs that take part in the constraint and the formula whether it should be or it should not be found in the host graph. Also, the graphs can be existentialy or universaly quantified. An example is "whenever graph A is found, there must exist a graph B linked to it". Of course, much more complicated combinations can be defined.
Now notice that the left hand side L of a production is in fact a graph constraint or an application condition: It asks for the existence of L in the host graph (the graph the production is going to be applied to). In fact, in MGG, application conditions are a particular case of graph constraints. Notice that in order to apply a production we do not only ask for the existence of the LHS (left hand side, L) but also for the non-existence of the nihilation matrix K (see this post). So in fact we have a positive and a negative application condition.
The first thing we have to prove is that MGG is general enough to handle with positive and negative application conditions as well as with existential and universal quantifiers. Notice that the existence of the LHS of a production is an existential qunatifier, but universals are not considered, at least explicitely. Interestingly, Sec. 7.2 proves that it is not necessary to extend the theory in order to cope with application conditions.
I interpret the following quotation from Plato as saying that we have to be very careful when setting the initial framework: The beginning is the most important part of the work. In some sense this was the initial reason for this blog.
Graph constraints and application conditions are restrictions set on the host graph and on the applicability of a production, respectively. Conceptually, what we try to address is the especification of properties. For example, is a (host) graph three-colorable?, or, is every node of type 1 linked to one of type 2? This topic is important both from the theoretical and the practical points of view. It si addressed in Chap. 7 of the MGG book in full detail.
If we try to describe properties of a single graph, they are known as graph constraints; if there is a production involved they are known as application conditions. Application conditions can be set on the left hand side of the production (precondition) or on the right hand side (postcondition), or on both.
The proposal in MGG generalizes any previous approach to the topic. In essence, a graph constraint consists of a diagram (made up of graphs and morphisms between them) and a logical formula (monadic second order, to be concrete). The diagram specifies the graphs that take part in the constraint and the formula whether it should be or it should not be found in the host graph. Also, the graphs can be existentialy or universaly quantified. An example is "whenever graph A is found, there must exist a graph B linked to it". Of course, much more complicated combinations can be defined.
Now notice that the left hand side L of a production is in fact a graph constraint or an application condition: It asks for the existence of L in the host graph (the graph the production is going to be applied to). In fact, in MGG, application conditions are a particular case of graph constraints. Notice that in order to apply a production we do not only ask for the existence of the LHS (left hand side, L) but also for the non-existence of the nihilation matrix K (see this post). So in fact we have a positive and a negative application condition.
The first thing we have to prove is that MGG is general enough to handle with positive and negative application conditions as well as with existential and universal quantifiers. Notice that the existence of the LHS of a production is an existential qunatifier, but universals are not considered, at least explicitely. Interestingly, Sec. 7.2 proves that it is not necessary to extend the theory in order to cope with application conditions.
I interpret the following quotation from Plato as saying that we have to be very careful when setting the initial framework: The beginning is the most important part of the work. In some sense this was the initial reason for this blog.
miércoles, 11 de julio de 2012
spreading mathematics
accessing mathematics and headaches
Studying mathematics and getting a headache need not be cause and effect. However, many times in seminars or reading some papers one gets the impression of being a little dumb. Well, I'm pretty sure you know those seminars in which everybody's constantly nodding or papers with obvious steps (once written they take three sheets, but they are obvious).
At times I think that we need to be admired for something and in mathematics this "something" is intelligence. The less people that understands something, the more difficult it is, the more intelligent the writer is. Something similar applies to speeches. The strange thing is that if you do not understand something in a seminar, you just keep quiet and spend (lose) one or two hours waiting for the storm to pass you by. Well one should stand up and quietly leave the room.
Our life is short. I should be able to quickly decide if something will be of my interest. If so, then I can dedicate time to it. For established theories there are plenty of tutorials on the web (god blesses the web) but not so for recent research papers or new theories. After all, it is not that difficult to include some examples to illustrate the concepts. Even in those papers submitted for publishing.
I agree in that mathematics are not easy, but most times we make them even more difficult. I think that mathematicians should be aware of the necessity of selling the product (I should include myself). The Bourbaki school which has had a big influence on the twentieth century belongs to the past. We should react and go to the opposite - as it is always the case: thesis, antithesis, synthesis - and try to make accessible even state-of-the-art papers. Good ideas are not difficult.
Another point is that technicalities prevail over conceptual research. In a "deep paper" one expects hard-to-follow equations just above obscure paragraphs. With minor exceptions, new approaches and concepts are not normally recognized though they are usually more influential as they allow us to think from a different perspective.
I confess I'm not a fan of B. Mandelbrot at all, but I do mind the importance of his work. Today's quote I agree, first, because it seems to support the thesis of this post and, second, because for me mathematics is nothing more (and nothing less) than a language: being a language, mathematics may be used not only to inform but also, among other things, to seduce.
Studying mathematics and getting a headache need not be cause and effect. However, many times in seminars or reading some papers one gets the impression of being a little dumb. Well, I'm pretty sure you know those seminars in which everybody's constantly nodding or papers with obvious steps (once written they take three sheets, but they are obvious).
At times I think that we need to be admired for something and in mathematics this "something" is intelligence. The less people that understands something, the more difficult it is, the more intelligent the writer is. Something similar applies to speeches. The strange thing is that if you do not understand something in a seminar, you just keep quiet and spend (lose) one or two hours waiting for the storm to pass you by. Well one should stand up and quietly leave the room.
Our life is short. I should be able to quickly decide if something will be of my interest. If so, then I can dedicate time to it. For established theories there are plenty of tutorials on the web (god blesses the web) but not so for recent research papers or new theories. After all, it is not that difficult to include some examples to illustrate the concepts. Even in those papers submitted for publishing.
I agree in that mathematics are not easy, but most times we make them even more difficult. I think that mathematicians should be aware of the necessity of selling the product (I should include myself). The Bourbaki school which has had a big influence on the twentieth century belongs to the past. We should react and go to the opposite - as it is always the case: thesis, antithesis, synthesis - and try to make accessible even state-of-the-art papers. Good ideas are not difficult.
Another point is that technicalities prevail over conceptual research. In a "deep paper" one expects hard-to-follow equations just above obscure paragraphs. With minor exceptions, new approaches and concepts are not normally recognized though they are usually more influential as they allow us to think from a different perspective.
I confess I'm not a fan of B. Mandelbrot at all, but I do mind the importance of his work. Today's quote I agree, first, because it seems to support the thesis of this post and, second, because for me mathematics is nothing more (and nothing less) than a language: being a language, mathematics may be used not only to inform but also, among other things, to seduce.
sábado, 23 de junio de 2012
congruence
congruence
Congruence or G-congruence (graph congruence) checks whether two sequences (one a permutation of the other) or derivations have the same initial digraphs. It is studied in detail in Sec. 6.1 in the MGG book.
Congruence is used to characterize sequential independence: If the sequence and its permutation are both compatible, coherent and congruent, then they are sequentially independent, i.e. they can be applied to the same initial graph and will eventually derive the same image graph.
Sequential independence means that the ordering of the productions (at least the two orderings specified by these sequences) do not affect the inital nor the final states.
In the MGG book there are some formulas that guarantee congruence in case of a single production being advanced a finite number of positions inside a sequence. They are known as congruence conditions. They can be calculated during design time, while the grammar is being defined, i.e. they are independent to some extent of the initial graph the sequence is going to be applied to.
Albert Einstein: Do not worry about your difficulties in Mathematics. I can assure you mine are still greater.
Congruence or G-congruence (graph congruence) checks whether two sequences (one a permutation of the other) or derivations have the same initial digraphs. It is studied in detail in Sec. 6.1 in the MGG book.
Congruence is used to characterize sequential independence: If the sequence and its permutation are both compatible, coherent and congruent, then they are sequentially independent, i.e. they can be applied to the same initial graph and will eventually derive the same image graph.
Sequential independence means that the ordering of the productions (at least the two orderings specified by these sequences) do not affect the inital nor the final states.
In the MGG book there are some formulas that guarantee congruence in case of a single production being advanced a finite number of positions inside a sequence. They are known as congruence conditions. They can be calculated during design time, while the grammar is being defined, i.e. they are independent to some extent of the initial graph the sequence is going to be applied to.
Albert Einstein: Do not worry about your difficulties in Mathematics. I can assure you mine are still greater.
viernes, 8 de junio de 2012
composition and compatibility
composition and compatibility of sequences
So far I have introduced sequentialization (the productions inside a sequence are applied one after the other). Today I will scratch on parallelism, but first we need to introduce composition of productions.
Consider a sequence. Its composition is just the composition of the productions. Thus, we obtain a single production that performs the same actions than the whole sequence. The natural question that arises with composition is: What do we need sequences and concatenation for?. There are some differences that make composition and sequentialization pretty different concepts.
The first is that of intermediate states: Sequences of productions generate intermediate states while their composition does not (it is a single production). Not only that, but the final state may differ in both cases. Think of a sequence that first deletes and then adds one node. Had the node any dangling edge, it is deleted by some epsilon-production. However, its composition does not touch the node, so it does not delete those edges.
If two productions are sequentially independent, it does not matter the order of their application, so they can be executed in parallel. But in the MGG book, Chap. 6, it is proved that advancing (or delaying) one production two positions inside a sequence in a single step is weaker (less demanding) than advancing one position and then another position.
In general, if two sequences are going to be applied in parallel, then every production in the first sequence needs to be sequentially independent with respect to all productions in the second. Previous comments weaken this, so it is possible to execute independent subsequences in parallel. See Sec. 5.4 of the MGG book.
Today's post ends quoting Edsger Dijkstra: Elegance is not a dispensable luxury but a quality that decides between success and failure.
So far I have introduced sequentialization (the productions inside a sequence are applied one after the other). Today I will scratch on parallelism, but first we need to introduce composition of productions.
Consider a sequence. Its composition is just the composition of the productions. Thus, we obtain a single production that performs the same actions than the whole sequence. The natural question that arises with composition is: What do we need sequences and concatenation for?. There are some differences that make composition and sequentialization pretty different concepts.
The first is that of intermediate states: Sequences of productions generate intermediate states while their composition does not (it is a single production). Not only that, but the final state may differ in both cases. Think of a sequence that first deletes and then adds one node. Had the node any dangling edge, it is deleted by some epsilon-production. However, its composition does not touch the node, so it does not delete those edges.
If two productions are sequentially independent, it does not matter the order of their application, so they can be executed in parallel. But in the MGG book, Chap. 6, it is proved that advancing (or delaying) one production two positions inside a sequence in a single step is weaker (less demanding) than advancing one position and then another position.
In general, if two sequences are going to be applied in parallel, then every production in the first sequence needs to be sequentially independent with respect to all productions in the second. Previous comments weaken this, so it is possible to execute independent subsequences in parallel. See Sec. 5.4 of the MGG book.
Today's post ends quoting Edsger Dijkstra: Elegance is not a dispensable luxury but a quality that decides between success and failure.
Suscribirse a:
Entradas (Atom)