[#P2834] Logarithmic DFA separation of binary words

Problem. For distinct words \(x,y\in\{0,1\}^n\), let \(s(x,y)\) be the minimum number of states in a deterministic finite automaton that accepts exactly one of \(x,y\), and let \(S(n)=\max_{x\ne y}s(x,y)\). Is \(S(n)=O(\log n)\)?

Agent access

Work on this problem in ChatGPT

Definitions and notation

1Context

The problem asks how little finite memory suffices to distinguish two known inputs. Modular position counts and short pattern statistics can be stored as independent separators, while hard pairs record which entire classes of small automata fail.

2Problem setup

Definition 1 (A deterministic finite automaton has a finite state set, one start state, a set of accepting states, and one outgoing transition for each state and input symbol). A deterministic finite automaton has a finite state set, one start state, a set of accepting states, and one outgoing transition for each state and input symbol.

Definition 2 (An automaton separates \(x\) and \(y\) when it accepts one word and rejects the other). An automaton separates \(x\) and \(y\) when it accepts one word and rejects the other.

Definition 3 (The assertion \(S(n)=O(\log n)\). The assertion \(S(n)=O(\log n)\) means that an absolute constant \(C\) exists with \(S(n)\le C\log n\) for every sufficiently large \(n\).

Remark 1. The problem asks how little finite memory suffices to distinguish two known inputs. Modular position counts and short pattern statistics can be stored as independent separators, while hard pairs record which entire classes of small automata fail.

3What counts as a solution

Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded.

1Status

What counts as a solution

Current status (Current status and unresolved remainder). UNKNOWN as of 2026-07-31. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound. Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded.^[1]

1Packet records

Show recorded summaries

Record	Kind	Assessment
UNKNOWN as of 2026-07-31. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound. Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 UNKNOWN as of 2026-07-31. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound. Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded.^[1] Relevance to this problem For binary word logarithmic dfa separation, pins the dated research frontier: UNKNOWN as of 2026-07-31. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound. Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\). Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1 Details UNKNOWN as of 2026-07-31. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound. A complete resolution must satisfy this condition: Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded. Open full record →
Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded.	Trace	Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 1 Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded.^[1] Relevance to this problem For Logarithmic DFA separation of binary words, record binary-word-logarithmic-dfa-separation-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. Prove that \(s(x,y)\le C\log n\) for an absolute \(C\), every sufficiently large \(n\), and all distinct binary \(n\)-letter words, or give infinitely many pairs with \(s(x,y)/\log n\) unbounded. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion material

Original intake status. UNKNOWN as of 2026-07-31. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound.

2026-07-27 status search checked the 2011 separating-words survey, the 2020 bound, the March 2025 polylogarithmic improvement, and 2026 work on minimal DFA witnesses. No source checked settles \(S(n)=O(\log n)\).
The strongest neighboring result is the 2025 \(O(\log^2 n)\) construction, improving an earlier \(O(n^{1/3}\log^7 n)\) bound.
A reusable positive artifact should specify the distinguishing statistic and compile it into a DFA with an explicit state count. A lower-bound artifact should give hard word pairs and an equivalence relation respected by every smaller DFA.

Recorded example 1. For \(x=0\) and \(y=1\), a two-state DFA separates the words. For arbitrary \(x\ne y\) of length \(n\), a DFA recognizing the singleton language \(\{x\}\) gives the elementary bound \(s(x,y)\le n+2\).

How the 2 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemLogarithmic DFA separation of binary words

All 1 recorded relations between these records and the problem

Resolve the stated acceptance condition addresses Current status and unresolved remainder

2See also

Multiplicative complexity of the six-bit threshold-at-least-three functiontheoretical computer science
Polynomial determinization of two-way finite automatatheoretical computer science
Decidability of zeros in integer linear recurrence sequencestheoretical computer science

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Logarithmic DFA separation of binary words.” TheoremDB. P2834. Problem statement; statement text SHA-256 54056e901f1ba9bdce5db81b10cfa4494c34ee1e78e8b35aee9c09d42e35f234. https://theoremdb.org/statement/?ref=P2834

BibTeX

@misc{theoremdb-problem-54056e901f1ba9bdce5db81b10cfa4494c34ee1e78e8b35aee9c09d42e35f234,
  title = {{Logarithmic DFA separation of binary words}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 54056e901f1ba9bdce5db81b10cfa4494c34ee1e78e8b35aee9c09d42e35f234},
  url = {https://theoremdb.org/statement/?ref=P2834}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 1 typed links, sourced from arxiv.org^[1], current as of July 31, 2026.

1Lean verification

1References

Packet source. A Sharper Upper Bound for the Separating Words Problem, source checked for the TheoremDB status review (2026-07-31). The preprint proves the current polylogarithmic upper bound; the logarithmic target is the standard remaining separating-words question. This CC0 self-contained record was prepared on 2026-07-27. ↗preprint · primary source · arXiv:2503.23184, checked 2026-07-31 · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound.Also cited at See dataset.references[0] for the exact external source and locator.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.Source named by the research packet.
Zachary Chase, “A new upper bound for separating words”. arXiv:2007.12097 (2020). Status evidence identified in the source record and checked at the linked publication. ↗preprint · primary source · arXiv:2007.12097, checked 2026-07-31 · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound.Also cited at Full preprint relevant to Logarithmic DFA separation of binary words.Source used to assess the problem's recorded status.For Logarithmic DFA separation of binary words: UNKNOWN as of 2026-07-27. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound.
Erik D. Demaine, Sarah Eisenstat, Jeffrey Shallit, and David A. Wilson, “Remarks on separating words”. arXiv:1103.4513 (2011). Status evidence identified in the source record and checked at the linked publication. ↗preprint · primary source · arXiv:1103.4513, checked 2026-07-31 · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound.Also cited at Full preprint relevant to Logarithmic DFA separation of binary words.Source used to assess the problem's recorded status.For Logarithmic DFA separation of binary words: UNKNOWN as of 2026-07-27. A March 2025 primary preprint proves \(S(n)=O(\log^2 n)\). The checked primary literature and subsequent searches do not prove the logarithmic bound or a superlogarithmic lower bound.

Original CC0 record prose for the logarithmic separating-words problem.

[#P2834] Logarithmic DFA separation of binary words

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance