3447 Arbeiten
Dieser Artikel liefert einen neuen, elementaren Beweis für die endliche Modell-Eigenschaft der Kleene-Algebra mittels Transformationsautomaten und zeigt damit, dass die Algebra vollständig bezüglich endlicher relationaler Modelle ist, was die Ergebnisse von Palka, Pratt und Kozen vereint.
Dieser Artikel untersucht Dyck-Wörter in binären Folgen, indem er die Beziehung zwischen $7/3$-Potenzfreiheit und der Verschachtelungstiefe analysiert, eine explizite Charakterisierung der Dyck-Faktoren im Thue-Morse-Wort liefert und scharfe Schranken für deren Anzahl herleitet.
Dieser Artikel stellt eine neue, rechnerisch direkte Methode vor, die mit dem Walnut-Theorembeweiser klassische und neue Ergebnisse über -Darstellungen, einschließlich der Arbeiten von Dekking und Van Loon, einheitlich und ohne Induktion beweist.
Diese Arbeit widerlegt die Hoffnung auf effizientere Verfahren, indem sie zeigt, dass die Eliminierung eines einzigen universellen Quantors in automatischen Strukturen im schlimmsten Fall einen doppel-exponentiellen Blow-up erfordert und das Leerheitsproblem EXPSPACE-vollständig ist.
Die Arbeit verfeinert die Technik gewichteter Typgraphen zum Nachweis der Terminierung von DPO-Graphtransformationssystemen, indem sie die Methode für Graphen erweitert, auf andere Kategorien verallgemeinert und Variationen des DPO-Ansatzes berücksichtigt.
Die Studie stellt BOPIM vor, einen Bayesian-Optimization-Algorithmus für die Einflussmaximierung in zeitlichen Netzwerken, der durch die Verwendung spezieller Kernel-Funktionen und einer angepassten Akquisitionsfunktion nicht nur eine signifikant schnellere Berechnung als herkömmliche gierige Algorithmen ermöglicht, sondern auch erstmals Unsicherheiten in den optimalen Seed-Knoten quantifiziert.
Diese Studie untersucht die longitudinale Robustheit von drei prominenten LLM-Familien (GPT, Llama, Qwen) gegenüber Adversarial Examples und zeigt, dass Modell-Updates nicht konsistent zu verbesserten Sicherheitsmerkmalen führen, sondern teilweise zu Verschlechterungen bei Missklassifizierung, Jailbreaks oder Halluzinationen führen können.
Diese Arbeit verallgemeinert die Axiomatisierung der Kardinalitätsoperation von Relationenalgebren auf Stone-Relationenalgebren zur Modellierung gewichteter Graphen, leitet daraus vereinfachte Axiome für Relationenalgebren ab und liefert hinreichende Bedingungen für die Darstellbarkeit sowie für die Äquivalenz von Stone-Relationenalgebren und Relationenalgebren.
Diese Arbeit charakterisiert die Mengen von Graphen, die sowohl durch zählende monadische zweite Logik definierbar als auch kontextfrei sind, als genau die Mengen mit beschränkter Baumweite, die in der Algebra der Hyperedge-Replacement-Operationen erkennbar sind, und stellt deren Äquivalenz zu parsbaren Mengen sowie zu Bildern erkennbarer ungerichteter Baummengen unter definierbaren Transduktionen her.
Die Arbeit untersucht den Einfluss der Austauschregel auf die Interpolationseigenschaft und zeigt, dass es zwar kontinuum-viele nicht-kommutative, aber nur genau sechzig kommutative idempotente semilineare residuierte Gitter mit der Amalgamierungseigenschaft gibt.
Die Arbeit entwickelt eine bindungsfreie Kalkül-Theorie für kontextfreie Ausdrücke, indem sie Normalform-Sätze für Elemente in einem Tensorprodukt aus einer *-stetigen Kleene-Algebra und einer polycyclischen Algebra nutzt, um eine Kopie der Fixpunktabschließung zu identifizieren und Ergebnisse zur „Vollständigkeitsgleichung" zu liefern.
Diese Arbeit stellt einen polynomiellen Algorithmus vor, der ein einfaches Polygon in die minimale Anzahl von sternförmigen Polygonen zerlegt und damit ein seit über vier Jahrzehnten offenes Problem in der algorithmischen Geometrie löst.
Dieser Artikel fasst bekannte Ungleichungen für die Summenfunktion der Ziffernsumme in einer gegebenen Basis zusammen, verallgemeinert diese und zeigt, dass sie sich aus einem Satz einer 2023er-Publikation über die maximale mutative Robustheit in Genotyp-Phänotyp-Karten ableiten lassen.
Die Autoren zeigen, dass das Isomorphieproblem für Turniere mit beschränkter Zwillingbreite in polynomieller Zeit lösbar ist, indem sie gruppentheoretische Techniken einsetzen, und beweisen gleichzeitig, dass der kombinatorische Weisfeiler-Leman-Algorithmus für diese Klasse ohne hohe Dimension versagt.
Diese Arbeit stellt einen neuartigen LTL-Umschreibungsansatz vor, der in das OCRA-Tool integriert wurde, um die asynchrone Komposition von Softwarekomponenten mit Datenports sowohl für unendliche als auch für endliche Traces effizient zu verifizieren und dabei lokale Eigenschaften in globale umzuwandeln.
Dieser Artikel liefert einen einfachen Beweis dafür, dass die rekursiv definierte Folge die Anzahl der -regulären Wörter über zählt, die bestimmte Muster vermeiden, ergänzt dies durch eine neue Zählung für die Folge und stellt eine Vermutung über die Quadrate der Fibonacci-Zahlen im Kontext von Stirling-Permutationen auf.
Diese Arbeit liefert eine vollständige Charakterisierung positionaler ω-regulärer Sprachen durch Paritätsautomaten, beweist die Polynomialzeit-Entscheidbarkeit dieser Eigenschaft und bestätigt eine Vermutung von Kopczyński über die Abgeschlossenheit unter Vereinigung für prefix-unabhängige Ziele.
Der Artikel verallgemeinert die Darstellung von Call-by-Value-Sprachen mit Freyd-Kategorien, indem er zeigt, dass die Repräsentation von effektenbehafteten, bewachten Funktionsräumen parameterisierte Monaden erfordert, was eine intrinsisch-kategorische Beschreibung von Bewachtheit ermöglicht.
Die Autoren präsentieren einen Algorithmus, der es ermöglicht, MSO-Abfragen auf durch einen Straight-Line-Program (SLP) komprimierten Bäumen nach einer linearen Vorverarbeitung mit output-linearem Verzögerung zu enumerieren, was eine signifikante Verbesserung gegenüber bisherigen Verfahren darstellt und zudem logarithmische Vertex-Neubearbeitungszeiten unterstützt.
Diese Arbeit zeigt, dass sich Kausale Graphendynamiken durch Kan-Erweiterungen formalisieren lassen, wodurch die Gültigkeit des Global-Transformations-Anspruchs für diese Klasse nachgewiesen und die universelle Bedeutung der monotonen Variante aufgezeigt wird.