A Canonical Semi-Deterministic Transducer

Issue title: Grammatical Inference

Guest editors: Rémi Eyraud, Colin de la Higuera, Makoto Kanazawa and Ryo Yoshinaka

Article type: Research Article

Authors: Beros, Achilles A.^a | Higuera, Colin de la^{b; *}

Affiliations: [a] Department of Mathematics, University of Hawai‘i at Mānoa, 2565 McCarthy Mall, Keller Hall 401A, Honolulu, Hawaii 96822, USA. beros@math.hawaii.edu | [b] Laboratoire d’Informatique de Nantes Atlantique, Université de Nantes, 2 rue de la Houssinière BP 92208, 44322 Nantes Cedex 03, France. cdlh@univ-nantes.fr

Correspondence: [*] Address for correspondence: Laboratoire d’Informatique de Nantes Atlantique, Université de Nantes, 2 rue de la Houssinière BP 92208, 44322 Nantes Cedex 03, France

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.

Keywords: Grammatical Inference, Semi-Deterministic Transducers

DOI: 10.3233/FI-2016-1394

Journal: Fundamenta Informaticae, vol. 146, no. 4, pp. 431-459, 2016