Kõrgemamõõtmeline ümberkirjutamine põhineb tähelepanekul, et teatud ümberkirjutamissüsteemid vastavad suunatud rakk-kompleksidele (directed cell complexes) erinevates dimensioonides. See annab meile geomeetrilise haarde ümberkirjutamissüsteemide ja nende tuletuste üle, ühendades arvutusliku matemaatika kõrgemate kategooriate ja homotoopiateooriaga: ümberkirjutamissüsteemid on suunatud rakk-kompleksid ning ümberkirjutamisreeglid on suunatud homotoopiad.

Selles doktoritöös võtame arvutusliku vaatenurga ning käsitleme kõrgemamõõtmelist ümberkirjutamist kui arvutusmudelit, milles n-mõõtmeline ümberkirjutus tähistab arvutust (n − 1)-mõõtmelisel andmestikul. Meie motivatsiooniks on küsimus, kas niisugune arvutusmudel võiks olla teostatav. Seda silmas pidades alustame diagrammide konstrueerimise arvutusliku keerukuse uurimisega diagrammiliste hulkade (diagrammatic sets) raamistikus. Üheks peamiseks tulemuseks on läbikäigu algoritm (traversal algorithm), mis lahendab isomorfismi probleemi ajaga O(n2 log(n)).

Seejärel uurime kõrgemamõõtmelise aladiagrammi sobitamise probleemi (subdiagram matching) ümberkirjutatavate aladiagrammide korral. Pakume välja algoritmi selle probleemi lahendamiseks suvalises dimensioonis ning anname ka ajalise ülemise piiri algoritmi tööajale. Üldjuhul kuulub probleem klassi NP. Lisaks näitame, et teatud tsüklilisuseta tingimuste korral — mis on rahuldatud kõikides diagrammides, mille dimensioon on väiksem või võrdne 3-ga — on algoritmi tööaeg polünoomne diagrammi suuruse suhtes. Siiani käsitletud diagrammid vastavad liimimisdiagrammidele (pasting diagrams). Töös lõpetame tsüklilisuseta tingimuste uurimisega üldisemas diagrammiraamistikus. Näitame, et ühe tsüklilisuseta tingimuse korral, mida käsitleme aladiagrammi sobitamise probleemi kontekstis, on diagrammikujuga määratud ω-kategooria vabalt genereeritud polügraafide mõttes. Samuti näitame, et tugevamate tsüklilisuseta tingimuste korral on see ω-kategooria ekvivalentne kas sellisega, mis on saadud täiendatud suunatud ahelkompleksist (augmented directed chain complex) Steiner’i mõttes, või koosneb üksnes diagrammi rakkude osahulkadest.

Doktoritöö ”Kõrgemamõõtmeliste diagrammide ümberkirjutamise arvutuslikud aspektid” on avaldatud Tehnikaülikooli raamatukogu digikogus.

Juhendajad:

• prof Amar Hadzihasanovic (TalTech)
• kaasjuhendaja: prof Pawel Sobocinski (TalTech)

Oponendid:

• prof Samuel Mimram, Ecole Polytechnique, Prantsusmaa;
• prof Fabio Zanasi, University College London (UCL), Suurbritannia.

Jälgi avalikku kaitsmist Zoomis

Meeting ID: 913 8289 7259
Passcode: 660867