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

Question

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

Проблемы: Учитывая конечный алфавит Σ и конечный язык L & subseteq; Σ ^*, определить, является ли L ^* является свободным моноидом.

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

Answer 1

Эта проблема эквивалентно заявлена ​​как: когда есть L a код над Σ?

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

Существует интересное обсуждение в book review by Juhani Karhumäki (Бюллетень AMS, т. 17 нет. 1, стр. 161-167, 1987) Берстеля и Перрена Теория кодов (Чистая и прикладная математика, т. 117, Academic Press, NY, 1985.)