On non-complete sets and restivo's conjecture
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
On non-complete sets and restivo's conjecture
|
|
| Автор |
Gusev, V. V.
Pribavkina, E. V. |
|
| Тематика |
FINITE SET
INFINITE SERIES COMPLETE SETS FINITE SET INFINITE SERIES COMPUTER SCIENCE COMPUTERS ARTIFICIAL INTELLIGENCE |
|
| Описание |
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.
2.1.1/13995; Russian Foundation for Basic Research, RFBR: 10-01-00524 ★The authors acknowledge support from the Russian Foundation for Basic Re-search, grant 10-01-00524, and from the Federal Education Agency of Russia, grant 2.1.1/13995. |
|
| Дата |
2024-04-24T12:38:26Z
2024-04-24T12:38:26Z 2011 |
|
| Тип |
book-chapter
Other (info:eu-repo/semantics/other) info:eu-repo/submittedVersion |
|
| Идентификатор |
Gusev, V. V., & Pribavkina, E. V. (2011). On Non-complete Sets and Restivo’s Conjecture. In Lecture Notes in Computer Science. Developments in Language Theory (pp. 239–250). doi:10.1007/978-3-642-22321-1_21
978-3-64222320-4 0302-9743 Final All Open Access, Green https://arxiv.org/pdf/1104.0388.pdf http://elar.urfu.ru/handle/10995/132595 10.1007/978-3-642-22321-1_21 |
|
| Язык |
en
|
|
| Права |
Open access (info:eu-repo/semantics/openAccess)
|
|
| Формат |
application/pdf
|
|
| Издатель |
Springer Berlin Heidelberg
|
|
| Источник |
Lecture Notes in Computer Science
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|