Mikołaj Bojańczyk

May 31, 2019
## PhD Open Lecture Problems

### Mistakes

### Problems

You can get points by either finding mistakes in the atom book or by solving problems.

**Grades:**3=2 points, 4=2.5 points, 5=3 points.

**Deadline: **June 30

Each mistake in the atom book (not counting solutions to exercises) gets you 0.1 points. Mark the mistakes on this page with your name, if it does not work you can use this google docs. Mistakes also include typos, bad grammar, and unclear parts (explain why), generally speaking anything that requires improvement. You don’t need to start to read the book from the beginning. The lecture corresponds to Chapters 3,4,7 and 10, but you are encouraged to find mistakes in other parts (later chapters have a higher expected mistake rate, so it might be profitable to look at them).

Each of the problems (see below) gets you 1 point if it is solved by ≥3 people including you, 2 points otherwise.

- Define a
*register automaton*to be an equivariant automaton where the state space is of the formfor some Find an example of oligomorphic atoms and a language over input alphabet which is recognised by a deterministic orbit-finite automaton, but is not recognised by any equivariant deterministic register automaton.

- Show an example of infinite oligomorphic atoms which satisfy the following property (*): if a language is recognised by (hereditarily orbit-finite) deterministic Turing machine, then the same is true for
- Show an example of infinite oligomorphic atoms where the property (*) from the previous problem is false.
- Assume that the atoms are the random undirected graph. Are the following two conditions equivalent for a class of finite graphs? (a) There is an equivariant nondeterministic orbit-finite automaton with input alphabet which recognises the language

(b) there is some such that property can be defined by a formula of first-order logic which has shape

- Assume that the atoms are the universal tree, i.e. the limit of trees modelled as structures with a closest common ancestor function. Is there are set builder expression, without constants, which defines a dense total order ?
- Let be oligomorphic atoms. Show that for every there can only be finitely many atoms such that the -orbit of is finite.
- Let be infinite oligomorphic atoms. Show that deterministic orbit-finite automata recognise strictly more languages than orbit-finite monoids.
- Let be infinite oligomorphic atoms. Show that universality is undecidable for nondeterministic orbit-finite automata.
- Consider the equality atoms. We say that a class of languages is
*closed under orbit-finite union*if for every orbit-finite set and finitely supported function , the class also contains the unionDefine the

*regular expressions*to be the smallest class of languages (over orbit-finite alphabets) which: contains all languages with finitely many words and is closed under orbit-finite union, concatenation and Kleene star . Do regular expressions define the same languages as nondeterministic-orbit finite automata?

March 30, 2018
## Lipa Summer School 2018 (June 25-28)

The Lipa Summer School (click here for the page of the school, including registration) is a summer school on topics connected to logic in computer science. The school consists of 4 mini-courses given by:

- Rajeev Alur (UPenn)
*Regular processing of data streams* - Matt Valeriote (McMaster)
*Finite algebras and connections with tree languages* - Igor Walukiewicz (Bordeaux)
*MSOL and higher-order computation* - Mikołaj Bojańczyk (Warsaw, organiser)
*Recognisable languages of graphs*

January 31, 2018
## How to run my slides

My slides are now deemed a security risk. To run them in Chrome, click this button:

I promise I’m not trying to hurt your computer. Promise.

I will be working on a better solution.

October 2, 2017
## Hilbert’s Basis Theorem and transducers

These slides show how to decide equivalence of tree-to-string transducers using the Hilbert Basis Theorem. The idea is based on

Helmut Seidl, Sebastian Maneth, Gregor Kemper:

Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable. FOCS 2015: 943-962

There are two parts:

- consider grammars that generate tuples of rational numbers, and use the Hilbert Basis Theorem to show that the following is decidable: “given a grammar, decide if the only tuple that it generates is the zero tuple”. slides
- reduce the equivalence problem for transducers to the zero-ness problem discussed above. slides

May 8, 2017
## Lipa Summer School (July 3-6, 2017)

The Lipa Summer School (click here for the page of the school, including registration) is a summer school on topics connected to logic in computer science. There will be 4 mini-courses given by:

- Stephan Kreutzer (Berlin)
*Algorithmic meta-theorems* - Joël Ouaknine (Saarbrücken)
*Decision Problems for Linear Recurrence Sequences* - Moshe Vardi (Rice)
*Linear-time verification and synthesis* - Mikołaj Bojańczyk (Warsaw, organiser)
*What is a recognisable language?*

March 27, 2017
## Positions (deadline April 30, 2017)

I am leading an ERC Consolidator grant on automata and logic called “A unified theory of finite-state recognisability”. The main goal is to find algebraic structures (like monoids) for things like infinite trees or profinite words. However, I can be very flexible on the topic, as long as it is tangentially connected to logic or automata.

I am searching for talented postdocs and phd students. The deadline for applications is April 30, 2017. Send applications to me by email. Please feel to ask questions before that date!

**Postdocs. **The postdoc can begin at any time from June 1 until the end of 2017. The duration is 6 – 12 months, with a possibility of extension for another year. The application consists of your name and 1-2 names of people who can provide references. I am looking for people with a good track record in the top conferences of the field. Teaching is optional.

**PhD students. **A typical duration is 4 years, starting any time from June 1 until the end of 2017. In application please include a cv and 1-2 names of people who can provide references. I am looking for candidates with a strong background in mathematics.

August 11, 2015
## Tree width à la metro

Here is a way of drawing graphs of bounded tree width, inspired by metro maps. The horizontal black lines are graph edges, the coloured shapes are vertices, and the gray background is the tree underlying the decomposition.

The mathematical content of the picture is that a graph has tree width *k* if and only if it is a subgraph of a (*k+1*)-colourable chordal graph (thanks to Michał Pilipczuk for pointing this out).

June 20, 2015
## EATCS council

In 2013, I joined the EATCS council. Here is what I promised to do:

I am a candidate for the EATCS council. My program consists of three items. The first item is something where I promise concrete action, the remaining two are more speculative.

- I will support open access, in particular for ICALP proceedings.
- In the long term, I think that the TCS community should move from publishing in conferences to publishing in journals. The ensuing travel is a waste of time and money. It is not clear to me how the EATCS can help solve this problem right now, without losing the accumulated prestige capital of ICALP. Maybe ICALP could move to a continuous submission model like VLDB?
- It is my impression that the current EATCS members are mainly people who have recently attended ICALP, which is a bit random. Membership should be made more representative. Maybe we should make membership free (but still feed EATCS from an ICALP tax)?

**Update.** The first item is solved: starting with 2016, ICALP will be using the open access LIPICS system. As it turned out, this idea had overwhelming support inside the council.

June 20, 2015
## Mojżesz Presburger in Warsaw

A presentation on documents about Mojżesz Presburger from the archives of Warsaw University

The documents in high resolution:

Birth certificate (Presburger was born in 1904, but this document is from August 1923)

Application to study at Warsaw University (September 1923)

Hand-written CV (September 1923)

Courses for the winter semester in 1924

Courses for the autumn/winter trimester in 1927/28

Graduation diploma (October 1930) (1/2)

Graduation diploma (October 1930) (2/2)

Court document concerning 70 złoty unpaid tuition (January 1939)