Personal tools
You are here: Home Events Lab lunch by Sebastian Maneth

Lab lunch by Sebastian Maneth

— filed under:

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

  • Lab Lunch
When Oct 06, 2015
from 01:10 PM to 02:00 PM
Where MF2
Add event to calendar vCal

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 finite-state graph automaton nor of regular graph grammar. Instead, monadic second-order (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