BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T052422Z
UID:Seminar-dept-474@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20190312T130000
DTEND:20190312T140000
SUMMARY:School Seminar Series
DESCRIPTION:Sarah Winter: Parameterized synthesis of subsequetial transducers from rational relations over finite words\n\nThe synthesis problem asks, given a specification that relates possible inputs to allowed outputs, whether there is a program realizing the specification, and if so, construct one.\n\n\n\nWe consider synthesis of subsequential transducers with synchronization parameters from rational relations over finite words.\n\nA subsequential transducer is basically a deterministic finite automaton that outputs a finite word on each transition.\n\nA word relation can be represented by a set of synchronizations, called synchronization language.\n\nA synchronization of a pair of words is a single word where each position is annotated over {1,2}, which indicates whether it came from the input or output component, e.g., the synchronization (1a 2a 2b 1b 2a) represents the pair (ab,aba).\n\nThe decision problems that have been studied so far either ask for synthesis by a synchronous subsequential or by an arbitrary subsequential transducer.\n\nWe ask whether a subsequential transducer whose allowed input/output behavior is specified by a given synchronization language can be synthesized from a given rational relation.\n\nThe given synchronization language is referred to as synchronization parameter.\n\n\n\nRecently, main classes of rational relations have been characterized in terms of admissible synchronization languages, and we study the above problem for different combinations of classes of rational relations and classes of synchronization languages.\n\nThe problem is undecidable in general, because it is known to be undecidable whether an arbitrary subsequential transducer can be synthesized from a rational relation.\n\nFor automatic relations (also called synchronized rational relations) it is known that it is decidable whether an arbitrary subsequential transducer or a synchronous subsequential transducer can be synthesized.\n\nRegarding our framework, the key contribution is that it is decidable whether a subsequential transducer whose synchronization language lies within a given ``automatic'' synchronization language can be synthesized from an automatic relation.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=474
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR