Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 9 of 9 for “"Longest Common Subsequence"”.
-
On the probabilistic longest common subsequence problem for sequences of independent blocks
… of each other. Let Ln denote the length of the Longest Common Subsequence (LCS) of X and Y. In general the order of magnitude in n of VAR[Ln] is not known. So far, Matzinger and his collaborators had been able to prove that VAR[Ln] has order asymptotic n in few cases depending on the …
-
Longest Common Subsequence Over Constant-Sized Alphabets: Beating the Naive Approximation Ratio
… thesis investigates the approximability of the Longest Common Subsequence (LCS) problem. The fastest known algorithm for solving the LCS problem runs in essentially quadratic time in the length of the input, and it is known that under the Strong Exponential Time Hypothesis there can be no …
-
Identifying similar code fragments in Haskell
… algorithm (The Hungarian method) and the longest common subsequence algorithm. Munkres assignment algorithm helps to identify rearranged code fragments. The LCS algorithm is used to compare subtrees of different syntactic variants. Experiments showed that these algorithms can help better …
-
An efficient score alignment algorithm and its applications
… space with classic problems such as Longest Common Subsequence that have practical application in bioinformatic genomic sequencing and data comparison in revision control systems. In the field of musicology, score alignment and comparison is a problem with many similarities to string …
-
Optimal payoff to ensure opacity in Discrete-Event Systems
… approach, which relies on the solution to the longest common subsequence problem. This approach can lower the complexity of the solution at least for some cases (namely, systems with no loops). Secondly, we propose to add utilities for revealing transitions and provide algorithms that enforce …
-
Solving problems in P using correlated instances
… focus our attention on a number of problems: the Longest Common Subsequence (LCS), the minimum Edit Distance between sequences, and the Dynamic Time Warping Distance (DTWD) of curves, for which the best known algorithms achieve Ō(n² ) runtime via dynamic programming. These problems form an …
-
OPTIMAL SUBSEQUENCE BIJECTION AND CLASSIFICATION OF IMBALANCED DATA SETS
Time series are common in many research fields. Since both a query and a target sequence may be noisy, i.e., contain some outlier elements, it is desirable to exclude the outlier elements from matching in order to obtain a robust matching performance. Moreover, in many applications like shape …
-
Communication avoiding parallel algorithms for amorphous problems
Parallelizing large sized problem in parallel systems has always been a challenge for programmer. This difficulty is caused by the complexity of the existing systems as well as the target problems. This is becoming a greater issue as the data sizes are constantly growing and as a result, larger …