quotes - repository

This post is related to patience. I selected the following nice german proverb to close today's post: Patience is a bitter plant but it has sweet fruit.

I enjoy very much this from David Hilbert: Physics is much too hard for physicists.

Today I quote Noam Chomsky: "Tough love" is just the right phrase: love for the rich and privileged, tough for everyone else.

A very nice quote from Lewis Mumford: I'm a pessimist about probabilities; I'm an optimist about possibilities.

Another quote from Lewis Mumford: Unfortunately, once an economy is geared to expansion, the means rapidly turn into an end and "the going becomes the goal." 


I am optimistic because, among other things, I have no choice. Claudine Schneider once said "A Healthy Ecology is the Basis for a Healthy Economy". Richard Stallman, the father of the GNU beast: "Paying is not wrong, and being paid is not wrong. Trampling other people’s freedom and community is wrong, so the free software movement aims to put an end to it, at least in the area of software".

Today I quote Linus Pauling who according to Wikipedia "ranks among the most important scientists in any field of the 20th century": If you want to have good ideas you must have many ideas. Most of them will be wrong, and what you have to learn is which ones to throw away.

geometric complexity theory

Puedo iniciar una serie de posts sobre este tema y otros relacionados como teoria de representacion y analisis harmonico abstracto. Interesaria relacionarlo con MGG

Mathematical Universe Hypothesis

Mathematical Universe Hypothesis

so everything comes down to...

recognition? I mean regarding research. What do you expect? Other people realizing how brilliant you are?

DSL

Domain Specific Languages

relabelling

relabelling and groups of permutations


A nice cite from Eric Bell concerning groups is: Wherever groups disclosed themselves, or could be introduced, simplicity crystallized out of comparative chaos.

research investment

What research is more profitable?

MGG and Petri nets

ver cómo pueden aplicarse los resultados de MGG a redes de Petri

reachability

entrada sobre alcanzabilidad. De paso repaso

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

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.

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.

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.

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.

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.

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:

1. All the machinery developed for sequences can now be applied to graph constraints and ACs.
2. Through sequential independence, preconditions can be transformed into equivalent postconditions and viceversa.
3. 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.

In fact more can be said: Any precondition is equivalent to some postcondition and viceversa. This is a quite strong statement. It says that ACs are "delocalized" inside the production. Again, more can be said: Application conditions can be moved from one production to another inside sequences. So this "delocalization" happens in sequences as well.

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.

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.

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.

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.

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.