Alfabety nieskończone 1000-2M16AN

Pierwsza część wykładu dotyczy automatów, gdzie alfabet jest nieskończony, ale wyposażony w pewną strukturę (np. porządek, albo tylko równość). Przykłady języków to “wszystkie litery są różne”, “litery są rosnące”, “pewne dwie litery są takie same”.

Druga część wykładu dotyczy bardziej abstrakcyjnej teorii, gdzie algorytmy przetwarzają obiekty nieskończone (jak np. zbiór liczb wymiernych), oczywiście pod warunkiem pewnego skończonego opisu.

Program:
1. Automaty rejestrowe
2. Algorytmy sprawdzające niepustość korzystające z well-quasi orders oraz vector addition systems
3. Zbiory skończenie orbitowe
4. Trochę teorii modeli – struktury oligomorficzne i homogeniczne
5. Algorytmy przetwarzające zbiory skończenie orbitowe