On the expected duration of a search for a fixed pattern in random data

Peter Tolstrup Nielsen

Research output: Contribution to journalLetterResearchpeer-review

626 Downloads (Pure)

Abstract

An expression is obtained for the expected duration of a search to find a givenL-ary sequence in a semi-infinite stream of randomL-ary data. The search time is found to be an increasing function of the lengths of the "bifices" of the pattern, where the term bifix denotes a sequence which is both a prefix and a suffix.
Original languageEnglish
JournalI E E E Transactions on Information Theory
Volume19
Issue number5
Pages (from-to)702-704
ISSN0018-9448
Publication statusPublished - 1973

Bibliographical note

Copyright 1973 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

Fingerprint

Dive into the research topics of 'On the expected duration of a search for a fixed pattern in random data'. Together they form a unique fingerprint.

Cite this