Алгоритмическая комбинаторика частичных слов - Algorithmic Combinatorics on Partial Words

Алгоритмическая комбинаторика частичных слов это книга в области комбинаторика слов, и более конкретно на частичные слова. Он был написан Франсин Бланше-Садри и опубликован в 2008 году компанией Chapman & Hall / CRC в их серии книг «Дискретная математика и ее приложения».

Темы

А частичное слово это нить чьи персонажи могут принадлежать к данному алфавит или быть подстановочный знак. Такое слово может представлять набор строк в алфавите без подстановочных знаков, позволяя заменять каждый подстановочный знак любым одиночным символом алфавита, независимо от замен других подстановочных знаков. Два частичных слова совместимы, если они согласовывают свои символы без подстановочных знаков, или, что эквивалентно, когда есть строка, которой они оба соответствуют; одно частичное слово ${\displaystyle x}$ содержит другое частичное слово ${\displaystyle y}$ если они совместимы и позиции без подстановочных знаков ${\displaystyle x}$ содержат те из ${\displaystyle y}$; эквивалентно, строки, соответствующие ${\displaystyle x}$ являются подмножеством тех, которые соответствуют ${\displaystyle y}$.^[1]

В книге 12 глав,^[2] которые можно разделить на пять больших частей. Первая часть состоит из двух вводных глав, определяющих частичные слова, совместимость и локализацию, а также связанные концепции. Вторая часть обобщает на частичные слова некоторые стандартные результаты о повторениях в строках, а третья часть изучает проблему определения и распознавания примитивных частичных слов, частичных слов, которые не имеют повторения. Четвертая часть касается кодов, определенных из наборов частичных слов в том смысле, что никакие две отдельные конкатенации частичных слов из набора не могут быть совместимы друг с другом. Последняя часть включает три главы по более сложным темам, включая построение повторений заданного количества копий частичных слов, совместимых друг с другом, перечисление возможных шаблонов повторений частичных слов и наборов частичных слов со свойством, что каждое бесконечная строка содержит подстроку, соответствующую набору.^[1] Каждая глава включает в себя комплекс упражнений, а в конце книги даются советы по некоторым из этих упражнений.^[2]

Аудитория и прием

Несмотря на то что Алгоритмическая комбинаторика частичных слов в первую очередь нацелено на выпускников, рецензентов Миклош Бона пишет, что его по большей части «удивительно легко читать», и предлагает, чтобы его могли читать и продвинутые студенты. Однако Бона критикует книгу как слишком сосредоточенную на комбинаторике слов как на самоцели, без обсуждения того, как преобразовать математические структуры других типов в частичные слова, чтобы к ним можно было применить методы этой книги. Из-за отсутствия общности и применимости он предполагает, что аудитория книги, вероятно, будет состоять только из других исследователей, специализирующихся в этой области.^[1] Точно так же, хотя Патрис Себольд отмечает, что эта область может быть мотивирована приложениями к сравнению генов, он критикует книгу как в значительной степени каталог результатов собственных исследований ее автора в частичных словах, без более широкого тематического обзора или идентификации фундаментальных тем и теорем что можно ожидать от учебника, и предполагает, что учебник, который выполняет эти цели, все еще ждет своего написания.^[3]

Однако рецензент Ян Кратохвил является более позитивным, называя это «первым справочником по теории частичных слов», хваля его темп от вводного материала к более сложным темам, и писал, что он хорошо подтверждает лежащий в его основе тезис о том, что многие из основных результатов комбинаторики слов без подстановочных знаков может быть расширен до частичных слов. Он резюмирует его как «отличный учебник, а также справочник для заинтересованных исследователей».^[2]

Рекомендации

1. Бона, Миклош (Сентябрь 2009 г.), "Обзор Алгоритмическая комбинаторика частичных слов" (PDF), Новости ACM SIGACT, 40 (3): 39–41, Дои:10.1145/1620491.1620497
2. Кратохвил, Ян (Июнь 2011 г.), "Обзор Алгоритмическая комбинаторика частичных слов", Обзоры EMS, Европейское математическое общество
3. Себольд, Патрис (2009), "Обзор Алгоритмическая комбинаторика частичных слов", MathSciNet, МИСТЕР  2384993