Nummer

INFO-4445 		Titel

Algebraische Struktur und Komplexität formaler Sprachen 		Lehrform(en)

Vorlesung
ECTS 3
Arbeitsaufwand
- Kontaktzeit
- Selbststudium
Arbeitsaufwand:
90 h
Kontaktzeit:
30 h / 2 SWS
Selbststudium:
60 h
Veranstaltungsdauer 1 Semester
Häufigkeit des Angebots Unregelmäßig
Unterrichtssprache Deutsch
Prüfungsform

mündliche Prüfung
Inhalt

Viele Konstruktionen und Verfahren regulärer Sprachen werden erst durch die Endlichkeit der zugrundeliegenden algebraischen Strukturen ermöglicht. Die Konstruktionsprinzipien gelten aber auch im Unendlichen und sind fuer ausgewaehlte nichtreguläre Fallbeispiele im unteren Komplexitätsbereich durchführbar. Die gründliche Bearbeitung der Beispiele unter Beteiligung der Studierenden gibt der Vorlesung stellenweise Übungscharakter.
Qualifikationsziele

Verständnis für die grundlegenden algebraischen Konstruktionen formaler Sprachen sowie ein Überblick über die Beziehungen zwischen formalen Sprachen und Komplexität
Vergabe von Leistungspunkten/Benotung
Lehrform
Status
SWS
LP
Prüfungsform
Prüfungsdauer
Benotung
Berechnung
Modulnote (%)
Teilnahmevoraussetzungen Es gibt keine besonderen Voraussetzungen.
Dozent/in Lange
Literatur / Sonstiges

Literatur / Literature:
- Howard Straubing: Finite Automata, Formal Logic, and Circuit Complexity, Birkhaeuser 1994.
- O. Matz, A. MIller, A. Potthoff, W. Thomas, E. Valkema: Report on the Program AMoRe, Universitaet Kiel 1995

--

Voraussetzungen / Prerequisites: Grundlagen der regulaeren und kontextfreien
Sprachen / Basics of regular and context-free languages.
Zuletzt angeboten nicht bekannt
Geplant für Wintersemester 2023
Zugeordnete Studienbereiche INFO-INFO, INFO-THEO, MEDI-APPL, MEDI-INFO, ML-CS