检索结果-内蒙古大学图书馆

THE CODE PROBLEM FOR DIRECTED FIGURES

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2010年第4期44卷 489-506页

作者： Kolarz, Michal Jagiellonian Univ Inst Comp Sci PL-30348 Krakow Poland

We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.

关键词： Directed figures variable-length codes codicity verification sardinas-patterson algorithm

来源：评论

学校读者我要写书评

暂无评论

Directed figure codes are decidable

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2009年第2期11卷 1-13页

作者： Kolarz, Michal Moczurad, Wlodzimierz Jagiellonian Univ Inst Comp Sci PL-30348 Krakow Poland

Two-dimensional structures of various kinds can be viewed as generalizations of words. Codicity verification and the defect effect, important properties related to word codes, are studied also in this context. Unfortunately, both are lost in the case of two common structures, polyominoes and figures. We consider directed figures defined as labelled polyominoes with designated start and end points, equipped with catenation operation that uses a merging function to resolve possible conflicts. We prove that in this setting verification whether a given finite set of directed figures is a code is decidable and we give a constructive algorithm. We also clarify the status of the defect effect for directed figures.

关键词： directed figures variable-length codes codicity verification sardinas-patterson algorithm defect effect

来源：评论

学校读者我要写书评

暂无评论

Relational codes of words

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-2期389卷 237-249页

作者： Halava, Vesa Harju, Tero Karki, Tomi Univ Turku Dept Math FIN-20014 Turku Finland Univ Turku Turku Ctr Comp Sci FIN-20014 Turku Finland

We consider words, i.e. strings over a finite alphabet together with a similarity relation induced by a compatibility relation on letters. This notion generalizes that of partial words. The theory of codes on combinatories on words is revisited by defining (R, S)-codes for arbitrary similarity relations R and S. We describe an algorithm to test whether or not a finite set of words is an (R, S)-code. Coding properties of finite sets of words are explored by finding maximal and minimal relations with respect to relational codes. (c) 2007 Elsevier B.V. All rights reserved.

关键词： code relational code partial word NP-completeness sardinas-patterson algorithm

来源：评论

学校读者我要写书评

暂无评论

On the ratio of prefix codes to all uniquely decodable codes with a given length distribution

引用

DISCRETE APPLIED MATHEMATICS 2018年 244卷 205-213页

作者： Woryna, Adam Silesian Tech Univ Inst Math Ul Kaszubska 23 PL-44100 Gliwice Poland

We investigate the ratio ma of prefix codes to all uniquely decodable codes over an n-letter alphabet and with length distribution L. For any integers n >= 2 and m >= 1, we construct a lower bound and an upper bound for inf(L rho n,L), the infimum taken over all sequences L of length m for which the set of uniquely decodable codes with length distribution L is nonempty. As a result, we obtain that this infimum is always greater than zero. Moreover, for every m >= 1 it tends to I when n -> infinity, and for every n >= 2 it tends to 0 when m -> infinity. In the case m = 2, we also obtain the exact value for this infimum. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Uniquely decodable code Prefix code Length distribution Kraft's inequality sardinas-patterson algorithm

来源：评论

学校读者我要写书评

暂无评论

On the set of uniquely decodable codes with a given sequence of code word lengths

引用

DISCRETE MATHEMATICS 2017年第2期340卷 51-57页

作者： Woryna, Adam Silesian Tech Univ Inst Math Ul Kaszubska 23 PL-44100 Gliwice Poland

For every natural number n >= 2 and every finite sequence L of natural numbers, we consider the set UDn(L) of all uniquely decodable codes over an n-letter alphabet with the sequence L as the sequence of code word lengths, as well as its subsets PRn(L)and FDn(L) consisting of, respectively, the prefix codes and the codes with finite delay. We derive the estimation for the quotient vertical bar UDn(L)vertical bar/vertical bar PRn(L)vertical bar, which allows to characterize those sequences L for which the equality PRn(L) = UDn(L) holds. We also characterize those sequences L for which the equality FDn(L) = UDn(L) holds. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Uniquely decodable code Prefix code Code with finite delay Kraft's procedure sardinas-patterson algorithm

来源：评论

学校读者我要写书评

暂无评论

On the proportion of prefix codes in the set of three-element codes

引用

DISCRETE MATHEMATICS 2020年第8期343卷 111939-111939页

作者： Woryna, Adam Silesian Tech Univ Fac Appl Math Ul Kaszubska 23 PL-44100 Gliwice Poland

Let L be a finite sequence of natural numbers. In Woryna (2017, 2018), we derived some interesting properties for the ratio rho(n,L) = vertical bar PRn (L)vertical bar/vertical bar UDn(L)vertical bar, where UDn(L) denotes the set of all codes over an n-letter alphabet and with length distribution L, and PRn(L) subset of UDn(L) is the corresponding subset of prefix codes. In the present paper, we study the case when the length distributions are three-element sequences. We show in this case that the ratio rho(n,L) is always greater than alpha(n), where alpha(n) = (n - 2)/n for n > 2 and alpha(2) = 1/6. Moreover, the number alpha(n) is the best possible lower bound for this ratio, as the length distributions of the form L = (1, 1, c) and L = (1, 2, c) assure that the ratios asymptotically approach alpha(n). Namely, if L = (1, 1, c), then rho(n,L) tends to (n- 2)/n with c -> infinity, and, if L = (1, 2, c), then rho(2,L) tends to 1/6 with c -> infinity. (C) 2020 The Author(s). Published by Elsevier B.V.

关键词： Code Prefix code Length distribution of a code Kraft inequality sardinas-patterson algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：