The set of codewords for a standard error-correcting code can be viewed
as subset of the vertices of a hypercube. Two vertices are adjacent in a hypercube exactly when their Hamming distance is 1. A code is a perfect-error-correcting code if no two codewords are adjacent and every non-codeword is...
Basic biological information is stored in strings of nucleic acids (DNA, RNA) or amino acids
(proteins). Teasing out the meaning of these strings is a central problem of modern biology. Matching and
aligning strings brings out their shared characteristics. Although string matching is well-understood in the
edit-distance model, biological strings...
One dimensional nonlinear difference equations have been used to model population growth. The standard biological models have the interesting characteristic that
they display global stability if they display local stability. Various researchers have sought
a simple explanation for this agreement of local and global stability. Here, we show that
enveloping...
It is well known that the Fibonacci numbers can be expressed in the
form Round {1/√5 λ₀[superscript n]} where λ₀ = (1 + √5)/2. [Knu75] We look at integer sequences which are solutions to non-negative difference equations and show that if the equation is 1-Bounded then the solution can be...
The meaning of biological sequences is a central problem
of modern biology. Although string matching is well understood
in the edit-distance model, biological strings
with transpositions and inversions violate this model's
assumptions. To align biologically reasonable strings, we
proposed the Walking Tree Method [4,5,6,7,8], an
approximate string alignment method that...
The N-Queens problem is commonly used to teach the programming technique of backtrack search. The N-Queens problem may also be used to illustrate the important concept of isomorphism. Here we show how the N-Queens problem can be used as a vehicle to teach the concepts of isomorphism, transformation groups or...
This note briefly discusses some of the classical results of McCulloch and Pitts. It then deals with some current research in neural nets. Several questions about neural nets are shown to be computationally difficult by showing that they are NP-Complete or worse. The size of neural nets necessary to compute...
"Fifty years after the pioneering work of McCulloch and Pitts, the study of neural nets is alive and active. In this paper, I have discussed some of the work that is of current interest to me and my co-workers. I would, perhaps, be remiss if I failed to mention some...
We consider learning tree patterns from queries extending
our preceding work [Amoth, Cull, & Tadepalli,
1998]. The instances in this paper are unordered
trees with nodes labeled by constant identifiers.
The concepts are tree patterns and unions
of tree patterns (unordered forests) with leaves labeled
with constants or variables. A...
Approximate string matching is commonly used to align genetic sequences (DNA or RNA) to determine their shared
characteristics. Most genetic string matching methods are based on the edit-distance model, which does not provide
alignments for inversions and translocations. Recently, a heuristic called the Walking Tree Method [2, 3] has been...