A Canonical Semi-Deterministic Transducer

被引：0
|
作者：
Beros, Achilles A. [1 ]
de la Higuera, Colin [2 ]
机构：
[1] Univ Hawaii Manoa, Dept Math, 2565 McCarthy Mall,Keller Hall 401A, Honolulu, HI 96822 USA
[2] Univ Nantes, Lab Informat Nantes Atlantique, 2 Rue Houssiniere BP 92208, F-44322 Nantes 03, France
来源：
FUNDAMENTA INFORMATICAE | 2016年 / 146卷 / 04期
关键词：
Grammatical Inference; Semi-Deterministic Transducers; FINITE-STATE TRANSDUCERS; SUBSEQUENTIAL TRANSDUCERS; MACHINE TRANSLATION; LANGUAGE; IDENTIFICATION; COMPLEXITY; INFERENCE; GRAMMARS;
D O I：
10.3233/FI-2016-1394
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
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.
引用
收藏
页码：431 / 459
页数：29
相关论文
共 50 条
  • [41] MoM based semi-deterministic approach for modelling scattering from building faces
    Mahmood, Kashif
    Rafiq, Gulzaib
    Mughal, M. Junaid
    10TH IEEE INTERNATIONAL MULTITOPIC CONFERENCE 2006, PROCEEDINGS, 2006, : 373 - +
  • [42] Semi-deterministic versus genetic algorithms for global optimisation of multichannel optical filters
    Ivorra, Benjamin
    Mohammadi, Bijan
    Redont, Patrick
    Dumas, Laurent
    Durand, Olivier
    INTERNATIONAL JOURNAL OF COMPUTATIONAL SCIENCE AND ENGINEERING, 2006, 2 (3-4) : 170 - 178
  • [43] The Application of Semi-Deterministic Method on High-Speed Railway Cutting Scenario
    Chen, Binghao
    Zhong, Zhangdui
    Ai, Bo
    Michelson, David G.
    2014 XXXITH URSI GENERAL ASSEMBLY AND SCIENTIFIC SYMPOSIUM (URSI GASS), 2014,
  • [44] Cooperative Binning for Semi-deterministic Channels with Non-causal State Information
    Gattegno, Ido B.
    Permuter, Haim H.
    Shamai, Shlomo
    Ozgur, Ayfer
    2017 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2017, : 31 - 35
  • [45] Semi-Deterministic Modeling of Diffuse Scattering Component Based on Propagation Graph Theory
    Tian, Li
    Degli-Esposti, Vittorio
    Vitucci, Enrico M.
    Yin, Xuefeng
    Mani, Francesco
    Lu, Stan X.
    2014 IEEE 25TH ANNUAL INTERNATIONAL SYMPOSIUM ON PERSONAL, INDOOR, AND MOBILE RADIO COMMUNICATION (PIMRC), 2014, : 155 - 160
  • [46] Secrecy-Reliability Tradeoff for Semi-Deterministic Wiretap Channels at Finite Blocklength
    Yang, Wei
    Schaefer, Rafael F.
    Poor, Fl. Vincent
    2017 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2017, : 2133 - 2137
  • [47] Coherent Vortex Simulation (CVS), A Semi-Deterministic Turbulence Model Using Wavelets
    Marie Farge
    Kai Schneider
    Flow, Turbulence and Combustion, 2001, 66 : 393 - 426
  • [48] Coherent Vortex Simulation (CVS), a semi-deterministic turbulence model using wavelets
    Farge, M
    Schneider, K
    FLOW TURBULENCE AND COMBUSTION, 2001, 66 (04) : 393 - 426
  • [49] A Semi-deterministic Approach for Clipping Noise Mitigation in DCO-OFDM Systems
    Bera, Krishnendu
    Bakaul, Masuduzzaman
    Karmakar, Nemai
    PROCEEDINGS OF 2019 25TH ASIA-PACIFIC CONFERENCE ON COMMUNICATIONS (APCC), 2019, : 122 - 125
  • [50] A Semi-deterministic Method for Predicting Indoor Cellular Coverage in Dense Urban Areas
    Degli-Esposti, V.
    Lu, J. S.
    Wu, J. N.
    Zhu, J. J.
    Blaha, J. A.
    Vitucci, E. M.
    Fuschini, F.
    Barbiroli, M.
    2016 10TH EUROPEAN CONFERENCE ON ANTENNAS AND PROPAGATION (EUCAP), 2016,
12345