Computing longest (common) Lyndon subsequences

DOI10.1007/978-3-031-06678-8_10MaRDI QIDQ2169947zbMATH OpenOpenAlexFDO

Authors Hideo Bannai, Tomasz Kociumaka, Dominik Köppl, Simon J. Puglisi, Tomohiro I

Publication date 30 August 2022

Full work available at URL https://arxiv.org/abs/2201.06773

zbMATH Keywords

dynamic programmingLyndon wordsubsequence

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• A hardness result and new algorithm for the longest common palindromic subsequence problem
• Absent subsequences in words
• Algorithms for the Longest Common Subsequence Problem
• Computing a longest common almost-increasing subsequence of two sequences
• Computing a longest common palindromic subsequence
• Counting Lyndon factors
• Dynamic LCA Queries on Trees
• Factorizing words over an ordered alphabet
• Fast and longest rollercoasters
• Faster algorithms for computing longest common increasing subsequences
• Free differential calculus. IV: The quotient groups of the lower central series
• scientific article; zbMATH DE number 177536 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• Longest common rollercoasters
• Longest common subsequence in sublinear space
• Longest Increasing and Decreasing Subsequences
• Lowest common ancestors in trees and directed acyclic graphs
• On Burnside's Problem
• On the Representations of the Symmetric Group
• Permutations, matrices, and generalized Young tableaux
• Rollercoasters: Long Sequences without Short Runs
• String Processing and Information Retrieval
• The ``runs theorem
• The longest almost-increasing subsequence
• The longest commonly positioned increasing subsequences problem
• The String-to-String Correction Problem

Cited in

(7)

• Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence
• Computing the least common subsumer w.r.t. a background terminology
• Computing a Longest Common Palindromic Subsequence
• scientific article; zbMATH DE number 7651110 (Why is no real title available?)
• Computing longest Lyndon subsequences and longest common Lyndon subsequences
• Cyclic longest common subsequence
• Longest bordered and periodic subsequences

This page was built for publication: Computing longest (common) Lyndon subsequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2169947)