Formal Computer Science / Languages & logic

Kenton Labs / Languages & logic

Formal languages

Characterize bounded membership in a recursively structured language while keeping the length bound visible.

The vocabulary.

These definitions state the objects and properties used by the dataset. The complete instance specification remains the authority for each result.

Dyck word
A balanced parenthesis string whose prefix balance never goes negative.
Prefix balance
Opening parentheses minus closing parentheses in an input prefix.
Membership
Whether a particular word belongs to the specified language.

How the dataset works.

Three deterministic instances define this family. Each includes its input model, a checked result, evidence, and an acceptance procedure. Download the complete dataset JSON ↘ or the area’s readable source ↘.

Acceptance procedure

  1. Generate every parenthesis string up to the stated length.
  2. Scan each prefix and reject any negative balance.
  3. Accept only strings with terminal balance zero.
  4. Compare the complete accepted-word list and its cardinality.

Cost and scope

A length bound n produces 2ⁿ⁺¹−1 candidate words; each membership scan takes O(n).

A common failure

Equal numbers of opening and closing symbols do not guarantee proper nesting.

Worked records.

Three instances expose concrete claims and the artifacts that establish or refute them. Expand a record for the problem, checker reasoning, formal payload, and verification metadata.

KL-FCS-031
Formal languagesBalanced words through length 4Complete bounded membership · 31 candidates

The problem

List every balanced parenthesis word of length at most 4, including the empty word.

The checked result

Accepted words: 4.

A prefix can invalidate a word before its final symbol. The accepted list includes different nesting structures and concatenations, not only fully nested strings.

Why the checker accepts it

  1. Generate every parenthesis string up to the stated length.
  2. Scan each prefix and reject any negative balance.
  3. Accept only strings with terminal balance zero.
  4. Compare the complete accepted-word list and its cardinality.

Formal specification

{
  "max_length": 4,
  "alphabet": [
    "(",
    ")"
  ],
  "language": "Every prefix has nonnegative balance and the terminal balance is zero."
}

Claim and evidence

{
  "claim": {
    "accepted_count": 4
  },
  "witness": {
    "words": [
      "",
      "()",
      "(())",
      "()()"
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 31 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

A length bound n produces 2ⁿ⁺¹−1 candidate words; each membership scan takes O(n).

This enumerates a bounded language slice; it is not a grammar-equivalence theorem.

A boundary to investigate

Equal numbers of opening and closing symbols do not guarantee proper nesting. Add context-free grammar membership, CYK charts, and parse-tree certificates.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-032 ↘Related KL-FCS-033 ↘
KL-FCS-032
Formal languagesBalanced words through length 6Complete bounded membership · 127 candidates

The problem

List every balanced parenthesis word of length at most 6, including the empty word.

The checked result

Accepted words: 9.

A prefix can invalidate a word before its final symbol. The accepted list includes different nesting structures and concatenations, not only fully nested strings.

Why the checker accepts it

  1. Generate every parenthesis string up to the stated length.
  2. Scan each prefix and reject any negative balance.
  3. Accept only strings with terminal balance zero.
  4. Compare the complete accepted-word list and its cardinality.

Formal specification

{
  "max_length": 6,
  "alphabet": [
    "(",
    ")"
  ],
  "language": "Every prefix has nonnegative balance and the terminal balance is zero."
}

Claim and evidence

{
  "claim": {
    "accepted_count": 9
  },
  "witness": {
    "words": [
      "",
      "()",
      "(())",
      "()()",
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 127 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

A length bound n produces 2ⁿ⁺¹−1 candidate words; each membership scan takes O(n).

This enumerates a bounded language slice; it is not a grammar-equivalence theorem.

A boundary to investigate

Equal numbers of opening and closing symbols do not guarantee proper nesting. Add context-free grammar membership, CYK charts, and parse-tree certificates.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-031 ↘Related KL-FCS-033 ↘
KL-FCS-033
Formal languagesBalanced words through length 8Complete bounded membership · 511 candidates

The problem

List every balanced parenthesis word of length at most 8, including the empty word.

The checked result

Accepted words: 23.

A prefix can invalidate a word before its final symbol. The accepted list includes different nesting structures and concatenations, not only fully nested strings.

Why the checker accepts it

  1. Generate every parenthesis string up to the stated length.
  2. Scan each prefix and reject any negative balance.
  3. Accept only strings with terminal balance zero.
  4. Compare the complete accepted-word list and its cardinality.

Formal specification

{
  "max_length": 8,
  "alphabet": [
    "(",
    ")"
  ],
  "language": "Every prefix has nonnegative balance and the terminal balance is zero."
}

Claim and evidence

{
  "claim": {
    "accepted_count": 23
  },
  "witness": {
    "words": [
      "",
      "()",
      "(())",
      "()()",
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()",
      "(((())))",
      "((()()))",
      "((())())",
      "((()))()",
      "(()(()))",
      "(()()())",
      "(()())()",
      "(())(())",
      "(())()()",
      "()((()))",
      "()(()())",
      "()(())()",
      "()()(())",
      "()()()()"
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 511 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

A length bound n produces 2ⁿ⁺¹−1 candidate words; each membership scan takes O(n).

This enumerates a bounded language slice; it is not a grammar-equivalence theorem.

A boundary to investigate

Equal numbers of opening and closing symbols do not guarantee proper nesting. Add context-free grammar membership, CYK charts, and parse-tree certificates.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-031 ↘Related KL-FCS-032 ↘

Go further.

Add context-free grammar membership, CYK charts, and parse-tree certificates.

Questions to investigate

  1. Equal numbers of opening and closing symbols do not guarantee proper nesting.
  2. Which assumption in the specification can be changed to make the current evidence insufficient?
  3. Add context-free grammar membership, CYK charts, and parse-tree certificates.

Conceptual references

These sources explain the surrounding theory. The linked material was not imported as a dataset, and these records do not claim checking by the source’s software.

Primary conceptual reference ↗

Related areas

AutomataProgramming-language semanticsType systemsSAT / SMTTerm rewriting