Palindrome words and reverse closed languages

A word which is equal to its mirror image is called a palindrome word. Any language consisting of palindrome words is called a palindrome language. In this paper we investigate properties of palindrome words and languages. We show that there is no dense regular language consisting of palindrome words. A language contains all the mirror images of its elements is called a reverse closed language. Clearly, every palindrome language is reverse closed. We show that whether a given regular or context-free language is reverse closed is decidable. We study certain properties concerning reverse closed finite maximal prefix codes in this paper. Properties of languages that commute with reverse closed languages are investigated too.     

Bi-catenation and shuffle product of languages

The shuffle product of two words consists of all words obtained by inserting one word into another word sparsely. The shuffle product of two languages is the union of all the shuffle products of two words taken one from each of these two languages. The bi-catenation of two languages A andB is the set . A non-empty word which is not a power of any other word is called a primitive word. A language is a prefix code if no word in this language is a prefix of any other word in this language. This paper is devoted to the investigation of the elementary properties of bi-catenation and shuffle product of languages. The families of prefix codes, disjunctive languages and languages consisting of primitive words with respective to these two operations are studied. We characterize languages of which the bi-catenation or the shuffle product with any non-empty word are prefix codes. We also derive that for any bifix code A, both and , , are disjunctive languages, where Q is the set of all primitive words over an alphabet X with more than one letter and . For the shuffle product case, surprisingly is a regular language, where a is a letter of the alphabet X. Received: 22 September 1997 / 7 January 1998     

On the structure of systematic prefix codes

Systematic prefix codes play an important role in coding theory, we relate them with the problem of the partition of a free (sub-) monoid into two free sub-monoids. We show too that among the dual codes of a systematic prefix code A there exists one and only one which appears in the automaton recognizing A ^*. The characterization of this automaton and some corollaries stated here will allow us to show in further note that systematic prefix codes are involved in the structure of any regular prefix code. Work done under CNR contract No. R-l7-02-417-0-A.     

Optimal Prefix Codes And Huffman Codes

Existence of the optimal prefix codes is shown in this paper. Relationship between the optimal prefix code and the Huffman code is also discussed. We prove that all Huffman codes are optimal prefix codes and conversely optimal prefix codes need not be Huffman codes. Especially, the problem of whether the optimal prefix code has to be maximal is presented. Although for information source alphabets of being not greater than four letters we show that an optimal prefix code must be maximal, it remains to be an open problem in general. As seen from Huffman codes, optimal prefix codes are used not only for statistical modeling but also for dictionary methods. Moreover, it is obtained that the complexity of breaking an optimal prefix code is NP-complete from the viewpoint of computational difficulty.     

Prefix codes and isomorphic automata

We give here the related structures of two regular prefix codes generating languages recognized by isomorphic automata.     

正则表达式在编程题自动阅卷中的应用

分析了编程题的自动阅卷的现状及存在的不足。为了让计算机能够更加合理和有效地进行编程题的阅卷，提出了一种用正则表达式来分析程序代码，模拟人工阅卷的方法。介绍了此方法的原理和主要功能，给出了方法实现的具体步骤，对方法的关键部分如Java处理正则表达式的各个类以及方法的具体实施等都进行了详细的解释并举例进行了说明。其核心思想是利用正则表达式来抽象标准答案，再利用正则表达式强大的文本匹配功能来进行程序代码的分析，把不变的文本转化为具有一般性的表达式，大幅度增加了匹配的灵活性，从而达到简化阅卷的目的。     

正则表达式在编程题自动阅卷中的应用

分析了编程题的自动阅卷的现状及存在的不足。为了让计算机能够更加合理和有效地进行编程题的阅卷,提出了一种用正则表达式来分析程序代码,模拟人工阅卷的方法。介绍了此方法的原理和主要功能,给出了方法实现的具体步骤,对方法的关键部分如Java处理正则表达式的各个类以及方法的具体实施等都进行了详细的解释并举例进行了说明。其核心思想是利用正则表达式来抽象标准答案,再利用正则表达式强大的文本匹配功能来进行程序代码的分析,把不变的文本转化为具有一般性的表达式,大幅度增加了匹配的灵活性,从而达到简化阅卷的目的。     

Searching and encoding for infinite ordered sets

We consider the relationships between binary search algorithms and binary prefix encodings of infinite linearly ordered sets. It is known that each search algorithm determines a prefix code, and in three cases we show to what extent the converse is true. For sets similar to the natural numbers we show that search-related codes are as flexible as all prefix codes, while for general ordered sets they are only asymptotically as flexible.Research partially supported by a fellowship from the State University of New York University Awards Committee.     

Multicomponent codes with maximum code distance

We consider subspace codes, called multicomponent codes with zero prefix (MZP codes), whose subspace code distance is twice their dimension. We find values of parameters for which the codes are of the maximum cardinality. We construct combined codes where the last component of the multicomponent code is the code from [1] found by exhaustive search for particular parameter values. As a result, we obtain a family of subspace codes with maximum cardinality for a number of parameters. We show that the family of maximum-cardinality codes can be extended by using dual codes.     

Bounds on the Cardinality of Subspace Codes with Non-maximum Code Distance

We study subspace codes with nonmaximum code distance. As opposed to spreads, i.e., codes with the maximum subspace distance, we refer to them as nonspreads here. We consider families of nonspreads based on using the Silva–Kötter–Kschischang (SKK) subspace code construction and Gabidulin–Bossert multicomponent codes with zero prefix (MZP). We give estimates for cardinalities of nonspreads for a large number of parameters. We show that for large dimensions, the cardinalities almost attain the upper bound given by the Johnson inequality.

     

低密度校验码在瑞利衰落信道中的性能分析

低密度校验（LDPC）码具有编码增益高，译码速度快，可并行译码等特点，是当前编码界的一个研究热点，但是目前已有的研究成果都集中在高斯信道上，该文分析和讨论了LDPC码在瑞利衰落信道下的性能，应用联合界技术推导了一个规则友的性能限，并给同了仿真结果，且发现LDPC码在瑞利衰落信道下也具有非常好的性能。     

一种高效匹配PCRE的扩展自动机

分析现有方法处理状态爆炸的局限性,将条件函数和位图结构引入自动机,提出一种位图移位有限自动机(Bs-FA),并给出由正则表达式到Bs-FA的一般方法。对计数字符组与前缀交迭的情况,仅需引入较小位图空间,就能使整个自动机内存空间明显减少。在实际规则集上评估,并与现有方法进行比较,说明该自动机的应用价值。     

右边正则纠删码中二部图的构造算法

通过深入研究右边正则度序列的分析性质,设计了右边正则纠删码度序列的参数优化算法.基于此算法,提出了右边正则纠删码设计中随机二部图的连边构造算法.数值结果证明了所给的度序列参数优化算法的有效性.仿真结果表明基于右边正则度序列的级联型纠删码的性能优于Tornado码.随机二部图的连边构造算法和度序列的参数优化算法有助于右边正则纠删码的设计及其工程应用.     

NIDS中正则表达式匹配电路的改进与优化

对网络入侵检测系统(NIDS)中复杂正则表达式匹配电路进行改进和优化。为达到最大吞吐量和最小的单位字符占用资源量,设计利用预译码、前缀树、规则分组、并行处理等方法进行结构优化。实验结果表明,改进后的电路结构提高了约47%匹配速度,缩减了约39%的电路面积,具有较低的资源占用和更广泛的适用性。     

Decoding prefix codes

Minimum‐redundancy prefix codes have been a mainstay of research and commercial compression systems since their discovery by David Huffman more than 50 years ago. In this experimental evaluation we compare techniques for decoding minimum‐redundancy codes, and quantify the relative benefits of recently developed restricted codes that are designed to accelerate the decoding process. We find that table‐based decoding techniques offer fast operation, provided that the size of the table is kept relatively small, and that approximate coding techniques can offer higher decoding rates than Huffman codes with varying degrees of loss of compression effectiveness. Copyright © 2006 John Wiley & Sons, Ltd.     

Regular prefix relations

We define a class ofn-ary relations on strings called the regular prefix relations, and give four alternative characterizations of this class:

1. the relations recognized by a new type of automaton, the prefix automata,
2. the relations recognized by tree automata specialized to relations on strings,
3. the relations between strings definable in the second order theory ofk successors,
4. the smallest class containing the regular sets and the prefix relation, and closed under the Boolean operations, Cartesian product, projection, explicit transformation, and concatenation with Cartesian products of regular sets.

We give concrete examples of regular prefix relations, and a pumping argument for prefix automata. An application of these results to the study of inductive inference of regular sets is described.     

MPEG-4变长解码器设计及VLSI实现

变长编码（Variable Length Codes，简称VLCs）由于其较强的数据压缩能力而被广泛应用在多媒体数据压缩领域，变长编码又分为传统的前缀码和具有错误恢复能力的可逆变长编码（Reversible Variable Length Codes，简称RVLCs）．传统VLCs的自身性质使它对信道错误的恢复能力很弱，RVLCs解码遇到传输错误时，充分利用了可用的数据．错误恢复能力强于VLCs．本文详细描述了传统VLCs和RVLCs解码器的解码算法和解码器的体系结构设计，最后，给出了一个基于MPEG-4 ASP@L5的变长解码嚣VLSI实现，结果表明，该实现完全适用于MPEG-4实时编解码系统．     

d-Words and d-languages

Let X be a finite alphabet containing more than one letter. A d-primitive word u overX is a non-overlapping word in the sense that no proper prefix of u is a suffix of u. D(1) is the set of all d-primitive words over X and D is the set of all positive powers of all words in D (1). Every language in D will be called a d-language. In this paper, we study some algebraic properties of d-primitive words and d-languages relative to formal language theory and codes. We show that there are infinitely many cyclic-square-free words over alphabet with three letters. A characterization of three elements codes in D (1) is obtained and we prove that every regular component in D (1) is either a prefix code or a suffix code. Received: 22 September 1997 / 7 January 1998     

On new completely regular <Emphasis Type="Italic">q</Emphasis>-ary codes

In this paper, new completely regular q-ary codes are constructed from q-ary perfect codes. In particular, several new ternary completely regular codes are obtained from the ternary [11, 6, 5] Golay code. One of these codes with parameters [11, 5, 6] has covering radius ρ = 5 and intersection array (22, 20, 18, 2, 1; 1, 2, 9, 20, 22). This code is dual to the ternary perfect [11, 6, 5] Golay code. Another [10, 5, 5] code has covering radius ρ = 4 and intersection array (20, 18, 4, 1; 1, 2, 18, 20). This code is obtained by deleting one position of the former code. All together, the ternary Golay code results in eight completely regular codes, only four of which were previously known. Also, new infinite families of completely regular codes are constructed from q-ary Hamming codes.     

Regular Model Checking Using Inference of Regular Languages

Regular model checking is a method for verifying infinite-state systems based on coding their configurations as words over a finite alphabet, sets of configurations as finite automata, and transitions as finite transducers. We introduce a new general approach to regular model checking based on inference of regular languages. The method builds upon the observation that for infinite-state systems whose behaviour can be modelled using length-preserving transducers, there is a finite computation for obtaining all reachable configurations up to a certain length n. These configurations are a (positive) sample of the reachable configurations of the given system, whereas all other words up to length n are a negative sample. Then, methods of inference of regular languages can be used to generalize the sample to the full reachability set (or an overapproximation of it). We have implemented our method in a prototype tool which shows that our approach is competitive on a number of concrete examples. Furthermore, in contrast to all other existing regular model checking methods, termination is guaranteed in general for all systems with regular sets of reachable configurations. The method can be applied in a similar way to dealing with reachability relations instead of reachability sets too.