StringologyTimes

Stringology for Stringologist

Stringology 2021

  1. Towards an Efficient Text Sampling Approach for Exact and Approximate Matching.
  2. The n-ary Initial Literal and Literal Shuffle.
  3. Counting Lyndon Subsequences.
  4. Pitfalls of Algorithm Comparison.
  5. Refined Upper Bounds on the Size of the Condensed Neighbourhood of Sequences.
  6. Searching with Extended Guard and Pivot Loop.
  7. Automata Approach to Inexact Tree Pattern Matching Using 1-degree Edit Distance.
  8. Computational Substantiation of the d-step Conjecture for Distinct Squares Revisited.

Stringology 2020

  1. Reducing Time and Space in Indexed String Matching by Characters Distance Text Sampling.
  2. New Compression Schemes for Natural Number Sequences.
  3. Enumerative Data Compression with Non-Uniquely Decodable Codes.
  4. Conversion of Finite Tree Automata to Regular Tree Expressions By State Elimination.
  5. On Arithmetically Progressed Suffix Arrays.
  6. Greedy versus Optimal Analysis of Bounded Size Dictionary Compression and On-the-Fly Distributed Computing.
  7. Forward Linearised Tree Pattern Matching Using Tree Pattern Border Array.
  8. Fast Exact Pattern Matching in a Bitstream and 256-ary Strings.
  9. Left Lyndon Tree Construction.
  10. Fast Practical Computation of the Longest Common Cartesian Substrings of Two Strings.
  11. Tune-up for the Dead-Zone Algorithm.
  12. Simple KMP Pattern-Matching on Indeterminate Strings.
  13. Pointer-Machine Algorithms for Fully-Online Construction of Suffix Trees and DAWGs on Multiple Strings.
  14. Re-Pair in Small Space.

Stringology 2019

  1. Bidirectional Adaptive Compression.
  2. Translating Between Wavelet Tree and Wavelet Matrix Construction.
  3. Online Parameterized Dictionary Matching with One Gap.
  4. Computing Maximal Palindromes and Distinct Palindromes in a Trie.
  5. An Improvement of the Franek-Jennings-Smyth Pattern Matching Algorithm.
  6. Selective Dynamic Compression.
  7. Optimal Time and Space Construction of Suffix Arrays and LCP Arrays for Integer Alphabets.
  8. A Fast SIMD-Based Chunking Algorithm.
  9. Pattern Matching on Weighted Strings.
  10. k-Abelian Pattern Matching: Revisited, Corrected, and Extended.
  11. Algorithms to Compute the Lyndon Array Revisited.
  12. Lexicalized Syntactic Analysis by Restarting Automata.

Stringology 2018

  1. On Baier’s Sort of Maximal Lyndon Substrings.
  2. Three Strategies for the Dead-Zone String Matching Algorithm.
  3. Synchronizing Dynamic Huffman Codes.
  4. Constrained Approximate Subtree Matching by Finite Automata.
  5. A Faster V-order String Comparison Algorithm.
  6. Discovery of Regulatory Motifs in DNA.
  7. O(n log n)-time Text Compression by LZ-style Longest First Substitution.
  8. Fast and Simple Algorithms for Computing both LCSk and LCSk+.
  9. Right-to-left Online Construction of Parameterized Position Heaps.
  10. Fibonacci Based Compressed Suffix Array.
  11. Parameterized Dictionary Matching with One Gap.

Stringology 2017

  1. Dismantling DivSufSort.
  2. On Reverse Engineering the Lyndon Tree.
  3. Speeding Up String Matching by Weak Factor Recognition.
  4. Range Queries Using Huffman Wavelet Trees.
  5. Faster Batched Range Minimum Queries.
  6. Counting Mismatches with SIMD.
  7. A Lempel-Ziv-style Compression Method for Repetitive Texts.
  8. The Linear Equivalence of the Suffix Array and the Partially Sorted Lyndon Array.
  9. Trade-offs in Query and Target Indexing for the Selection of Candidates in Protein Homology Searches.
  10. A Family of Exact Pattern Matching Algorithms with Multiple Adjacent Search Windows.
  11. Regular Expressions with Backreferences Re-examined.
  12. Online Recognition of Dictionary with One Gap.
  13. Dynamic Succinct Data Structures and Compressed Random Access Memory.
  14. Many-MADFAct: Concurrently Constructing MADFAs.

Stringology 2016

  1. A Resource-frugal Probabilistic Dictionary and Applications in (Meta)Genomics.
  2. Jumbled Matching with SIMD.
  3. The String Matching Algorithms Research Tool.
  4. Interpreting the Subset Construction Using Finite Sublanguages.
  5. Using Human Computation in Dead-zone based 2D Pattern Matching.
  6. Generating All Minimal Petri Net Unsolvable Binary Words.
  7. Fast Full Permuted Pattern Matching Algorithms on Multi-track Strings.
  8. Accelerated Partial Decoding in Wavelet Trees.
  9. Algorithms to Compute the Lyndon Array.
  10. Forced Repetitions over Alphabet Lists.
  11. Computing All Approximate Enhanced Covers with the Hamming Distance.
  12. Computing Smallest and Largest Repetition Factorizations in O(n log n) Time.
  13. A Family of Data Compression Codes with Multiple Delimiters.
  14. Dynamic Index and LZ Factorization in Compressed Space.
  15. The Use and Usefulness of Fibonacci Codes.

Stringology 2015

  1. Computing Left-Right Maximal Generic Words.
  2. A Formal Framework for Stringology.
  3. Enhanced Extraction from Huffman Encoded Files.
  4. Efficient Algorithm for δ-Approximate Jumbled Pattern Matching.
  5. Refined Tagging of Complex Verbal Phrases for the Italian Language.
  6. Combinatorics of the Interrupted Period.
  7. Alternative Algorithms for Order-Preserving Matching.
  8. Controlling the Chunk-Size in Deduplication Systems.
  9. Parameterized Matching: Solutions and Extensions.
  10. Tuning Algorithms for Jumbled Matching.
  11. A Faster Longest Common Extension Algorithm on Compressed Strings and its Applications.
  12. An Efficient Skip-Search Approach to the Order-Preserving Pattern Matching Problem.
  13. Quantum Leap Pattern Matching.

Stringology 2014

  1. Closed Factorization.
  2. A Process-Oriented Implementation of Brzozowski’s DFA Construction Algorithm.
  3. New Tabulation and Sparse Dynamic Programming Based Techniques for Sequence Similarity Problems.
  4. Multiple Pattern Matching Revisited.
  5. Alternative Algorithms for Lyndon Factorization.
  6. Two Squares Canonical Factorization.
  7. Speeding up Compressed Matching with SBNDM2.
  8. Approximation of Greedy Algorithms for Max-ATSP, Maximal Compression, Maximal Cycle Cover, and Shortest Cyclic Cover of Strings.
  9. Fast Regular Expression Matching Based On Dual Glushkov NFA.
  10. Metric Preserving Dense SIFT Compression.
  11. Two Simple Full-Text Indexes Based on the Suffix Array.
  12. On the Number of Distinct Squares.
  13. Computing Abelian Covers and Abelian Runs.
  14. Threshold Approximate Matching in Grammar-Compressed Strings.
  15. Improved Two-Way Bit-parallel Search.
  16. Using Correctness-by-Construction to Derive Dead-zone Algorithms.
  17. Random Access to Fibonacci Codes.
  18. Efficient Online Abelian Pattern Matching in Strings by Simulating Reactive Multi-Automata.
  19. Reducing Squares in Suffix Arrays.

Stringology 2013

  1. Maximal Palindromic Factorization.
  2. Optimal Partitioning of Data Chunks in Deduplication Systems.
  3. Graphs and Automata.
  4. Crochemore’s String Matching Algorithm: Simplification, Extensions, Applications.
  5. Degenerate String Reconstruction from Cover Arrays.
  6. Sorting Suffixes of a Text via its Lyndon Factorization.
  7. The Sum of Exponents of Maximal Repetitions in Standard Sturmian Words.
  8. Swap Matching in Strings by Simulating Reactive Automata.
  9. Towards a Very Fast Multiple String Matching Algorithm for Short Patterns.
  10. Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagrams .
  11. On Morphisms Generating Run-Rich Strings.
  12. Computing Reversed Lempel-Ziv Factorization Online.
  13. Improved and Self-Tuned Occurrence Heuristics.
  14. Finding Distinct Subpalindromes Online.
  15. Deciding the Density Type of a Given Regular Language.
  16. Weak Factor Automata: Comparing (Failure) Oracles and Storacles.
  17. Parallel Suffix Array Construction by Accelerated Sampling.

Stringology 2012

  1. A Multiobjective Approach to the Weighted Longest Common Subsequence Problem.
  2. A Computational Framework for Determining Square-maximal Strings.
  3. Quasi-linear Time Computation of the Abelian Periods of a Word.
  4. BlastGraph: Intensive Approximate Pattern Matching in Sequence Graphs and de-Bruijn Graphs.
  5. The Number of Cubes in Sturmian Words.
  6. Correctness-by-Construction in Stringology.
  7. An Efficient Parallel Determinisation Algorithm for Finite-state Automata.
  8. Similarity Based Deduplication with Small Data Chunks.
  9. New and Efficient Approaches to the Quasiperiodic Characterisation of a String.
  10. LZW Data Compression on Large Scale and Extreme Distributed Systems.
  11. Failure Deterministic Finite Automata.

Stringology 2011

  1. Computing Longest Common Substring/Subsequence of Non-linear Texts.
  2. Binary Image Compression via Monochromatic Pattern Substitution: A Sequential Speed-Up.
  3. 2001-2010: Ten Years of Exact String Matching Algorithms.
  4. Algorithmics of Posets Generated by Words over Partially Commutative Alphabets.
  5. Finding Long and Multiple Repeats with Edit Distance.
  6. Variations of Forward-SBNDM.
  7. Efficient Eager XPath Filtering over XML Streams.
  8. Improving Exact Search of Multiple Patterns From a Compressed Suffix Array.
  9. Computing Abelian Periods in Words.
  10. On Compile Time Knuth-Morris-Pratt Precomputation.
  11. Notes on Sequence Binary Decision Diagrams: Relationship to Acyclic Automata and Complexities of Binary Set Operations.
  12. Computing the Number of Cubic Runs in Standard Sturmian Words.
  13. Minimization of Acyclic DFAs.
  14. Observations On Compressed Pattern-Matching with Ranked Variables in Zimin Words.
  15. Inexact Graph Matching by “Geodesic Hashing” for the Alignment of Pseudoknoted RNA Secondary Structures.
  16. A Parameterized Formulation for the Maximum Number of Runs Problem.
  17. Analyzing Edit Distance on Trees: Tree Swap Distance is Intractable.
  18. Improving Deduplication Techniques by Accelerating Remainder Calculations.
  19. Inferring Strings from Suffix Trees and Links on a Binary Alphabet.
  20. An Improved Version of the Runs Algorithm Based on Crochemore’s Partitioning Algorithm.

Stringology 2010

  1. Tiling Binary Matrices in Haplotyping: Complexity, Models and Algorithms.
  2. Inferring Strings from Runs.
  3. (In)approximability Results for Pattern Matching Problems.
  4. A Space-Efficient Implementation of the Good-Suffix Heuristic.
  5. Binary Image Compression via Monochromatic Pattern Substitution: Effectiveness and Scalability.
  6. The Number of Runs in a Ternary Word.
  7. Approximate String Matching Allowing for Inversions and Translocations.
  8. Simple Tree Pattern Matching for Trees in the Prefix Bar Notation.
  9. Tight and Simple Web Graph Compression.
  10. Bounded Number of Squares in Infinite Repetition-Constrained Binary Words.
  11. Formal Characterizations of FA-based String Processors.
  12. On the Complexity of Variants of the k Best Strings Problem.
  13. Average Number of Runs and Squares in Necklace.
  14. Improving Automata Efficiency by Stretching and Jamming.
  15. Reactive Links to Save Automata States.
  16. New Simple Efficient Algorithms Computing Powers and Runs in Strings.
  17. Practical Fixed Length Lempel Ziv Coding.

Stringology 2009

  1. An Efficient Algorithm for Approximate Pattern Matching with Swaps.
  2. An Input Sensitive Online Algorithm for LCS Computation.
  3. On the Usefulness of Backspace.
  4. Compressing Bi-Level Images by Block Matching on a Tree Architecture.
  5. Asymptotic Behaviour of the Maximal Number of Squares in Standard Sturmian Words.
  6. String Suffix Automata and Subtree Pushdown Automata.
  7. On Bijective Variants of the Burrows-Wheeler Transform.
  8. Bit-parallel Algorithms for Computing all the Runs in a String.
  9. Crochemore’s Repetitions Algorithm Revisited - Computing Runs.
  10. Constant-memory Iterative Generation of Special Strings Representing Binary Trees.
  11. Filter Based Fast Matching of Long Patterns by Using SIMD Instructions.
  12. On-line Construction of a Small Automaton for a Finite Set of Words.
  13. Finding All Covers of an Indeterminate String in O(n) Time on Average.
  14. Feature Extraction for Image Pattern Matching with Cellular Automata.
  15. Taxonomies of Regular Tree Algorithms.
  16. Reducing Repetitions.
  17. On Minimizing Deterministic Tree Automata.
  18. Parallel Algorithms for Degenerate and Weighted Sequences Derived from High Throughput Sequencing Technologies.
  19. Combining Text Compression and String Matching: The Miracle of Self-Indexing.
  20. Adapting Boyer-Moore-Like Algorithms for Searching Huffman Encoded Texts.
  21. Finding Characteristic Substrings from Compressed Texts.
  22. Delta Encoding in a Compressed Domain.
  23. Validation and Decomposition of Partially Occluded Images with Holes.
  24. Searching for Jumbled Patterns in Strings.

Stringology 2008

  1. Fast Optimal Algorithms for Computing All the Repeats in a String.
  2. An Adaptive Hybrid Pattern-Matching Algorithm on Indeterminate Strings.
  3. Dynamic Burrows-Wheeler Transform.
  4. Infinite Smooth Lyndon Words.
  5. Parameterized Suffix Arrays for Binary Strings.
  6. In-place Update of Suffix Array while Recoding Words.
  7. Average Value of Sum of Exponents of Runs in Strings.
  8. The Road Coloring and Cerny Conjecture.
  9. Usefulness of Directed Acyclic Subword Graphs in Problems Related to Standard Sturmian Words.
  10. New Efficient Bit-Parallel Algorithms for the delta-Matching Problem with alpha-Bounded Gaps in Musical Sequences.
  11. Huffman Coding with Non-Sorted Frequencies.
  12. A Concurrent Specification of an Incremental DFA Minimisation Algorithm.
  13. Edit Distance with Single-Symbol Combinations and Splits by Manolis.
  14. Speeding up Lossless Image Compression: Experimental Results on a Parallel Machine.
  15. On the Uniform Distribution of Strings.
  16. New Lower Bounds for the Maximum Number of Runs in a String.
  17. Lossless Image Compression by Block Matching on Practical Massively Parallel Architectures.
  18. Efficient Variants of the Backward-Oracle-Matching Algorithm.
  19. On Regular Expression Hashing to Reduce FA Size.
  20. Conservative String Covering of Indeterminate Strings.
  21. The Virtual Suffix Tree: An Efficient Data Structure for Suffix Trees and Suffix Arrays.

Stringology 2006

  1. A concurrent specification of Brzozowski’s DFA construction algorithm.
  2. 2D context-free grammars: Mathematical formulae recognition.
  3. Flipping letters to minimize the support of a string.
  4. On the problem of deciding if a polyomino tiles the plane by translation.
  5. Modeling delta encoding of compressed files.
  6. Sparse compact directed acyclic word graphs.
  7. The gapped-factor tree.
  8. Using alignment for multilingual text compression.
  9. Two-dimensional bitwise memory matrix: A tool for optimal parallel approximate pattern matching.
  10. On implementation and performance of table-driven DFA-based string processors.
  11. Can dist tables be merged in linear time - An Open Problem.
  12. A Markovian approach for the analysis of the gene structure.
  13. Working with compressed concordances.
  14. Efficient algorithms for (delta, gamma, alpha)-matching.
  15. Song classifications for dancing.
  16. Efficient automata constructions and approximate automata.
  17. An asymptotic lower bound for the maximal-number-of-runs function.
  18. On some combinatorial problems concerning the harmonic structure of musical chord sequences.
  19. FireµSat: An algorithm to detect microsatellites in DNA.
  20. FM-KZ: An even simpler alphabet-independent FM-index.
  21. Reachability on suffix tree graphs.

Stringology 2005

  1. Reordering finite automata states for fast string recognition.
  2. A space efficient bit-parallel algorithm for the multiple string matching problem.
  3. From suffix trees to suffix vectors.
  4. Alphabets in generic programming.
  5. Context-dependent stopper encoding.
  6. A missing link in root-to-frontier tree pattern matching.
  7. Asynchronous pattern matching - Metrics.
  8. Bounded size dictionary compression: Relaxing the LRU deletion heuristic.
  9. Backward pattern matching automaton.
  10. Bit-parallel computation of local similarity score matrices with unitary weights.
  11. A taxonomy of suffix array construction algorithms.
  12. Compressed pattern matching in JPEG images.
  13. Incremental string correction: Towards correction of XML documents.
  14. Flexible music retrieval in sublinear time.
  15. Approximation algorithm for the cyclic swap problem.
  16. A simple alphabet-independent FM-index.
  17. General pattern matching on regular collage system.
  18. Reconstructing a suffix array.

Stringology 2004

  1. A Simple Lossless Compression Heuristic for Grey Scale Images.
  2. Algorithms for the Constrained Longest Common Subsequence Problems.
  3. A Note on Bit-Parallel Alignment Computation.
  4. Conditional Inequalities and the Shortest Common Superstring Problem.
  5. BDD-Based Analysis of Gapped q-Gram Filters.
  6. A Framework for the Dynamic Implementation of Finite Automata for Performance Enhancement.
  7. A Fully Compressed Pattern Matching Algorithm for Simple Collage Systems.
  8. Sorting suffixes of two-pattern strings.
  9. Theoretical Issues of Searching Aerial Photographs: A Bird’s Eye View.
  10. Semi-Lossless Text Compression.
  11. A First Approach to Finding Common Motifs With Gaps.
  12. Arithmetic Coding in Parallel.
  13. Efficient Algorithms for the delta-Approximate String Matching Problem in Musical Sequences.
  14. Combinatorial Characterization of the Language Recognized by Factor and Suffix Oracles.

Stringology 2003

  1. Operation L-INSERT on Factor Automaton.
  2. Matching Numeric Strings under Noise.
  3. The Transformation Distance Problem Revisited.
  4. Learning the Morphological Features of a Large Set of Words.
  5. An Efficient Mapping for Score of String Matching.
  6. Approximate Seeds of Strings.
  7. A Linear Algorithm for the Detection of Evolutive Tandem Repeats.
  8. Forward-Fast-Search: Another Fast Variant of the Boyer-Moore String Matching Algorithm.
  9. Constructing Factor Oracles.
  10. Computing the Minimum k-Cover of a String.
  11. Computing the Repetitions in a Weighted Sequence.

Stringology 2002

  1. Image Recognition Using Finite Automata.
  2. A Note on Crochemore’s Repetitions Algorithm a Fast Space-Efficient Approach.
  3. A Recursive Function for Calculating the Number of Legal Strings of Parentheses and for Calculating Catalan Numbers.
  4. Bidirectional Construction of Suffix Trees.
  5. String Regularities with Don’t Cares.
  6. A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances.
  7. A Work-Optimal Parallel Implementation of Lossless Image Compression by Block Matching.
  8. String Matching with Gaps for Musical Melodic Recognition.
  9. A Note on Randomized Algorithm for String Matching with Mismatches.
  10. Border Array on Bounded Alphabet.
  11. Split and join for minimizing: Brzozowski’s algorithm.

Stringology 2001

  1. Approximate String Matching in Musical Sequences.
  2. Searching in an Efficiently Stored DNA Text Using a Hardware Solution.
  3. A linear time string matching algorithm on average with efficient text storage.
  4. Bioinformatics: tools for analysis of biological sequences.
  5. Construction of the CDAWG for a Trie.

Stringology 2000

  1. Multiple Sequence Alignment as a Facility Location Problem.
  2. Computing Approximate Repetitions in Musical Sequences.
  3. The Set-Set Closest Common Subsequence Problem.
  4. Word-based Compression Method with Direct Access.
  5. A new family of Commentz-Walter-style multiple-keyword pattern matching algorithms.
  6. Repetitions in two-pattern strings.
  7. Condensation Principle.

Stringology 1999

  1. A New Practical Linear Space Algorithm for the Longest Common Subsequence Problem.
  2. Centroid Trees with Application to String Processing.
  3. On Procedures for Multiple-string Match with Respect to Two Sets.
  4. The Closest Common Subsequence Problems.
  5. A Fast String Matching Algorithm and Experimental Results.

Stringology 1998

  1. On the All Occurrences of a Word in a Text.
  2. Approximate String Matching by Fuzzy Automata.
  3. Validating and Decomposing Partially Occluded Two-Dimensional Images (Extended Abstract).
  4. Local Prediction for Lossless Image Compression.
  5. An Early-Retirement Plan for the States.
  6. Implementation of DAWG.
  7. A Fast Morphological Analysis Using the Extended AC Machine for Oriental Languages.
  8. The Factor Automaton.
  9. Exact String Matching Animation in Java.
  10. A Highly Parallel Finite State Automaton Processor for Biological Pattern Matching.
  11. Application of Sequence Alignment Methods to Multiple Structural Alignment and Superposition.
  12. The Longest Restricted Common Subsequence Problem.
  13. Dynamic Programming for Reduced NFAs for Approximate String and Sequence Matching.
  14. Directed Acyclic Subsequence Graph.

Stringology 1997

  1. SPARE Parts: A C++ Toolkit for String PAttern REcognition.
  2. Algebra of Pattern Matching Problems.
  3. A New Family of String Pattern Matching Algorithms.
  4. An Efficient Trie Hashing Method Using a Compact Binary Trie.
  5. 6D Classification of Pattern Matching Problems.
  6. A Boyer-Moore (or Watson-Watson) Type Algorithm for Regular Tree Pattern Matching.
  7. Simulation of NFA in Approximate String and Sequence Matching.

Stringology 1996

  1. An Efficient Multi-Attribute Pattern Matching Machine.
  2. Efficiency of AC-Machine and SNFA in Practical String Matching.
  3. Approximate Regular Expression Matching.
  4. Space Complexity of Linear Time Approximate String Matching.
  5. A Collection of New Regular Grammar Pattern Matching Algorithms.
  6. Fast Full Text Search Using Tree Structured[TS] File.
  7. Reduced Nondeterministic Finite Automata for Approximate String Matching.
This site is open source. Improve this page.