Seminár z teoretickej informatiky - Peter Kostolányi (7.4.2017)

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

03. 04. 2017 21.49 hod.
Od: Rastislav Královič

Prednášajúci: Peter Kostolányi

Názov: Bezkontextové gramatiky a analytická kombinatorika

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

Abstrakt:
Asymptotické vyčíslenie počtu slov dĺžky n generovaných danou bezkontextovou gramatikou je úloha veľkého významu ako pre enumeratívnu kombinatoriku, tak aj pre teóriu bezkontextových jazykov. Výskum otázok s touto úlohou spojených bol pre jednoznačné gramatiky z veľkej časti zavŕšený nedávnym analyticko-kombinatorickým výsledkom Banderiera a Drmotu charakterizujúcim Puiseuxove rozvoje N-algebraických funkcií. V prvej časti prednášky podáme prehľad vybraných konceptov a tvrdení z oblasti analytickej kombinatoriky s hlavným cieľom priblížiť znenie a myšlienku dôkazu Banderierovej-Drmotovej vety a ozrejmiť jej kľúčové dôsledky.

V rámci druhej časti prednášky odprezentujeme časť originálneho výskumu zameraného na analýzu využívania prepisovacích pravidiel a neterminálov v (nie nutne jednoznačných) bezkontextových gramatikách, ktorý sa o teóriu okolo Banderierovej-Drmotovej vety silno opiera. Hlavnými výsledkami pritom budú charakterizácie bezkontextových gramatík s proporčným využívaním prepisovacích pravidiel resp. neterminálov.

(Prezentované originálne výsledky sú spoločnou prácou s B. Rovanom.)

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