Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/111367
Название: | On Non-complete Sets and Restivo's Conjecture |
Авторы: | Gusev, V. V. Pribavkina, E. V. |
Дата публикации: | 2011 |
Издатель: | Springer Berlin Heidelberg |
Библиографическое описание: | Gusev V. V. On Non-complete Sets and Restivo's Conjecture / V. V. Gusev, E. V. Pribavkina. — DOI 10.21146/0042-8744-2020-7-104-112 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2011. — Vol. 6795 LNCS. — P. 239-250. |
Аннотация: | A finite set S of words over the alphabet ∑ is called non-complete if Fact(S*) ≠ ∑*. A word w ∈ ∑* \ Fact(S*) is said to be uncompletable. We present a series of non-complete sets S k whose minimal uncompletable words have length 5k 2-17k+13, where k ≥ 4 is the maximal length of words in S k . This is an infinite series of counterexamples to Restivo's conjecture, which states that any non-complete set possesses an uncompletable word of length at most 2k 2. © 2011 Springer-Verlag. |
Ключевые слова: | FINITE SET INFINITE SERIES COMPLETE SETS FINITE SET INFINITE SERIES COMPUTER SCIENCE COMPUTERS ARTIFICIAL INTELLIGENCE |
URI: | http://elar.urfu.ru/handle/10995/111367 |
Условия доступа: | info:eu-repo/semantics/openAccess |
Конференция/семинар: | 15th International Conference on Developments in Language Theory, DLT 2011 |
Дата конференции/семинара: | 19 July 2011 through 22 July 2011 |
Идентификатор SCOPUS: | 79960704311 |
Идентификатор PURE: | 38013502 |
ISSN: | 0302-9743 |
ISBN: | 9783642223204 |
DOI: | 10.21146/0042-8744-2020-7-104-112 |
Сведения о поддержке: | The authors acknowledge support from the Russian Foundation for Basic Research, grant 10-01-00524, and from the Federal Education Agency of Russia, grant 2.1.1/13995. |
Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
2-s2.0-79960704311.pdf | 177,29 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.