Teorie konecnych modelu
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
