Applying A Normalized Compression Metric To The Measurement Of Dialect Distance

The paper discusses the application of a similarity metric based on compression to the measurement of the distance among Bulgarian dia- lects. The similarity metric is de ned on the basis of the notion of Kolmo- gorov complexity of a le (or binary string). The application of Kolmogorov complexity in practice is not possible because its calculation over a le is an undecidable problem. Thus, the actual similarity metric is based on a real life compressor which only approximates the Kolmogorov complexity. To use the metric for distance measurement of Bulgarian dialects we rst represent the dialectological data in such a way that the metric is applicable. We propose two such representations which are compared to a baseline distance between dialects. Then we conclude the paper with an outline of our future work.

An Improvement to the Achievement of the Griesmer Bound

We denoted by nq(k, d), the smallest value of n for which an [n, k, d]q code exists for given q, k, d. Since nq(k, d) = gq(k, d) for all d ≥ dk + 1 for q ≥ k ≥ 3, it is a natural question whether the Griesmer bound is attained or not for d = dk , where gq(k, d) = ∑[d/q^i], i=0,...,k-1, dk = (k − 2)q^(k−1) − (k − 1)q^(k−2). It was shown by Dodunekov [2] and Maruta [9], [10] that there is no [gq(k, dk ), k, dk ]q code for q ≥ k, k = 3, 4, 5 and for q ≥ 2k − 3, k ≥ 6. The purpose of this paper is to determine nq(k, d) for d = dk as nq(k, d) = gq(k, d) + 1 for q ≥ k with 3 ≤ k ≤ 8 except for (k, q) = (7, 7), (8, 8), (8, 9).