domingo, 27 de mayo de 2012

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 p2;p1 (p1 is applied before p2 by convention). In this case if p2 can be advanced -- or equivalently p1 can be delayed -- and the new sequence p1;p2 has the same output as the original, then we say that p2 is sequentially independent of p1 (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.

domingo, 13 de mayo de 2012


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.