Nie jesteś zalogowany | Zaloguj się

Regular Path Queries problems under different semantics

Prelegent(ci)
Bartosz Ruszewski
Afiliacja
MIMUW
Termin
19 października 2023 12:15
Pokój
p. 4060
Seminarium
Seminarium "DeSeR: Dane, strumienie, rozpraszanie"

Na dzisiejszym referacie opowiemy sobie o grafowych bazach danych, powiemy sobie jak z pozoru łatwe problemy grafowe stają się NP trudne w momencie gdy dodamy do nich wyrażenie regularne. Opowiemy sobie o tym jak wybrana semantyka ścieżek wpływa na złożoność obliczeniową problemów, oraz jakie realne konsekwencje niesie to ze sobą.
Zdefiniujemy klasę STE (Simple Transitive Expressions) dla wyrażeń regularnych, i pokażemy na niej ważną zasadę dychotomii która pozwala na dokładniejsze określenie złożoności obliczeniowej danych problemów.