Teorie konecnych modelu
Jan Krajicek, jaro 2000, FF KU
Teorie konecnych modelu se odlisuje od obecne teorie modelu ve dvou aspektech. Jednak vetsina zakladnich vet a konstrukci obecne teorie modelu je infinitarni a ve tride konecnych struktur neplati. Do popredi se tak dostavaji zajimave metody zalozene na ruznych hrach (napr.Ehrenfeucht-Fraisse hry ci oblazkove hry) a pravdepodobnostni konstrukce.
Druhym dulezitym aspektem je primy vztah mezi definovatelnosti v konecnych strukturach a algoritmickou rozhodnutelnosti s omezenou vypocetni slozitosti. Nektere problemy teorie slozitosti se tak daji zformulovat v teorii konecnych modelu bez pouziti pojmu Turingova stroje.
Pozadavky: zakladni kurs logiky/t.modelu
Literatura: J.Flum - H.-D.Ebbinghaus:"Finite Model Theory", Springer, 1995.
Postupne bude k dispozici strucny syllabus a nektere doplnujici reference.
Webova stranka Finite Model Theory Homepage