Theoretical Computer Science

Kamal Lodaya

7th M4M, 10-12 Nov '11, Osuna

4th ICLA, 9-11 Jan '11, Delhi
(submission 31 July)

30th FSTTCS, 15-18 Dec, Chennai
(notification 13 Sep)

5th IPEC, 13-15 Dec, Chennai
(notification 23 Aug)

Logic and set theory, 15-17 Aug, Chennai
(satellite event of 26th ICM, 19-27 Aug, Hyderabad)

Papers

Reviews

Tutorials

Talks

TCS at IMSc

IARCS

ALI

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

Graduate teaching: Programming languages and correctness, logic, concurrency, automata II, theory of computation, computability, databases.

Short courses:

Programming concurrency and communication. IMSc, June-July 10; IARCS instructional course, Vijayawada, 4-5 Aug 07; Suratkhal, 23-27 Jul 07; Tiruchirapalli, 26-28 Aug 04; and Tirupattur, 26-30 Apr 04.

Automata, algorithms, parsing. UGC refresher course for college teachers, Madras University, 29-30 June 10, 22-23 July 04; DST lecture series, Krishnankoil, 28-29 Oct 06; and IARCS instructional course, Tiruchengode, 22-23 Sep 06.

Algorithms on machines, IMSc, May-June 09. Algorithms as machines. Resonance 14,4 (2009), pp 367-379. Presented at Easwari Engg College, Chennai, 30 Apr 10; IIT Roorkee, 19 Jan 08; and Kongu Engg College, Perundurai, 28-29 Dec 07.
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, Chennai, 15 Oct-9 Nov 01.

Tutorials:

A language-theoretic view of verification. Modern applications of automata theory, IISc-World Scientific (2010), 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.
Models for concurrency. TIFR Mumbai, May 09 and 21-23 Feb 06; and University of Birmingham, June 03.
Regularity. TIFR Mumbai, May 09, 4 Jul 08 and 6-9 Feb 07.
(with M. Praveen) The Petri net reachability problem. 8th Formal methods update, IIT Roorkee, 13-15 Jul 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.
Temporal logic. 1st ISLA school, IIT Bombay, 3-18 Jan 06; and Modal logic and applications, CLC workshop, Kolkata, 28-31 Oct 02.
Reasoning about time: points and intervals. Logic and artificial intelligence, CLC workshop, Kolkata, 13-16 Oct 03.
Parsing as deduction. Logic, automata and modelling, CLC summer seminar, Kolkata, 18-22 June 01.
Logic and automata on words and terms. 1st Automata, concurrency and logic school, IMSc, 26-28 Jan 01; and Complexity, logic and applications, CLC summer school, Kolkata, 24-30 June 99.

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.

Some talks:

LTL can be more succinct. 2nd Automata, concurrency and timed systems workshop, Chennai, 1-3 Feb 10.
Collecting garbage concurrently (but correctly). CLC annual meet, Kolkata, 18-20 Sep 09; and IMSc, 27 Nov 06.
Around dot depth two. 1st Automata, concurrency and timed systems workshop, Chennai, 29-31 Jan 09.
An unambiguous temporal logic. IIT Bombay, 21 Nov 08; Algebra, combinatorics and complexity, Ural State University, Ekaterinburg, 1-3 Oct 08; and University of Birmingham, 19 Sep 08.
An informatic history of first order time. Logic, navya-nyāya and applications, Jadavpur University, Kolkata, 3-7 Jan 07; and Advances and issues in timed systems, 26th FSTTCS workshop, ISI Kolkata, 11-12 Dec 06.
Looking back at process algebra. 11th AFL, Dobogókő, 17-20 May 05.
A logic for user-controlled navigation on the web. Knowledge and logic oriented software engineering, 1st ITPAR workshop, Mumbai, 19-21 Jan 05.
Hypercomputation. Logic, philosophy and applications, CLC workshop, Kolkata, 13-17 Oct 04.
A syntax for Petri nets. 2nd Automata, concurrency and logic workshop, IMSc, 27-29 Jan 03.
A definition of fusion for posets. Logic, graph transformations and discrete structures, 1st ICGT workshop, Barcelona, 11-12 Oct 02.
Poset languages. 1st Automata, concurrency and logic workshop, IMSc, 29-31 Jan 01.
A non-monoidal view of Petri nets. Logic and algebra in concurrency workshop, Dresden, 13-16 Sep 00.
Lines, a while, and intervals. Many-dimensional logical systems, 12th ESSLLI workshop, Birmingham, 6-18 Aug 00.

Book reviews:

Grumberg O., Kaminski M., Katz S., Wintner S. (eds) - Languages: from formal to natural, online Apr 10.

Raymond Turner - Computable models, online Sep 09.

Jeffrey Shallit - A second course in formal languages and automata theory. Computing Reviews, Feb 10.
Avron A., Dershowitz N. and Rabinovich A. (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 work:

(with A V Sreejith) LTL can be more succinct. 8th ATVA, Singapore, 21-24 September (2010).
(with Paritosh Pandya and Simoni Shah) Around dot depth two. 14th DLT, London (Canada), 17-20 August, 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 M. Praveen) Analyzing reachability for some Petri nets with fast growing markings. 2nd RP, Liverpool, ENTCS 223 (2008), pp 215-237.
(with Paritosh Pandya and Simoni Shah) Marking the chops: an unambiguous temporal logic. 5th TCS, Milano, IFIP 273 (2008), pp 461-476.
(with Kalpesh Kapoor and Uday Reddy) Fine-grained concurrency with separation logic. Manuscript, Nov 06.

Some finished work:

Marking time. 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 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