50 Years of Theoretical Computer Science

Since the birth of ICALP and the EATCS

This year’s edition of the International Colloquium on Automata, Languages and Programming (ICALP) marks the 50th anniversary of the conference.

When first held in July 1972 at IRIA Rocquencourt near Paris, ICALP was the first conference for the newly drafted European Association for Theoretical Computer Science (EATCS). Beyond the start of a new academic venue, this was in many ways a defining moment for theoretical computer science.

An exhibition celebrating 50 years of Theoretical Computer Science since the birth of ICALP and the EATCS is on display during the conference.

History

In the early 1970’s, computer science was generally viewed as a technology to support other enterprises, and had only recently won its autonomy as an academic discipline.

There was absolutely no appreciation of the work on the issues of computing. Mathematicians did not recognize the emerging field.

Michael Rabin

It was becoming clear however that studies were needed in order to improve the correctness and efficiency of large-scale programs. This motivated new theoretical approaches to computer science, ones that would use mathematical and logical tools to clarify and study the notion of computation. (On a more pragmatic note, this pen-and-paper endeavour had the further advantage of requiring comparably little funding, at a time when computers were massive devices whose costs could only be met by few universities.)

An IBM 360 mainframe computer in 1972.
(CC-BY-SA 4.0, Yves Tessier, Kalos, Bibliothèque de l’Université Laval)
Marcel-Paul Schutzenberger at ICALP in 1972.
(© Inria / Photo Studio 9)

A theoretical computer scientist will have the same aim as any other computer scientist: namely to understand, analyze and hopefully clarify the fascinating concept of computation. The theoretical computer scientist distinguishes himself by his choice of the ways to achieve such an understanding and clarification—the choice being, after proper models have been formalised, to prove theorems that are meaningful. With the mathematician and logician, the theoretical computer scientist has in common the knowledge that sometimes the solution to a problem has to be obtained at some distance from the problem itself, and that an extensive knowledge of the relevant objects and concepts has to be developed before any major question can be answered.

Maurice Nivat

Theoretical computer science existed before the first ICALP, and that was not the first series of meetings dedicated to the topic: the annual symposium on SWitching and Automata Theory (nowadays known as IEEE FOCS) and the Symposium on Theory of Computing (ACM STOC) had been running for several years in North America. But such work in Europe tended to be local and national. Initially envisioned in an attempt to secure funding and foster collaborations among selected researchers and their institutions, the EATCS was established in September 1972 and opened to new members, growing rapidly and helping build a vibrant community through ICALP, the Bulletin of the EATCS, the journal Theoretical Computer Science, and yearly Spring schools.

Highlights

There was a very special spirit in the air; we knew that we were witnessing the birth of a new scientific discipline centered on the computer.

Richard Karp

Maurice Nivat, Louis Nolin, and Marcel-Paul Schützenberger outlined the main pillars of the new scientific discipline in their Rapport préliminaire sur l’informatique théorique, and even held a press conference announcing the birth of theoretical computer science.

The original vision revolved around three main areas: algorithms and complexity, automata and formal languages, and programming languages. These core topics have grown considerably in scope and in depth since 1971, and have found wide-ranging impact on the real world.

Theoretical computer science has also spawned into many new directions: distributed computing, databases, machine-checked proofs, quantum computing, cryptography, machine learning, model-checking, etc.

Special Thanks

Special thanks to all the people involved into creating this exhibition.

Coordination

Sandrine Cadet (IRIF, Université Paris Cité), Sylvain Schmitz (IRIF, Université Paris Cité)

Scientific Advisory Board

Luca Aceto (Reykjavik University), Susanne Albers (Technische Universität München), Giorgio Ausiello (Sapienza University of Rome), Gilles Dowek (ENS Paris-Saclay), Phokion G. Kolaitis (UC Santa Cruz), Mike Paterson (University of Warwick), Sylvain Schmitz (IRIF, Université Paris Cité)

Additional Contributors

Simon Apers (CNRS), Alex Bredariol Grilo (LIP6, CNRS, Sorbonne Université), Ioannis Catzigiannakis (Sapienza University of Rome), Geoffroy Couteau (CNRS), Pierluigi Crescenzi (Gran Sasso Science Institute, L’Aquila), Irène Guessarian (IRIF, Université Paris Cité), Hugo Herbelin (Inria, IRIF), Ce Jin (MIT), Jean-Jacques Levy (Inria, IRIF, CNRS), Kurt Melhorn (Max-Planck-Institut für Informatik), Subhasree Patro (QuSoft, CWI Amsterdam), Sylvain Périfel (IRIF, Université Paris Cité), Jean-Éric Pin (IRIF, CNRS)


Co-organizers

IRIF
FSMP
Université Paris Cité
EATCS

Partners

CNRS
Inria
Nomadic Labs

CONTACT US
icalp2022@irif.fr
@ICALPconf