Recuperando una LCS en O (n ^ 2 / w) tiempo y espacio

Vista sencilla de ítem
dc.contributor.authorIliopoulos, Costas S.spa
dc.contributor.authorPinzón Ardila, Yoanspa
dc.contributor.researchgroupGrupo de Investigación Tecnologías de Información - GTIspa
dc.contributor.researchgroupGrupo de Investigaciones Clínicasspa
dc.date.accessioned2020-10-27T00:21:31Z
dc.date.available2020-10-27T00:21:31Z
dc.date.issued2002-06-01
dc.description.abstractAquí utilizamos el paralelismo a nivel de palabra para recuperar una subsecuencia común más larga de dos cadenas de entrada, ambas de longitud n en O (n2 / w) & nbsp; tiempo y espacio, donde w es el número de bits en una palabra de máquina. Para el caso especial en el que una de las cadenas de entrada está cerca de w, su complejidad se reduce a tiempo y espacio lineales. Palabras clave: Subsecuencia común más larga, paralelismo de bits.spa
dc.description.abstractenglishHere we make use of word-level parallelism to recover a longest common subsequence of two input strings both of length n in O(n2/w)  time and space, where w is the number of bits in a machine word. For the special case where one of the input atrings is close to w its complexity is reduced to linear time and space.Keywords: Longest Common Subsequence, Bit-parallelism.eng
dc.format.mimetypeapplication/pdfspa
dc.identifier.instnameinstname:Universidad Autónoma de Bucaramanga UNABspa
dc.identifier.issn2539-2115
dc.identifier.issn1657-2831
dc.identifier.repourlrepourl:https://repository.unab.edu.co
dc.identifier.urihttp://hdl.handle.net/20.500.12749/9066
dc.language.isospaspa
dc.publisherUniversidad Autónoma de Bucaramanga UNAB
dc.relationhttps://revistas.unab.edu.co/index.php/rcc/article/view/1107/1079
dc.relation.referencesL. Allison and T.L. Dix, A bit-string longest common subsequence algorithm, Inform. Process. Lett., 23, 305-310, (1986).
dc.relation.urihttps://revistas.unab.edu.co/index.php/rcc/article/view/1107
dc.rightsDerechos de autor 2002 Revista Colombiana de Computación
dc.rights.accessrightsinfo:eu-repo/semantics/openAccessspa
dc.rights.creativecommonsAtribución-NoComercial-SinDerivadas 2.5 Colombia*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-sa/4.0/*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/2.5/co/
dc.sourceRevista Colombiana de Computación; Vol. 3 Núm. 1 (2002): Revista Colombiana de Computación; 41-51
dc.subject.keywordsLongest common subsequenceeng
dc.subject.keywordsBit-parallelismeng
dc.subject.keywordsSystem designeng
dc.subject.keywordsInvestigationeng
dc.subject.keywordsInformation technologyeng
dc.subject.keywordsInformation scienceseng
dc.subject.lembDiseño de sistemasspa
dc.subject.lembInvestigaciónspa
dc.subject.lembTecnología de la informaciónspa
dc.subject.lembCiencias de la informaciónspa
dc.subject.proposalSubsecuencia común más largaspa
dc.subject.proposalParalelismo de bitsspa
dc.titleRecuperando una LCS en O (n ^ 2 / w) tiempo y espacio
dc.title.translatedRecovering an LCS in O(n^2/w) time and space
dc.type.coarhttp://purl.org/coar/resource_type/c_7a1f
dc.type.driverinfo:eu-repo/semantics/article
dc.type.hasversioninfo:eu-repo/semantics/acceptedVersion
dc.type.localArtículospa
dc.type.redcolhttp://purl.org/redcol/resource_type/CJournalArticle

Archivos

Bloque original

Mostrando 1 - 1 de 1
Miniatura
Nombre:
2002_Recuperando_una_LCS.pdf
Tamaño:
612.31 KB
Formato:
Adobe Portable Document Format
Descripción:
Artículo
Descargar

Colecciones

Revista Colombiana de Computación
Grupo de Investigaciones Clínicas
Grupo de Investigación Tecnologías de Información - GTI