Lab lunch by Sebastian Maneth
Sebastian Maneth will speak about Formal Graph Language Theory. Biscuits will be arranged by Fabian Peternek.
What 


When 
Oct 06, 2015 from 01:10 PM to 02:00 PM 
Where  MF2 
Add event to calendar 
vCal iCal 
Speaker: Sebastian Maneth
Title: Formal Graph Language Theory
Abstract: An important tool in formal language theory is the notion of finite state transducer. How can this notion be generalised from strings to finite graphs? For graphs there is no accepted notion of finitestate graph automaton nor of regular graph grammar. Instead, monadic secondorder (MSO) logic is used to characterise "regular" graph languages. In this talk I explain MSO definable graph transductions and their properties: (1) they are closed under composition, (2) their inverses preserve regularity, and (3) if the output graphs are string or trees, then equivalence is decidable.