martes, 11 de diciembre de 2012
sábado, 24 de noviembre de 2012
domingo, 11 de noviembre de 2012
time is all we have
blog sobre aprovechar el tiempo. Mirar atrás y disfrutar de lo que has hecho. Dar un pequeño repaso a mi existencia
domingo, 28 de octubre de 2012
are mathematics invented or discovered?
discovery or invention?
In the LinkedIn group about mathematics "Math, Math Education, Math Culture" Opher Liba asked an old and recurrent question in mathematics: Invention or Discovery? This was the title. Many people contributed to this interesting topic. I am not going to make a summary of all the relevant opinions, some of which were quite elaborated. Just let me highlight the new term proposed by Jonathan Visona: innovery (a mixture of invention and discovery). I will limit myself to reproduce my entry.
I am one of those who think that mathematics is nothing more (and nothing less) than a language: http://www.cut-the-knot.org/language/MathIsLanguage.shtml
Is the language (theormems, propositions, corollaries) already in the grammar (axioms) that specifies it? Well, in some sense it is, but on the other hand you do not care for every possible sentece that can be expressed in the language (leaving aside incompleteness results), but for those sentences or sets of sentences (theories) that are of interest for some practical or theoretical reason.
My opinion is that mathematics are discovered, but the way in which we put everything together and make it "understable" is invented.
Today's quote naturally belongs to J.W.Gibbs: Mathematics is a language.
In the LinkedIn group about mathematics "Math, Math Education, Math Culture" Opher Liba asked an old and recurrent question in mathematics: Invention or Discovery? This was the title. Many people contributed to this interesting topic. I am not going to make a summary of all the relevant opinions, some of which were quite elaborated. Just let me highlight the new term proposed by Jonathan Visona: innovery (a mixture of invention and discovery). I will limit myself to reproduce my entry.
I am one of those who think that mathematics is nothing more (and nothing less) than a language: http://www.cut-the-knot.org/language/MathIsLanguage.shtml
Is the language (theormems, propositions, corollaries) already in the grammar (axioms) that specifies it? Well, in some sense it is, but on the other hand you do not care for every possible sentece that can be expressed in the language (leaving aside incompleteness results), but for those sentences or sets of sentences (theories) that are of interest for some practical or theoretical reason.
My opinion is that mathematics are discovered, but the way in which we put everything together and make it "understable" is invented.
Today's quote naturally belongs to J.W.Gibbs: Mathematics is a language.
lunes, 15 de octubre de 2012
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.
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.
sábado, 29 de septiembre de 2012
main problems II
Main problems: termination, confluence and complexity
The main problems tackled in the MGG book are applicability, sequential independence and reachability. A lot is yet to be done. There are three more problems that - no doubt -are extremely interesting: Termination, confluence and complexity.
Roughly, termination asks whether a given grammar finishes its execution. A complementary problem is confluence which asks whether a terminating grammar has a unique final state. As you have probably noticed these are the omnipresent (in mathematics) existence and uniqueness. They are not addressed in the MGG book but there are some comments in the first and the last chapters, mainly relating them to reachability and sequential independence.
I introduce a restricted version of confluence in the first chapter of the MGG book, named sequential confluence: Tthe derivations used must be permutations one of each other. Actually the notion of confluence in the MGG book is not confluence as introduced above but one more closely related to independence and sequential independence (to ease the use of the theory developed in the book to study it).
The next natural question is, for a given initial state of a confluent MGG, how long does it take to reach its final state?. This is complexity. Currently it is my main motivation.
Before getting to complexity we need to study MGG as a model of computation and its submodels. Among them I find most interesting the one that does not allow the deletion nor the addition of nodes.
In this post I touch on topics that will be addressed in future posts: Models of computation. My intention is to stay at a conceptual level, ignoring the technical part if possible (even if not possible). I will revisit the main concepts that we have been reviewed in previous posts and will generalize them, introducing new ones such as swaps.
Edsger Dijkstra is for me a source of inspiration: Probably I am very naive, but I also think I prefer to remain so, at least for the time being and perhaps for the rest of my life.
The main problems tackled in the MGG book are applicability, sequential independence and reachability. A lot is yet to be done. There are three more problems that - no doubt -are extremely interesting: Termination, confluence and complexity.
Roughly, termination asks whether a given grammar finishes its execution. A complementary problem is confluence which asks whether a terminating grammar has a unique final state. As you have probably noticed these are the omnipresent (in mathematics) existence and uniqueness. They are not addressed in the MGG book but there are some comments in the first and the last chapters, mainly relating them to reachability and sequential independence.
I introduce a restricted version of confluence in the first chapter of the MGG book, named sequential confluence: Tthe derivations used must be permutations one of each other. Actually the notion of confluence in the MGG book is not confluence as introduced above but one more closely related to independence and sequential independence (to ease the use of the theory developed in the book to study it).
The next natural question is, for a given initial state of a confluent MGG, how long does it take to reach its final state?. This is complexity. Currently it is my main motivation.
Before getting to complexity we need to study MGG as a model of computation and its submodels. Among them I find most interesting the one that does not allow the deletion nor the addition of nodes.
In this post I touch on topics that will be addressed in future posts: Models of computation. My intention is to stay at a conceptual level, ignoring the technical part if possible (even if not possible). I will revisit the main concepts that we have been reviewed in previous posts and will generalize them, introducing new ones such as swaps.
Edsger Dijkstra is for me a source of inspiration: Probably I am very naive, but I also think I prefer to remain so, at least for the time being and perhaps for the rest of my life.
domingo, 9 de septiembre de 2012
main problems I
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.
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.
Suscribirse a:
Entradas (Atom)