Infinite alphabets 1000-2M16AN

The first part of the course is devoted to automata in which despite of the fact that the alphabet is infinite it is augmented with some structure (e.g. order or equality). Examples or accepted languages are `all symbols are different', `the order on letters increases', `there are two equal symbols'.

The second part of the course is devoted to a more abstract theory, in which algorithms operate on infinite objects (such as the set of rationals) under condition that they have a finite description.

Programme:
1. Register automata
2. Automata checking for non-emptiness that use well-quasi orders and vector addition systems
3. Orbint-finite sets
4. Elements of model theory – oligomorphic and homogenic structures
5. Algorithms operating on orbit-finite sets