Theoretical Computer Science faculty

Kamal Lodaya

5th ISLA, 6-17 Jan 2014, Tezpur

33rd FSTTCS, 10-14 Dec, Guwahati

Papers

Talks

Reviews

Tutorials

TCS at IMSc

IARCS

ALI

Research interests: Concurrency, Petri nets, logic, automata.

Graduate teaching: Automata II, logic, theory of computation, infinite discrete structures, concurrency, programming languages, computability, databases.

Short courses:

Turing machines and computability. University of Chennai, 21-22 Nov 12; A celebration of Turing, IMSc thematic lectures, 25 Aug 12; Automata and computability workshop, Colombo, 29 July-5 Aug 02; and 2nd Theoretical aspects of computer science course, IMSc, 15 Oct-9 Nov 01.
Programming concurrency and communication (slides). IMSc, 23 June 12, June 11 and June-July 10; SNS College of Engg, Coimbatore, 25-26 Nov 10; PBS College, Vijayawada, 4-5 Aug 07; NIT Surathkal, 23-27 July 07; St Joseph's College, Tiruchirapalli, 26-28 Aug 04; and Sacred Heart College, Tirupattur, 26-30 Apr 04.
Model checking. IMSc, May 12; 2nd Automata, concurrency and logic school, IMSc, 24-26 Jan 03; Bangalore, 10 Sep-3 Oct 01.
Algorithms as machines. Resonance 14,4 (2009), pp 367-379. PSG Tech, Coimbatore, 2 Mar 12; University of Chennai, 29-30 June 10 and 22-23 July 04; Easwari Engg College, Chennai, 30 Apr 10; IMSc, May-June 09; IIT Roorkee, 19 Jan 08; Kongu Engg College, Perundurai, 28-29 Dec 07; AK College of Engg, Krishnankoil, 28-29 Oct 06; and KSR College of Technology, Tiruchengode, 22-23 Sep 06.

Tutorials:

Using formal logic in programming. University of Chennai, 7 Dec 12; AVIT Paiyanoor, Feb 09; Practical program verification, Hyderabad, 14-18 Feb 08.

Alan Turing and the origin of computer science. Tezpur University, 2 Nov 12.

Logic and definability on words and trees. 4th ISLA school, Manipal, 9-20 Jan 12; 1st Automata, concurrency and logic school, IMSc, 26-28 Jan 01; and CLC '99, Kolkata, 24-30 June 99.
Programs, proofs, languages and questions of provability. Concurrency workshop, TIFR Mumbai, 12 Nov 10.
Models for concurrency. TIFR Mumbai, May 09 and 21-23 Feb 06; and University of Birmingham, June 03.
Regularity. TIFR Mumbai, May 09, 4 July 08 and 6-9 Feb 07.
(with M. Praveen) The Petri net reachability problem. 8th Formal methods update, Roorkee, 13-15 July 09; Mumbai, 18 Nov 08; and 2nd RP workshop, Liverpool, 15-17 Sep 08.
(with Srikanth Srinivasan) Monadic logic of finite graphs. 6th Formal methods update, Kanpur, 12-15 Apr 07; Mumbai, Mar 02.
Timed and hybrid automata. Models of embedded computation workshop, Banasthali, 15-19 Mar 07.
Temporal logic. 1st ISLA school, IIT Bombay, 3-18 Jan 06; and CLC '02, Kolkata, 28-31 Oct 02.
Reasoning about time: points and intervals. CLC '03, Kolkata, 13-16 Oct 03.
Parsing as deduction. CLC '01, Kolkata, 18-22 June 01.

Update talks:

Probabilistic systems and their verification. Guwahati, 1 Nov 12; IMSc, 30 Aug 12; 11th Formal methods update, Chennai, 19-21 July 12; Mumbai, June 12.
From temporal logic to circuits. 9th Formal methods update, Gandhinagar, 15-17 July 10.
Doing automata theory over dense linear orders. 7th Formal methods update, Pune, 17-19 July 08.
Logical characterization of pushdown and automatic graphs. 5th Formal methods update, Guwahati, 3-6 July 06.
Separation logic. 4th Formal methods update, Mumbai, 18-22 July 05.
Infinite state automata. 3rd update, IMSc, 29 Feb-2 Mar 04.
Monadic second order logics and timed sequences. 2nd update, IMSc, 16-20 June 97.

Book reviews:

Tiziano Villa, Nina Yevtushenko, Robert Brayton, Alan Mishchenko, Alexandre Petrenko and Alberto Sangiovanni-Vincentelli - The unknown component problem: theory and applications. Computing Reviews, Nov 12.
Dov Gabbay and Karl Schlechta - Logical tools for handling change in agent-based systems. Computing Reviews, Oct 11.
Ernst-Erich Doberkat - Stochastic coalgebraic logic. Computing Reviews, Aug 11.
Manfred Droste, Werner Kuich and Heiko Vogler (eds) - Handbook of weighted automata. Computing Reviews, Mar 11.
Orna Grumberg, Michael Kaminski, Shmuel Katz and Shuly Wintner (eds) - Languages: from formal to natural. Computing Reviews, Feb 11.
Raymond Turner - Computable models. Computing Reviews, Sep 10.
Jeffrey Shallit - A second course in formal languages and automata theory. Computing Reviews, Feb 10.
Arnon Avron, Nachum Dershowitz and Alexander Rabinovich (eds) - Pillars of computer science. Computing Reviews, Nov 09.
Javier Esparza and Keijo Heljanko - Unfoldings. Computing Reviews, Sep 09.
Marco Aiello, Ian Pratt-Hartmann and Johan van Benthem (eds) - Handbook of spatial logics. Computing Reviews, Nov 08.
Eric Schechter - Classical and nonclassical logics. Computing Reviews, Sep 06.
Leonid Libkin - Elements of finite model theory. Computing Reviews, Mar 05.
Melvin Fitting - Types, tableaus and Gödel's god. Computing Reviews, Nov 03.
(with Sitabhra Sinha) Michael Arbib (ed) - The handbook of brain theory and neural networks. Computing Reviews, June 03.
Stephen Wolfram - A new kind of science. Reviewed in 03.
Patrick Blackburn, Maarten de Rijke and Yde Venema - Modal logic. Computing Reviews, May 02.
Susantha Goonatilake - Toward a global science: mining civilizational knowledge. Review of Development and Change V,2, Dec 00.
Melvin Fitting and Richard L. Mendelsohn - First-order modal logic. Computing Reviews, Mar 00.

Recent talks:

Automata, concurrency and communication. Anna University, Chennai, 16 Nov 12; VIT, Vellore, 14 July 11; TIFR, Mumbai, 28 May 10; IMSc, Mar 10; and Formal theories of communication workshop, Lorentz Center, Leiden, 22-26 Feb 10.
Locality and free choice. IIT Bombay, 11 June 12; CLC '11, Kolkata, 2-4 Sep 11.
Countifiers. ISI Chennai, 16 Apr 12; IMSc, 27 Mar 12; TIFR, Mumbai, 26 May 11.
Fine-grained concurrency with separation logic. TU Darmstadt, 5 Sep 11; CLC '09, Kolkata, 18-20 Sep 09; and IMSc, 27 Nov 06.
LTL can be more succinct. 2nd Automata, concurrency and timed systems workshop, Chennai, 1-3 Feb 10.

Recent work:

(with R. Ramanujam) Axioms for locality as product. In Reminiscing ideas and interactions: essays in honour of Mihir Kr. Chakraborty, Calcutta Logic Circle (2011), pp 162-180.
(with Madhavan Mukund and Ramchandra Phawade) Kleene theorems for product systems. 13th DCFS, Limburg, LNCS 6808 (2011), pp 235-247.
(with A.V. Sreejith) LTL can be more succinct. 8th ATVA, Singapore, LNCS 6252 (2010), pp 245-258.

Some finished work:

A language-theoretic view of verification. In Modern applications of automata theory (Deepak D'Souza and Priti Shankar, eds), IISc research monographs, World Scientific (2012), pp 149-169.
(with Kalpesh Kapoor and Uday Reddy) Fine-grained concurrency with separation logic. J. Philos. Logic 40,5 (Oct 2011), pp 583-632.
(with M. Praveen) Parameterized complexity results for 1-safe nets. 22nd Concur, Aachen, LNCS 6901 (2011), pp 358-372.
(with Paritosh Pandya and Simoni Shah) Around dot depth two. 14th DLT, London (Canada), LNCS 6224 (2010), pp 303-314.
(with M. Praveen) Modelchecking counting properties of 1-safe nets with buffers in paraPspace. 29th FSTTCS, Kanpur, LIPIcs 4 (2009), pp 347-358.
(with Paritosh Pandya and Simoni Shah) Marking the chops: an unambiguous temporal logic. 5th TCS, Milano, IFIP 273 (2008), pp 461-476.
(with M. Praveen) Analyzing reachability for some Petri nets with fast growing markings. 2nd RP, Liverpool, ENTCS 223 (2008), pp 215-237.
Marking time. In Logic, navya-nyāya and applications (Mihir K.Chakraborty, Benedikt Löwe, Madhabendra Nath Mitra and Sundar Sarukkai, eds.), College Publications (2008), pp 185-203.
(with Paritosh Pandya) A dose of timed logic, in guarded measure. 4th Formats, Paris, LNCS 4202 (2006), pp 260-273.
Product automata and process algebra. 4th SEFM, Pune, IEEE (2006), pp 128-136.
A regular viewpoint on processes and algebra. Acta Cybernetica 17,4 (2006), pp 751-763.
Petri nets, event structures and algebra. In Formal models, languages and applications (K.G. Subramanian, K. Rangarajan and Madhavan Mukund, eds.), World Scientific (2006), pp 246-259.
(with D. Ranganayakulu and K. Rangarajan) Hierarchical structure of 1-safe Petri nets. 8th Asian, Mumbai, LNCS 2896 (2003), pp 173-187.
(with D. Ranganayakulu) Infinite series-parallel posets of 1-safe nets. Proc Algorithms and Artificial Systems, Chennai, Allied (2003), pp 107-124.
(with R. Ramanujam) An automaton model of user-controlled navigation on the web. 5th CIAA, London (Canada) '00, LNCS 2088 (2001), pp 208-216.
Sharpening the undecidability of interval temporal logic. 6th Asian, Penang, LNCS 1961 (2000), pp 290-298.
(with Pascal Weil) Rationality in algebras with a series operation. Information and Computation 171,2 (2001), pp 269-293.
(with Pascal Weil) Series-parallel languages and the bounded-width property. TCS 237,1-2 (2000), pp 347-380.
(with Rohit Parikh, R. Ramanujam and P.S. Thiagarajan) A logical study of distributed transition systems. Information and Computation 119,1 (1995), pp 91-115.
(with R. Ramanujam and P.S. Thiagarajan) Decidability of a partial order based temporal logic. 20th ICALP, Lund, LNCS 700 (1993), pp 582-592.
(with R. Ramanujam and P.S. Thiagarajan) Temporal logics for communicating sequential agents: I. IJFOCS 3,2 (1992), pp 117-159.
(with Madhavan Mukund, R. Ramanujam and P.S. Thiagarajan) Models and logics for true concurrency. Sādhanā 17, Part 1 (1992), pp 131-165.
(with R.K. Shyamasundar) Proof theory for exception handling in a tasking environment. Acta Informatica 28 (1991), pp 7-41.
Proof theory for exception handling in distributed programs, PhD thesis, TIFR, Bombay University (1988).

Edited collections:

Proc. 5th ICLA, Chennai, LNCS 7750, Springer (2013).
(with Meena Mahajan) Proc. 30th FSTTCS, Chennai, LIPIcs 8 (2010).
(with Madhavan Mukund and R. Ramanujam) Perspectives in concurrency theory, Universities Press, CRC Press (2009).
The paper "Folding systems of communicating agents" in this volume, by myself and S.Paul, has a serious bug. Philippe Darondeau gave us an example event structure from his paper "Context-free event domains are recognizable" with Eric Badouel and J.-C. Raoult (1999) on which our proof does not work.
(with Meena Mahajan) Proc. 24th FSTTCS, Chennai, LNCS 3328, Springer (2004).

Science stuff:

Jantar mantar, a science magazine for children in English
Thulir, a science magazine for children in Tamil
(An article about) Tamil nadu science forum, a voluntary organization which publishes both these magazines
Pondicherry science forum, a voluntary organization which supports both these magazines
Indian scientists against nuclear weapons
(An article about) Indian scientists who disapprove of Mr Modi