A combinatorial game is a two-player game without hidden information or chance elements. One of the major approaches to analyzing games in combinatorial game theory is to break down a given game position into a disjunctive sum of multiple sub-positions, then evaluate the game value of each component of the sum, and finally integrate these game values to find which player has a winning strategy in the whole position. Accordingly, finding the game value of a given position is a major topic in combinatorial game theory. The sequential compound proposed by Stromquist and Ullman is a combinatorial game consisting of two combinatorial games. In the sequential compound of games $G$ and $H$, the players make moves on $G$ until $G$ is over, and then they play on $H$. In this paper, we investigate the general properties of sequential compounds. As the main result, we give the game values of sequential compounds of a finite number of integers and stars, which are basic and typical games in combinatorial game theory.

The class of$k$-symbol delay decodable code-tuples is a set of noiseless source codes, which can achieve an average codeword length less than or equal to that of Huffman codes by utilizing a finite number of code tables and allowing a decoding delay of at most$k$coding symbols. This paper establishes a lower bound of the worst-case redundancy of$d$-ary$k$-symbol delay decodable code-tuples for$d \geq 2, k \geq 1$by proving a stronger theorem that provides a lower bound of the average codeword length.

Based on a study of ABS (Asymmetric Binary Systems), we introduce a new theorem related to Rayleigh's theorem. We also present an extension of ABS to finite source alphabets with probability distribution taking real numbers.

For an integer$k \geq 0$, k-bit delay decodable code-tuples are source codes that use a finite number of code tables and allow a decoding delay of at most k bits. It is known that the class of k-bit delay decodable code-tuples can achieve a better average codeword length than Huffman codes for$k \geq 2$. However, it is generally challenging to find an optimal k-bit delay decodable code-tuple (i.e., a k-bit delay decodable code-tuple achieving the optimal average codeword length among all k-bit delay decodable code-tuples) because the class of k-bit delay decodable code-tuples is a comprehensive and flexible class containing a variety of source code consisting of any finite number of code tables. AIFV (almost instantaneous fixed-to-variable length) codes are 2-bit delay decodable code-tuples consisting of two code tables satisfying certain constraints. This paper proves that the class of AIFV codes always contains an optimal 2-bit delay decodable code-tuple for any given source distribution. Thus, we can find an optimal 2-bit delay decodable code-tuple in the class of 2-bit delay decodable code-tuples by considering only the class of AIFV codes, which is a very restricted subclass compared to the whole class of 2-bit delay decodable code-tuples.

This paper considers noiseless source codes for the unequal cost of bits, a generalization of the cost measured by the codeword length of binary source codes. We generalize AIFV (Almost Instantaneous Fixed-to-Variable length) codes to the case of unequal bit costs taking positive integers.

Huffman code is the optimal code in the class of uniquely decodable codes in the sense of the average length of codeword when a single code tree can represent the code. This paper defines hierarchical subclasses of noiseless source codes by allowing$k$-bit decoding delay for positive integer$k$and clarifies a necessary and sufficient condition for the uniquely decodable codes with$k$-bit decoding delay. Furthermore, we show that AIFV code is the optimal code in the class of uniquely decodable codes with 2-bit decoding delay when two code trees represent the noiseless source code.

In the entropy coding, AIVF (almost instantaneous variable-to-fixed length) codes using multiple parsing trees can attain a better compression rate than the Tunstall code, which attains the best compression rate in the class of VF codes with a single parsing tree. Furthermore, the multiple parsing trees of an AIVF code can be multiplexed into a single parsing tree. In this paper, we propose a new universal data compression code based on the techniques of the AIVF code. The proposed universal code can also be considered as an improvement of the LZW code (Welch code). We explain how the AIVF coding techniques can be applied to universal coding by growing dynamically a single parsing tree, and we evaluate the compression rate of the proposed universal code theoretically and using several corpora.

We extend the concept of compact code trees, i.e., canonical code trees, of Huffman codes to the case of binary AIFV (almost instantaneous fixed-to-variable length) codes. We give an algorithm to enumerate the number of all compact AIFV code trees by using a bijection between the compact AIFV code trees and the proper sequences defined in this paper. Based on the enumeration of compact AIFV code trees, we give an efficient coding scheme to describe the compact AIFV code trees, which is required when we send a decoder the information of code trees used in the encoding of source sequences.