Separating words problem

From Wiki @ Karl Jones dot com
Revision as of 16:33, 26 August 2016 by Karl Jones (Talk | contribs) (Created page with "In theoretical computer science, the '''separating words problem''' is the problem of finding the smallest deterministic finite automaton that behaves differently on t...")

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

In theoretical computer science, the separating words problem is the problem of finding the smallest deterministic finite automaton that behaves differently on two given strings, meaning that it accepts one of the two strings and rejects the other string.

It is an open problem how large such an automaton must be; in the worst case, as a function of the length of the input strings.

See also

External links