Parameteranalyse für bestimmte gerichtete azyklische Graphen

01.03.2024 - 28.02.2027
Forschungsförderungsprojekt

Im Projekt werden klassische Datenstrukturen aus der Informatik als kombinatorische Strukturen aufgefasst und algorithmisch und quantitativ untersucht. In den letzten zehn Jahren wurden viele Verbesserungen erzielt, um die Modellierung dieser Datenstrukturen als gerichtete azyklische Graphen (oder DAGs) kombinatorisch zu charakterisieren und so den Weg für die Analyse von Objekten zu ebnen, die durch Kompaktifizierungsverfahren erzeugt werden. Besonderes Augenmerk liegt dabei auf Booleschen Schaltungen und Entscheidungsdiagrammen. Das Projekt betrachtet somit neue Arten von Objekten im kombinatorischen Rahmen. Für einige von ihnen fehlt sogar eine geeignete Spezifikation, und es könnte eine große Herausforderung sein, eine solche zu finden. Eine weitere Herausforderung besteht darin, die Algebra der erzeugenden Funktionen auf diese neuen Structuren zu erweitern.             

Obwohl die zu entwickelnde Methodik auf die vorgeschlagenen Probleme zugeschnitten ist, ist sie potenziell allgemein anwendbar, insbesondere, da DAGs in vielen verschiedenen Anwendungen vorkommen. Ein endgültiger Durchbruch wäre die Identifizierung einer allgemeinen Klasse von DAGs, die analytisch handhabbar ist und einen einheitlichen Rahmen für Datenstrukturen schafft, die aus jeder Art von Kompaktifizierungsverfahren hervorgehen. Dies würde somit eine einheitliche Methode zur Analyse der wichtigsten Formeigenschaften solcher Strukturen liefern.


Personen

Projektleiter_in

Institut

Förderungmittel

  • FWF - Österr. Wissenschaftsfonds (National) Programm Joint Projects Internationale Programme Fonds zur Förderung der wissenschaftlichen Forschung (FWF) Ausschreibungskennung 10.55776/I6744

Forschungsschwerpunkte

  • Fundamental Mathematics Research: 50%
  • Computer Science Foundations: 50%

Schlagwörter

DeutschEnglisch
Gerichtete azyklische Graphendirected acyclic graphs
Erzeugende Funktionengenerating functions
Gleichmäßige Erzeugung von kombinatorischen Strukturenuniform random generation of combinatorial structures

Externe Partner_innen

  • SORBONNE UNIVERSITE (SU)

Publikationen