A Canonical Semi-Deterministic Transducer

Achilles Beros, Colin Higuera
The 12th International Conference on Grammatical Inference, PMLR 34:33-48, 2014.

Abstract

We prove the existence of a canonical form for semi-deterministic transducers with sets of pairwise incomparable 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v34-beros14a, title = {A Canonical Semi-Deterministic Transducer}, author = {Beros, Achilles and Higuera, Colin}, booktitle = {The 12th International Conference on Grammatical Inference}, pages = {33--48}, year = {2014}, editor = {Clark, Alexander and Kanazawa, Makoto and Yoshinaka, Ryo}, volume = {34}, series = {Proceedings of Machine Learning Research}, address = {Kyoto, Japan}, month = {17--19 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v34/beros14a.pdf}, url = {https://proceedings.mlr.press/v34/beros14a.html}, abstract = {We prove the existence of a canonical form for semi-deterministic transducers with sets of pairwise incomparable 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.} }
Endnote
%0 Conference Paper %T A Canonical Semi-Deterministic Transducer %A Achilles Beros %A Colin Higuera %B The 12th International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2014 %E Alexander Clark %E Makoto Kanazawa %E Ryo Yoshinaka %F pmlr-v34-beros14a %I PMLR %P 33--48 %U https://proceedings.mlr.press/v34/beros14a.html %V 34 %X We prove the existence of a canonical form for semi-deterministic transducers with sets of pairwise incomparable 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.
RIS
TY - CPAPER TI - A Canonical Semi-Deterministic Transducer AU - Achilles Beros AU - Colin Higuera BT - The 12th International Conference on Grammatical Inference DA - 2014/08/30 ED - Alexander Clark ED - Makoto Kanazawa ED - Ryo Yoshinaka ID - pmlr-v34-beros14a PB - PMLR DP - Proceedings of Machine Learning Research VL - 34 SP - 33 EP - 48 L1 - http://proceedings.mlr.press/v34/beros14a.pdf UR - https://proceedings.mlr.press/v34/beros14a.html AB - We prove the existence of a canonical form for semi-deterministic transducers with sets of pairwise incomparable 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. ER -
APA
Beros, A. & Higuera, C.. (2014). A Canonical Semi-Deterministic Transducer. The 12th International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 34:33-48 Available from https://proceedings.mlr.press/v34/beros14a.html.

Related Material