Modulcode:	Inf-SRS
Englische Bezeichnung:	String Rewriting Systems
Modulverantwortliche(r):	Prof. Dr. Dirk Nowotka
Turnus:	unregelmäßig
Präsenzzeiten:	2V 2Ü
ECTS:	4
Workload:	30 Std. Vorlesung, 30 Std. Präsenzübung, 120 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	WO_approval (Sonstige)
Lehrsprache:	Englisch
Voraussetzungen:

Kurzfassung:

This course aims to provide an overview of the theory of rewriting systems from a formal-languages viewpoint, covering systems such as L-systems, Semi-Thue systems and regulated grammars, and considering the main topics such termination, confluence and normal forms. A strong background in theory, and in formal reasoning is essential, while a good working knowledge of formal languages is also preferable.

Lernziele:

By the end of the course, students should know what a rewriting system system, and be aware of various examples and their motivations. They should understand and be familiar with the important definitions, theorems and properties associated with rewriting systems, including being able to produce proofs in some cases.

Lehrinhalte:

The course will aim to cover:

• Introduction to rewriting systems
• Fundamental notions including termination, confluence, and normal forms
• Prominent examples in formal languages such as L-systems, Semi-Thue systems, etc.
• Regulated rewriting systems
• Term rewriting systems and applications

Weitere Voraussetzungen:

• Theoretische Grundlagen der Informatik
• Logik in der Informatik

Prüfungsleistung:

Oral examination at the end of the course

Lehr- und Lernmethoden:

Lectures with beamer, reading, written exercises

Verwendbarkeit:

Literatur:

J. Dassow and G. Paun: Regulated Rewriting in Formal Language Theory

F. Baader and T. Nipkow: Term rewriting and all that,

J. W. Klop: Term Rewriting Systems

R. V. Book and F. Otto: String-Rewriting systems

Verweise:

Kommentar: