Volume formula and growth rates of the balls of strings under the edit distances

DOI10.1016/j.amc.2023.128202OpenAlexW4384520799MaRDI QIDQ6096340

Hitoshi Koyano, Morihiro Hayashida

Publication date: 12 September 2023

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2023.128202

zbMATH Keywords

growth raterandomized algorithmformal languageedit distanceball of stringsball volume formula

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15) Randomized algorithms (68W20)

Cites Work

• On the growth of linear languages
• Fast string correction with Levenshtein automata
• Context-free languages of sub-exponential growth
• Uniformly growing k-th power-free homomorphisms
• Optimal string clustering based on a Laplace-like mixture and EM algorithm on a set of strings
• Growth of repetition-free words -- a review
• On the structure of the counting function of sparse context-free languages.
• Finite state languages
• Algorithms for approximate string matching
• Random Number Generators
• On the Theory and Computation of Evolutionary Distances
• Biological Sequence Analysis
• The String-to-String Correction Problem
• Error Detecting and Error Correcting Codes
• Matching Sequences under Deletion/Insertion Constraints
• The growth function of context-free languages
• Language simplification through error-correcting and grammatical inference techniques
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Volume formula and growth rates of the balls of strings under the edit distances