Module Number

INFO-4445 		Module Title

Algebraic Structure and Complexity of Formal Languages 		Lecture Type(s)

Lecture
ECTS 3
Work load
- Contact time
- Self study
Workload:
90 h
Class time:
30 h / 2 SWS
Self study:
60 h
Duration 1 Semester
Frequency Irregular
Language of instruction German
Type of Exam

oral exam
Content

Many constructions and procedures of regular languages are only possible because of the finiteness of the underlying algebraic structures. However, the construction principles are also valid at infinity and are feasible for selected non-regular case studies in the lower complexity range. The thorough treatment of the examples with the participation of the students gives the lecture an exercise character in places.
Objectives

An understanding of the basic algebraic constructions of formal languages, and an overview of the relationships between formal languages and complexity
Allocation of credits / grading
Type of Class
Status
SWS
Credits
Type of Exam
Exam duration
Evaluation
Calculation
of Module (%)
Prerequisite for participation There are no specific prerequisites.
Lecturer / Other Lange
Literature

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.
Last offered unknown
Planned for Wintersemester 2023
Assigned Study Areas INFO-INFO, INFO-THEO, MEDI-APPL, MEDI-INFO, ML-CS