Spring Semester

Computation theory with atoms

Lecturer: Bartosz Klin (University of Warsaw).

About the lecturer | Course Summary | Slides 1 2 3 4 5 | Additional material | Assignment

About the lecturer:

Bartek Klin obtained his PhD from University of Aarhus (Denmark) in 2004. After holding postdoctoral positions at the Universities of Sussex and Edinburgh, he held an EPSRC Fellowship at the University of Cambridge. He has been on the faculty of the University of Warsaw since 2010. His research is focused on concurrency theory, process algebra semantics, algebraic and coalgebraic methods in Theoretical Computer Science, and - more recently - computation theory.

His papers appeared at leading computer science conferences (CONCUR, LICS, POPL), and journals (Logical Methods in Computer Science). He also served as a PC member of several international conferences, including twice the International Colloquium on Automata, Languages and Programming (ICALP). He served as the general chair of the Fourth International Conference on Algebra and Coalgebra (CALCO'11).

Course summary:

First, a caveat: "atoms" here are mathematical rather than physical entities, so people hoping for some kind of nuclear computation devices will be disappointed.

"Computation with atoms" means computation over structures that are infinite, but exhibit a lot of symmetries that make them amenable to symbolic manipulation. Examples include automata over infinite alphabets that can only compare their letters for equality, pushdown automata, Turing machines subject to similar restrictions, etc. Traditional intuitions about computation models sometimes fail, for example automata or Turing machines do not determinize. However, many interesting problems remain decidable and tractable on infinite but highly symmetric domains.

In the course I will present: - the basic mathematical theory of sets with atoms, - notions of automata and Turing machines with atoms, with their (sometimes surprising) properties, - programming languages for computing with atoms with example applications.


Slides
Part 1: Register Automata
Part 2: Sets with Atoms
Part 3: Turing Machines
Part 4: Constraint Satisfaction Problems with Atoms
Part 5: Programming with Atoms

Additional material
Book by Mikolaj Bojanczyk


Assignment: problem set. Please submit the solutions at the address klin@mimuw.edu.pl by May 31st.