Zobrazeno 1 - 10
of 58
pro vyhledávání: '"94A45"'
Autor:
Dębowski, Łukasz
Motivated by problems of statistical language modeling, we consider probability measures on infinite sequences over two countable alphabets of a different cardinality, such as letters and words. We introduce an invertible mapping between such measure
Externí odkaz:
http://arxiv.org/abs/2409.13600
Autor:
Wang, Geyang, Wang, Qi
Non-overlapping codes are a set of codewords such that the prefix of each codeword is not a suffix of any codeword in the set, including itself. If the lengths of the codewords are variable, it is additionally required that every codeword is not cont
Externí odkaz:
http://arxiv.org/abs/2402.18896
Autor:
Shen, Alexander
This note provides a simplified exposition of the proof of hierarchical Kraft lemma proven by Barmpalias and Lewis-Pye and its consequences for the oracle use in the Ku\v{c}era--G\'acs theorem (saying that every sequence is Turing reducible to a rand
Externí odkaz:
http://arxiv.org/abs/2304.04852
Non-overlapping codes have been studied for almost 60 years. In such a code, no proper, non-empty prefix of any codeword is a suffix of any codeword. In this paper, we study codes in which overlaps of certain specified sizes are forbidden. We prove s
Externí odkaz:
http://arxiv.org/abs/2211.10309
Publikováno v:
ACM Transactions on Algorithms 18(1) (2022) 1-11
We present a simple $O(n^4)$-time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the same running time, but is significantly more complicated and is restricte
Externí odkaz:
http://arxiv.org/abs/2103.01084
Publikováno v:
Information and Computation 281 (2021)
Search trees are commonly used to implement access operations to a set of stored keys. If this set is static and the probabilities of membership queries are known in advance, then one can precompute an optimal search tree, namely one that minimizes t
Externí odkaz:
http://arxiv.org/abs/2103.01052
Autor:
Matsumoto, Kengo
We introduce a notion of coded equivalence in one-sided topological Markov shifts. The notion is inspired by coding theory. One-sided topological conjugacy implies coded equivalence. We will show that coded equivalence implies continuous orbit equiva
Externí odkaz:
http://arxiv.org/abs/2011.13589
Autor:
Childers, L., Gopalakrishnan, K.
Gopala-Hemachandra codes are a variation of the Fibonacci universal code and have applications in cryptography and data compression. We show that $GH_{a}(n)$ codes always exist for $a=-2,-3$ and $-4$ for any integer $n \geq 1$ and hence are universal
Externí odkaz:
http://arxiv.org/abs/2004.00821
Autor:
Alderson, Tim L.
Publikováno v:
IEEE Trans. Inform. Theory 66 (2020), no. 9, 5414-5418
The weight spectra of MDS codes of length $ n $ and dimension $ k $ over the arbitrary alphabets are studied. For all $ q $-ary MDS codes of dimension $ k $ containing the zero codeword, it is shown that all $ k $ weights from $ n $ to $ n-k+1 $ are
Externí odkaz:
http://arxiv.org/abs/1910.05634
Publikováno v:
Acta Informatica (2022)
Huang and Wong [1984] proposed a polynomial-time dynamic-programming algorithm for computing optimal generalized binary split trees. We show that their algorithm is incorrect. Thus, it remains open whether such trees can be computed in polynomial tim
Externí odkaz:
http://arxiv.org/abs/1901.03783