3447 artigos
Este artigo apresenta uma nova prova elementar da propriedade do modelo finito para a Álgebra de Kleene, estabelecendo sua completude em relação a modelos relacionais finitos e unificando resultados anteriores de Palka e Pratt através do uso de autômatos de transformação.
Este artigo investiga as palavras de Dyck em sequências binárias, demonstrando que palavras livres de potências $7/3$ possuem nível de aninhamento limitado, caracterizando explicitamente os fatores da palavra de Thue-Morse que são Dyck e estabelecendo limites superiores e inferiores rigorosos para a contagem desses fatores.
Este artigo apresenta uma nova abordagem computacional para provar o teorema de Frougny e Sakarovitch sobre representações , permitindo obter demonstrações simples e uniformes de resultados existentes e novos, incluindo a recuperação automática de trabalhos recentes de Dekking e Van Loon, utilizando o provador de teoremas Walnut.
Este artigo demonstra que a eliminação de quantificadores universais em estruturas automáticas pode exigir um aumento exponencial duplo no tamanho do autômato, provando que tal blow-up é inevitável e que o problema de decidir a vacuidade da linguagem resultante é EXPSPACE-completo.
Este artigo aprimora a técnica de grafos de tipos ponderados para provar a terminação de sistemas de transformação gráfica DPO, generalizando o método para outras categorias e permitindo variações da abordagem DPO encontradas na literatura.
O artigo apresenta o BOPIM, um algoritmo de Otimização Bayesiana que supera métodos concorrentes na maximização de influência em redes temporais ao oferecer uma solução rápida e eficiente com quantificação de incerteza, utilizando kernels adaptados para espaços combinatórios.
Este estudo longitudinal analisa a evolução da robustez adversarial em três famílias de modelos de linguagem (GPT, Llama e Qwen), revelando que atualizações sucessivas nem sempre melhoram a segurança e que tamanhos maiores não garantem necessariamente maior resistência a ataques como jailbreaks, alucinações ou erros de classificação.
Este artigo generaliza os axiomas de cardinalidade para álgebras de relação de Stone, que modelam grafos ponderados, estabelecendo condições suficientes para sua representabilidade e simplificando os axiomas correspondentes para álgebras de relação.
Este artigo caracteriza os conjuntos de grafos que são simultaneamente definíveis em Lógica Monádica de Segunda Ordem com Contagem (CMSO) e contextuais (gerados por gramáticas de substituição de hiperarestas), provando sua equivalência com conjuntos reconhecíveis de largura de árvore limitada, conjuntos analisáveis e imagens de conjuntos de árvores reconhecíveis sob transduções definíveis, estabelecendo uma conexão fundamental entre resultados lógicos sobre transduções e a construção de decomposições de árvores ótimas.
O artigo investiga o papel da regra de troca na propriedade de interpolação de extensões axiomáticas de lógicas subestruturais, demonstrando que, ao contrário do caso comutativo que possui exatamente 60 variedades com essa propriedade, existem continuum de variedades não comutativas de reticulados residuais semilineares idempotentes que também a possuem.
Este artigo estabelece uma base para um cálculo de expressões de linguagens livres de contexto sem ligadores de variáveis, demonstrando que o fechamento de ponto fixo de qualquer álgebra de Kleene -contínua pode ser representado no produto tensorial com a álgebra polycíclica , utilizando formas normais em autômatos e explorando as propriedades da álgebra de bra-ket .
Este artigo apresenta um algoritmo de tempo polinomial para particionar um polígono simples no número mínimo de polígonos em forma de estrela, resolvendo um problema teórico aberto por mais de quatro décadas e superando limitações de versões anteriores que restringiam o uso de pontos de Steiner.
O artigo generaliza desigualdades para a função somatória da soma dos dígitos em uma base inteira, demonstrando que vários resultados conhecidos podem ser deduzidos de um teorema de um trabalho de 2023 originalmente focado na robustidade mutacional máxima em mapas genótipo-fenótipo.
Os autores demonstram que o problema de isomorfismo para torneios de largura de gêmeos (twin width) limitada é solúvel em tempo polinomial, estabelecendo que a largura de gêmeos é funcionalmente menor que a largura de árvore direcionada em torneios e provando que o algoritmo combinatório de Weisfeiler-Leman é insuficiente para resolver esse problema em dimensões sublineares.
Este artigo propõe uma abordagem de reescrita simbólica em LTL para compor propriedades locais em sistemas de software assíncronos que interagem via portas de dados, garantindo equivalência semântica tanto para traços infinitos quanto finitos e otimizando o tamanho da fórmula, método que foi implementado na ferramenta OCRA e validado experimentalmente.
Este artigo apresenta uma prova simples de que a recorrência conta as palavras -regulares sobre que evitam os padrões , complementa o resultado demonstrando que conta as palavras que evitam , e conjectura que o quadrado do número de Fibonacci corresponde ao conjunto de palavras que evitam os padrões vinculares .
Este trabalho caracteriza completamente as linguagens -regulares posicionais por meio de autômatos de paridade, estabelecendo a decidibilidade polinomial dessa propriedade, validando elevações de jogos e provando o fechamento sob união para objetivos prefixo-independentes, resolvendo assim uma conjectura de Kopczyński.
Este artigo generaliza a interpretação de linguagens de chamada por valor com iteração guardada em categorias de Freyd, demonstrando que a representação de espaços funcionais guardados e efetivos exige o uso de monads parametrizados, estabelecendo assim a guardada como uma propriedade categórica intrínseca dos programas.
O artigo apresenta um algoritmo que enumera respostas de consultas em lógica monádica de segunda ordem (MSO) sobre florestas não ordenadas comprimidas por programas de linha reta (SLP), alcançando pré-processamento linear no tamanho da compressão e atraso linear na saída, o que representa uma melhoria significativa em relação a métodos anteriores e estende resultados anteriores para entradas comprimidas.
Este artigo demonstra que as Dinâmicas de Grafos Causais podem ser formalizadas como extensões de Kan, validando a capacidade do formalismo de Transformações Globais de capturar suas transformações e revelando a universalidade das Dinâmicas de Grafos Causais Monotônicas.