The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory

Resumen Técnico: Cálculo de la Profundidad de Inclusión de un Patrón

Definición del Problema
Esta nota aborda el problema de calcular la profundidad de inclusión de un lenguaje de patrones, una métrica diseñada para capturar la "complejidad de cambio de mente" inherente a los problemas de identificación de patrones. La indagación central es si esta profundidad es computable para cualquier patrón dado y, específicamente, si admite una caracterización combinatoria simple basada en las propiedades estructurales del patrón.

Formalmente, sea $X$ un conjunto de variables y $\Sigma$ un alfabeto finito con al menos dos símbolos. Un patrón $p$ es una secuencia finita y no vacía sobre $X \cup \Sigma$. El lenguaje $L_\Sigma(p)$ consiste en todas las cadenas base generadas al sustituir cada variable en $p$ por una cadena no vacía de $\Sigma^+$.

La profundidad de inclusión, denotada como $ID_\Sigma(p)$, se define como la longitud de la cadena de inclusiones estrictas más larga que conecta el lenguaje del patrón universal $L_\Sigma(x_1)$ con el lenguaje $L_\Sigma(p)$. Por ejemplo, si $p = 0x_11$ sobre $\Sigma=\{0,1\}$, la profundidad de inclusión es 4, lo que corresponde a una cadena de cuatro inclusiones estrictas desde $L_\Sigma(x_1)$ hasta $L_\Sigma(0x_11)$.

Metodología y Conjeturas
El artículo aborda la computabilidad de la profundidad de inclusión proponiendo una fórmula combinatoria directa. El autor postula que la profundidad de inclusión está determinada únicamente por la longitud del patrón ($|p|$) y el número de variables distintas que contiene ($\#var(p)$).

La hipótesis principal, Pregunta 2, sugiere que para cualquier alfabeto $\Sigma$ con $|\Sigma| \geq 2$:
$$ID_\Sigma(p) = 2|p| - \#var(p) - 1$$

Si esta ecuación se cumple, implica la existencia de un algoritmo de tiempo lineal para calcular la profundidad de inclusión, respondiendo así a la Pregunta 1 (la existencia de un algoritmo computable) en sentido afirmativo.

Para validar esta fórmula, el artículo introduce la Conjetura 1, que establece una condición necesaria para la inclusión de patrones. Establece que si el lenguaje del patrón $p$ es un subconjunto estricto del lenguaje del patrón $q$ ($L(p) \subset L(q)$), entonces la siguiente desigualdad debe cumplirse:
$$2|p| - \#var(p) > 2|q| - \#var(q)$$

El autor señala que la dependencia del alfabeto específico $\Sigma$ puede reducirse al caso donde $\Sigma$ contiene exactamente dos símbolos, ya que las relaciones de inclusión se preservan a través de los subconjuntos del alfabeto.

Resultados y Soluciones Parciales
El artículo no proporciona una prueba formal de las conjeturas, sino que ofrece evidencia empírica y contexto teórico:

• Contexto de Indecidibilidad: Se reconoce que el problema general de decidir la inclusión de patrones es indecidible. Sin embargo, el autor argumenta que calcular la profundidad de inclusión puede no requerir resolver el problema general de inclusión para pares arbitrarios.
• Verificación Empírica: Una computación exhaustiva realizada por el programa del autor confirmó que la desigualdad de la Conjetura 1 se cumple para todos los patrones con una longitud menor o igual a 7.
• Límites Computacionales: La verificación para patrones de longitud superior a 7 se consideró computacionalmente impráctica. En consecuencia, si existe un contraejemplo a la conjetura, este debe involucrar patrones con una longitud mayor a 7.

Significancia y Reivindicaciones
La significancia de este trabajo radica en su intento de cerrar la brecha entre la complejidad teórica de la identificación de patrones y la computabilidad práctica.

• Complejidad de Cambio de Mente: La profundidad de inclusión tiene la intención de cuantificar la complejidad de cambio de mente para identificar patrones dada una evidencia inicial.
• Implicaciones Algorítmicas: Si la caracterización combinatoria propuesta (Ecuación 1) se demuestra verdadera, permitiría la construcción de un algoritmo de tiempo lineal para calcular la profundidad de inclusión.
• Construcción del Aprendiz: Una resolución positiva a la cuestión de la computabilidad permitiría el cálculo de los límites de cambio de mente para los problemas de identificación de patrones y facilitaría la construcción de un aprendiz uniformemente óptimo en cambio de mente.

El artículo concluye enmarcando el problema como una pregunta abierta, invitando a la investigación adicional para probar la caracterización combinatoria o encontrar un contraejemplo en patrones más largos.