**Reset sequences for monotonic automata**.

D. Eppstein.

*15th Int. Coll. Automata, Languages and Programming,*Tampere, Finland, 1988.

Springer,*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^{2}*n*in the maximum length of reset sequences for general automata.^{3}(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.

Springer,*Lecture Notes in Comp. Sci.*372, 1989, pp. 304–318.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.

Springer,*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))

**Stable-matching Voronoi diagrams: combinatorial complexity and algorithms**.

G. Barequet, D. Eppstein, M. T. Goodrich, and N. Mamano.

arXiv:1804.09411

*Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)*, Prague, to appear.The stable-matching Voronoi diagram of a collection of point sites in the plane, each with a specified area, is a collection of disjoint regions of the plane, one for each site and having the specified area, so that no pair of a point and a site are closer to each other than to the farthest other site and point that they may be matched to. We prove nearly-matching upper and lower bounds on the combinatorial complexity of these diagrams and provide algorithms that can compute them in a polynomial number of primitive steps.

**Optimally sorting evolving data**.

J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.

arXiv:1805.03350

*Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)*, Prague, to appear.Suppose that a collection of objects has a linear order that is evolving by swaps of randomly chosen consecutive elements. We would like to maintain an approximation to this order using an algorithm that performs one comparison per swap. We show that repeated insertion sort can maintain linear inversion distance from the underlying order, the best possible.

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

Semi-automatically filtered from a common source file.