Separating words problem
id:
separating-words-problem-162-14993177
title:
Separating words problem
text:
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.
brand slug:
wiki
category slug:
encyclopedia
description:
Problem in theoretical computer science
original url:
https://en.wikipedia.org/wiki/Separating_words_problem
date created:
2015-12-29T00:30:26Z
date modified:
2024-08-28T01:37:49Z
main entity:
{"identifier":"Q25304554","url":"https://www.wikidata.org/entity/Q25304554"}
image:
fields total:
13
integrity:
15