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
Type of course
Course coordinators
Learning outcomes
The knowledge of infinite state systems and their connections with model theory.
Assessment criteria
oral exam & homework assignments with star
Bibliography
Slightly infinite sets. Mikołaj Bojańczyk
https://www.mimuw.edu.pl/~bojan/upload/main-2.pdf
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: