3447 artículos
Este artículo presenta una nueva prueba elemental del propiedad de modelo finito para el álgebra de Kleene, demostrando que es completa respecto a modelos relacionales finitos mediante el uso de autómatas de transformación y unificando así resultados previos de Kozen, Pratt y Palka.
Este artículo estudia las palabras de Dyck en secuencias binarias, demostrando que las palabras libres de potencias $7/3$ tienen un nivel de anidamiento acotado, caracterizando y contando los factores de la palabra de Thue-Morse que son de Dyck, y estableciendo cotas ajustadas para su número.
Este artículo demuestra cómo utilizar el demostrador de teoremas Walnut para obtener una prueba computacionalmente directa de un teorema clásico sobre representaciones , lo que permite recuperar automáticamente resultados existentes y obtener nuevos hallazgos de manera uniforme y sin inducción.
Este artículo demuestra que la eliminación de cuantificadores universales en estructuras automáticas puede requerir un aumento exponencial doble en el tamaño de la representación, estableciendo que el problema de decidir la vacuidad de tales lenguajes es completo para EXPSPACE.
Este artículo refina la técnica de grafos de tipos ponderados para probar la terminación de sistemas de transformación gráfica DPO, aumentando su potencia, generalizándola a otras categorías y adaptándola a variaciones de DPO presentes en la literatura.
El artículo presenta BOPIM, un algoritmo de optimización bayesiana que supera a los métodos existentes en velocidad y eficacia para la maximización de influencia en redes temporales, resolviendo desafíos de espacio combinatorio mediante nuevas funciones de kernel y cuantificando por primera vez la incertidumbre en los conjuntos de nodos semilla óptimos.
Este estudio longitudinal revela que las actualizaciones sucesivas de modelos de lenguaje grandes (como GPT, Llama y Qwen) no garantizan una mejora consistente en su robustez adversarial frente a la mala clasificación, los jailbreaks y las alucinaciones, demostrando que versiones más recientes o de mayor tamaño pueden incluso degradar ciertos aspectos de seguridad.
Este artículo generaliza los axiomas de cardinalidad de las álgebras de relaciones a las álgebras de Stone para modelar grafos ponderados, estableciendo condiciones suficientes para su representabilidad y derivando axiomas más simples para las álgebras de relaciones.
Este artículo caracteriza los conjuntos de grafos definibles en lógica monádica de segundo orden con conteo y contextolibres, demostrando su equivalencia con conjuntos reconocibles de ancho arbóreo acotado, conjuntos analizables mediante transducciones definibles y la imagen de conjuntos de árboles reconocibles bajo transducciones definibles, basándose en la conexión entre resultados seminales de Courcelle, Engelfriet, Bojanczyk y Pilipczuk.
El artículo demuestra que, mientras existen continuas extensiones axiomáticas de la lógica sin la regla de intercambio que poseen la propiedad de interpolación deductiva, exactamente sesenta extensiones con intercambio (y sus variedades algebraicas correspondientes) cumplen dicha propiedad y admiten una completación de modelo.
Este artículo establece una base para un cálculo de expresiones contextuales sin ligadores de variables mediante la identificación de una copia del cierre de punto fijo de un álgebra de Kleene dentro de un producto tensorial con un álgebra poliacíclica, utilizando representaciones de autómatas y teoremas de forma normal que restringen la aparición de paréntesis.
Este artículo presenta un algoritmo de tiempo polinómico para particionar un polígono simple en el número mínimo de polígonos estelares, resolviendo así un problema teórico abierto durante más de cuatro décadas.
El artículo generaliza desigualdades para la función sumatoria de la suma de dígitos en una base entera, demostrando que varios resultados conocidos se deducen de un teorema de un trabajo de 2023 sobre la robustidad mutacional máxima en mapas genotipo-fenotipo.
Los autores demuestran que el problema de isomorfismo para torneos de ancho gemelo acotado es resoluble en tiempo polinómico mediante técnicas de teoría de grupos, estableciendo además que el ancho gemelo en torneos es funcionalmente menor que el ancho de árbol dirigido y que el algoritmo combinatorio de Weisfeiler-Leman no es suficiente para resolver este problema en dimensiones sublineales.
Este artículo presenta un enfoque de reescritura LTL optimizado e integrado en la herramienta OCRA para verificar la composición asíncrona de propiedades temporales sobre componentes de software, abordando tanto trazas infinitas como finitas y garantizando la equivalencia semántica entre las propiedades locales y globales.
Este artículo presenta una demostración simple de que la recurrencia cuenta las palabras -regulares que evitan ciertos patrones, complementa el resultado probando que cuenta las que evitan otros patrones específicos, y conjetura una relación cuadrática con los números de Fibonacci para un caso vinculado.
Este trabajo caracteriza completamente las lenguas -regulares posicionales mediante autómatas de paridad, demostrando que su posición es decidible en tiempo polinómico, estableciendo ciertos levantamientos de jugadores y resolviendo la conjetura de Kopczyński sobre la clausura bajo unión de objetivos posicionales independientes del prefijo.
Este artículo generaliza la interpretación de lenguajes de llamada por valor con iteración guardada en categorías de Freyd, demostrando que la representación de espacios funcionales con efectos guardados requiere el uso de monadas parametrizadas, lo que ofrece una descripción de la guardiandad como una propiedad categórica intrínseca de los programas.
El artículo presenta un algoritmo que permite enumerar las respuestas a consultas en lógica monádica de segundo orden (MSO) sobre bosques no ordenados comprimidos mediante programas lineales rectos (SLP) con un preprocesamiento lineal en el tamaño de la compresión y un retraso lineal en la salida, superando así las limitaciones de los métodos anteriores al trabajar directamente con datos comprimidos.
Este artículo demuestra que las Dinámicas de Grafos Causales pueden expresarse como extensiones de Kan, validando así la formalización de las Transformaciones Globales para este modelo y revelando la universalidad de las Dinámicas Causales Monótonas.