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 条

[21] Improving the Recovery of Principal Components with Semi-Deterministic Random Projections
Kang, Keegan
Hooker, Giles
2016 ANNUAL CONFERENCE ON INFORMATION SCIENCE AND SYSTEMS (CISS), 2016,
[22] Semi-deterministic Urban Canyon Models of Received Power for Microcells
Lu, Jonathan S.
Wu, Jeffrey N.
Zhu, Jian J.
Blaha, Jerome A.
2015 IEEE INTERNATIONAL SYMPOSIUM ON ANTENNAS AND PROPAGATION & USNC/URSI NATIONAL RADIO SCIENCE MEETING, 2015, : 1794 - 1795
[23] Semi-deterministic recursive optimization methods for multichannel optical filters
Ivorra, Benjamin
Mohammadi, Bijan
Dumas, Laurent
Durand, Olivier
NUMERICAL MATHEMATICS AND ADVANCED APPLICATIONS, 2006, : 1007 - +
[24] Study of MIMO channels using a novel semi-deterministic model
Forooshani, Arghavan Emami
Noghanian, Sima
2007 IEEE ANTENNAS AND PROPAGATION SOCIETY INTERNATIONAL SYMPOSIUM, VOLS 1-12, 2007, : 1233 - 1236
[25] Semi-deterministic Sparse Matrix for Low Complexity Compressive Sampling
Quan, Lei
Xiao, Song
Xue, Xiao
Lu, Cunbo
KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS, 2017, 11 (05): : 2468 - 2483
[26] \ Secrecy capacity of semi-deterministic wire-tap channels
Grubb, Jared
Vishwanath, Sriram
Liang, Yingbin
Poor, H. Vincent
PROCEEDINGS OF THE 2007 IEEE INFORMATION THEORY WORKSHOP ON INFORMATION THEORY FOR WIRELESS NETWORKS, 2007, : 199 - +
[27] The Capacity of Several New Classes of Semi-Deterministic Relay Channels
Chong, Hon-Fah
Motani, Mehul
IEEE TRANSACTIONS ON INFORMATION THEORY, 2011, 57 (10) : 6397 - 6404
[28] A simple, semi-deterministic approximation to the distribution of selective sweeps in large populations
Martin, Guillaume
Lambert, Amaury
THEORETICAL POPULATION BIOLOGY, 2015, 101 : 40 - 46
[29] On the Multiple Description Coding Problem with One Semi-deterministic Distortion Measure
Zhou, Lin
Motani, Mehul
GLOBECOM 2017 - 2017 IEEE GLOBAL COMMUNICATIONS CONFERENCE, 2017,
[30] A new achievable rate and the capacity of a class of semi-deterministic relay networks
Ghabeli, Leila
Aref, Mohammad Reza
2007 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS, VOLS 1-7, 2007, : 281 - 285

← 1 2 3 4 5 →