A Canonical Semi-Deterministic Transducer
This work addresses a theoretical problem in automata theory and machine learning, specifically for researchers in formal languages and computational learning, but it appears incremental as it builds on existing transducer models.
The paper tackled the problem of learning semi-deterministic transducers by proving the existence of a canonical form for such transducers with incomparable output sets and developing an algorithm that uses translation queries, while also proving that domain knowledge alone is insufficient for learning them.
We prove the existence of a canonical form for semi-deterministic transducers with incomparable sets of output strings. Based on this, we develop an algorithm which learns semi-deterministic transducers given access to translation queries. We also prove that there is no learning algorithm for semi-deterministic transducers that uses only domain knowledge.