An algorithm for recognizing the completeness of a set of words and dynamics of prohibitions | Applied Discrete Mathematics. Supplement. 2016. № 9.

An algorithm for recognizing the completeness of a set of words and dynamics of prohibitions

Some reduction operations on a set of words are introduced. For recognizing the completeness of such sets, an algorithm using these operations is proposed. A theorem substantiating the algorithm is given.

Download file

Counter downloads: 234

Keywords

множество слов, полнота, динамика запретов, алгоритм 'распознавания, a set of words, completeness, dynamics, prohibitions, algorithm, recognition

Authors

Name	Organization	E-mail
Evdokimov A. A.	Institute of Mathematics	evdok@math.nsc.ru

Всего: 1

References

Евдокимов А. А., Крайнев В. А. Задачи о полноте систем слов // XXII Обл. науч.-технич. конф. Тезисы. Новосибирск, 1979. С. 105-107.

Евдокимов А. А. Полные множества слов и их числовые характеристики // Методы дискретного анализа в исследовании экстремальных структур: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1983. Вып. 39. С. 7-19.

Евдокимов А. А. Исследование полноты множеств слов и языков с запретами // Вестник Томского государственного университета. Приложение. 2004. №9(1). С. 8-12.

Evdokimov A. A. and Kitaev S. V. Crucial words and the complexity of some extremal problems for sets of prohibited words // J. Comb. Theory. Ser. A. 2004. V. 105. P. 273-289.

Berstel J. and Karhumaki J. Combinatorics on words - a tutorial // Bull. EATCS. 2003. V. 79. P. 178-229.