Combinatorical and Algebraic Structures Seminar
Session details
Date: | 4.4.2017 |
Speaker: | Edita Pelantová, |
Title: | Enumerace jazyků definovaných antislovníkem |
Abstract: | Antislovnik $T$ je konečný seznam slov nad konečnou abecedou $A$. Všechna konečná slova nad abecedou $A$, která neobsahují jako svoje podslovo žádný faktor z $T$, tvoří jazyk $L(T)$ zadaný antislovníkem $T$. V roce 1981 Guibas a Odlyzko odvodili metodu na určení počtu slov délky $n$ v jazyce $L(T)$. Tato metoda využívá formalizmus generujících funkcí. Představíme metodu Guibase a Odlyzka a budeme diskutovat její vztah k metodě založené na Aho-Corasickové automatu. |
Return to index.
last update: 27.9.2007, webmaster: Petr Ambrož