{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R819",
  "content_hash": null,
  "slug": "twnfa-claim-unary-one-way-tight-quadratic",
  "type": "claim",
  "title": "Unary one-way NFAs have a tight quadratic two-way determinization cost",
  "summary": "Every unary n-state 1NFA has an equivalent 2DFA with O(n^2) states, and some unary n-state 1NFAs require Omega(n^2) states in every equivalent 2DFA.",
  "relevance": "For Polynomial determinization of two-way finite automata, record twnfa-claim-unary-one-way-tight-quadratic (“Unary one-way NFAs have a tight quadratic two-way determinization cost”) records a bound, answer, status fact, or structural consequence. The record states: Every unary n-state 1NFA has an equivalent 2DFA with O(n^2) states, and some unary n-state 1NFAs require Omega(n^2) states in every equivalent 2DFA.",
  "relevance_source": "recorded",
  "body": "Chrobak proves both directions in Section 6. Theorem 6.2 converts any unary \\(n\\)-state 1NFA to a 2DFA with \\(O(n^2)\\) states by first placing the NFA in unary normal form, checking the bounded prefix, and using separate passes for the eventual cycles. Theorem 6.3 gives an \\(n\\)-state unary 1NFA family for which every equivalent 2DFA needs \\(\\Omega(n^2)\\) states.\n\nThis settles the tradeoff for one-way nondeterministic source automata over the singleton alphabet. Unary 2NFA determinization and the full fixed-alphabet 2NFA problem remain open. The 2003 erratum is recorded alongside the original article.",
  "status": "reported",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "family",
    "statement": "conversion of unary n-state one-way nondeterministic finite automata into equivalent two-way deterministic finite automata",
    "family": "unary 1NFAs"
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://doi.org/10.1016/0304-3975(86)90142-8",
      "locator": "Chrobak, Section 6, Theorems 6.2 and 6.3, pp. 156-157"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1016/0304-3975(86)90142-8",
    "locator": "Chrobak, Section 6, Theorems 6.2 and 6.3, pp. 156-157"
  },
  "models": [],
  "relations": [
    {
      "slug": "R815",
      "title": "The fixed-alphabet determinization question remains open",
      "object_type": "claim",
      "relation": "supports",
      "direction": "outgoing"
    },
    {
      "slug": "two-way-nfa-polynomial-determinization",
      "title": "two way nfa polynomial determinization",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}