Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences
View through CrossRef
AbstractGiven a string T of length n whose characters are drawn from an ordered alphabet of size $$\sigma $$
σ
, its longest Lyndon subsequence is a maximum-length subsequence of T that is a Lyndon word. We propose algorithms for finding such a subsequence in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^3)$$
O
(
n
3
)
time with $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n)$$
O
(
n
)
space, or online in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^3)$$
O
(
n
3
)
space and time. Our first result can be extended to find the longest common Lyndon subsequence of two strings of length at most n in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^4 \sigma )$$
O
(
n
4
σ
)
time using $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^2)$$
O
(
n
2
)
space.
Springer Science and Business Media LLC
Title: Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences
Description:
AbstractGiven a string T of length n whose characters are drawn from an ordered alphabet of size $$\sigma $$
σ
, its longest Lyndon subsequence is a maximum-length subsequence of T that is a Lyndon word.
We propose algorithms for finding such a subsequence in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^3)$$
O
(
n
3
)
time with $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n)$$
O
(
n
)
space, or online in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^3)$$
O
(
n
3
)
space and time.
Our first result can be extended to find the longest common Lyndon subsequence of two strings of length at most n in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^4 \sigma )$$
O
(
n
4
σ
)
time using $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^2)$$
O
(
n
2
)
space.
Related Results
Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences
Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences
Abstract
Given a string T with length n whose characters are drawn from an ordered alphabet of size σ, its longest Lyndon subsequence is a longest subsequence of T that is ...
Frequency of Common Chromosomal Abnormalities in Patients with Idiopathic Acquired Aplastic Anemia
Frequency of Common Chromosomal Abnormalities in Patients with Idiopathic Acquired Aplastic Anemia
Objective: To determine the frequency of common chromosomal aberrations in local population idiopathic determine the frequency of common chromosomal aberrations in local population...
Kinetics of folding of αα‐tropomyosin subsequences
Kinetics of folding of αα‐tropomyosin subsequences
AbstractThe kinetics of folding random coils of αα‐tropomyosin (Tm) subsequences to two‐chain coiled coils was studied by stopped‐flow CD. Subsequences studied were those comprisin...
Enhancing Graph-based Machine Learning through Lyndon Partial Words
Enhancing Graph-based Machine Learning through Lyndon Partial Words
Objectives: This study integrates the combinatorial properties of Lyndon partial words with Graph-Based Machine Learning (GBML) to develop an innovative approach for sequence analy...
CLOUD COMPUTING - NAVIGATING THE DIGITAL SKY
CLOUD COMPUTING - NAVIGATING THE DIGITAL SKY
“Cloud Computing – Navigating the Digital Sky” is an extensive guide designed to provide a thorough understanding of cloud computing, an essential technology in today’s digital age...
Advancements in Quantum Computing and Information Science
Advancements in Quantum Computing and Information Science
Abstract: The chapter "Advancements in Quantum Computing and Information Science" explores the fundamental principles, historical development, and modern applications of quantum co...
Structural stability of short subsequences of the tropomyosin chain
Structural stability of short subsequences of the tropomyosin chain
AbstractThe native tropomyosin molecule is a parallel, registered, α‐helical coiled coil made from two 284‐residiic chains. Long excised subsequences (≥ 95 residues) form the same ...
Lyndon Words and Christoffel Words
Lyndon Words and Christoffel Words
This chapter covers the lexicographical ordering of lower Christoffel words, which is equivalent to the ordering by their slopes (Borel and Laubie). Lower Christoffel words are par...