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.

sequentialization and sequential independence

sequentialization and sequential independence

Assume we are given a sequence of productions. Recall that a sequence is just an ordered (finite) set of productions. A natural question is whether some production can be applied before (advanced) or after (delayed) its current position without altering the result of the sequence. In essence, this is sequential independence.
Suppose that our sequence is made up of two productions p₂;p₁ (p₁ is applied before p₂ by convention). In this case if p₂ can be advanced -- or equivalently p₁ can be delayed -- and the new sequence p₁;p₂ has the same output as the original, then we say that p₂ is sequentially independent of p₁ (or vice versa).

Sequential independence is an important concept, both from the theoretical and the practical points of view. Theoretically, it extends commutativity to an arbitrary (though finite) amount of elements. Practically, it is closely related to parallel execution of tasks (a future post on this).

Chapter 6 of the MGG book addresses independence for sequences and for derivations (recall that a derivation is a sequence applied to an initial graph). Sufficient conditions for moving productions are stated and proved. In the literature, in order to test sequential independence for jumps larger than a single position, the production is checked to be sequentially independent with respect to every single production in the jump. One interesting result proved in the MGG book is that this is much more restrictive than what a direct jump actually needs.

Sequential independence can be characterized in terms of coherence (see this post or Chap. 4 in the MGG book) and congruence (I will write a post on it; it is addressed in Sec. 6.1 of the MGG book).

Today I quote Henri Poincaré: to doubt everything or to believe everything are two equally convenient solutions; both dispense with the necessity of reflection.

publishing

My personal opinion on publishing

Today's post deviates from previous ones. I will tell you my opinion about publishing. I am not a fan of the standard way: submit, go to a revision-correction process, (eventually) publish.

There are a few problems I see in the process: it is much easier if you have a well-known surname "in the business" (or more generally, how objective the evaluation process is?), it takes quite a long time (one and a half years is not uncommon) and, most important, which is the real impact?. I mean, nowadays most of us use web engines to search for topics and most research is publicly available in the web. There are other problems that I see but keep for myself (let's be polite).

But my main objection is that once you get through and eventually the paper is published in some journal, potential readers usually have to pay.

Of course, there are good by-products even if the paper is not eventually published. For example, the feedback of the reviewers is normally very valuable. Besides, the author is usually more careful and the paper is revised and well-thought before submitting.

I absolutely support initiatives like the Electronic Journal of Combinatorics and arXiv. Needless to say, everything can be improved but in my opinion these are two examples of how scientific communication will be driven in the future. In fact, I have submitted and got published a paper to the Electronic Journal of Combinatorics.

There are two very interesting critiques that I recommend to you:

1. The first, written by David Lorge Parnas with title Stop the Numbers Game, revises the big negative impact on current research due to the wide-spread policy of measuring researchers by the number of papers that they publish. In fact, the critique goes a bit further. Thanks to Juan de Lara for letting me know.
2. The second, signed by 10 computer scientists (Oded Goldreich among them), with title On evaluating conceptual contributions, is an attempt to draw the community attention on this problem: conceptual contributions are considered far less relevant than technical ones. I see mathematics as a language, being concepts the building blocks of the skycraper, so you can figure out what I think of this.

I end today quoting Henri Poincaré: It is by logic that we prove, but by intuition that we discover. To know how to criticize is good, to know how to create is better.