En informática y en el estudio de la combinatoria de palabras , una palabra parcial es una cadena que puede contener una serie de símbolos de "no sé" o "no me importa", es decir, marcadores de posición en la cadena donde el valor del símbolo no se conoce o no se especifica. Más formalmente, una palabra parcial es una función parcial donde es un alfabeto finito. Si u ( k ) no está definido para algún , entonces el elemento desconocido en el lugar k en la cadena se llama "agujero". En expresiones regulares (siguiendo el estándar POSIX ) un agujero se representa con el metacarácter ".". Por ejemplo, aab.ab.b es una palabra parcial de longitud 8 sobre el alfabeto A ={ a , b } en el que el cuarto y séptimo caracteres son agujeros. [1]
Se han desarrollado varios algoritmos para el problema de "coincidencia de cadenas con indiferencia", en el que la entrada es un texto largo y una palabra parcial más corta y el objetivo es encontrar todas las cadenas en el texto que coincidan con la palabra parcial dada. [2] [3] [4]
Se dice que dos palabras parciales son compatibles cuando tienen la misma longitud y cuando cada posición que no es un comodín en ambas tiene el mismo carácter en ambas. Si se forma un grafo no dirigido con un vértice para cada palabra parcial en una colección de palabras parciales, y una arista para cada par compatible, entonces las camarillas de este grafo provienen de conjuntos de palabras parciales que coinciden todas con al menos una cadena común. Esta interpretación grafo-teórica de la compatibilidad de palabras parciales juega un papel clave en la prueba de la dificultad de aproximación del problema de la camarilla , en el que una colección de palabras parciales que representan ejecuciones exitosas de un verificador de prueba probabilísticamente comprobable tiene una camarilla grande si y solo si existe una prueba válida de un problema NP-completo subyacente . [5]
Las caras (subcubos) de un hipercubo de dimensión 1 pueden describirse mediante palabras parciales de longitud sobre un alfabeto binario, cuyos símbolos son las coordenadas cartesianas de los vértices del hipercubo (por ejemplo, 0 o 1 para un cubo unitario ). La dimensión de un subcubo, en esta representación, es igual al número de símbolos de indiferencia que contiene. La misma representación también puede utilizarse para describir los implicantes de funciones booleanas . [6]
Las palabras parciales pueden generalizarse a palabras de parámetro , en las que algunos de los símbolos "no sé" se marcan como iguales entre sí. Una palabra parcial es un caso especial de una palabra de parámetro en la que cada símbolo "no sé" puede sustituirse por un carácter independientemente de todos los demás. [7]
