3447 papers
Dit artikel presenteert een nieuw, elementair bewijs voor de eindige model-eigenschap van Kleene-algebra door transformatieautomaten te gebruiken, wat leidt tot een veralgemening van eerdere resultaten over de volledigheid van eindige relationele modellen.
Dit artikel onderzoekt Dyck-woorden in binaire rijen, waarbij wordt aangetoond dat $7/3$-vrije woorden een beperkte nestingsdiepte hebben, en biedt een expliciete karakterisering en telling van Dyck-factoren in het woord van Thue-Morse.
Dit artikel herlevert een klassiek stelling over automaten voor -representaties met behulp van de Walnut-theoremaprover, waardoor eerdere resultaten op een uniforme en automatische manier kunnen worden bewezen en nieuwe inzichten worden verkregen.
Deze paper bewijst dat het elimineren van universele kwantoren in automatische structuren onvermijdelijk leidt tot een dubbel-exponentiële complexiteitsstijging en dat het bepalen van de leegte van het resulterende taal EXPSPACE-volledig is, waardoor de vraag of dit in beperkte settings beter kan negatief wordt beantwoord.
Dit artikel verfijnt de techniek van gewogen typegrafen om de terminatie van DPO-graftransformatiesystemen te bewijzen, door de methode krachtiger te maken voor grafen, te generaliseren naar andere categorieën en variaties van DPO te ondersteunen.
In dit artikel wordt BOPIM voorgesteld, een Bayesiaanse optimalisatie-algoritme voor invloedmaximalisatie op tijdsafhankelijke netwerken dat door middel van aangepaste kernel-functies en een hebberige acquisitie-strategie concurrerende resultaten behaalt ten opzichte van de gouden standaard, maar tot tien keer sneller is en bovendien onzekerheid in de optimale zaadknopen kwantificeert.
Dit onderzoek toont aan dat updates van grote taalmodellen niet consequent leiden tot verbeterde weerbaarheid tegen adversariële aanvallen, aangezien nieuwe versies soms juist slechter presteren op gebieden zoals misclassificatie en hallucinaties ondanks verbeterde beveiliging tegen jailbreaks.
Dit artikel generaliseert de axioma's voor kardinaliteit van relatiealgebra's naar Stone-relation-algebra's om gewogen grafen te modelleren, wat leidt tot vereenvoudigde axioma's en voldoende voorwaarden voor representabiliteit.
Dit artikel karakteriseert de verzamelingen van grafen die zowel in tellende monadische tweede-orde logica definieerbaar als contextvrij zijn, door hun equivalentie te tonen met herkenbare verzamelingen van begrensde boombreedte, parsbare verzamelingen en afbeeldingen van herkenbare boomverzamelingen onder definieerbare transducties.
Dit artikel toont aan dat er continuüm veel niet-commutatieve idempotente semilineaire residuatiegittervariëteiten de amalgamerings eigenschap bezitten, terwijl er onder de commutatieve varianten precies zestig zulke variëteiten zijn die deze eigenschap hebben.
Dit artikel ontwikkelt een calculus voor context-vrije expressies zonder variabele binders door de vaste-punten-sluiting van een *-continue Kleene-algebra te identificeren als de centralisator van de polycyclische algebra in hun tensorproduct, en levert tevens inzichten in de relatie tussen de bra-ket algebra en .
De auteurs presenteren een polynomiale tijd-algoritme voor het partitioneren van een eenvoudig veelhoek in een minimaal aantal stervormige veelhoeken, waarmee een meer dan veertig jaar oude open vraag uit de computationele meetkunde wordt beantwoord.
Dit artikel heroverweegt en generaliseert ongelijkheden voor de sommatiefunctie van de som van cijfers in een gegeven grondtal, en toont aan dat verschillende bekende resultaten kunnen worden afgeleid uit een theorema uit een 2023-publieatie over mutatie-robuustheid.
De auteurs bewijzen dat het isomorfismeprobleem voor toernooien met een beperkte twin width in polynomiale tijd kan worden opgelost met behulp van groepstheoretische technieken, terwijl ze ook aantonen dat de combinatorische Weisfeiler-Leman-algoritme hiervoor ontoereikend is.
Dit paper introduceert een nieuwe LTL-herschrijftechniek voor het asynchrone compositie van lokale eigenschappen tot globale eigenschappen over zowel oneindige als eindige traces, wat is geïmplementeerd in het OCRA-tool en experimenteel gevalideerd.
Dit artikel bewijst dat het aantal -reguliere woorden over dat bepaalde patronen vermijdt, correspondeert met twee specifieke -ary Fibonacci-achtige recurrenties, en formuleert een conjectuur dat het kwadraat van de Fibonacci-getallen gelijk is aan het aantal woorden dat een verankerd patroon vermijdt.
Dit artikel biedt een volledige karakterisering van positionele -reguliere talen via pariteitautomata, wat leidt tot een polynomiale beslisprocedure, bewijzen voor diverse lifts en sluiting onder unie, en zo een conjectuur van Kopczyński voor -reguliere talen bevestigt.
Dit artikel generaliseert de interpretatie van call-by-value talen met guarded iteratie door aan te tonen dat het modelleren van effectvolle functieruimtes vereist dat de onderliggende categorie voortkomt uit een specifieke vorm van geparametriseerde monaden, waardoor guardedheid wordt gepresenteerd als een intrinsieke categorische eigenschap van programma's in plaats van slechts een predicaat op een categorie.
Dit artikel presenteert een algoritme dat na O(|D|) voorverwerking MSO-queries op door een SLP gecomprimeerde bomen met output-lineaire doorlooptijd kan enumereren, wat een aanzienlijke verbetering vormt ten opzichte van eerdere methoden voor ongecomprimeerde data.
Dit artikel toont aan dat de theorie van globale transformaties, gebaseerd op kansextensies, ook van toepassing is op causale grafdynamica, waarbij het de universaliteit van monotoon causale grafdynamica binnen dit kader blootlegt.