28 artículos
El artículo presenta FATE, una nueva serie de benchmarks en álgebra formal que abarca desde ejercicios universitarios hasta problemas de investigación avanzada, revelando que los modelos de lenguaje actuales tienen un rendimiento muy limitado en esta área, especialmente en la formalización de su razonamiento natural.
Este artículo construye autómatas para reconocer relaciones en secuencias -automáticas, establece una conexión entre la complejidad de subpalabras y la complejidad de estados de subsecuencias lineales, resuelve una pregunta reciente de Zantema y Bosma sobre el formato de dígitos más significativos primero, y analiza la complejidad computacional de dichas construcciones utilizando aritmética de Büchi.
Este artículo presenta un enfoque que extiende la minería de especificaciones más allá de las abstracciones booleanas mediante la combinación de síntesis guiada por sintaxis y una interpretación de lógica temporal (TSL) para aprender transformaciones de datos y especificaciones temporales, demostrando una mayor eficiencia y robustez en la síntesis de programas reactivos en entornos de aprendizaje automático.
Este artículo estudia juegos concurrentes en grafos con aleatorización distribuida, demostrando que las estrategias sin memoria son suficientes para problemas de umbral y casi seguros, estableciendo su complejidad computacional, introduciendo la lógica IRATL y presentando un solucionador práctico.
Este artículo resuelve la tensión entre la estructura combinatoria y el comportamiento observable de los autómatas de dimensiones superiores (HDA) al desarrollar una semántica independiente del orden basada en ipomsets de intervalos, demostrando la equivalencia entre sus trazas ST y representaciones categóricas, lo que proporciona una base unificada y libre de orden para la teoría de la concurrencia.
Este artículo demuestra que la complejidad de giros en autómatas de pila y de un contador es indecidible, establece una mejora no recursiva entre estas máquinas, y revela una jerarquía infinita de clases de complejidad basada en funciones sublineales para el número de giros necesarios para aceptar lenguajes.
Este artículo investiga los árboles contextuales libres, demostrando que admiten una descripción mediante autómatas no deterministas de múltiples aristas y que el problema de isomorfismo para estos árboles deterministas es completo para la clase de complejidad NL.
Este artículo demuestra nuevas propiedades de la representación de los enteros, incluyendo la resolución de una conjetura de Kimberling de 2012, utilizando herramientas como el demostrador de teoremas Walnut y ChatGPT 5.
Este artículo presenta una nueva visión unificada de la asimetría entre generación y reconocimiento en la teoría de lenguajes formales, identificando seis dimensiones divergentes (incluyendo dos nuevas: direccionalidad y temporalidad) para desmitificar la noción de que la generación es siempre fácil y el análisis siempre difícil, y conectando estas diferencias con el marco de la sorpresa en el procesamiento del lenguaje natural y las arquitecturas de los modelos de lenguaje grandes.
Este artículo demuestra que los factores de las palabras suaves son f-suaves y avanza en la conjetura de Sing sobre su complejidad, probándola para alfabetos pares, estableciendo una cota inferior para cualquier alfabeto binario y mejorando la cota superior para alfabetos impares.
El artículo presenta ZipLex, un marco de análisis léxico invertible y verificado formalmente que garantiza una complejidad temporal lineal y la propiedad de inversa mutua entre la lexación y la impresión, superando las limitaciones de rendimiento de enfoques anteriores como Verbatim++ y Coqlex.
Este artículo presenta un enfoque basado en datos para el control supervisorio no bloqueante de sistemas de eventos discretos con modelos desconocidos, introduciendo el concepto de informatividad de datos de marcado y algoritmos para verificarlo o maximizar la especificación controlable cuando los datos son insuficientes.
Este artículo establece fundamentos teóricos para la decodificación restringida por gramáticas, demostrando que la equivalencia lingüística no garantiza eficiencia computacional al introducir una métrica de costo de ambigüedad estructural, probar límites inferiores de complejidad y derivar acotaciones precisas de distorsión para el muestreo condicional en arquitecturas de transformadores.
Este trabajo demuestra que es posible realizar máquinas de Moore como modelos de espacio de estados, y propone un enfoque híbrido que utiliza el aprendizaje de autómatas simbólicos para inicializar estos modelos, logrando así una convergencia más rápida y una mayor precisión en comparación con la inicialización aleatoria.
Este artículo presenta un marco de monitoreo en línea eficiente y escalable para la Lógica Temporal Métrica (MTL) en sistemas ciberfísicos, basado en la construcción unificada de redes secuenciales mediante una técnica de marcado temporal futuro que utiliza representaciones simbólicas basadas en intervalos para comportamientos en tiempo discreto y denso.
Este artículo establece que la verificación de módulos en sistemas multiagente de pila (PMS) es 2EXPTIME-completa para especificaciones ATL y 4EXPTIME-completa para ATL*, demostrando que este último caso es exponencialmente más difícil que la verificación de modelos y constituye un problema natural elemental con una complejidad superior al tiempo triplemente exponencial.
Este artículo estudia teoremas tipo Ramsey para árboles infinitos y herramientas combinatorias relacionadas, aplicándolas al problema de la expansión para álgebras de árboles.
Este artículo presenta un enfoque para la conducción autónoma que equilibra diversos riesgos, como colisiones e infracciones de tráfico, mediante la extensión de métricas de riesgo a especificaciones de lógica temporal lineal (LTL) y su resolución eficiente a través de un problema de programación lineal, validando su eficacia en el simulador Carla.
Este artículo demuestra las conjeturas de Clark Kimberling sobre su secuencia binaria definida por reglas de inflación, establece su relación con la palabra infinita de Tribonacci y determina su complejidad de subpalabras y exponente crítico, utilizando en parte el demostrador de teoremas Walnut.
Este artículo presenta una clasificación completa de la complejidad computacional distribuida para problemas de optimización local en ciclos dirigidos, identificando cuatro clases de complejidad posibles tanto para modelos deterministas como aleatorizados, y ofrece un metaalgoritmo eficiente para determinar automáticamente la clase de complejidad y sintetizar un algoritmo distribuido óptimo para cualquier problema de este tipo.