Алгоритмическая комбинаторика частичных слов

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

Темы

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

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

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

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

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

Ссылки

^ Jump up to: ^а ^б ^с Бона, Миклош (сентябрь 2009 г.), «Обзор алгоритмической комбинаторики частичных слов » (PDF) , ACM SIGACT News , 40 (3): 39–41, doi : 10.1145/1620491.1620497
^ Jump up to: ^а ^б ^с Кратохвил, Ян (июнь 2011 г.), «Обзор алгоритмической комбинаторики частичных слов » , EMS Reviews , Европейское математическое общество
^ Себольд, Патрис (2009), «Обзор алгоритмической комбинаторики частичных слов », MathSciNet , MR 2384993

[bona-1] Jump up to: ^а ^б ^с Бона, Миклош (сентябрь 2009 г.), «Обзор алгоритмической комбинаторики частичных слов » (PDF) , ACM SIGACT News , 40 (3): 39–41, doi : 10.1145/1620491.1620497

[jkrat-2] Jump up to: ^а ^б ^с Кратохвил, Ян (июнь 2011 г.), «Обзор алгоритмической комбинаторики частичных слов » , EMS Reviews , Европейское математическое общество

[seebold-3] Себольд, Патрис (2009), «Обзор алгоритмической комбинаторики частичных слов », MathSciNet , MR 2384993

[1]

[2]

[3]