Deskriptivna teorija složenosti: verifikacija modela (CROSBI ID 341938)
Ocjenski rad | magistarski rad (mr. sc. i mr. art.)
Podaci o odgovornosti
Botinčan, Matko
Rosenzweig, Dean ; Vuković, Mladen
hrvatski
Deskriptivna teorija složenosti: verifikacija modela
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.
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
nije evidentirano
engleski
Descriptive complexity theory: model verification
nije evidentirano
descriptive complexity theory; model verification; complexity classes; first-order logic; least fixed point logic; inflatory fixed point logic; reachability games; parity games; backtracking games
nije evidentirano
Podaci o izdanju
130
15.06.2005.
obranjeno
Podaci o ustanovi koja je dodijelila akademski stupanj
Prirodoslovno-matematički fakultet, Zagreb
Zagreb
