Desambiguabilidad y Minimización de Registros de Modelos Min-Plus

Información Básica

• ID del Artículo: 2512.09484
• Título: Desambiguabilidad y Minimización de Registros de Modelos Min-Plus
• Autores: Shaull Almagor, Guy Arbel, Sarai Sheinvald (Technion – Instituto Tecnológico de Israel)
• Clasificación: cs.FL (Teoría de Lenguajes Formales y Autómatas)
• Fecha de Publicación: Diciembre de 2025 (preimpresión en arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2512.09484

Resumen

Este artículo estudia el problema de desambiguabilidad de autómatas finitos ponderados (WFAs) en el semianillo min-plus (tropical), así como el problema de minimización de contadores en autómatas de registros de costo (CRAs) que son equivalentes en capacidad expresiva a los WFAs. Ambos problemas investigan si el "grado de no determinismo" en el modelo puede reducirse. Los autores demuestran que el problema de desambiguabilidad de WFA es decidible, resolviendo así un problema abierto de larga data. El método de prueba se basa en una reducción al problema de determinización de WFA (que recientemente fue probado como decidible). En cuanto a resultados negativos, los autores demuestran que el problema de minimización de contadores de CRA es indecidible, incluso para un número fijo de registros (específicamente, siete registros).

Contexto de Investigación y Motivación

1. Problemas de Investigación

Este artículo estudia dos problemas centrales:

• Problema de Desambiguabilidad: Dado un autómata ponderado A, ¿existe un autómata desambiguado equivalente?
• Problema de Minimización de Registros: Dado un autómata de registros de costo con k registros, ¿existe un autómata de registros de costo equivalente con (k-1) registros?

2. Importancia del Problema

• Significado Teórico: Los autómatas finitos ponderados son modelos cuantitativos importantes que definen funciones de palabras a valores. Los WFAs sobre el semianillo tropical (Z∪{∞}, min, +) tienen aplicaciones generalizadas en modelado de sistemas y pueden utilizarse para razonar sobre formas óptimas de uso de recursos (como consumo de energía).
• Valor Práctico: La existencia de no determinismo hace que el razonamiento sobre WFAs sea más difícil. Por ejemplo, el problema de equivalencia de WFAs tropicales es indecidible para autómatas no deterministas, pero decidible para autómatas deterministas.
• Posición Histórica: Los WFAs tropicales jugaron un papel crucial en la resolución de la conjetura de star-height.

3. Limitaciones de Métodos Existentes

• El problema de determinización solo fue probado como decidible recientemente (2025)
• Para autómatas tropicales con ambigüedad polinomial, el problema de desambiguabilidad ha sido probado como decidible, pero el caso general permanecía abierto
• El problema de desambiguabilidad sobre campos de números racionales es decidible, pero la situación sobre semianillos tropicales no había sido resuelta
• En la mayoría de modelos, los problemas de determinización y desambiguabilidad se resuelven típicamente de manera simultánea, pero los WFAs tropicales presentan un caso especial

4. Motivación de la Investigación

• Los WFAs desambiguados son estrictamente más expresivos que los WFAs deterministas, pero conservan algunas propiedades de clausura y algorítmicas favorables
• El no determinismo puede medirse de múltiples formas: la ambigüedad y el ancho proporcionan perspectivas diferentes
• El número de registros corresponde al ancho del WFA, proporcionando otra forma de medir el no determinismo

Contribuciones Principales

Las contribuciones principales del artículo incluyen:

1. Resolución de un Problema Abierto de Larga Data: Se demuestra que el problema de desambiguabilidad de WFA tropical es decidible, un problema que había permanecido sin resolver durante mucho tiempo.
2. Método de Reducción Innovador: Se resuelve el problema de desambiguabilidad mediante reducción al problema de determinización. Esto es en cierto sentido contraintuitivo, ya que típicamente se resuelve primero la desambiguabilidad y luego la determinización.
3. Nueva Caracterización de Brechas: Se introduce el concepto de testigo de brecha de tipo U (U-type gap witness), proporcionando una caracterización completa de la desambiguabilidad.
4. Resultados Negativos: Se demuestra que el problema de minimización de registros de CRA es indecidible, incluso cuando se fija el número de registros en siete.
5. Resultados de Equivalencia: Se refinan las relaciones de equivalencia entre k-CRA y WFA de ancho k.

Explicación Detallada de Métodos

Definición de Tareas

Problema de Desambiguabilidad (Problema 2):

• Entrada: Un WFA A
• Salida: Determinar si existe un WFA desambiguado equivalente
• Definición: Un WFA A es desambiguado si y solo si cada palabra tiene como máximo una ejecución aceptante

Problema de Minimización de Registros:

• Entrada: Un CRA con k registros
• Salida: Determinar si existe un CRA equivalente con (k-1) registros

Arquitectura del Método Principal

1. Caracterización de Brechas de Tipo U (Sección 3)

Definición 5 (Testigo de Brecha B de Tipo U): Para B ∈ N, un testigo de brecha B de tipo U consiste en pares de palabras x, y ∈ Σ* y estados p₁, q₁ ∈ Q, p₂, q₂ ∈ F con ejecuciones:

• ρ: q₀ →^x p₁ →^y p₂
• χ: q₀ →^x q₁ →^y q₂

que satisfacen:

1. mwt(q₀ →^x Q) = wt(χx) (el prefijo de χ es la ejecución de peso mínimo en x)
2. mwt(q₀ →^xy F) = wt(ρ) (ρ es la ejecución aceptante de peso mínimo en xy)
3. wt(ρx) - wt(χx) > B (después de leer x, ρ es al menos B más alto que la ejecución mínima)

Teorema 6: Un WFA A puede desambiguarse si y solo si existe B ∈ N tal que la brecha de A está acotada por B.

2. Construcción de Desambiguabilidad (Sección 3.2)

Dado un WFA A cuya brecha está acotada por B, se construye un WFA desambiguado equivalente U:

Espacio de Estados: S = Q × B-Win, donde B-Win = {-∞, -B, ..., B, ∞}^Q

Idea Clave:

• Rastrear la ejecución mínima canónica
• Usar una ventana B para registrar el desplazamiento de peso de cada estado relativo al estado rastreado actual
• Seleccionar la ejecución mínima única y canónica entre múltiples ejecuciones mínimas mediante ordenamiento por prioridad (orden lineal ⪯)

Definición de la Relación de Transición Λ: Para un estado (q, f_q) y letra σ, considere la transición (q, σ, c, p):

1. Calcule la función intermedia g(p) = min{f_q(r) + mwt(r →^σ p) - c | r ∈ Q}
2. Verificación de consistencia:
   • Si g(p) < 0, no agregue la transición (existe una ejecución de peso más bajo)
   • Si existe r ≠ q y q ⪯ r tal que f_q(r) + mwt(r →^σ p) - c = g(p), no agregue la transición (existe una ejecución de prioridad más alta)
3. Truncar g a -B, B para obtener f_p

Estados Aceptantes: G = {(q, f_q) | q ∈ F ∧ ∀p ∈ F, (f_q(p) > 0 ∨ (f_q(p) = 0 ∧ p ⪯ q))}

3. Reducción a Determinización (Sección 4)

Idea Central: Construir un WFA B tal que A puede desambiguarse si y solo si B puede determinizarse.

Detalles de Construcción:

• Estados: S = Q × Com, donde Com = {⊥, ↛, →}^Q (funciones de compromiso)
• Alfabeto: Γ = Σ × Updt, donde Updt = {⊥, ↛, →}^(Q×Q) (funciones de actualización)
• Semántica de Compromiso:
  • →: el estado es alcanzable y está en una ejecución aceptante
  • ↛: el estado es alcanzable pero no está en una ejecución aceptante
  • ⊥: el estado no es alcanzable

Condiciones de Consistencia:

1. Consistencia Δ: la proyección a A es una transición válida
2. Consistencia de Actualización: α refleja correctamente las transiciones disponibles en σ
3. Consistencia de Aristas Salientes: f(r) = → si y solo si existe r' tal que r → r' ∈ α
4. Consistencia de Aristas Entrantes: g(r') = → si y solo si existe r tal que r → r' ∈ α

Lemas Clave:

• Lema 15: Si existe un testigo de brecha B de tipo U en A, entonces existe un testigo de brecha B de tipo D en B
• Lema 16: Si existe un testigo de brecha B de tipo D en B, entonces existe un testigo de brecha B de tipo U en A

Puntos de Innovación Técnica

1. Innovación en la Caracterización de Brechas:
   • Introducción de testigos de brecha de tipo U, distintos de los testigos de tipo D conocidos
   • El tipo U requiere que la "ejecución baja" también pueda continuar hasta un estado aceptante, que es la diferencia clave con el tipo D
2. Construcción de Ejecuciones Canónicas:
   • Seleccionar la ejecución mínima única de forma progresiva hacia atrás mediante un orden lineal ⪯
   • Garantizar unicidad mientras se mantiene la propiedad de peso mínimo
3. Diseño Ingenioso de la Reducción:
   • Usar mecanismos de compromiso y actualización para forzar que los testigos de tipo D de B sean también testigos de tipo U de A
   • Garantizar la extensibilidad de la ejecución baja mediante verificaciones de consistencia
4. Equivalencia de Ancho y Registros:
   • Establecer conversiones bidireccionales precisas entre k-CRA y WFA de ancho k
   • En la dirección WFA→CRA, la innovación clave es reutilizar registros en lugar de asignar registros independientes a cada estado

Configuración Experimental

Este artículo es un trabajo puramente teórico que no incluye evaluación experimental. Todos los resultados se obtienen mediante pruebas matemáticas rigurosas.

Estructura de Pruebas

1. Decidibilidad de Desambiguabilidad (Secciones 3-4):
   • Sección 3: Prueba de necesidad y suficiencia de la caracterización de brechas
   • Sección 4: Reducción al problema de determinización
2. Indecidibilidad de Minimización de Registros (Sección 5):
   • Reducción desde el problema de parada 0 de máquinas de dos contadores
   • Utilización de la construcción del Teorema 22 (de 2)
   • Construcción de WFA de ancho 7, prueba de que no puede reducirse a ancho 6

Herramientas Teóricas

• Técnica de Testigos de Brecha: Originaria de la investigación del problema de determinización
• Construcción de Subconjuntos: Utilizada para la conversión de CRA a WFA
• Representación Matricial: Utilizada para la definición semántica de CRA
• Técnica de Reducción: Desde problemas indecidibles (máquinas de dos contadores) al problema objetivo

Resultados Experimentales

Resultados Teóricos Principales

1. Decidibilidad de Desambiguabilidad (Teorema 13 + Corolario 17)

Teorema 13: El problema de desambiguabilidad se reduce al problema de determinización.

Corolario 17: El problema de desambiguabilidad de WFA es decidible.

Puntos Clave de la Prueba:

• Dirección Positiva: Si B puede determinizarse, entonces A puede desambiguarse
  • Utilizar el Lema 16: los testigos de tipo D de B implican testigos de tipo U de A
  • Mediante el mecanismo de compromiso de consistencia de aristas entrantes, garantizar que la ejecución baja pueda extenderse a un estado aceptante
• Dirección Inversa: Si A puede desambiguarse, entonces B puede determinizarse
  • Utilizar el Lema 15: los testigos de tipo U de A son automáticamente testigos de tipo D de B
  • Mantener peso y minimalidad mediante proyección

2. Indecidibilidad de Minimización de Registros (Teorema 20)

Teorema 20: El siguiente problema es indecidible, incluso para k=7: Dado un WFA de ancho k, determinar si existe un WFA equivalente de ancho k-1.

Corolario 21: El siguiente problema es indecidible, incluso para k=7: Dado un k-CRA, determinar si existe un (k-1)-CRA equivalente.

Estrategia de Prueba:

1. Construir un WFA de ancho 6 A a partir de una máquina de dos contadores M (Teorema 22)
2. Extender A para obtener un WFA de ancho 7 A', agregando:
   • Estados q_a y q_i (i∈6)
   • Letras $, i, a, ī_i
3. Si el límite superior de A está acotado, entonces q_a es redundante, obteniéndose un WFA equivalente de ancho 6
4. Si A es ilimitado, entonces existe ζ=x@ tal que q₀ →^ζ q₀ tiene peso 1
5. Usar la palabra w = ζ^(6m) 1^(5m) 2^(4m) ... 5^m y sufijo x = a ī₁ī₂...ī₅ para construir una contradicción:
   • 7 prefijos x₀,...,x₆ tales que A'(wx_i) = im
   • Principio del Palomar: al menos dos prefijos i<j alcanzan el mismo estado t
   • Diferencia de peso (j-i)m ≤ 12||B||, contradiciendo m > 12||B||

Análisis de Complejidad

Problema de Desambiguabilidad:

• Cota Inferior: PSPACE-hard (heredada de la cota inferior del problema de determinización)
• Cota Superior: Desconocida (el límite superior de complejidad del problema de determinización aún no se ha establecido)
• Complejidad de Reducción: Expansión de espacio de estados exponencial simple

Problema de Minimización de Registros:

• Para k≥7 fijo: indecidible
• Para k<7: problema abierto
• Para CRA sobre campos de números racionales: decidible (6)

Perspectivas Técnicas Clave

1. Esencia de la Acotación de Brechas:
   • La caracterización de brecha de tipo U captura el "grado de separación" de dos ejecuciones aceptantes
   • Las brechas acotadas garantizan que se pueda rastrear todas las ejecuciones relevantes con una ventana finita
2. Determinización vs Desambiguabilidad:
   • Típicamente se resuelve primero la desambiguabilidad, luego la determinización
   • En el semianillo tropical se hace lo opuesto: resolver primero la determinización, luego reducir la desambiguabilidad
   • Razón: el mecanismo de compromiso puede "forzar" que los testigos de tipo D se conviertan en testigos de tipo U
3. Incompresibilidad del Ancho:
   • Los 7 componentes (q_a y q_1,...,q_6) producen configuraciones de peso no fusionables mediante palabras cuidadosamente diseñadas y letras asesinas
   • Cada componente alcanza el mínimo en diferentes momentos, no pudiendo simularse con 6 registros

Trabajo Relacionado

1. Investigación del Problema de Determinización

• Historia: Se remonta a los años 1990 19, 20
• Campo de Números Racionales: Recientemente probado como decidible 5, 14
• Semianillo Tropical: Probado como decidible en 2025 1 (trabajo anterior de los autores del presente artículo)
• Caracterización de Brechas: Filiot et al. 11 introdujeron el concepto de brecha de tipo D

2. Investigación de Ambigüedad

• Clasificación: k-ambigüedad, ambigüedad finita, ambigüedad polinomial 7
• Ambigüedad Polinomial: Kirsten y Lombardy 16 probaron que la desambiguabilidad de autómatas tropicales es decidible
• Campo de Números Racionales: Bell y Smertnig 5 probaron decidibilidad
• Contribución del Presente Artículo: Resolver el caso general (ambigüedad arbitraria)

3. Autómatas de Registros de Costo

• Introducción: Alur et al. 4 definieron el modelo CRA
• Capacidad Expresiva: Equivalente a WFA 4
• Minimización de Registros:
  • Campo de Números Racionales: decidible 6
  • Semianillo Tropical: indecidible según el presente artículo
• CRA Débil: Almagor et al. 3 estudian CRA sin copia

4. Aplicaciones del Semianillo Tropical

• Problema de Star-Height: Trabajo de Hashiguchi 12, 13, Kirsten 15
• Problema de Restricción: Leung y Podolskiy 18
• Acotación de Límite Superior: Almagor et al. 2 probaron indecidibilidad (base de la reducción de minimización de registros del presente artículo)

Contribuciones Únicas del Presente Artículo

1. Primera Resolución del problema general de desambiguabilidad de WFA tropical
2. Dirección Innovadora: Resolver mediante reducción a determinización en lugar de construcción directa
3. Panorama Completo: Proporcionar simultáneamente resultados positivos (decidibilidad de desambiguabilidad) y negativos (indecidibilidad de minimización de registros)
4. Caracterización Refinada: Establecer correspondencia exacta entre k-CRA y WFA de ancho k

Conclusiones y Discusión

Conclusiones Principales

1. Resultado de Decidibilidad: El problema de desambiguabilidad de WFA tropical es decidible, resolviendo un problema abierto de larga data.
2. Resultado de Indecidibilidad: El problema de minimización de registros de CRA es indecidible incluso para 7 registros fijos.
3. Contribución Metodológica: Resolver el problema de desambiguabilidad mediante reducción al problema de determinización, demostrando conexiones profundas entre problemas.
4. Equivalencia Refinada: Equivalencia exacta entre k-CRA y WFA de ancho k.

Limitaciones

1. Complejidad Desconocida:
   • La complejidad exacta del problema de desambiguabilidad no se ha determinado
   • Solo se conoce la cota inferior PSPACE-hard
   • La reducción tiene expansión exponencial simple, se desconoce si es necesaria
2. Brecha en Minimización de Registros:
   • Indecidible para k=7
   • La decidibilidad para k<7 sigue siendo un problema abierto
   • Para k=1 (determinización) es decidible
3. Ambigüedad Relajada:
   • La decidibilidad general de 2-desambiguabilidad, desambiguabilidad finita y desambiguabilidad polinomial no se ha resuelto
   • Falta caracterización de brechas correspondiente
4. Fragmentos Especiales:
   • La decidibilidad de minimización de registros de CRA sin copia es desconocida
   • Casos bajo otras restricciones estructurales no explorados

Direcciones Futuras

Problemas abiertos explícitamente planteados por los autores:

1. Ambigüedad Relajada:
   • ¿Se puede determinar si un WFA dado tiene un WFA equivalente 2-ambiguo/finitamente ambiguo/polinomialmente ambiguo?
   • El problema de 2-desambiguabilidad parece extremadamente difícil, sin criterios de brecha correspondientes actualmente disponibles
2. Perfeccionar el Panorama de Minimización de Registros:
   • ¿Es decidible la minimización de registros para k<7?
   • Aunque de menor importancia, una caracterización completa sigue siendo valiosa
3. Fragmentos Estructurales:
   • Minimización de registros de CRA sin copia
   • Propiedades de otras clases de CRA restringidas
4. Delimitación de Complejidad:
   • Determinar la complejidad exacta del problema de desambiguabilidad
   • Una vez que se delimite la complejidad de determinización, investigar si la reducción puede mejorarse (tiempo polinomial o espacio logarítmico)

Evaluación Profunda

Fortalezas

1. Avance Teórico Significativo:
   • Resuelve el problema abierto de larga data de desambiguabilidad
   • Método novedoso: utilizar inversamente la determinización para resolver la desambiguabilidad
   • Técnicas de prueba profundas y elegantes
2. Panorama Teórico Completo:
   • Coexistencia de resultados positivos (decidibilidad) y negativos (indecidibilidad)
   • Establece conexiones entre diferentes modelos (WFA y CRA) y diferentes medidas (ambigüedad y ancho)
3. Innovación Técnica Significativa:
   • Caracterización de brecha de tipo U: captura precisamente la esencia de la desambiguabilidad
   • Construcción de ejecuciones canónicas: logra unicidad mediante ordenamiento por prioridad
   • Mecanismo de compromiso: convierte ingeniosamente testigos de tipo D en testigos de tipo U
   • Reutilización de registros: evita expansión exponencial en la conversión WFA→CRA
4. Pruebas Rigurosas y Completas:
   • Todos los teoremas tienen pruebas detalladas
   • Lógica clara entre lemas
   • Argumentación suficiente para puntos técnicos clave (como Lemas 8, 9)
5. Alta Calidad de Escritura:
   • Estructura clara, progresión de motivación a resultados por capas
   • Buena combinación de explicaciones intuitivas y definiciones formales
   • Diagramas (como Figuras 1-5) facilitan la comprensión

Insuficiencias

1. Falta de Límites de Complejidad:
   • Límite superior desconocido para el problema de desambiguabilidad
   • Análisis no realizado sobre si la expansión de la reducción es necesaria
   • Evaluación de computabilidad práctica no realizada
2. Brecha en Minimización de Registros:
   • ¿Es k=7 el límite más ajustado?
   • Casos para k∈{2,3,4,5,6} completamente abiertos
   • Punto de inflexión de k=1 (decidible) a k=7 (indecidible) no determinado
3. Problemas de Ambigüedad Relajada No Abordados:
   • Problemas como 2-desambiguabilidad solo mencionados en discusión
   • Sin pistas técnicas o resultados parciales proporcionados
4. Falta de Consideraciones Prácticas:
   • Trabajo puramente teórico, sin implementación de algoritmos
   • Sin análisis de complejidad o discusión de viabilidad
   • Orientación limitada para aplicaciones prácticas
5. Generalizabilidad de Técnicas de Prueba:
   • No se discute si los métodos aplican a otros semianillos
   • Relación con resultados conocidos sobre campos de números racionales no analizada profundamente

Evaluación de Impacto

1. Significado Teórico Importante:
   • Resolución de problema abierto de larga data, se espera que sea un hito en el campo
   • Proporciona nuevas herramientas para investigación posterior (brecha de tipo U, mecanismo de compromiso)
   • Revela conexiones profundas entre determinización y desambiguabilidad
2. Contribución Metodológica:
   • Las técnicas de reducción pueden inspirar soluciones a otros problemas
   • El método de caracterización de brechas puede generalizarse a otros modelos
3. Inspiración de Problemas Abiertos:
   • Identifica claramente direcciones importantes de investigación posterior
   • Proporciona referencia para minimización de registros con k<7
4. Restricción de Impacto por Limitaciones:
   • Falta de límites de complejidad limita aplicaciones prácticas
   • Se requiere trabajo adicional en algoritmización e implementación

Escenarios Aplicables

1. Investigación Teórica:
   • Teoría de Lenguajes Formales y Autómatas
   • Teoría de Decidibilidad y Complejidad
   • Modelos de Computación sobre Semianillos
2. Verificación de Sistemas:
   • Sistemas que requieren razonamiento sobre consumo de recursos (energía, tiempo)
   • Simplificación de autómatas en verificación cuantitativa
3. Diseño de Algoritmos:
   • Optimización y transformación de autómatas ponderados
   • Medición y control de no determinismo
4. Valor Educativo:
   • Demuestra el poder de técnicas de reducción
   • Ilustra la sutileza de los límites de decidibilidad

Resumen de Puntos Técnicos Destacados

1. Caracterización Precisa de Brecha de Tipo U: Captura perfectamente la esencia combinatoria de la desambiguabilidad
2. Construcción de Ejecuciones Canónicas: Resuelve el problema de unicidad mediante un mecanismo simple de prioridad
3. Diseño del Mecanismo de Compromiso: Codifica explícitamente el DAG de ejecuciones en el alfabeto, forzando consistencia
4. Estrategia de Reutilización de Registros: Logra correspondencia exacta de ancho mientras mantiene equivalencia
5. Elegancia de la Prueba de Indecidibilidad: Demuestra incompresibilidad mediante cuidadosa orquestación de 7 componentes

Referencias (Referencias Clave)

1 Almagor, Arbel, Sheinvald (2025). Determinización de autómatas ponderados min-plus es decidible. SODA 2025.

2 Almagor, Boker, Kupferman (2020). ¿Qué es decidible sobre autómatas ponderados? Information and Computation.

4 Alur et al. (2013). Funciones regulares y autómatas de registros de costo. LICS 2013.

5 Bell, Smertnig (2023). Computación del casco lineal: Decidibilidad de determinización y desambiguabilidad para autómatas ponderados sobre campos. LICS 2023.

11 Filiot et al. (2017). Sobre determinización con retardo y arrepentimiento de autómatas max-plus. LICS 2017.

16 Kirsten, Lombardy (2009). Decidibilidad de desambiguabilidad y secuencialidad de autómatas min-plus polinomialmente ambiguos. STACS 2009.

Evaluación General: Este artículo es una contribución teórica importante en el campo de la Teoría de Lenguajes Formales y Autómatas, resolviendo el problema abierto de larga data de desambiguabilidad y revelando la indecidibilidad de la minimización de registros. Las técnicas de prueba son profundas e innovadoras, particularmente el enfoque inverso de utilizar determinización para resolver desambiguabilidad. Aunque carece de límites de complejidad y algoritmos prácticos, su valor teórico y contribuciones metodológicas lo convierten en un avance importante en el campo. Para investigadores en ciencias de la computación teórica, este es un artículo de lectura obligatoria.