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 ...
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...
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...
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...
THE IMPACT OF CLOUD COMPUTING ON CONSTRUCTION PROJECT DELIVERY ABUJA NIGERIA
THE IMPACT OF CLOUD COMPUTING ON CONSTRUCTION PROJECT DELIVERY ABUJA NIGERIA
Cloud computing is the delivery of computing services, such as storage, processing power, and software applications, via the internet. Cloud computing offers various advantages and...
Nature Inspired Parallel Computing
Nature Inspired Parallel Computing
Parallel computing is more and more important for science and engineering, but it is not used so widely as serial computing. People are used to serial computing and feel parallel c...
On Computing
On Computing
A proposal that computing is not merely a form of engineering but a scientific domain on a par with the physical, life, and social sciences.
Computing is not simply ...
Lyndon Interpolation holds for the Prenex ⊃ Prenex Fragment of Gödel Logic
Lyndon Interpolation holds for the Prenex ⊃ Prenex Fragment of Gödel Logic
First-order interpolation properties are notoriously hard to determine, even for logics where propositional interpolation is more or less obvious. One of the most prominent example...