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 string

Authors: Hiroyoshi Morita 1; Takahiro Ota 2

  • 1 University of Electro-Communications [Tokyo]
  • 2 Department of Electronic Engineering

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.

https://doi.org/10.46298/dmtcs.3378
Source: HAL:hal-01184213v1
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]

Share and export

Consultation statistics

This page has been seen 144 times.
This article's PDF has been downloaded 146 times.