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.

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.