Browsing by Author "Horton, J. D."

Now showing 1 - 5 of 5
  • Thumbnail Image
    Item
    A Fast Incremental Convex Hull Algorithm for Higher Dimensions
    (1990) Stewart, W. M.; Horton, J. D.
    An online algorithm is described which finds the facets of the convex hull of a set of points in d-dimensional space. For point sets chosen at random from some distribution, the algorithm is O(nl +F) for fixed d, where n is the number of points, l is the expected number of sides of a polygon defined by the intersection of a 2-flat with the polytope, and F is the expected number of facets.
  • Thumbnail Image
    Item
    Clause Trees and Factor Paths
    (1994) Horton, J. D.; Spencer, Bruce
    The concept of a clause is generalized to that of a clause tree which shows how the clause can be proved from a set of input clauses. Procedures are provided to find factorizations and tautologies at build time using the internal structure of the tree. Model Elimination and SLI are specializations of this technique. Other resolution-based proof procedures, including bottom-up ones, could include these concepts to make better procedures. One example top-down procedure, ALPOC, has been implemented as part of Stickel's PTTP system. Content areas: automated reasoning, theorem proving, disjunctive logic programming
  • Thumbnail Image
    Item
    Merge Path Improvements for Minimal Model Hyper Tableaux
    (1998) Baumgartner, Peter; Horton, J. D.; Spencer, Bruce
    We combine techniques originally developed for refutational first-order theorem proving within the clause tree framework with techniques for minimal model computation developed within the hyper tableau framework. This combination generalizes well-known tableaux teclmiques like complement splitting and foldingup/down. We argue that this combination allows for efficiency improvements over previous, related methods. It is motivated by application to diagnosis tasks; in particular the problem of avoiding redundancies in the diagnoses of electrical circuits with reconvergent fanouts is addressed by the new technique. In the paper we develop as our main contribution in a more general way a sound and complete calculus for propositional circumscriptive reasoning in the presence of minized and varying predicates.
  • Thumbnail Image
    Item
    Orthogonal starters in finite abelian groups
    (1987) Horton, J. D.
    Two problems are considered. First, the conjecture that all odd abelian groups except Z[subscript 3], Z[subscript 5], Z[subscript 9], and Z[subscript 3] + Z[subscript 3] admit strong starters, is reduced to finding strong starters in five types of groups: the cyclic groups of order 3p, 9p, 3[superscript k] for k > 6, 5 • 3[superscript k] for k > 4, and Z[subscript 3] + Z[subscript 3p] where p is any odd prime greater than five. It is shown that all abelian groups G other than Z[subscript 5] such that three does not divide the order of G admits a strong starter. As well, strong starters are given in some small non-cyclic groups which were previously not known to admit starters. Also, a multiplication theorem for sets of pairwise orthogonal starters is given. An exhaustive computer search for orthogonal starters in odd groups smaller than 19 is carried out. The results require the construction of special permutations of some groups.
  • Thumbnail Image
    Item
    Orthogonal starters in finite abelian groups
    Horton, J. D.
    Two problems are considered. First, the conjecture that all odd abelian groups except Z[subscript 3], Z[subscript 5], Z[subscript 9], and Z[subscript 3] + Z[subscript 3] admit strong starters, is reduced to finding strong starters in five types of groups: the cyclic groups of order 3p, 9p, 3[superscript k] for k > 6, 5 • 3[superscript k] for k > 4, and Z[subscript 3] + Z[subscript 3p] where p is any odd prime greater than five. It is shown that all abelian groups G other than Z[subscript 5] such that three does not divide the order of G admits a strong starter. As well, strong starters are given in some small non-cyclic groups which were previously not known to admit starters. Also, a multiplication theorem for sets of pairwise orthogonal starters is given. An exhaustive computer search for orthogonal starters in odd groups smaller than 19 is carried out. The results require the construction of special permutations of some groups.