Fakulta matematiky, fyziky
a informatiky
Univerzity Komenského v Bratislave

Seminár z teoretickej informatiky - Peter Kostolányi

v piatok 16.3.2018 o 11:00 hod. v miestnosti M/213


13. 03. 2018 10.54 hod.
Od: Rastislav Královič

Prednášajúci:  Peter Kostolányi

Názov:  Algebraické systémy nad sumačnými polokruhmi

Termín:  16.3.2018, 11:00 hod., M/213

Abstrakt: 
Algebraické systémy nad polokruhmi sú známym zovšeobecnením (aj) bezkontextových gramatík, pri ktorom sa od generovania bezkontextových jazykov (čiže algebraických prvkov v polokruhu formálnych jazykov) prechádza k realizácii algebraických prvkov v nejakom všeobecnejšom polokruhu. Nie je ale možné zmysluplne definovať prvok realizovaný ľubovoľným algebraickým systémom nad ľubovoľným polokruhom - a to ani v prípade, že sa obmedzíme na najčastejšie skúmaný špeciálny prípad polokruhov nekomutatívnych formálnych mocninových radov. Typická prezentácia teórie algebraických systémov tak zvyčajne začína voľbou: buď sa pozornosť venuje len nejakej špeciálnej triede polokruhov, ako sú napríklad spojité polokruhy alebo úplné polokruhy, alebo sa nad všeobecným polokruhom mocninových radov pracuje len so systémami spĺňajúcimi určité podmienky. To je obzvlášť nepríjemné z dôvodu, že výsledné teórie vykazujú mnohé spoločné znaky.

Na prednáške predstavíme zjednocujúci prístup k definovaniu algebraických prvkov polokruhu, ktorý eliminuje nutnosť tejto voľby tým, že zahŕňa obidva zvyčajné prístupy (to možno z časti prirovnať efektu Ésikovej a Kuichovej zjednocujúcej teórie racionálnych prvkov polokruhu, ktorá ale využíva odlišné prostriedky). Pôjde o metódu založenú na pojme sumačného polokruhu (ide tu o premenovanie Sigma-polokruhov Hebischa a Weinerta) a na priraďovaní určitých jednoznačných bezkontextových jazykov premenným každého algebraického systému. Na tejto všeobecnej úrovni potom dokážeme dva klasické výsledky pre algebraické systémy: ich ekvivalenciu so zásobníkovými automatmi a Chomského- Schützenbergerovu vetu o reprezentácii. Prínosom prezentovaného prístupu tiež bude možnosť dokazovať určité tvrdenia pre algebraické systémy nad polokruhmi ako jednoduché dôsledky známych tvrdení pre bezkontextové jazyky.


web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php