Complexity of Dependences in Bounded Domains, Armstrong Codes, and Generalizations

DOI10.1109/TIT.2014.2377735MaRDI QIDQ2978769zbMATH OpenOpenAlexFDO

Authors Yeow Meng Chee, Hui Zhang, Xian De Zhang

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.06070

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Combinatorial codes (94B25)

Abstract: The study of Armstrong codes is motivated by the problem of understanding complexities of dependencies in relational database systems, where attributes have bounded domains. A $(q,k,n)$-Armstrong code is a $q$-ary code of length $n$ with minimum Hamming distance $n-k+1$, and for any set of $k-1$ coordinates there exist two codewords that agree exactly there. Let $f(q,k)$ be the maximum $n$ for which such a code exists. In this paper, $f(q,3)=3q-1$ is determined for all $qgeq5$ with three possible exceptions. This disproves a conjecture of Sali. Further, we introduce generalized Armstrong codes for branching, or $(s,t)$-dependencies, construct several classes of optimal Armstrong codes and establish lower bounds for the maximum length $n$ in this more general setting.

Cited in

(1)

• Blum Static Complexity and Encoding Spaces

This page was built for publication: Complexity of Dependences in Bounded Domains, Armstrong Codes, and Generalizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978769)