Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/51029
Full metadata record
DC FieldValueLanguage
dc.contributor.authorShur, Arseny M.en
dc.date.accessioned2017-09-04T14:45:09Z-
dc.date.available2017-09-04T14:45:09Z-
dc.date.issued2012-
dc.identifier.citationShur 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.en
dc.identifier.issn0037-1912-
dc.identifier.other1good_DOI
dc.identifier.other12d49118-edd6-4efc-bc7d-25db2e9c83bcpure_uuid
dc.identifier.otherhttp://www.scopus.com/inward/record.url?partnerID=8YFLogxK&scp=84860997403m
dc.identifier.urihttp://hdl.handle.net/10995/51029-
dc.identifier.urihttps://elar.urfu.ru/handle/10995/51029en
dc.description.abstractWe 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.en
dc.format.mimetypeapplication/pdfen
dc.language.isoenen
dc.rightsinfo:eu-repo/semantics/restrictedAccessen
dc.sourceSemigroup Forumen
dc.subjectCONTEXT EQUIVALENCEen
dc.subjectOVERLAP-FREE WORDSen
dc.subjectSYNTACTIC MONOIDen
dc.subjectWORD PROBLEMen
dc.titleDeciding context equivalence of binary overlap-free words in linear timeen
dc.typeArticleen
dc.typeinfo:eu-repo/semantics/publishedVersionen
dc.typeinfo:eu-repo/semantics/articleen
dc.identifier.doi10.1007/s00233-012-9382-6-
dc.identifier.scopus84860997403-
local.contributor.employeeШур Арсений Михайловичru
local.description.firstpage447-
local.description.lastpage471-
local.issue3-
local.volume84-
dc.identifier.wos000306590200003-
local.contributor.departmentИнститут естественных наук и математикиru
local.identifier.pure1081855-
local.identifier.eid2-s2.0-84860997403-
local.identifier.wosWOS:000306590200003-
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.