Combinatorical and Algebraic Structures Seminar
Session details
Date: | 18.11.2014 |
Speaker: | Kateřina Medková, FJFI, České vysoké učení technické v Praze |
Title: | Lyndon + Christoffel = digitally convex |
Abstract: | Budeme referovat o článku S. Brlek, J.-O.Lachaud, X. Provencal, C. Reutenauer: Lyndon + Christoffel = digitally convex. Článek využívá poznatky z kombinatoriky na slovech ke konstrukci efektivních algoritmů využitelných v diskrétní geometrii. V první části se seznámíme s potřebným kombinatorickým základem, zejména si představíme tzv. Lyndonova a Christoffelova slova. Poté si definujeme digitální konvexitu a představíme si algoritmus na ověřování konvexity zadané diskrétní množiny. Algoritmus je založen na Lyndonově faktorizaci slov a rozpoznávání Christofellových faktorů. |
Return to index.
last update: 27.9.2007, webmaster: Petr Ambrož