{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R481",
  "content_hash": null,
  "slug": "lyndon8-attempt-fkm-literature-audit",
  "type": "attempt",
  "title": "The FKM construction addresses a larger target family",
  "summary": "The classic Lyndon concatenation theorem gives a de Bruijn cycle containing every eight-bit word, while the present target contains one representative from each primitive necklace.",
  "relevance": "For Shortest superstring of the binary Lyndon words of length eight, record lyndon8-attempt-fkm-literature-audit (“The FKM construction addresses a larger target family”) documents a concrete method, search boundary, or failed route. The record states: The classic Lyndon concatenation theorem gives a de Bruijn cycle containing every eight-bit word, while the present target contains one representative from each primitive necklace.",
  "relevance_source": "recorded",
  "body": "Fredricksen and Maiorana prove that concatenating, in lexicographic order, the Lyndon words whose lengths divide \\(n\\) produces a de Bruijn sequence of order \\(n\\). At \\(n=8\\), the construction uses Lyndon words of lengths 1, 2, 4, and 8 and covers all 256 binary words of length eight around a cycle.\n\nThe present problem asks for a linear word covering only the 30 length-eight Lyndon representatives. Removing the shorter factors from the FKM concatenation does not preserve the theorem's boundary windows, so the construction supplies context and a loose upper bound rather than an exact answer here.\n\nThe overlap formulation is standard: for equal-length targets with no containment, an ordering of their occurrences gives a Hamilton path whose arc weight is the longest suffix-prefix overlap. Mucha's shortest-superstring paper uses this reduction to maximum asymmetric traveling-salesperson path. The exact finite computation recorded here instead uses the equivalent order-seven de Bruijn-edge view to expose the 11 required paths.",
  "status": "completed",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "bounded",
    "statement": "the Fredricksen-Maiorana Lyndon concatenation theorem, its de Bruijn target at order 8, and the standard shortest-superstring overlap reduction",
    "bounds": {
      "publication_year": {
        "min": 1978,
        "max": 2013
      },
      "de_bruijn_order": {
        "min": 8,
        "max": 8
      }
    },
    "exhaustive": false
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "attempt",
    "citation": {
      "url": "https://doi.org/10.1016/0012-365X(78)90002-X",
      "locator": "Harold Fredricksen and James Maiorana, Necklaces of beads in k colors and k-ary de Bruijn sequences, Discrete Mathematics 23 (1978), 207-210; Marcin Mucha, Lyndon Words and Short Superstrings, Proceedings of SODA 2013, arXiv:1205.6787"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1016/0012-365X(78)90002-X",
    "locator": "Harold Fredricksen and James Maiorana, Necklaces of beads in k colors and k-ary de Bruijn sequences, Discrete Mathematics 23 (1978), 207-210; Marcin Mucha, Lyndon Words and Short Superstrings, Proceedings of SODA 2013, arXiv:1205.6787"
  },
  "models": [],
  "relations": [
    {
      "slug": "R482",
      "title": "The certified interval is 49 to 94",
      "object_type": "claim",
      "relation": "informs",
      "direction": "outgoing"
    },
    {
      "slug": "length-eight-lyndon-superstring",
      "title": "length eight lyndon superstring",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}