A tight upper bound on the size of the antidictionary of a binary string

Hiroyoshi Morita; Takahiro Ota

doi:10.46298/dmtcs.3378

Conference paper

A tight upper bound on the size of the antidictionary of a binary string

Hiroyoshi Morita⁽¹⁾, Takahiro Ota⁽²⁾

(1) University of Electro-Communications [Tokyo]

(2) Department of Electronic Engineering

Download article

Open on HAL

Imported on

May 10, 2017

Published on

December 31, 2004

Last modified on

March 31, 2025

Volume 0

DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms

Proceedings

DOI

10.46298/dmtcs.3378

License

https://about.hal.science/hal-authorisation-v1

Indicators

496

Views

425

Downloads

A tight upper bound on the size of the antidictionary of a binary string

Hiroyoshi Morita⁽¹⁾, Takahiro Ota⁽²⁾

(1) University of Electro-Communications [Tokyo]

(2) Department of Electronic Engineering

Abstract

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.

Keywords