×

Algorithmic aspects of genetic sequences and relative Kolmogorov complexity. (English) Zbl 1100.68578

Summary: We use the concept of the relative Kolmogorov complexity for searching fast computable short representations of finite sequences. We investigate different types of regularities of such sequences in order to obtain polynomial-time algorithms for certain versions of the relative Kolmogorov complexity or for their majorants, which can be applied to genetic sequences.

MSC:

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDFBibTeX XMLCite