StringologyTimes

Stringology for Stringologist

Stringology 2021

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

Stringology 2020

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

Stringology 2019

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

Stringology 2018

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

Stringology 2017

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

Stringology 2016

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

Stringology 2015

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

Stringology 2014

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

Stringology 2013

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

Stringology 2012

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

Stringology 2011

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

Stringology 2010

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

Stringology 2009

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

Stringology 2008

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

Stringology 2006

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

Stringology 2005

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

Stringology 2004

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

Stringology 2003

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

Stringology 2002

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

Stringology 2001

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

Stringology 2000

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

Stringology 1999

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

Stringology 1998

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

Stringology 1997

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

Stringology 1996

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