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

DOI10.1109/TIT.2014.2377735zbMATH Open1359.94790arXiv1906.06070OpenAlexW2076092585MaRDI QIDQ2978769FDOQ2978769

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)

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.

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

Mathematics Subject Classification ID

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

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)