PPL 155 / 177 permanent IDsPrize Problem Ledger · PPLChecked 2026.07.26
Prize Problem LedgerIndependentPPL 155Shallit #5 · Reversal gap for separating words

Permanent problem IDPPL 155

Source-statedIndependentconjecture

Formal languages

Shallit #5 · Reversal gap for separating words

Is the change in deterministic separating complexity between a pair of words and their reversals unbounded?

automata theorytheoretical computer scienceformal languages
01

The problem

Is the change in deterministic separating complexity between a pair of words and their reversals unbounded?

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

Reward offers

Offer 01£10Jeffrey 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.

03

Sources & reading