Когда клинская звезда конечного языка свободна?

Question

Я ищу ссылки, которые дают алгоритм для решения этой проблемы:

Задача: для заданного конечного алфавита Σ и конечного языка L ⊆ Σ^* определить, является ли L^* свободным моноидом.

Эквивалентно, проблема состоит в том, чтобы определить, учитывая конечный набор строк, является ли каждая конкатенация этих строк однозначно разложимой, используя те же строки. Например, любой язык, строки которого имеют одинаковый размер, будет удовлетворять этому условию, как и язык L = {a, ba}, но язык L = {ab, ba, aba} не удовлетворяет условию, поскольку строка ababa может быть разложен как ababa или же ababa,

Answer 1

Эта проблема эквивалентно сформулирована следующим образом: когда L является кодом над Σ?

Стандартным алгоритмом для определения этого является алгоритм Сардинаса-Паттерсона, опубликованный в 1953 году.

В рецензии на книгу Юхани Кархумяки (Бюллетень AMS, том 17, № 1, с. 161-167, 1987) обсуждается теория кодов Берстеля и Перрена ("Чистая и прикладная математика", том 117, Academic). Press, NY, 1985.)