cs articoli | Gist.Science

Characterizations of Monadic Second Order Definable Context-Free Sets of Graphs

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.

Radu Iosif, Florian Zuleger2026-03-11💻 cs

Interpolation and the Exchange Rule

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.

Wesley Fussner, George Metcalfe, Simon Santschi2026-03-11💻 cs

Normal Forms for Elements of ${}^*$ -Continuous Kleene Algebras Representing the Context-Free Languages

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.

Mark Hopkins, Hans Leiß2026-03-11💻 cs

Minimum Star Partitions of Simple Polygons in Polynomial Time

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.

Mikkel Abrahamsen, Joakim Blikstad, André Nusser + 1 more2026-03-11💻 cs

Summing the sum of digits

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.

Jean-Paul Allouche, Manon Stipulanti2026-03-11💻 cs

Isomorphism for Tournaments of Small Twin Width

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.

Martin Grohe, Daniel Neuen2026-03-11💻 cs

Asynchronous Composition of LTL Properties over Infinite and Finite Traces

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.

Alberto Bombardelli, Stefano Tonetta2026-03-11💻 cs

Pattern Avoidance for Fibonacci Sequences using $k$ -Regular Words

Il documento fornisce una dimostrazione semplice che le ricorrenze di Fibonacci $k$ -arie $a_k(n)$ e $b_k(n)$ contano rispettivamente il numero di parole $k$ -regolari su $[n]$ 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.

Emily Downing, Elizabeth Hartung, Cody Lucido + 1 more2026-03-11💻 cs

Positional $ω$ -regular languages

Questo lavoro fornisce una caratterizzazione completa delle lingue $\omega$ -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.

Antonio Casares, Pierre Ohlmann2026-03-11💻 cs

Representing Guardedness in Call-by-Value and Guarded Parametrized Monads

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.

Sergey Goncharov2026-03-11💻 cs

Enumeration for MSO-Queries on Compressed Trees

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.

Markus Lohrey, Markus L. Schmid2026-03-11💻 cs

Causal Graph Dynamics and Kan Extensions

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.

Luidnel Maignan, Antoine Spicher2026-03-11💻 cs

Using weakest application conditions to rank graph transformations for graph repair

Questo articolo presenta un approccio teorico e algoritmico per la riparazione graduale di grafi, che utilizza condizioni di applicazione deboli (indicatori di danno e di riparazione) per classificare le trasformazioni in base al loro potenziale di recupero della coerenza, dimostrando efficacia e scalabilità attraverso una valutazione sperimentale.

Lars Fritsche, Alexander Lauer, Maximilian Kratz + 2 more2026-03-11💻 cs

Möbius-Transformed Trapezoidal Rule

Questo articolo dimostra che l'uso di una trasformazione di Möbius per applicare la regola del trapezio a funzioni in spazi di Sobolev pesati su una retta reale garantisce un tasso di convergenza ottimale, permettendo l'integrazione numerica senza richiedere campioni probabilistici o derivate della funzione peso.

Yuya Suzuki, Nuutti Hyvönen, Toni Karvonen2026-03-11💻 cs

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros

Il paper dimostra che il partizionante del modello di Potts antiferromagnetico non si annulla per un numero di colori $q$ leggermente inferiore a $2\Delta $, permettendo così di ottenere un algoritmo deterministico in tempo polinomiale per approssimare il numero di colorazioni proprie dei grafi, superando la precedente barriera di$ q=2\Delta$.

Ferenc Bencs, Khallil Berrekkal, Guus Regts2026-03-11💻 cs

Optimizing QoS in HD Map Updates: Cross-Layer Multi-Agent with Hierarchical and Independent Learning

Il paper propone una soluzione cross-layer basata su agenti multipli con apprendimento gerarchico e indipendente per ottimizzare la latenza degli aggiornamenti delle mappe HD nelle reti VANET, regolando dinamicamente i parametri IEEE802.11 (CWmin, CWmax e IFSn) e ottenendo miglioramenti significativi rispetto allo standard EDCA.

Jeffrey Redondo, Nauman Aslam, Juan Zhang + 1 more2026-03-11💻 cs

TIMotion: Temporal and Interactive Framework for Efficient Human-Human Motion Generation

Il paper introduce TIMotion, un framework efficiente per la generazione di motion umane interattive che combina modellazione temporale e mixing interattivo tramite tecniche come l'iniezione causale interattiva, la scansione evolutiva dei ruoli e l'amplificazione di pattern localizzati, ottenendo prestazioni superiori rispetto ai metodi esistenti.

Yabiao Wang, Shuo Wang, Jiangning Zhang, Ke Fan, Jiafu Wu, Zhucun Xue, Yong Liu2026-03-11💻 cs

VisPoison: An Effective Backdoor Attack Framework for Tabular Data Visualization Models

Il paper introduce VisPoison, un framework di attacco backdoor che sfrutta l'avvelenamento dei dati per compromettere i modelli di visualizzazione da testo a tabella, inducendo con successo esposizioni di dati sensibili, visualizzazioni fuorvianti o interruzioni del servizio tramite trigger specifici, evidenziando gravi vulnerabilità di sicurezza e l'inefficacia delle attuali difese.

Shuaimin Li, Chen Jason Zhang, Xuanang Chen, Anni Peng, Zhuoyue Wan, Yuanfeng Song, Shiwen Ni, Min Yang, Fei Hao, Raymond Chi-Wing Wong2026-03-11💻 cs

Open-World Task and Motion Planning via Vision-Language Model Genereated Constraints

Il paper presenta OWL-TAMP, un approccio che integra i Modelli Vision-Language per generare vincoli di linguaggio che potenziano i sistemi di pianificazione di compiti e movimento, permettendo ai robot di risolvere compiti di manipolazione a lungo termine in ambienti aperti specificati direttamente in linguaggio naturale.

Nishanth Kumar, William Shen, Fabio Ramos, Dieter Fox, Tomás Lozano-Pérez, Leslie Pack Kaelbling, Caelan Reed Garrett2026-03-11💻 cs

"Should I Give Up Now?" Investigating LLM Pitfalls in Software Engineering

Questo studio analizza come gli ingegneri del software interagiscono con gli assistenti AI, rivelando che l'incapacità dei modelli linguistici di fornire risposte corrette porta spesso all'abbandono dello strumento, nonostante gli utenti tentino di mitigare tali errori con strategie di scaffolding e chiarimento dei prompt.

Jiessie Tie, Bingsheng Yao, Tianshi Li, Hongbo Fang, Syed Ishtiaque Ahmed, Dakuo Wang, Shurui Zhou2026-03-11💻 cs

← Precedente Successivo →

cs