Partielle Information in Logik und Spielen

• Applicant: Professor Dr. Erich Grädel
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 211982289

Die generelle Zielsetzung dieses Projekts ist die Entwicklung und Untersuchung von mathematisch fundierten logischen Theorien für Interaktion. Speziellere Ziele sind die Modellierung, Klassifikation und algorithmische Behandlung von partieller bzw. imperfekter Information in formalen Modellen für Interaktion (insbesondere in Spielen) und die Integration von Konzepten wie Abhängigkeit und Unabhängigkeit, welche eng mit partieller Information verbunden sind, in geeignete logische Systeme.Wir untersuchen, welche Arten von partieller Information in informatikrelevanten Modellen berücksichtigt werden müssen und analysieren die Modelle systematisch anhand der verschiedenen Arten und Grade von Informationsunschärfen. Dabei sollen möglichst große Klassen von Modellen in allgemeine Rahmenwerke eingebettet werden, so dass auf gewissen Ebenen eine einheitliche und abstrakte Sichtweise auf die Konzepte möglich ist. Eine derartige Systematisierung der Modelle und Lösungsverfahren (mit einem gewissen Abstraktionspotential) wird die Theorie anwendbarer und für weitere Bereiche zugänglich machen.Ein zentrales Kriterium ist hierbei algorithmische Handhabbarkeit, das heißt, die relevanten Fragestellungen sollten über den entwickelten Modellen algorithmisch möglichst effizient gelöst werden können. Wir streben an, bisherige ineffiziente oder auf Spezialfälle beschränkte algorithmische Lösungen zu optimieren und zu verallgemeinern, beispielsweise unter Ausnutzung spezieller Arten von Informationsunschärfe. Hierbei ist es auch von fundamentalem Interesse, die inhärenten Grenzen algorithmischer Möglichkeiten für solche Modelle auszuloten. Ein weiteres Ziel ist es, optimale Verhaltensstrategien mit möglichst geringen Ressourcen zu implementieren und klar abzugrenzen, für welche Arten von partieller Information welche der Ressourcen benötigt werden, damit die Agenten die Informationen, welche sie (schrittweise) erhalten ausreichend akkumulieren können.Die Konzepte Abhängigkeit und Unabhängigkeit sind eng mit Informationsunschärfe verknüpft. Wir integrieren diese Konzepte systematisch in geeignete logische Systeme, ausgehend von bekannten Logiken auf der Basis von Abhängigkeit und der von uns gemeinsam mit Väänänen eingeführten stärkeren Unabhängigkeitslogik. Gemeinsam ist all diesen Ansätzen, dass die Semantik entweder auf der Basis von Spielen mit imperfekter Information definiert wird, oder auf der Basis einer kompositionalen Semantik mit Mengen von Bewertungen (Team-Semantik), welche sich damit wesentlich von der Tarski-Semantik üblicher Logiken unterscheidet. Zentrale Fragen betreffen Ausdrucksstärke, Algorithmen und Komplexität des Model-Checkings, Axiomatisierung des Unabhängigkeitsbegriffs im Zusammenhang mit der Dependency-Theorie für Datenbanken, und die Frage, welche Varianten solcher Logiken mit welchen Konzepten von partieller Information zusammenhängen.

• DFG Programme: Research Grants