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
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
The FSTTCS Conference gave rise
to the Indian Association for Research
in Computing Science (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
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.
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
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
of the brightest
in the country.