{
  "id": "1906.06070",
  "version": "v1",
  "published": "2019-06-14T08:16:19.000Z",
  "updated": "2019-06-14T08:16:19.000Z",
  "title": "Complexity of Dependencies in Bounded Domains, Armstrong Codes, and Generalizations",
  "authors": [
    "Yeow Meng Chee",
    "Hui Zhang",
    "Xiande Zhang"
  ],
  "journal": "IEEE Trans. Inform. Theory, Vol. 61, No 02, 2015, pp. 812--819",
  "categories": [
    "math.CO",
    "cs.IT",
    "math.IT"
  ],
  "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 $q\\geq 5$ 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-06-14T08:16:19.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bounded domains",
      "dependencies",
      "complexity",
      "generalizations",
      "relational database systems"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}