Konstruktionen und Modelltheorie für Hypergraphen kontrollierter Azyklizität

• Applicant: Professor Dr. Martin Otto
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 210896119

• Final Report Year: 2018

Final Report Abstract

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.

Publications

• Highly acyclic groups, hypergraph covers and the guarded fragment, Journal of the ACM, JACM, 59 (2012)
  M. Otto
  
• 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
  
• Expressive completeness through logically tractable models, Annals of Pure and Applied Logic, 164 (2013), pp. 1418–1453
  M. Otto
  
• 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
  
• Pebble games and linear equations, Journal of Symbolic Logic, 80 (2015), pp. 797–844
  M. Grohe and M. Otto
  
• 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
  
• Bisimulation in inquisitive modal logic, in Proceedings of Theoretical Aspects of Rationality and Knowledge (TARK), 2017
  I. Ciardelli and M. Otto
  
• 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
  
• FO model checking on map graphs, in Proceedings of Foundamentals of Computation Theory (FCT), Springer LNCS, 2017
  K. Eickmeyer and K. Kawarabayashi
  
• Succinctness of order-invariant logics on depth-bounded structures, ACM Transactions on Computational Logic, 18 (2017)
  K. Eickmeyer, M. Elberfeld, and F. Harwath
  
• 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