Naslov
Deskriptivna teorija složenosti: verifikacija modela
(Descriptive complexity theory: model verification)

Autori
Botinčan, Matko

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, magistarski rad

Fakultet
Prirodoslovno matematički fakultet - Matematički odjel

Mjesto
Zagreb

Datum
15.06

Godina
2005

Stranica
130

Mentor
Rosenzweig, Dean ; Vuković, Mladen

Ključne riječi
deskriptivna teorija složenosti; verifikacija modela; klase složenosti; logika prvog reda; logika najmanje fiksne točke; logika inflatorne fiksne točke; igre dostiživosti; igre parnosti; igre s povratom
(descriptive complexity theory; model verification; complexity classes; first-order logic; least fixed point logic; inflatory fixed point logic; reachability games; parity games; backtracking games)

Sažetak
Tema rada je deskriptivna teorija složenosti s glavnim naglaskom stavljenim na analizu i rješavanje problema verifikacije modela. U prvom dijelu rada izlažu se klasični rezultati deskriptivne teorije složenosti o hvatanju istaknutih klasa složenosti odgovarajućim logikama. Drugi i središnji dio rada bavi se problemom verifikacije modela za logike fiksne točke pomoću pristupa baziranog na igrama. Nakon razmatranja najvažnijih logika fiksne točke i njihovih istaknutih svojstava, uvode se osnovni pojmovi i rezultati teorije beskonačnih igara za dva igrača. Posebno su razmotrene igre dostiživosti, igre parnosti i igre s povratom, te algoritmi za njihovo rješavanje. U završnom dijelu rada uspostavlja se veza između problema verifikacije modela za pojedine logike i odgovarajućih tipova igara. Dokazuje se da igre dostiživosti predstavljaju igre za verifikaciju modela za logiku prvog reda, igre parnosti za logiku najmanje fiksne točke, te igre s povratom za logiku inflatorne fiksne točke.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA