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.