Computing with Multiple Discrete Flows

The nearest in the literature to the model of mapcode is the UNITY work of Chandy and Misra. While mapcode considers a set X together with a map F: X -> X, UNITY considers several maps acting on X. The result is a fascinating theory of parallel and distributed programming. UNITY stands for Unbounded Nondeterministic Iterative Transformation theorY. We interpret this theory purely in mathematical terms as with mapcode. Our first paper on this subject dealing with standard sequential programs that are expected to terminate in a finite number of steps and return a value is given in our paper Computing with Multiple Discrete Flows.

Quantum Formalism and Information Retrieval

In 2004 Keith van Rijsbergen published a book with the title "The Geometry of Information Retrieval". In this book he suggested that quantum formalism can be successfully used to model some of the problems of Information Retrieval. This book was given to me by my colleague Dr. Vasudev Varma of the International Institute of Information Technology, Hyderabad with a request to offer a course on the ideas of the book.

Last semester I did so. I had hoped for senior students who already knew Linear Algebra, but none of those who joined was clear about the basics of Linear Algebra. So almost the entire course was spent teaching them linear algebra and then some of the basics of quantum terminology. At the end I was left with only one class to explain how quantum formalism relates to Information Retrieval.

There was another difficulty. The book of Rijsbergen used the physics notation for the inner product according to which it is the second term of the inner product that is linear and the first term antilinear. The mathematics text books have the opposite convention. So there was a need to rewrite the basics of Hilbert Space theory in the mathematical tradition but using the physics notation. This is now summarized in a document and attached here as Review of Hilbert Space Theory. Also attached is my write-up on the Hilbert Space Model for Information Retrieval.

Fifth meeting of the Formal Methods Reading Group

Chapter 3 was concluded by me and Dr. Venkatesh began discussing the concept of concurrency in Chapter 4. My notes of the part of my lecture are here as FMRG-5. Dr. Venkatesh will also put up his notes soon at the wiki of http://enhanceedu.iiit.ac.in. You may send mail to choppell@gmail.com for the login name and password that are necessary to access the wiki.

Fourth Meeting of the Formal Methods Reading Group

The fourth set of notes is up as FMRG-4. In this we study automata for which there is no start state specified and all states are considered to be accepting states. This is defined as a set together with a collection of choice maps on the set. We define the notion of a strong simulation as a choice map that carries a transition between states to a transition between sets of states. Other ideas of Milner are expressed in similar terms. Would like to know from the readers if this makes it easier to understand Milner's ideas.

Third Meeting of the Formal Methods Reading Group

The third meeting took place on 3rd March. Most of the time was spent discussing the example of the faulty vending machine given by Milner as motivation for the notion of bisimilarity. It became clear that the example needs to be discussed more fully than in the earlier meeting. Accordingly the set of notes were written up. They are available here as FMRG-3. Lesson 3 is in the form of a story: "The Case of the Faulty Vending Machine - An Allegory for Software Engineers".

Second meeting of the formal methods reading group

In the second meeting we discussed the second chapter of the book. In the notes I have posted on my web site at pi-calculus I have omitted the state space diagrams. Have made do with tables describing the state diagrams. A little patience and practice will help the reader feel comfortable with them. If the readers really miss the         diagrams,  when I find some time I will try to draw and upload them at the appropriate places.

Formal Methods Reading Group

Dr. Venkatesh Choppella and I, supported by several of our colleagues, have started a Formal Methods Reading Group. We plan to have meetings once a week to pursue a learning path. To begin with we have chosen Robin Milner's 1999 book on "Communicating and Mobile Systems: the pi-calculus". Skeletal notes of the first lecture are posted on my web site as pi-calculus-1. Comments by readers, and corrections where needed, are welcome.