Paper Info
Title
Transducers with Origin Information.
Abstract
Call a string-to-string function 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. This paper proposes to treat origin information as part of the semantics of a regular string-to-string function. 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.
Year
DOI
Venue
2013
10.1007/978-3-662-43951-7_3
Lecture Notes in Computer Science
DocType
Volume
ISSN
Journal
8573
0302-9743
Citations 
PageRank 
References 
6
0.50
4
Authors
1
Name
Order
Citations
PageRank
Mikolaj Bojanczyk135235.99