Joseph Douglas HORTON B.Sc. (Honours)in Mathematics(University of Manitoba) M.A in Mathematics (York University) Ph.D in Combinatorics(University of Waterloo) Professor

Address :           Tel : Fax : office : email :

Joseph Douglas Horton, Faculty of Computer Science, University of New Brunswick P.O. Box 4400, Fredericton, N.B. CANADA (506) 447-3336 (506) 453-3566 E118, Gillin Hall jdh@unb.ca

• CS1303
• MATH3343

Clause trees: Work with Professor Bruce Spencer. We have developed a new data structure for automated reasoning, the clause tree. Many old algorithms for automated reasoning become easier to understand when viewed as manipulating clause trees. Moreover new tighter algorithms can be defined. The method is useful in solving any problem to which automated reasoning can be applied, from an improved automated theorem proving tool to aid mathematicians (probable), to helping prove programs correct (a long shot). It may be beneficial in proving the security levels of computer systems.

• J.D. Horton and Bruce Spencer, "Clause Trees: a Tool for Understanding and Implementing Resolution in Automated Theorem Proving", TR95-095, Faculty of Computer Science, UNB, June 1995 (73 pages, submitted for publication).
• J.D. Horton and Bruce Spencer, "A Top Down Algorithm to Find Only Minimal Clause Trees" (2 pages, to appear in Proc. CPL-95 held in conjunction with KI-95, Bielefeld, Germany, September 1995).
• J.D. Horton and Bruce Spencer, "Reducing Search with Minimal Clause Trees", TR95-099, Faculty of Computer Science, UNB, November 1995 (11 pages).

My original field of research was combinatorial design, an area in which I continue to publish. Three of my papers were published in 1991 in this area.

After completing my Ph.D., I became very interested in graph theory. I found the first known non-hamilton bipartite cubic graph, and the first hypotraceable graph. Perhaps my best work in this area was with Izak Bouwer on graphs.

After coming to UNB in 1981, I became interested in Algorithm Analysis. The most important result here has been the discovery of a polynomial-time algorithm to find the shortest cycle basis of graph. This result has applications in many other areas of Mathematics and Engineering.

More recently I have been working in Computational Geometry. My Ph.D. student William Stewart worked on constructing the convex hull of sets of points in up to 10 dimensions. I also have recently developed an on-line algorithm to construct the Voronoi Diagram of a set of points which I was studying along with my student John Kyaruzi.

Selected Publications

• J.D. Horton, R.C. Mullin, and R.G. Stanton, 1971, "A Recursive Construction for Room Designs", Aequationes Mathematicae 6, 39-45.
• J.D. Horton, 1974, "Sublatin Squares and Incomplete Orthogonal Arrays", J. Combinatorial Theory A 16, 23-33.
• J.D. Horton, 1981, "Room Designs and One-Factorizations", Aequationes Mathematicae 22, 56-63.
• J.D. Horton, 1983, "Sets with no empty convex 7-gons", Canadian Mathematical Bulletin, 26, 482-484.
• J.D. Horton, 1987, "A Polynomial Time Algorithm to Find the Shortest Cycle Basis of a Graph", SIAM J. on Computing, 16, 358-366.
• J.D. Horton and I. Z. Bouwer, 1991, "Symmetric Y-graphs and H-graphs", J. Combinatorial Theory B, 53, 114-129.
• J. D. Horton and K. Kilakos, 1993, "Minimum Edge Dominating Sets", SIAM J. Discrete Math, 6, 375-387.
• J. D. Horton, R. Harland, E. Ashby, R. H. Cooper, W. F. Hyslop, B. G. Nickerson, W. M. Stewart, O. K. Ward, 1993,"The Cascade Vulnerability Problem", J. Computer Security, 2, 279-290.
• J. D. Horton and Bruce Spencer, 1997, "Clause trees: a tool for understanding and implementing resolution in automated reasoning", Artificial Intelligence, 92, 25-89.

• The Canadian Mathematical Society (Life member)
• Association for Computing Machinery - SIGACT
• Foundation Fellow of the Institute of Combinatorics and its Applications
• American Association for Artificial Intelligence

• Hold the rank of FIDE Master at chess (Atlantic Canada Champion 1984, 1992)
• Sing, play the piano and recorder

Homepage CS Homepage

Document: http://www.cs.unb.ca/profs/horton/
Last Revision : 11/24/99 By Sharmila Mehendale