\begin{picture}(30,20) \put(0,0){\circle*{2}} \put(30,0){\circle*{2}} \pu... ... \put(20,10){\line(-2,1){20}} \bezier{150}(14,12)(15,15)(16,13) \end{picture}
$\textstyle \parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Zakładu Matematyki Dyskretnej
Wydziału Matematyki Stosowanej
AGH
We wtorek, 28 maja 2002 roku, o godzinie 12:45
w sali 304, łącznik A-3-A-4, A G H

Paweł OLEKSIK
(WMS, AGH)

wygłosi referat pod tytułem:

Ekspansywne gramatyki grafowe


Od czasu pierwszych publikacji związanych z tematyką gramatyk grafowych (Pfalt i Rosenfeld, 1969) podejmowanych byóo wiele prób zmierzenia się z problemem uogólnienia pojęć z teorii języków formalnych na struktury grafowe. Najistotniejsze trudności na jakie napotyka się przy rozważaniu języków i gramatyk grafowych jest złożoność obliczeniowa algorytmów analizy syntaktycznej (parsingu). W ogólnym przypadku jest to problem NP-zupełny, co wyklucza jakiekolwiek zastosowania praktyczne.
Dlatego naukowcy zajmuący się tą tematyką skupili się na ograniczaniu rozważanych klas grafów tak, aby języki generowane przez definiowane dla tych klas gramatyki można było przetwarzać w czasie wielomianowym. W rezultacie większość zdefiniowanych gramatyk generuje niewielkie klasy grafów, często bardzo specyficzne, bo dedykowane pod konkretne zastosowania. Do najważniejszych osiągnięć w tej dziedzinie należy zaliczyć ekspansywne gramatyki grafowe zaproponowane przez King-Sun Fu w 1983 roku. Generują one dość obszerną podklasę acyklicznych digrafów, a złożoność czasowa zdefiniowanego dla nich algorytmu parsingu jest rzędu $O(n^2)$.
 
Serdecznie zapraszamy wszystkich chętnych !