Transducers with Origin Information
From MaRDI portal
Abstract: 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. This paper proposes 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.
Recommendations
- scientific article; zbMATH DE number 63751
- scientific article; zbMATH DE number 2089985
- Transducers with set output
- On two-way transducers
- Transducers and repetitions
- P transducers
- On reversible transducers
- scientific article; zbMATH DE number 3917738
- Pseudo-minimal transducer
- Transducers are type-converters
Cited in
(34)- Decision problems of tree transducers with origin
- Inferring regular languages and \(\omega\)-languages
- Regular \(\omega\)-languages with an informative right congruence
- Learning algorithms
- Modular descriptions of regular functions
- One-way resynchronizability of word transducers
- Minimal synthesis of string to string functions from examples
- Linking theorems for tree transducers
- Deciding origin equivalence of weakly self-nesting macro tree transducers
- Regular Transformations of Data Words Through Origin Information
- A circuit complexity approach to transductions
- Transducers are type-converters
- scientific article; zbMATH DE number 7447748 (Why is no real title available?)
- A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
- Provenance circuits for trees and treelike instances
- Decision problems of tree transducers with origin
- scientific article; zbMATH DE number 3917738 (Why is no real title available?)
- Output strictly local functions
- Deterministic stack transducers
- Resynchronizing classes of word relations
- scientific article; zbMATH DE number 7559429 (Why is no real title available?)
- The many facets of string transducers (invited talk)
- Origin-equivalence of two-way word transducers is in PSPACE
- On canonical models for rational functions over infinite words
- String-to-string interpretations with polynomial-size output
- On Synthesis of Resynchronizers for Transducers
- Which classes of origin graphs are generated by transducers
- Robustness analysis of string transducers
- From two-way transducers to regular function expressions
- Resynchronized uniformization and definability problems for rational relations
- Transducers of polynomial growth
- What you must remember when transforming datawords
- A logical characterization of weak determinism as simultaneous application
- Rank-decreasing transductions
This page was built for publication: Transducers with Origin Information
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167824)
