Theoretical Computer Science

Kamal Lodaya

5th ICLA, 10-12 Jan'13, Chennai

14th TARK, 7-9 Jan'13, Chennai

32nd FSTTCS, 15-18 Dec, Hyderabad

10th ATVA, 3-6 Oct, Thiruvananthapuram
(submission 30 Apr)

9th ICTAC, 24-27 Sep, Bangalore
(notification 14 June)

Papers

Talks

Reviews

Tutorials

TCS at IMSc

IARCS

ALI

Research interests: Automata, concurrency, Petri nets, logic.

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

Short courses:

Model checking. IMSc, May 12.
A language-theoretic view of verification. In Modern applications of automata theory (Deepak D'Souza and Priti Shankar, eds), IISc-World Scientific (2012), to appear. Practical program verification, TECS workshop, Hyderabad, 14-18 Feb 08; 2nd Automata, concurrency and logic school, IMSc, 24-26 Jan 03; and IISc, Bangalore, 10 Sep-3 Oct 01.
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.
Temporal logic. 1st ISLA school, IIT Bombay, 3-18 Jan 06; and CLC '02, Kolkata, 28-31 Oct 02.
Programming concurrency and communication (slides). IMSc, June 11 and June-July 10; SNS College of Engg, Coimbatore, 25-26 Nov 10; PBS College, Vijayawada, 4-5 Aug 07; NIT Suratkhal, 23-27 July 07; St Joseph's College, Tiruchirapalli, 26-28 Aug 04; and Sacred Heart College, Tirupattur, 26-30 Apr 04.
Algorithms as machines. Resonance 14,4 (2009), pp 367-379. PSG Tech, Coimbatore, 2 Mar 12; UGC refresher course for college teachers, Madras University, 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.
Turing machines and computability. Automata and computability workshop, University of Colombo, 29 July-5 Aug 02; and 2nd Theoretical aspects of computer science course, IMSc, 15 Oct-9 Nov 01.

Tutorials:

Automata, concurrency and communication. VIT, Vellore, 14 July 11.

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, IIT Roorkee, 13-15 July 09; TIFR 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, IIT Kanpur, 12-15 Apr 07; and TIFR Mumbai, Mar 02.
Timed and hybrid automata. Models of embedded computation workshop, Banasthali, 15-19 Mar 07.
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:

From temporal logic to circuits. 9th Formal methods update, DAIICT, Gandhinagar, 15-17 July 10.
Doing automata theory over dense linear orders. 7th Formal methods update, TRDDC, Pune, 17-19 July 08.
Logical characterization of pushdown and automatic graphs. 5th Formal methods update, IIT Guwahati, 3-6 July 06.
Separation logic. 4th Formal methods update, IIT Bombay, 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:

Dov Gabbay and Karl Schlechta - Logical tools for handling change in agent-based systems. Online, Feb 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:

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.
Locality as product. CLC '11, Kolkata, 2-4 Sep 11.
Communication in subclasses of Petri nets. TIFR, Mumbai, 28 May 10; IMSc, Mar 10; and Formal theories of communication workshop, Lorentz Center, Leiden, 22-26 Feb 10.
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:

(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:

(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