3447 articoli
Questo articolo presenta una nuova dimostrazione elementare della proprietà del modello finito per l'Algebra di Kleene, basata su automi di trasformazione, che unifica e generalizza i risultati precedenti di Palka e Pratt, stabilendo la completezza rispetto ai modelli relazionali finiti.
Questo studio analizza le parole di Dyck nelle sequenze binarie, dimostrando che le parole libere da potenze $7/3$ hanno un livello di annidamento limitato, fornendo una caratterizzazione esplicita e un conteggio dei fattori di Dyck nella parola di Thue-Morse, e stabilendo limiti superiori e inferiori stretti per il loro numero.
Il paper rivede un classico teorema sulle rappresentazioni -basate utilizzando il dimostratore Walnut per ottenere una prova computazionale diretta, permettendo di derivare in modo uniforme e automatico sia risultati noti che nuovi, senza ricorrere all'induzione.
Questo articolo dimostra che l'eliminazione di un singolo quantificatore universale nelle strutture automatiche comporta inevitabilmente un'esplosione esponenziale doppia, rendendo il problema della decisione completo per EXPSPACE, e utilizza queste tecniche per stabilire nuovi limiti inferiori per frammenti dell'aritmetica di Büchi.
Questo lavoro perfeziona la tecnica dei grafi di tipo pesati per dimostrare la terminazione dei sistemi di trasformazione grafica DPO, aumentandone la potenza, generalizzandola ad altre categorie e adattandola alle varianti DPO presenti in letteratura.
Il paper propone BOPIM, un algoritmo di ottimizzazione bayesiana per la massimizzazione dell'influenza su reti temporali che, superando le sfide legate agli spazi combinatori attraverso kernel specifici e una funzione di acquisizione adattata, supera i metodi esistenti in velocità mantenendo prestazioni comparabili e offrendo per la prima volta una quantificazione dell'incertezza negli insiemi di nodi semi ottimali.
Questo studio longitudinale su GPT, Llama e Qwen rivela che gli aggiornamenti dei modelli linguistici non garantiscono sistematicamente un miglioramento della robustezza contro attacchi avversariali, mostrando anzi che versioni successive possono talvolta peggiorare aspetti come la misclassificazione e le allucinazioni nonostante miglioramenti in altri ambiti.
Il lavoro generalizza gli assiomi di cardinalità dalle algebre di relazione alle algebre di Stone per modellare grafi pesati, semplificando di conseguenza gli assiomi originali e fornendo condizioni sufficienti per la rappresentabilità di queste strutture.
Il lavoro fornisce una caratterizzazione degli insiemi di grafi sia definibili in logica monadica del secondo ordine con conteggio (CMSO) sia context-free, dimostrando la loro equivalenza con insiemi riconoscibili a larghezza ad albero limitata, insiemi parsabili e immagini di insiemi di alberi riconoscibili tramite trasduzioni definibili, basandosi su una nuova connessione tra risultati fondamentali di Courcelle, Engelfriet, Bojanczyk e Pilipczuk.
Il paper dimostra che, mentre esistono un numero continuo di varietà di reticoli residuati semilineari idempotenti non commutativi con la proprietà di amalgamazione, esattamente sessanta varietà commutative godono della stessa proprietà, fornendo così una classificazione completa delle estensioni assiomatiche della logica corrispondente che possiedono l'interpolazione deduttiva.
Questo articolo sviluppa una fondazione per un calcolo delle espressioni contestuali senza legami di variabili, basandosi su forme normali per gli elementi di algebre di Kleene -continue che rappresentano i linguaggi contestuali all'interno di un prodotto tensoriale con un'algebra poliaciclica.
Questo articolo risolve un problema aperto da oltre quarant'anni presentando un algoritmo in tempo polinomiale per partizionare un poligono semplice nel numero minimo di poligoni a forma di stella, superando le limitazioni delle soluzioni precedenti che escludevano i punti di Steiner.
Il lavoro generalizza le disuguaglianze per la funzione sommatoria della somma delle cifre in una base intera, dimostrando che diversi risultati noti possono essere dedotti da un teorema di un articolo del 2023 sulla robustezza mutazionale nelle mappe genotipo-fenotipo.
Gli autori dimostrano che l'isomorfismo per i tornei con larghezza gemella (twin width) limitata è risolvibile in tempo polinomiale utilizzando tecniche di teoria dei gruppi, mentre l'algoritmo combinatorio di Weisfeiler-Leman risulta insufficiente per questa classe di grafi.
Questo articolo presenta un nuovo approccio di riscrittura simbolica per la composizione asincrona di proprietà LTL su tracce infinite e finite, che trasforma le proprietà locali in globali considerando l'interleaving dei componenti, ne dimostra l'equivalenza semantica e ne ottimizza la dimensione, integrando tali metodi nello strumento OCRA per la verifica dei contratti.
Il documento fornisce una dimostrazione semplice che le ricorrenze di Fibonacci -arie e contano rispettivamente il numero di parole -regolari su che evitano specifici insiemi di pattern, estendendo risultati noti sui numeri di Fibonacci e Jacobsthal e proponendo una congettura sui numeri di Fibonacci al quadrato.
Questo lavoro fornisce una caratterizzazione completa delle lingue -regolari posizionali attraverso gli automi di parità, dimostrando la decidibilità in tempo polinomiale, l'esistenza di lift da giochi finiti a infiniti e da un giocatore a due, e la chiusura rispetto all'unione per obiettivi posizionali indipendenti dal prefisso, risolvendo così una congettura di Kopczyński.
Il lavoro generalizza la semantica delle categorie di Freyd per i linguaggi call-by-value, dimostrando che la rappresentazione degli spazi funzionali con effetti protetti richiede l'uso di monadi parametrizzate, offrendo così una descrizione della proprietà di "guardedness" come caratteristica intrinseca dei programmi piuttosto che come semplice predicato sulla categoria.
Il paper presenta un algoritmo che, dopo una pre-elaborazione lineare rispetto alla dimensione del programma di compressione, enumera le risposte a query MSO su foreste non ordinate compresse con ritardo lineare rispetto all'output, offrendo un miglioramento sostanziale rispetto agli algoritmi esistenti e supportando aggiornamenti di etichettatura dei vertici in tempo logaritmico.
Questo articolo dimostra che le Dinamiche dei Grafi Causali, un modello di trasformazione di grafi portuali sincrono e deterministico, rientrano nel formalismo delle Trasformazioni Globali esprimibili come estensioni di Kan, rivelando inoltre l'universalità delle dinamiche causali monotone tra quelle generali.