Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/51029
Title: Deciding context equivalence of binary overlap-free words in linear time
Authors: Shur, Arseny M.
Issue Date: 2012
Citation: 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.
Abstract: 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.
Keywords: CONTEXT EQUIVALENCE
OVERLAP-FREE WORDS
SYNTACTIC MONOID
WORD PROBLEM
URI: http://hdl.handle.net/10995/51029
https://elar.urfu.ru/handle/10995/51029
Access: info:eu-repo/semantics/restrictedAccess
SCOPUS ID: 84860997403
WOS ID: 000306590200003
PURE ID: 1081855
ISSN: 0037-1912
DOI: 10.1007/s00233-012-9382-6
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
10.1007s00233-012-9382-6_2012.pdf798,93 kBAdobe PDFView/Open


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