Transducers with origin information

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

26 lutego 2014 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

Call a string-to-string transducer regular if it can be realised by one of the following equivalent models: mso transductions, two-way deterministic automata with output, and streaming transducers with registers. In the talk, I will propose to treat origin information as part of the semantics of a regular string-to-string transducer. With such semantics, the model admits a machine-independent characterisation, Angluin-style learning in polynomial time, as well as effective characterisations of natural subclasses such as one-way transducers or first-order definable transducers.

---