Geodesic
An algorithm for recognizing the completeness of a~set of words and dynamics of prohibitions
Prikladnaya Diskretnaya Matematika. Supplement, no. 9 (2016), pp. 10-12.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: a set of words, completeness, dynamics, prohibitions, algorithm, recognition. 
@article{PDMA_2016_9_a2,
     author = {A. A. Evdokimov},
     title = {An algorithm for recognizing the completeness of a~set of words and dynamics of prohibitions},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {10--12},
     publisher = {mathdoc},
     number = {9},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2016_9_a2/}
}
TY  - JOUR
AU  - A. A. Evdokimov
TI  - An algorithm for recognizing the completeness of a~set of words and dynamics of prohibitions
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2016
SP  - 10
EP  - 12
IS  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2016_9_a2/
LA  - ru
ID  - PDMA_2016_9_a2
ER  - 
%0 Journal Article
%A A. A. Evdokimov
%T An algorithm for recognizing the completeness of a~set of words and dynamics of prohibitions
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2016
%P 10-12
%N 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2016_9_a2/
%G ru
%F PDMA_2016_9_a2
A. A. Evdokimov. An algorithm for recognizing the completeness of a~set of words and dynamics of prohibitions. Prikladnaya Diskretnaya Matematika. Supplement, no. 9 (2016), pp. 10-12. http://geodesic.mathdoc.fr/item/PDMA_2016_9_a2/

[1] Evdokimov A. A., Krainev V. A., “Zadachi o polnote sistem slov”, XXII Obl. nauch.-tekhnich. konf., Tezisy, Novosibirsk, 1979, 105–107

[2] Evdokimov A. A., “Polnye mnozhestva slov i ikh chislovye kharakteristiki”, Metody diskretnogo analiza v issledovanii ekstremalnykh struktur. Sb. nauch. tr., 39, In-t matematiki SO AN SSSR, Novosibirsk, 1983, 7–19 | MR

[3] Evdokimov A. A., “Issledovanie polnoty mnozhestv slov i yazykov s zapretami”, Vestnik Tomskogo gosudarstvennogo universiteta. Prilozhenie, 2004, no. 9(1), 8–12

[4] Evdokimov A. A., Kitaev S. V., “Crucial words and the complexity of some extremal problems for sets of prohibited words”, J. Comb. Theory Ser. A, 105 (2004), 273–289 | DOI | MR | Zbl

[5] Berstel J., Karhumäki J., “Combinatorics on words – a tutorial”, Bull. EATCS, 79 (2003), 178–229 | MR