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.
No hay comentarios:
Publicar un comentario