Jelenlegi hely
Tanszékcsoporti szeminárium
Félév:
2015/16 I. félév
Helyszín:
Árpád tér 2. II. em. 220. sz.
Dátum:
2015-10-27
Időpont:
14:00-15:00
Előadó:
Krész Miklós (SZTE JGYPK)
Cím:
Hálózat alapú automaták
Absztrakt:
Hálózat alapú automaták alatt olyan rendszereket értünk, melyeknek az alapobjektuma egy gráf, a rendszer állapotait az élek bizonyos részhalmazai határozzák meg, az átmeneteket pedig a kitüntetett interfész csúcsok (külső csúcsok) közötti alternáló séták indukálják. Ezen típusú rendszerek alapját a H. Jürgensen és J. Dassow által 1990-ben definiált Szoliton automata adja, amely esetében az állapotok az úgynevezett teljes belső párosítások (olyan párosítások, amelyek legfeljebb külső csúcsokat nem fednek le). A hálózat alapú automaták egyrészt a Szoliton automaták általánosításainak tekinthetőek. Másrészt viszont a hálózat alapú automaták reprezentálják az úgynevezett Gráf Turing gépek olyan egyszerűsített típusait, melyeknél az egyes csúcspontokhoz rendelt automaták állapotait az adott csúcspontra illeszkedő élek egy-egy részhalmaza jelöli ki. Az előadás során ezen automaták komplexitását több szempontból analízáljuk. Egyrészt a transzformációs monoidon, valamint kompozíciós kérdéseken keresztül a hálózat alapú automaták számítási erejéről kapunk képet. Másrészt elemezzük a szimulációs komplexitást, azaz megvizsgáljuk, hogy az alapobjektumot adó gráf méretének függvényében milyen esetekben lehet az átmeneteket polinomiális időben meghatározni. Végezetül azon kérdés eldöntésének komplexitását vesszük górcső alá, hogy egy adott hálózat által definiált automata determinisztikus-e.