Quantum Algorithms for Some Strings Problems Based on Quantum String Comparator [PDF]
Mathematics, 2022 We study algorithms for solving three problems on strings. These are sorting of n strings of length k, “the Most Frequent String Search Problem”, and “searching intersection of two sequences of strings”.
Kamil Khadiev +2 more
doaj +2 more sources
Permuted Pattern Matching Algorithms on Multi-Track Strings [PDF]
Algorithms, 2019 A multi-track string is a tuple of strings of the same length. Given the pattern and text of two multi-track strings, the permuted pattern matching problem is to find the occurrence positions of all permutations of the pattern in the text. In this paper,
Diptarama Hendrian +4 more
doaj +2 more sources
Engineering rank queries on bit vectors and strings [PDF]
Algorithms for Molecular BiologyAdding rank support to strings over a fixed-sized alphabet has numerous applications. Prominent among those is the (bidirectional) FM-Index which is commonly utilized to index and analyze genomic data.
Simon Gene Gottlieb, Knut Reinert
doaj +2 more sources
Position Automata for Kleene Algebra with Tests [PDF]
Scientific Annals of Computer Science, 2012 Kleene algebra with tests (KAT) is an equational system that combines Kleene and Boolean algebras. One can model basic programming constructs and assertions in KAT, which allowed for its application in compiler optimization, program transformation and ...
A. Silva
doaj +1 more source
A Lossless Compression Method for Chat Messages Based on Huffman Coding and Dynamic Programming
Computers, 2021 There is always an increasing demand for data storage and transfer; therefore, data compression will always be a fundamental need. In this article, we propose a lossless data compression method focused on a particular kind of data, namely, chat messages,
Julián Moreno Cadavid +1 more
doaj +1 more source
Combinatoric topological string theories and group theory algorithms
Journal of High Energy Physics, 2022 A number of finite algorithms for constructing representation theoretic data from group multiplications in a finite group G have recently been shown to be related to amplitudes for combinatoric topological strings (G-CTST) based on Dijkgraaf-Witten ...
Sanjaye Ramgoolam, Eric Sharpe
doaj +1 more source
Compression and information entropy of binary strings from the collision history of three hard balls
Journal of Physics Communications, 2023 We investigate how to measure and define the entropy of a simple chaotic system, three hard spheres on a ring. A novel approach is presented, which does not assume the ergodic hypothesis.
M Vedak, G J Ackland
doaj +1 more source
gsufsort: constructing suffix arrays, LCP arrays and BWTs for string collections
Algorithms for Molecular Biology, 2020 Background The construction of a suffix array for a collection of strings is a fundamental task in Bioinformatics and in many other applications that process strings.
Felipe A. Louza +4 more
doaj +1 more source
Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines. [PDF]
PLoS ONE, 2014 Drawing on various notions from theoretical computer science, we present a novel numerical approach, motivated by the notion of algorithmic probability, to the problem of approximating the Kolmogorov-Chaitin complexity of short strings.
Fernando Soler-Toscano +3 more
doaj +1 more source
Linear space string correction algorithm using the Damerau-Levenshtein distance
BMC Bioinformatics, 2020 Background The Damerau-Levenshtein (DL) distance metric has been widely used in the biological science. It tries to identify the similar region of DNA,RNA and protein sequences by transforming one sequence to the another using the substitution, insertion,
Chunchun Zhao, Sartaj Sahni
doaj +1 more source