DECIDING MULTISET DECIPHERABILITY

Authors
HEAD T WEBER A
Citation
T. Head et A. Weber, DECIDING MULTISET DECIPHERABILITY, IEEE transactions on information theory, 41(1), 1995, pp. 291-297
Citations number
14
Categorie Soggetti
Information Science & Library Science","Engineering, Eletrical & Electronic
Journal title
IEEE transactions on information theory → ACNP
ISSN journal
00189448
Volume
41
Issue
1
Year of publication
1995
Pages
291 - 297
Database
ISI
SICI code
0018-9448(1995)41:1<291:DMD>2.0.ZU;2-E
Abstract
An O(n(2)L) time and O((n + k)L) space algorithm is provided for decid ing whether or not a finite set C consisting of n words having total l ength L, where all words are taken over a k-element alphabet, is a mul tiset decipherable code. The algorithm is based on a technique related to dominoes. At an early stage it decides in O(nL) time and O((n + k) L) space whether or not set C is uniquely decipherable.