Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111367
Title: On Non-complete Sets and Restivo's Conjecture
Authors: Gusev, V. V.
Pribavkina, E. V.
Issue Date: 2011
Publisher: Springer Berlin Heidelberg
Citation: 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.
Abstract: 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.
Keywords: FINITE SET
INFINITE SERIES
COMPLETE SETS
FINITE SET
INFINITE SERIES
COMPUTER SCIENCE
COMPUTERS
ARTIFICIAL INTELLIGENCE
URI: http://hdl.handle.net/10995/111367
Access: info:eu-repo/semantics/openAccess
Conference name: 15th International Conference on Developments in Language Theory, DLT 2011
Conference date: 19 July 2011 through 22 July 2011
SCOPUS ID: 79960704311
ISSN: 0302-9743
ISBN: 9783642223204
DOI: 10.21146/0042-8744-2020-7-104-112
metadata.dc.description.sponsorship: 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.
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-79960704311.pdf177,29 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.