1. Home
  2. /
  3. Studium
  4. /
  5. Lehrveranstaltungen
  6. /
  7. AutoTh

Automata Theory

NUMMER: 150334
KÜRZEL: AutoTh
MODULBEAUFTRAGTE:R: Prof. Dr. Thomas Zeume
DOZENT:IN: Prof. Dr. Thomas Zeume
FAKULTÄT: Fakultät für Informatik
SPRACHE: Englisch
SWS: 4
CREDITS: 5
ANGEBOTEN IM: jedes Sommersemester

LERNZIELE

Stu­dents learn about different au­to­ma­ta mo­dels that are used in com­pu­ter sci­ence. They learn how mo­dels can be ana­ly­sed with re­spect to clo­su­re pro­per­ties and al­go­rith­mic pro­per­ties. They shall de­ve­lop an un­der­stan­ding o the power o dis­tinct au­to­ma­ta mo­dels, and be enab­led to de­ve­lop and ana­ly­se new au­to­ma­ta mo­dels.

INHALT

Au­to­ma­ta play an im­portant role in com­pu­ter sci­ence and its ap­p­li­ca­ti­ons. As an ex­amp­le, fi­ni­te state au­to­ma­ta as in­tro­du­ced in in­tro­duc­to­ry cour­ses on theo­re­ti­cal com­pu­ter sci­ence, are used in com­pi­ler con­struc­tion and in pat­tern matching for strings. In this cour­se we sys­te­ma­ti­cal­ly study the theo­re­ti­cal fo­un­da­ti­ons of di­ver­se au­to­ma­ta mo­dels and es­ta­blish con­nec­tions of au­to­ma­ta theo­ry to other areas such as logic and al­ge­bra. Au­to­ma­ta mo­dels have been de­ve­lo­ped for a ple­t­ho­ra of ap­p­li­ca­ti­ons, among other we will study w-Au­to­ma­ta: Very si­mi­lar to fi­ni­te state au­to­ma­ta, these au­to­ma­ta work on in­fi­ni­te words. They are used in for­mal ve­ri­fi­ca­ti­on of hard­ware and soft­ware. Tree au­to­ma­ta: In­puts for these au­to­ma­ta are trees and they are used for in­stan­ce in spe­ci­fi­ca­ti­on and que­ry­ing of tree-shaped data, as for in­stan­ce XML or JSON. Pro­ba­bi­lis­tic au­to­ma­ta: These au­to­ma­ta ac­cept their in­puts with cer­tain pro­ba­bi­li­ties and can be used in pat­tern re­co­gni­ti­on and for­mal ve­ri­fi­ca­ti­on. The focus of this cour­se is on theo­re­ti­cal pro­per­ties of au­to­ma­ta, but we will also con­s­i­der some ap­p­li­ca­ti­ons.

VORAUSSETZUNGEN CREDITS

Bestandene Modulabschlussprüfung

EMPFOHLENE VORKENNTNISSE

This is a cour­se for stu­dents of ma­the­ma­tics, com­pu­ter sci­ence and ITS. Know­ledge from an in­tro­duc­to­ry theo­re­ti­cal com­pu­ter sci­ence cour­se is man­d­ato­ry.