Factorizing words over an ordered alphabet
From MaRDI portal
Publication:3315005
DOI10.1016/0196-6774(83)90017-2zbMath0532.68061OpenAlexW2073103034WikidataQ55951224 ScholiaQ55951224MaRDI QIDQ3315005
Publication date: 1983
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(83)90017-2
Related Items
Parallel RAM algorithms for factorizing words, Efficient operations on discrete paths, On maximal suffixes and constant-space linear-time versions of KMP algorithm., New results on Nyldon words and Nyldon-like sets, Extended suffix array construction using Lyndon factors, An efficient shift rule for the prefer-max de Bruijn sequence, Indeterminate string factorizations and degenerate text transformations, Average cost of Duval's algorithm for generating Lyndon words, Finding the leftmost critical factorization on unordered alphabet, Lyndon + Christoffel = digitally convex, Computing minimal and maximal suffixes of a substring, Factorizing strings into repetitions, Words over an ordered alphabet and suffix permutations, A formula for the determinant of a sum of matrices, A characterization of binary morphisms generating Lyndon infinite words, Inside the binary reflected gray code: flip-swap languages in 2-gray code order, Viennot factorization of infinite words, Functional relations for elliptic polylogarithms, \(V\)-order: new combinatorial properties \& a simple comparison algorithm, Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence, Lyndon heaps: An analogue of Lyndon words in free partially commutative monoids, The zooming method: A recursive approach to time-space efficient string-matching, Practical algorithms to rank necklaces, Lyndon words, and de Bruijn sequences, Can formal languages help pangenomics to represent and analyze multiple genomes?, A toolkit for Parikh matrices, Counting Lyndon factors, Inferring strings from Lyndon factorization, Computing longest (common) Lyndon subsequences, Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée. (Generation of a section of conjugation classes and trees of Lyndon words of bounded length), Simple real-time constant-space string matching, A linear partitioning algorithm for hybrid Lyndons using \(V\)-order, A Gray code for fixed-density necklaces and Lyndon words in constant amortized time, Linear construction of a left Lyndon tree, Lyndon words and Fibonacci numbers, Linear computation of unbordered conjugate on unordered alphabet, A note on a simple computation of the maximal suffix of a string, Flip-swap languages in binary reflected Gray code order, Convexity preserving deformations of digital sets: characterization of removable and insertable pixels, A Pascal-like bound for the number of necklaces with fixed density, Suffix array and Lyndon factorization of a text, On generalized Lyndon words, Fast parallel Lyndon factorization with applications, The “Runs” Theorem, Reconstructing a string from its Lyndon arrays, A survey of string orderings and their application to the Burrows-Wheeler transform, Finding the maximum suffix with fewer comparisons, Towards optimal packed string matching, PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS, Enhanced string factoring from alphabet orderings, A fast average case algorithm for lyndon decomposition, A bijective variant of the Burrows-Wheeler transform using \(V\)-order, A public key cryptosystem based on Lyndon words, Lyndon words, permutations and trees., Geometric preservation of 2D digital objects under rigid motions, UNAVOIDABLE SETS OF CONSTANT LENGTH, Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Optimal canonization of all substrings of a string, Combinatorics of Hall trees and Hall words, String-matching on ordered alphabets, Optimal algorithms for computing the canonical form of a circular string, Binary block order Rouen transform, Faster Lyndon factorization algorithms for SLP and LZ78 compressed text, String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time, Simple Real-Time Constant-Space String Matching, Optimal parallel detection of squares in strings, Generic Algorithms for Factoring Strings, Efficient detection of quasiperiodicities in strings, Time versus space trade-offs for rendezvous in trees, On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties, Lyndon trees, Lyndon factorization algorithms for small alphabets and run-length encoded strings, Efficient CRCW-PRAM algorithms for universal substring searching, Quasi-Monotonic Sequences: Theory, Algorithms and Applications, The standard factorization of Lyndon words: an average point of view, Unnamed Item, An efficient generalized shift-rule for the prefer-max de Bruijn sequence, A simple shift rule for \(k\)-ary de Bruijn sequences, Indexing Circular Patterns, Inverse Lyndon words and inverse Lyndon factorizations of words, Combinatorial View of Digital Convexity, The alternating BWT: an algorithmic perspective, Indexing the bijective BWT, Can we replace reads by numeric signatures? Lyndon fingerprints as representations of sequencing reads for machine learning, Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence, Two linear-time algorithms for computing the minimum length polygon of a digital contour, Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour, Nyldon words, Lyndon-like and V-order factorizations of strings, On the size of the smallest alphabet for Lyndon trees, Lyndon words and singular factors of sturmian words, Further steps on the reconstruction of convex polyominoes from orthogonal projections, SORTING CONJUGATES AND SUFFIXES OF WORDS IN A MULTISET, Elastic-Degenerate String Matching via Fast Matrix Multiplication, Almost linear time computation of maximal repetitions in run length encoded strings, Complete dynamical evaluation of the characteristic polynomial of binary quantum graphs, Longest Lyndon Substring After Edit, Lyndon factorization of grammar compressed texts revisited, Studies on finite Sturmian words, Infinite Lyndon words, Finding the cyclic covers of a string, Lyndon partial words and arrays with applications, String rearrangement inequalities and a total order between primitive words, Computing longest Lyndon subsequences and longest common Lyndon subsequences, Quantum algorithm for lexicographically minimal string rotation, Algorithms for pixelwise shape deformations preserving digital convexity, On the optimisation of the GSACA suffix array construction algorithm, Near-optimal quantum algorithms for string problems, Numeric Lyndon-based feature embedding of sequencing reads for machine learning approaches, Constructing and indexing the bijective and extended Burrows-Wheeler transform
