Algoritmická kombinatorika na dílčích slovech - Algorithmic Combinatorics on Partial Words

Algoritmická kombinatorika na dílčích slovech je kniha v oblasti kombinatorika slov a konkrétněji na dílčí slova. Autorem je Francine Blanchet-Sadri a v roce 2008 jej publikoval Chapman & Hall / CRC ve své knižní sérii Diskrétní matematika a její aplikace.

Témata

A částečné slovo je tětiva jejichž znaky mohou patřit danému abeceda nebo být zástupný znak. Takové slovo může představovat sadu řetězců nad abecedou bez zástupných znaků tím, že umožňuje nahrazení každého zástupného znaku jakýmkoli jediným znakem abecedy, nezávisle na nahrazení ostatních zástupných znaků. Dvě dílčí slova jsou kompatibilní, když se shodují na svých zástupných znakech, nebo ekvivalentně, když existuje řetězec, který oba odpovídají; jedno dílčí slovo ${ displaystyle x}$ obsahuje další dílčí slovo ${ displaystyle y}$ pokud jsou kompatibilní a pozice jiných než zástupných znaků ${ displaystyle x}$ obsahovat ty z ${ displaystyle y}$; ekvivalenty, řetězce odpovídající ${ displaystyle x}$ jsou podmnožinou těch, kterým odpovídá ${ displaystyle y}$.^[1]

Kniha má 12 kapitol,^[2] které lze seskupit do pěti větších částí. První část se skládá ze dvou úvodních kapitol, které definují dílčí slova, kompatibilitu a omezení a související pojmy. Druhá část zobecňuje na dílčí slova některé standardní výsledky opakování v řetězcích a třetí část studuje problém charakterizace a rozpoznávání primitivních dílčích slov, dílčích slov, která nemají opakování. Část čtyři se týká kódů definovaných ze sad dílčích slov v tom smyslu, že žádná dvě odlišná zřetězení dílčích slov ze sady nemohou být navzájem kompatibilní. Závěrečná část obsahuje tři kapitoly o pokročilých tématech, včetně konstrukce opakování daného počtu kopií dílčích slov, která jsou navzájem kompatibilní, výčet možných vzorů opakování dílčích slov a sady dílčích slov s vlastností, že každý nekonečný řetězec obsahuje podřetězec odpovídající sadě.^[1] Každá kapitola obsahuje sadu cvičení a konec této knihy poskytuje rady k některým z těchto cvičení.^[2]

Publikum a příjem

Ačkoli Algoritmická kombinatorika na dílčích slovech je primárně zaměřen na úroveň absolventa, recenzenta Miklós Bóna píše, že je z velké části „pozoruhodně snadno čitelný“, a navrhuje, že by jej mohli číst i pokročilí vysokoškoláci. Bóna však kritizuje knihu jako příliš zaměřenou na kombinatoriku slov jako na cíl sám o sobě, bez diskuse o tom, jak převést matematické struktury jiných typů na dílčí slova, aby na ně mohly být použity metody této knihy. Z důvodu tohoto nedostatku obecnosti a aplikace naznačuje, že publikum této knihy bude pravděpodobně sestávat pouze z dalších výzkumníků specializujících se na tuto oblast.^[1] Podobně, i když Patrice Séébold poznamenává, že tato oblast může být motivována aplikacemi ke srovnání genů, kritizuje knihu jako převážně katalog vlastních výsledků výzkumu autora v dílčích slovech, bez širšího tematického přehledu nebo identifikace základních témat a vět to by člověk očekával od učebnice, a naznačuje, že učebnice, která dosahuje těchto cílů, stále čeká na napsání.^[3]

Recenzent Jan Kratochvíl je pozitivnější, když nazývá tuto „první referenční knihu o teorii dílčích slov“, chválí její tempo od úvodního materiálu k pokročilejším tématům a píše, že dobře podporuje jeho základní tezi, že mnoho z hlavních výsledků v kombinatorice slov bez zástupných znaků lze rozšířit na částečná slova. Shrnuje to jako „vynikající učebnici i jako referenční knihu pro výzkumné pracovníky, kteří mají zájem“.^[2]

Reference