Automatische Strukturen - Interaktive Studienpläne der TU Ilmenau

endliche Automaten (vgl. z. B. Modul "Automaten und Formale Sprachen")

Prädikatenlogik (vgl. z. B. Modul "Logik und Logikprogrammierung")

Die Studenten kennen Methoden und Grenzen der algorithmischen Analysierbarkeit unendlicher Strukturen, insbes. am Beispiel der durch endliche Automaten beschriebenen automatischen Strukturen. Sie können diese anwenden, beweisen und fundierte Vermutungen über Erweiterungen aufstellen und begründen.

Die Studierenden können kritische Fragen zum behandelten Stoff, Probleme bei der Erarbeitung des Wissens bzw. bei der Lösung der Aufgaben klar formulieren und in Diskussionen mit Kommilitonen und Lehrenden vertreten.

In den Vorlesungen und im Selbstudium haben sie die genannten Kenntnisse erworben, in den Übungen und im Selbstudium die genannten Fähigkeiten erlernt.

effektive Strukturen

Beispiele automatischer Strukturen

Beispiel von Strukturen, die nicht automatisch sind

Abschlußeigenschaften der Klasse der automatischen Strukturen

Komplexität des Auswertungsproblems in automatischen Strukturen für Erweiterungen der Prädikatenlogik

Tafel

Rubin: Automata presenting structures - a survey of the finite string case. Bulletin of Symbolic Logic 2008

Barany, Grädel, Rubin: Automata presenting infinite structures. In: Finite and Algorithmic Model Theory, Cambridge University Press 2011