28 papers
Dit paper legt uit dat lineaire RNN's beter paralleliseerbaar zijn dan niet-lineaire RNN's doordat ze logische diepte-circuits simuleren die in de complexiteitsklasse NC1 vallen, terwijl niet-lineaire RNN's P-complete problemen kunnen oplossen wat een fundamenteel parallelisatiebeperking vormt.
De auteurs presenteren een één-rond randomiseerde distributieve algoritme dat cycli 2-kleurt met een verwachte fractie monochrome randen onder de 0,24118, waarbij zowel de boven- als ondergrenzen zijn bewezen met behulp van grote taalmodellen en geformaliseerd in Lean 4.
Deze paper onderzoekt de complexiteit van het bereikbaarheidsprobleem voor VASS met gehele tellers (VASS+Z) en toont aan dat het probleem NP-compleet is bij één niet-negatieve teller, terwijl voor een bovenste grens van wordt bewezen en de aanwezigheid van gehele tellers de complexiteit van de hardheid aanzienlijk verlaagt in vergelijking met standaard VASS.
Dit artikel presenteert een algebraïsche karakterisering van omkeerbare eerste-grads cellulaire automata over onder de null-randvoorwaarde, waarbij drie noodzakelijke en voldoende voorwaarden worden geïdentificeerd die het mogelijk maken om omkeerbaarheid voor elke roostergrootte in constante tijd te verifiëren of omkeerbare regels te synthetiseren.
Dit artikel onderzoekt de computationele complexiteit van het berekenen van alignments in procesmining en toont aan dat het probleem PSPACE-compleet is voor veilige Petri-netten, NP-compleet voor diverse subclasses zoals procesbomen en T-systemen, maar in P oplosbaar is voor levende, veilige S-systemen.
Dit paper lost een decennialang openstaand probleem op door een geschiedenis-deterministische Büchi-automaat met 65 toestanden te construeren die strikt beknopter is dan elke equivalente deterministische Büchi-automaat, een bewijs dat zowel theoretische inzichten als computationele hulpmiddelen vereiste.
Dit artikel beschrijft de formele modellering, verificatie met Uppaal en testgeneratie voor de Contract Automata Runtime Environment (CARE), waarmee de betrouwbaarheid van deze gedistribueerde applicatie wordt versterkt.
Dit paper introduceert SpotIt, een nieuwe evaluatiepipeline die formele verificatie gebruikt om onbetrouwbare testgebaseerde Text-to-SQL-evaluaties te verbeteren door actief databases te zoeken die gegenereerde en grondwaarheid SQL-query's onderscheiden.