A Canonical Semi-Deterministic Transducer
Authors:
- Achilles BerosABAchilles Beros
- Colin de la HigueraCHColin de la Higuera
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- LEARNING THEORY IN THE ARITHMETIC HIERARCHYThe Journal of Symbolic Logic, 2014
- Elements of Automata Theory2009
- Interactive learning of node selecting tree transducerMachine Learning, 2006
- Minimization algorithms for sequential transducersTheoretical Computer Science, 2000
- The design principles of a weighted finite-state transducer libraryTheoretical Computer Science, 2000
- Optimal linguistic decoding is a difficult computational problemPattern Recognition Letters, 1999
- Characteristic Sets for Polynomial Grammatical InferenceMachine Learning, 1997
- Text and speech translation by means of subsequential transducersNatural Language Engineering, 1996
- Transductions and Context-Free Languages1979
- Toward a mathematical theory of inductive inferenceInformation and Control, 1975