Konstruktionen und Modelltheorie für Hypergraphen kontrollierter Azyklizität

• Antragsteller: Professor Dr. Martin Otto
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2012 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 210896119

• Erstellungsjahr: 2018

Zusammenfassung der Projektergebnisse

Die Kontrolle zyklischer Konfigurationen bzw. ihre zumindest lokale Vermeidung durch partielle Abwicklungsprozesse ist eine kombinatorische und modelltheoretische Herausforderung in der Konstruktion bzw. Transformation von Modellen mit logisch und algorithmisch beherrschbarer Struktur. Die Anwendungen entsprechender Techniken für Graphen, Hypergraphen und relationale Strukturen verbinden so veschiedene Bereiche wie die kombinatorische und algebraische Behandlung homogener Strukturen (Algebra und Modelltheorie), die Ausdrucksstärke und Komplexität von spezifischen logischen Formalismen z.B. im Kontext von Datenbankabfragesprachen (guardedness), semantische Kriterien für ausdrucksstarke Systeme in der Wissenrepräsentation (epistemic logics) oder der Analyse von Strategien in modelltheoretischen Spielen und in komplexen Systemen (multi-agent systems). Die wichtigsten Arbeiten aus dem Projekt stellen starke lokale algebraisch-kombinatorische Azyklizitätskriterien in den Mittelpunkt der Betrachtung und liefern neue Einsichten zur Konstruktion und Verwendbarkeit von lokal stark azyklischen endlichen Gruppen und Gruppoiden für solche Zwecke. Die strukturelle Analyse solcher Gruppen und Gruppoide und der von ihnen induzierten Graphen- und Hypergraphen-Strukturen sowie darauf aufbauende Überlagerungs- und Amalgamierungs-Konstruktionen konnten wesentlich vorangetrieben werden. So wurden qualitativ neue Resultate mit konkreten Beiträgen zu den oben genannten Anwendungsfeldern erschlossen. Neben der v.a. auch kombinatorischen und universell-algebraischen Methodik und den verschiedenen technischen Resultaten ergibt sich als konzeptioneller Beitrag eine weiter reichende Perspektive auf logische Lokalitätsaspekte in komplexen strukturellen Szenarien. Die Ergebnisse des Projekt liefern in der Gesamtschau eine erweiterte Basis für das Verständnis und grundlegende exemplarische Beiträge zum Verhältnis zwischen lokalen und globalen Symmetrien bzw. zwischen lokaler und globaler Konsistenz und verbinden so zentrale Konzepte der universellen Algebra und Kombinatorik mit einem Leitthema der Logik und Modelltheorie.

Projektbezogene Publikationen (Auswahl)

• Highly acyclic groups, hypergraph covers and the guarded fragment, Journal of the ACM, JACM, 59 (2012)
  M. Otto
  (Siehe online unter https://dx.doi.org/10.1145/2108242.2108247)
• Queries with guarded negation, in Proceedings of the VLDB Endowment, vol. 5, 2012, pp. 1328–1339
  V. Bárány, B. ten Cate, and M. Otto
  (Siehe online unter https://dx.doi.org/10.14778/2350229.2350250)
• Expressive completeness through logically tractable models, Annals of Pure and Applied Logic, 164 (2013), pp. 1418–1453
  M. Otto
  (Siehe online unter https://doi.org/10.1016/j.apal.2013.06.017)
• Querying the guarded fragment, Logical Methods in Computer Science, 10 (2014)
  V. Bárány, G. Gottlob, and M. Otto
  
• The freedoms of (guarded) bisimulation, in Johan van Benthem on Logic and Information Dynamics, A. Baltag and S. Smets, eds., Springer, 2014, pp. 3–31
  E. Grädel and M. Otto
  (Siehe online unter https://doi.org/10.1007/978-3-319-06025-5_1)
• Pebble games and linear equations, Journal of Symbolic Logic, 80 (2015), pp. 797–844
  M. Grohe and M. Otto
  (Siehe online unter https://dx.doi.org/10.4230/LIPIcs.CSL.2012.289)
• Successor-invariant first-order logic on map graphs with excluded topological subgraphs, in Proceedings of Computer Science Logic (CSL), Leibniz Int. Proc. in Informatics, 2016
  K. Eickmeyer and K. Kawarabayashi
  (Siehe online unter https://dx.doi.org/10.4230/LIPIcs.CSL.2016.18)
• Bisimulation in inquisitive modal logic, in Proceedings of Theoretical Aspects of Rationality and Knowledge (TARK), 2017
  I. Ciardelli and M. Otto
  (Siehe online unter https://dx.doi.org/10.4204/EPTCS.251.11)
• Common knowledge & multi-scale locality analysis in Cayley structures, in Proceedings of 32th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017
  F. Canavoi and M. Otto
  (Siehe online unter https://doi.org/10.1109/LICS.2017.8005072)
• FO model checking on map graphs, in Proceedings of Foundamentals of Computation Theory (FCT), Springer LNCS, 2017
  K. Eickmeyer and K. Kawarabayashi
  (Siehe online unter https://doi.org/10.1007/978-3-662-55751-8_17)
• Succinctness of order-invariant logics on depth-bounded structures, ACM Transactions on Computational Logic, 18 (2017)
  K. Eickmeyer, M. Elberfeld, and F. Harwath
  (Siehe online unter https://dx.doi.org/10.1145/3152770)
• Cayley structures and the expressiveness of common knowledge logic. Dissertation, Fachbereich Mathematik, TU Darmstadt, 2018
  F. Canavoi
  
• Investigations in the universal algebra of hypergraph coverings and applications. Dissertation, Fachbereich Mathematik, TU Darmstadt, 2018
  J. Bitterlich