traces, TrPTL, was formulated in CMI.

The model checking problem was solved using the gossip automaton that uses a bounded set of time-stamps to dynamically keep track of updates among communicating processes.

Temporal logic is expressively equivalent to the first order theory of sequences. It is not known if TrPTL captures the first order theory of traces. Researchers at CMI, in collaboration with European colleagues, later developed the first expressively complete temporal logics over traces.

Results from trace theory generalize to communicating finite-state machines with bounded channels. Message sequence charts (MSCs) describe interactions between agents communicating through buffers. A robust theory of regular MSC languages was developed at CMI.

The converse of model checking is synthesis: construct an automaton that meets a logical specification.

In the sequential setting, this was solved by Buchi and Landweber. In the distributed setting, Pnueli and Rosner proved strong undecidability results that stem from enforcing global specifications across loosely coupled agents. The decidability of distributed synthesis with local specifications is still open. Some of the strongest positive results for subclasses of systems were proved in CMI and IMSc.

Automata theory and logic have expanded to incorporate other features. A number of timed extensions to temporal logic were developed at IMSc and TIFR. In parallel, there was also work on distributed timed automata at CMI and IISc, as well as on timed versions of communicating finite-state machines at CMI and IIT Bombay. There has been work at IMSc on automata and logics over data words, which capture computations over infinite datatypes. There has also been work at CMI and IIT Kanpur in extending model checking from finite-state systems to infinite-state systems such as pushdown automata.

 

The Academic Ecosystem in India Indian undergraduate programs in computing date back to the early

1980s—a time that also saw the first
generation of graduate students from
India taking up theoretical computer
science. In the 1990s, these young re-
searchers helped set up strong theory
groups in TIFR, the IITs at Bombay,
Delhi, Kanpur, and Madras, IISc,
IMSc, and CMI. This network is now
expanding to newer IITs at Gandhi-
nagar, Goa, Guwahati, Hyderabad,
and Palakkad, as well as IIITs and
some traditional universities such as
Delhi University.

The FSTTCS Conference gave rise to the Indian Association for Research in Computing Science (IARCS). 3 IARCS initiated several activities for the academic community, such as travel grants for Ph.D. students to attend conferences and faculty development programs to improve the quality of teaching. Many of these activities continue today in partnership with ACM India.

Some very robust mechanisms have arisen to sustain international collaborations. The Max-Planck Society of Germany set up the Indo-German Max Planck Center for Computer Science at IIT Delhi. The French National Centre for Scientific Research (CNRS) has established an international Research Lab in Computer Science at CMI in Chennai.

Theoretical computer science attracts some of the brightest graduate students in the country. Since the ACM India Doctoral Dissertation Awards began in 2012, nine of the 13 prizes awarded have been in theoretical computer science.

Finally, there are a large number of outstanding researchers trained in India who are active in theoretical computer science across the world.

To name just two: Madhu Sudan and Subhash Khot have both won the Ne-vanlinna Prize awarded at the International Congress of Mathematicians.

References

1. Agrawal, M., Kayal,N. and Saxena, N. PRIMES is in P.

Annals of Mathematics 150 (2004), 781–793.

2. Foundations of Software Technology and Theoretical
Computer Science; https://www.fsttcs.org.in/
3. Indian Association for Research in Computing
Science; https://www.iarcs.org.in/

Meena Mahajan is a professor at The Institute of Mathematical Sciences, Chennai, India.

Madhavan Mukund is a professor at the Chennai Mathematical Institute, Chennai, India.

Nitin Saxena is a professor at the Indian Institute of Technology Kanpur, Kanpur, India.

© 2019 ACM 0001-0792/19/11

Theoretical
computer science
attracts some
of the brightest
graduate students
in the country.