| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2013-03-18 16:05 半順序を持つコード語上の非コードについて ○守屋悦朗（早大）  COMP2012-61 |
|
| 抄録 | （和） | 有限アルファベット $\varSigma$ 上の言語 $X \subseteq \varSigma^*$ において，任意の $x \in X^+$ に対し，$X$ に関する分解 $x=x_1\cdots x_n$\ (各 $x_i \in X$) が一意的に定まるとき，$X$ を符号という．これに対し，$X$ 上の半順序 $\leq$ が存在して，任意の $x \in X^+$ に対し，「$x_i<x_j$ ならば $i<j$ である」という条件を満たすような分解 $x = x_1 \cdots x_n$ は唯一つしか存在しないとき，$X$ を半順序付き符号という．本研究では，言語 $X$ が符号に\underline{ならない}ための特徴付けを行い，それに基づき，$X^+$ に属する語の一意的でない分解が存在するならそれらを見つけるアルゴリズムを与える．また，一意的分解可能でない語 $x \in X^+$ に対し，$X$ 上にどのような半順序を入れたら半順序付き符号とすることができるか／できないかを決定するアルゴリズムを示す． |
| （英） | A code is a language $X$, the set of codewords, such that any word in $X^+$ can be factorized uniquely as the concatenation of words in $X$. The notion of code is extended by introducing a partial order on the set $X$ of codewords such that any word in $X^+$ satisfying a certain condition w.r.t. the partial order can be factorized uniquely. Such a language with a partial order is called a partially ordered code. Every code is a partially ordered code, and there exist non-codes that can be partially ordered with some partial orders. A necessary and sufficient condition for a language to be a non-code is given in terms of a sequence of prefixes of words in the language. Although it is a reformulation of a well-known characterization of codes, it can be used to produce a number of algorithms about non-codes. For example, a polynomial time algorithm is given to test whether or not a given finite language is a partially ordered code with respect to a given partial order. Also some algorithms to convert a non-code into a partially ordered code are considered. |
|
| キーワード | （和） | 符号 / 非符号 / 符号語 / 半順序 / 半順序付き符号 / / / |
| （英） | code / non-code / codeword / partial order / partially ordered code / / / | |
| 文献情報 | 信学技報, vol. 112, no. 498, COMP2012-61, pp. 61-68, 2013年3月. | |
| 資料番号 | COMP2012-61 | |
| 発行日 | 2013-03-11 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2012-61 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2013-03-18 - 2013-03-18 |
| 開催地（和） | 岐阜大学 |
| 開催地（英） | Gifu University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2013-03-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 半順序を持つコード語上の非コードについて |
| サブタイトル（和） | |
| タイトル（英） | An extension of code by introducing partial orders on codewords |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 符号 / code |
| キーワード(2)（和/英） | 非符号 / non-code |
| キーワード(3)（和/英） | 符号語 / codeword |
| キーワード(4)（和/英） | 半順序 / partial order |
| キーワード(5)（和/英） | 半順序付き符号 / partially ordered code |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 守屋 悦朗 / Etsuro Moriya / モリヤ エツロウ |
| 第1著者 所属（和/英） | 早稲田大学 (略称： 早大) Waseda University (略称： Waseda Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2013-03-18 16:05:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2012-61 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.498 |
| ページ範囲 | pp.61-68 |
| ページ数 | 8 |
| 発行日 | 2013-03-11 (COMP) |
[研究会発表申込システムのトップページに戻る]