
Lab lunch by Sebastian Maneth
—
filed under:
Lab Lunch
Sebastian Maneth will speak about Formal Graph Language Theory. Biscuits will be arranged by Fabian Peternek.
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. Document Actions 
