Combinatoria algorítmica de palabras parciales es un libro en el área de la combinatoria de palabras , y más específicamente de palabras parciales . Fue escrito por Francine Blanchet-Sadri y publicado en 2008 por Chapman & Hall/CRC en su serie de libros Matemática discreta y sus aplicaciones.
Una palabra parcial es una cadena cuyos caracteres pueden pertenecer a un alfabeto determinado o ser un carácter comodín . Una palabra de este tipo puede representar un conjunto de cadenas sobre el alfabeto sin comodines, permitiendo que cada carácter comodín sea reemplazado por cualquier carácter individual del alfabeto, independientemente de los reemplazos de los otros caracteres comodín. Dos palabras parciales son compatibles cuando coinciden en sus caracteres no comodín, o equivalentemente cuando hay una cadena con la que ambas coinciden; una palabra parcial contiene otra palabra parcial si son compatibles y las posiciones no comodín de contienen las de ; equivalentemente, las cadenas coincidentes con son un subconjunto de las coincidentes con . [1]
El libro consta de 12 capítulos [2] , que pueden agruparse en cinco partes más grandes. La primera parte consta de dos capítulos introductorios que definen las palabras parciales, la compatibilidad y la contención, y conceptos relacionados. La segunda parte generaliza a las palabras parciales algunos resultados estándar sobre repeticiones en cadenas, y la tercera parte estudia el problema de caracterizar y reconocer las palabras parciales primitivas, las palabras parciales que no tienen repetición. La cuarta parte trata de los códigos definidos a partir de conjuntos de palabras parciales, en el sentido de que no pueden existir dos concatenaciones distintas de palabras parciales del conjunto que sean compatibles entre sí. Una parte final incluye tres capítulos sobre temas avanzados que incluyen la construcción de repeticiones de un número dado de copias de palabras parciales que sean compatibles entre sí, la enumeración de los posibles patrones de repeticiones de palabras parciales y conjuntos de palabras parciales con la propiedad de que cada cadena infinita contiene una subcadena que coincide con el conjunto. [1] Cada capítulo incluye un conjunto de ejercicios, y el final del libro proporciona pistas para algunos de estos ejercicios. [2]
Aunque Combinatoria algorítmica de palabras parciales está dirigido principalmente a estudiantes de posgrado, el crítico Miklós Bóna escribe que, en su mayor parte, es "notablemente fácil de leer" y sugiere que también podría ser leído por estudiantes universitarios avanzados. Sin embargo, Bóna critica el libro por estar demasiado centrado en la combinatoria de palabras como un fin en sí mismo, sin ninguna discusión sobre cómo traducir estructuras matemáticas de otros tipos en palabras parciales para que los métodos de este libro puedan aplicarse a ellas. Debido a esta falta de generalidad y aplicación, sugiere que es probable que la audiencia del libro consista solo en otros investigadores especializados en esta área. [1] De manera similar, aunque Patrice Séébold señala que esta área puede estar motivada por aplicaciones a la comparación de genes, critica el libro por ser en gran medida un catálogo de los resultados de investigación del propio autor en palabras parciales, sin la descripción temática más amplia o la identificación de los temas y teoremas fundamentales que uno esperaría de un libro de texto, y sugiere que un libro de texto que logre estos objetivos aún está esperando ser escrito. [3]
Sin embargo, el crítico Jan Kratochvíl es más positivo y lo califica como "el primer libro de referencia sobre la teoría de las palabras parciales", elogia su ritmo desde el material introductorio hasta temas más avanzados y escribe que respalda bien su tesis subyacente de que muchos de los principales resultados en la combinatoria de palabras sin comodines se pueden extender a las palabras parciales. Lo resume como "un excelente libro de texto, así como un libro de referencia para investigadores interesados". [2]
