Համահեղինակ(ներ):

Minasyan Vahagn

Ամփոփում:

The Longest Common Subsequence (LCS) problem is aimed at constructing a maximum length subsequence, common to a given set of sequences, defined on some finite alphabet of symbols. The paper, without loss of generality considers the particular case of two input sequences. We consider the problem in an online fashion, where symbols arrive one-byone and the next acquired symbol is appending any one of the two input sequences. The sought-for LCS algorithm acts by recursive handling of parts of sequences arrival so far, constructing and updating specific structures of markers representing the interrelations of the longest common subsequences of the two input sequences. In paper we present a perfect online parallelization of that algorithm for the “simple” memory model, so that the parallel complexity becomes O �� � for � parallel threads.

Նույնականացուցիչ:

oai:noad.sci.am:135796

Լեզու:

English

URL:

Կազմակերպության անվանում:

Institute for Informatics and Automation Problems

Երկիր:

Armenia

Տարի:

2017

Ժամանակահատված:

September25-29

Գիտաժողովի անվանում:

11th International Conference on Computer Science and Information Technologies CSIT 2017

Վայր:

Yerevan

Մասնակցության տեսակը:

oral