Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/51029
Название: | Deciding context equivalence of binary overlap-free words in linear time |
Авторы: | Shur, Arseny M. |
Дата публикации: | 2012 |
Библиографическое описание: | Shur A. M. Deciding context equivalence of binary overlap-free words in linear time / Arseny M. Shur // Semigroup Forum. — 2012. — Vol. 84. — № 3. — P. 447-471. |
Аннотация: | We study the structure of the language of binary overlap-free words, which is one of the classical objects in combinatorics of words and formal languages. In a natural way, this study requires a solution to the word problem for the syntactic monoid of the language. In this paper we present an algorithm that efficiently solves this word problem. Namely, the time complexity of the algorithm is linear in the total length of compared words. © 2012 Springer Science+Business Media, LLC. |
Ключевые слова: | CONTEXT EQUIVALENCE OVERLAP-FREE WORDS SYNTACTIC MONOID WORD PROBLEM |
URI: | http://elar.urfu.ru/handle/10995/51029 |
Условия доступа: | info:eu-repo/semantics/restrictedAccess |
Идентификатор SCOPUS: | 84860997403 |
Идентификатор WOS: | 000306590200003 |
Идентификатор PURE: | 1081855 |
ISSN: | 0037-1912 |
DOI: | 10.1007/s00233-012-9382-6 |
Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
10.1007s00233-012-9382-6_2012.pdf | 798,93 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.