PPL 153 / 177 permanent IDsPrize Problem Ledger · PPLChecked 2026.07.26
Prize Problem LedgerPPL · Open reward indexAll 177 problems
Prize Problem LedgerIndependentPPL 153Shallit #3 · NFA separating-word bounds

Permanent problem IDPPL 153

Source-statedIndependentconjecture

Formal languages

Shallit #3 · NFA separating-word bounds

Find strong asymptotic bounds on the smallest nondeterministic finite automaton separating any two distinct words of length n.

automata theorytheoretical computer scienceformal languages
01

The problem

Find strong asymptotic bounds on the smallest nondeterministic finite automaton separating any two distinct words of length n.

Open since2014source-stated by 2014
Last checked2026.07.26Catalog verification
02

Reward offers

Offer 01£50Jeffrey Shallit
Personal offer

Personal cash offer stated in Shallit’s official talk. The live talks page records subsequent updates, including a paid solution to one omitted problem; confirm claim procedure with the sponsor before relying on the award.

Award source ↗Rules ↗
03

Sources & reading

2 unique reference linksSponsor’s official problem slides Claim or award rules
04

Related open targets

Formal languagesShallit #18 · Shortest forbidden factor boundsPPL 150 · £200 · 14 years openFormal languagesShallit #19 · Pierce expansion lengthPPL 151 · £200 · 12 years openFormal languagesShallit #7 · Are primitive binary words context-free?PPL 157 · £200 · 12 years open