Seminar za matematičku logiku i osnove matematike

lokacija: 
PMF Matematički odsjek
vrijeme: 
13.05.2019 - 17:00 - 18:30
Na Seminaru za matematičku logiku i osnove matematike, u ponedjeljak 13.
svibnja 2019. u 17 sati, u predavaonici 105, PMF-MO, Vedran Čačić će
održati predavanje
 
Büchijevi automati koji prepoznaju Hintikkina stabla (3)
 
Sažetak: Ovo je nastavak seminara održanog krajem 2017. godine, u sklopu
dokaza da je ispunjivost čvor-formula logike CPDL s dodanim negacijama
atomarnih programa EXPTIME-potpuna (netrivijalan dokaz je da je postoji
EXPTIME-algoritam). Tada smo izgradili Hintikkina stabla koja predstavljaju
modele (za jednu fiksnu formulu) te logike. Sada ćemo konstruirati
Büchijeve automate koji ih prepoznaju, što znači da ćemo za fiksnu formulu
fi moći izgraditi ne preveliki automat čiji jezik je neprazan ako i samo
ako fi ima model. Kako je provjera nepraznosti jezika zadanog Büchijevog
automata odlučiva u eksponencijalnom vremenu, time ćemo dokazati traženu
tvrdnju.
 
Predavanje se može pratiti i on-line na sljedećoj adresi:
Share this