Paper Abstract and Keywords |
Presentation |
2013-03-18 16:05
An extension of code by introducing partial orders on codewords Etsuro Moriya (Waseda Univ.) COMP2012-61 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
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. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
code / non-code / codeword / partial order / partially ordered code / / / |
Reference Info. |
IEICE Tech. Rep., vol. 112, no. 498, COMP2012-61, pp. 61-68, March 2013. |
Paper # |
COMP2012-61 |
Date of Issue |
2013-03-11 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
COMP2012-61 |
Conference Information |
Committee |
COMP |
Conference Date |
2013-03-18 - 2013-03-18 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Gifu University |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
COMP |
Conference Code |
2013-03-COMP |
Language |
English (Japanese title is available) |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
An extension of code by introducing partial orders on codewords |
Sub Title (in English) |
|
Keyword(1) |
code |
Keyword(2) |
non-code |
Keyword(3) |
codeword |
Keyword(4) |
partial order |
Keyword(5) |
partially ordered code |
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Etsuro Moriya |
1st Author's Affiliation |
Waseda University (Waseda Univ.) |
2nd Author's Name |
|
2nd Author's Affiliation |
() |
3rd Author's Name |
|
3rd Author's Affiliation |
() |
4th Author's Name |
|
4th Author's Affiliation |
() |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2013-03-18 16:05:00 |
Presentation Time |
25 minutes |
Registration for |
COMP |
Paper # |
COMP2012-61 |
Volume (vol) |
vol.112 |
Number (no) |
no.498 |
Page |
pp.61-68 |
#Pages |
8 |
Date of Issue |
2013-03-11 (COMP) |
|