Seminár z teoretickej informatiky - Peter Kostolányi (7.4.2017)
v piatok 7.4.2017 o 11:00 hod. v miestnosti M/213
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