ある種の有限状態変換器に対する多項式時間極限同定

• Item type: SIG Technical Reports(1)
• 公開日: 2007-11-30
• タイトル: ある種の有限状態変換器に対する多項式時間極限同定
• タイトル / 言語: en
• タイトル: Polynomial Time Identification of Finite State Transducers in Some Class
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 電気通信大学電気通信学部情報通信工学科
• 著者所属: 電気通信大学電気通信学部情報通信工学科
• 著者所属(英): en
• 著者所属(英): Department of Information and Communication Engineering, Faculty of Electro-Communications, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Department of Information and Communication Engineering, Faculty of Electro-Communications, The University of Electro-Communications
• 著者名: 若月, 光夫; 富田, 悦次
• 著者名(英): Mitsuo, WAKATSUKI; Etsuji, TOMITA
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，strict prefix deterministic finite state transducer (SPDFST と略す)と呼ぶ，状態数が有限個の変換器の真部分クラスに対する，正の例からの極限同定問題を扱う．SPDFST および，SPDFST によって表現される言語(受理される入力記号列とその際に出力される記号列の対の集合)に関する性質を示した後で，SPDFST のクラスに対する正の例からの極限同定アルゴリズムを提案する．また，Yokomori の定義において，SPDFST のクラスが正の例から多項式時間極限同定可能であることを示す．この極限同定可能性は，多項式の個数の特徴サンプルを与えることによって証明される．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This report is concerned with a subclass of finite state transducers, called strict prefix deterministic finite state transducers (SPDFST for short), and studies a problem of identifying the subclass in the limit from positive data. After providing some properties of languages represented by SPDFST's (that is, sets of pairs of input strings accepted by SPDFST's and their corresponding output strings), we show that the class of SPDFST's is polynomial time identifiable in the limit from positive data in the sense of Yokomori. This identifiability is proved by giving an exact characteristic sample of polynomial size for a language represented by an SPDFST.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2007, 号 119(2007-AL-115), p. 65-72, 発行日 2007-11-30
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会