Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: The Symbolic Computation of Functions of Sequences over Finite Alphabets with Given Transition Probabilities by Sequence Length Independent Algorithms
Authors: Jackson, D.M.
Horowitz, Ellis
Keywords: computer science
technical report
Issue Date: Jun-1971
Publisher: Cornell University
Abstract: A special case of the problem discussed in this paper occurs in connection with non-statistical classification and is introduced from this point of view. The special case concerns the computation of expectations of statistical functions of the "distance" between pairs of fixed length sequences over a binary alphabet with given a priori state transition probabilities. The general problem involves an extension to alphabets of arbitrary order and the comparison of an arbitrary number of fixed length sequences. Given a set of sequences, it is shown that for a large class of functions exact computation may be carried out by an algorithm whose computation time is independent of the length of the sequences. It is further shown that results for all functions of this class may be derived from a small number of basis functions. Two methods for computing basis functions are given. Basis functions for the commonly encountered special case involving pairs of binary sequences are given explicitly.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
71-100.pdf1.11 MBAdobe PDFView/Open
71-100.ps404.85 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us