David Eppstein - Publications

Int. Colloq. Automata, Languages, and Programming (ICALP)

• Reset sequences for monotonic automata.
  D. Eppstein.
  15th Int. Coll. Automata, Languages and Programming, Tampere, Finland, 1988.
  Lecture Notes in Comp. Sci. 317, 1988, pp. 230-238.
  SIAM J. Computing 19(3):500-510, 1990.

  Automata theory. A reset sequence for a DFA is an input such that, no matter which state the DFA starts in, it ends up after the input in a known state. These have been used by Natarajan and Goldberg for certain robot motion planning problems (in fact the conference version of this paper used the title "Reset sequences for finite automata with application to design of parts orienters"), and also in coding theory where they arise in the design of self-synchronizing codes. This paper considers DFAs in which the transition functions respect a given cyclic ordering of the states, and shows that their shortest reset sequences can be found quickly. It also considers parallel algorithms for the problem. There remains open a gap between n² and n³ in the maximum length of reset sequences for general automata.

  (BibTeX -- Citations -- CiteSeer -- ACM DL (ICALP) -- ACM DL (SJC))

• Parallel algorithmic techniques for combinatorial computation.
  D. Eppstein and Z. Galil.
  Ann. Rev. Comput. Sci. 3:233-283, 1988.
  Invited talk by Z. Galil, 16th Int. Coll. Automata, Languages and Programming, Stresa, Italy, 1989.
  Lecture Notes in Comp. Sci. 372, 1989, pp. 304-318, © Springer-Verlag.

  This survey on parallel algorithms emphasized the use of basic subroutines such as prefix sums, Euler tours, ear decomposition, and matrix multiplication for solving more complicated graph problems.

  (BibTeX -- Citations -- CiteSeer -- ACM DL (ARCS) -- ACM DL (ICALP))

• The expected extremes in a Delaunay triangulation.
  M. Bern, D. Eppstein, and F. Yao.
  18th Int. Coll. Automata, Languages and Programming, Madrid, Spain, 1991.
  Lecture Notes in Comp. Sci. 510, 1991, 674-685.
  Int. J. Comp. Geom. & Appl. 1(1):79-92, 1991.

  Discusses the expected behavior of Delaunay triangulations for points chosen uniformly at random (without edge effects). The main result is that within a region containing n points, the expected maximum degree is bounded to within a constant factor of log n / log log n.

  (BibTeX -- Citations -- CiteSeer -- ACM DL -- ACM DL (2))

Conferences -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.