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 条
  • [1] A Semi-Deterministic Random Walk with Resetting
    Villarroel, Javier
    Montero, Miquel
    Antonio Vega, Juan
    ENTROPY, 2021, 23 (07)
  • [2] Complementing Semi-deterministic Buchi Automata
    Blahoudek, Frantisek
    Heizmann, Matthias
    Schewe, Sven
    Strejcek, Jan
    Tsai, Ming-Hsien
    TOOLS AND ALGORITHMS FOR THE CONSTRUCTION AND ANALYSIS OF SYSTEMS (TACAS 2016), 2016, 9636 : 770 - 787
  • [3] Semi-Deterministic Broadcast Channels with Cooperation
    Goldfeld, Ziv
    Permuter, Haim H.
    Kramer, Gerhard
    2014 IEEE 28TH CONVENTION OF ELECTRICAL & ELECTRONICS ENGINEERS IN ISRAEL (IEEEI), 2014,
  • [4] THE CAPACITY OF THE SEMI-DETERMINISTIC RELAY CHANNEL
    ELGAMAL, A
    AREF, M
    IEEE TRANSACTIONS ON INFORMATION THEORY, 1982, 28 (03) : 536 - 536
  • [5] The Secrecy Capacity of the Semi-deterministic Broadcast Channel
    Kang, Wei
    Liu, Nan
    2009 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, VOLS 1- 4, 2009, : 2767 - 2771
  • [6] A comparison of semi-deterministic and stochastic search techniques
    Connor, AM
    Shea, K
    EVOLUTIONARY DESIGN AND MANUFACTURE, 2000, : 287 - 298
  • [7] A new semi-deterministic model for MIMO systems
    Forooshani, Arghavan Emami
    Noghanian, Sima
    2007 IEEE ANTENNAS AND PROPAGATION SOCIETY INTERNATIONAL SYMPOSIUM, VOLS 1-12, 2007, : 1229 - 1232
  • [8] Learning Bayesian networks in semi-deterministic systems
    Luo, Wei
    ADVANCES IN ARTIFICIAL INTELLIGENCE, PROCEEDINGS, 2006, 4013 : 230 - 241
  • [9] SEMI-DETERMINISTIC TERNARY MATRIX FOR COMPRESSED SENSING
    Lu, Weizhi
    Kpalma, Kidiyo
    Ronsin, Joseph
    2014 PROCEEDINGS OF THE 22ND EUROPEAN SIGNAL PROCESSING CONFERENCE (EUSIPCO), 2014, : 2230 - 2234
  • [10] On the Data Processing Theorem in the Semi-deterministic Setting
    Merhav, Neri
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2014, 60 (10) : 6032 - 6040
12345