Automatische Strukturen unter berechenbaren Strukturen

Der Zweck dieses Projekts ist, algorithmische Eigenschaften von Strukturen, die mit verschiedenen Typen von Automaten repräsentiert werden, zu untersuchen. In jedem Fall, bilden solche Strukturen eine Subklasse berechenbarer Strukturen. Wir planen Unterschiede und Ähnlichkeiten zu untersuchen, die entstehen, wenn man das Verhalten automatisch repräsentierter Strukturen mit dem berechenbarer Strukturen vergleicht. Berechenbare Repräsentationen einer Struktur illustrieren den Ansatz, unendliche Strukturen in einer endlichen Weise darzustellen. Endliche Repräsentationen unendlicher Strukturen spielen eine wichtige Rolle in Logik und Informatik. In solchen Fällen, ist oft eine effektive Semantik für Strukturen erforderlich. Um dieses Ziel zu erreichen, kann man Repräsentationen von Strukturen durch verschiedene Typen endlicher Automaten verwenden. In dem ersten Teil des vorgeschlagenen Forschungsprojekts untersuchen wir Strukturen, die durch endliche Automaten repräsentiert werden. Die Fragen, die wir stellen, können als Analoga ähnlicher Fragen in der berechenbaren Modelltheorie behandelt werden. Zum Beispiel, stellen wir Fragen über die Komplexität von Beschreibungen verschiedener Klassen von Strukturen, die mit endlichen Automaten repräsentiert werden, sowie über die Komplexität verschiedener Äquivalenzrelationen auf Klassen solcher Strukturen. Au\ss erdem formulieren wir Fragen über die Eigenschaften automatisch repräsentierter Strukturen mit verschiedenen wichtigen modelltheoretischen Eigenschaften (prime, saturated, countably categorical, uncountably categorical). Zudem schlagen wir eine neue Definition von Strukturen vor, die mit pushdown Automaten repräsentiert werden. Wir nennen einige Probleme, die in diesem Bereich entstehen (sie sind hauptsächlich von ähnlichen Fragen in der berechenbaren Modelltheorie motiviert). Unter anderem: Komplexität der Theorie einer mit pushdown Automat repäsentierten Struktur, oder Komplexität anderer Modelle einer solchen Theorie. Ebenso zielen wir darauf ab: eine Charakterisierung pushdown automatisch repräsentierter Strukturen mit besonderen algebraischen und modelltheoretischen Eigenschaften zu finden.

Viele mathematische Objekte können als Strukturen dargestellt werden, wobei eine Struktur aus einer Menge besteht, die auch das Universum der Struktur genannt wird, und Relationen und Funktionen auf Elementen des Universums. In diesem Projekt untersuchen wir unendliche effektiv darstellbare Strukturen. Das bedeutet, dass es für die Struktur einen Algorithmus gibt, der Schritt für Schritt die Elemente der Struktur ausgibt, zusammen mit Relationen und Funktionen auf diesen Elementen. Damit wird ein immer größerer und größerer Teil der Struktur bekannt. Wir forschen, wie die algorithmischen Eigenschaften solcher unendlichen effektiv darstellbaren Objekte von ihren mathematischen (algebraischen, strukturellen) Eigenschaften abhängen.