Hiroyoshi Morita ; Takahiro Ota - A tight upper bound on the size of the antidictionary of a binary string

dmtcs:3378 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms - https://doi.org/10.46298/dmtcs.3378
A tight upper bound on the size of the antidictionary of a binary stringArticle

Authors: Hiroyoshi Morita 1; Takahiro Ota 2

A tight upper bound of the size of the antidictionary of a binary string is presented. And it is shown that the size of the antidictionary of a binary sting is always smaller than or equal to that of its dictionary. Moreover, an algorithm to reconstruct its dictionary from its antidictionary is given.


Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: antidictionary,minimum forbidden words,suffix trees,data compression,ECG,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

Consultation statistics

This page has been seen 182 times.
This article's PDF has been downloaded 173 times.