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 tree pattern matches any tree with its variables replaced with constant subtrees. A negative result for learning with equivalence and membership/subset queries is shown for unordered trees where a successful match requires the number of children in the pattern and instance to be the same. Unordered trees and forests are shown to be learnable with an alternative matching semantics that allows an instance to have extra children at each node. 1 INTRODUCTION Many applications in mathematics and language processing represent data more naturally as trees (or as unions of these) than as vectors of features. Tree patterns also provide more information than simple s...

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 developed to solve this problem. Unlike other heuristics, it can handle more than one level of inversion, i.e., inversions within inversions. Furthermore, it tends to capture the matched strings' genes while other heuristics fail. There are two versions of the original walking tree heuristics: the score version gives only the alignment score, the alignment version gives both the score and the alignment mapping between the strings. The score version runs in quadratic time and uses linear space while the alignment version uses an extra log factor for time and space. In this paper, we will briefly describe the walking tree method and the original sequential and parallel algorithms. We will explain why different parallel algorithms are needed for a network of workstations rather than the original algorithm which worked well on a symmetric multi-processor. Our improved parallel method also led to a quadratic time sequential algorithm that uses less space. We give an example of our parallel method. We describe several experiments that show speedup linear in the number of processors, but eventual drop off in speedup as the communication network saturates. For big enough strings, we found linear speedup for all processors we had available. These results suggest that our improved parallel method will scale up as both the size of the problem and the number of processors increase. We include two figures that use real biological data and show that the walking tree methods can find translocations and inversions in DNA sequences and also discover unknown genes.

We consider learning tree patterns from queries. The instances are ordered and unordered trees with nodes labeled by constant identifiers. The concepts are tree patterns and unions of tree patterns (forests) where all the internal nodes are labeled with constants and the leaves are labeled with constants or variables. A tree pattern matches any tree with its variables replaced with constant subtrees. We show that ordered trees, in which the children are matched in a strict left-to-right order, are exactly learnable from equivalence queries, while ordered forests are learnable from equivalence and membership queries. Unordered trees are exactly learnable from superset queries, and unordered forests are learnable from superset and equivalence queries. Negatively, we also show that each of the query types used is necessary for learning each concept class. 1 INTRODUCTION A large part of computational learning theory is devoted to learning concepts over instances represented as attribute v...

The Mobius cubes are hypercube variants that give better performance with the same number of links and processors. We show that the diameter of the Mobius cubes is about one half the diameter of the equivalent hypercube, and that the average number of steps between processors for a Mobius cube is about two-thirds of the average for a hypercube. We give an efficient routing algorithm for the Mobius cubes. This routing algorithm finds a shortest path and operates in time proportional to the dimension of the cube. We also give efficient broadcast algorithms for the Mobius cubes. We show that the Mobius cubes contain ring networks and other networks. We report results of simulation studies on the dynamic message-passing performance of the hypercube, the Twisted Cube of P.A.J. Hilbers et al. (1987), and the Mobius cubes. Our results are in agreement with S. Abraham (1990), showing that the Twisted Cube has worse dynamic performance than the hypercube, but our results show that the 1-Mobius cube has dynamic performance superior to that of the hypercube. This contradicts current literature, which implies that twisted cube variants will have worse dynamic performance.>

The Twisted 3-cube is an interconnection network that twists the edges of the 3-dimensional hypercube to produce a network with diameter 2 and expected distance 11/8. A number of papers have shown that the Twisted 3-cube can be generalized into higher dimensional cube-like networks. We show that many of these networks can be described using a simple model. We place bounds on the diameter and expected distances of networks in this model, and show that the dynamic performance of these networks can match or improve upon the hypercube's performance in most conditions.

A tour of a graph (digraph or sequential machine) is a sequence of nodes from the graph such that each node appears at least once and two nodes are adjacent in the sequence only if they are adjacent in the graph. Finding the shortest tour of a graph is known to be an NP-complete problem. Several theorems are given that show that there are classes ofgraphs in which the shortest tour can be found easily. For more general graphs, we present approximating algorithms for finding short tours. For undirected graphs, the approximating algorithms give tours at worst a constant times the length of the shortest tour. For directed graphs, the size of the calculated tour is bounded by the size of the digraph times the shortest tour. Not only are the bounds worse for the directed case, but the running times of the approximating algorithms are also larger than those for the undirected case.