Konstruktionen und Modelltheorie für Hypergraphen kontrollierter Azyklizität
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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
