  Graph inverse semigroups generalize the polycyclic inverse monoids and play
an important role in the theory of C*-algebras. This paper has two main goals:
first, to provide an abstract characterization of graph inverse semigroups; and
second, to show how they may be completed, under suitable conditions, to form
what we call the Cuntz-Krieger semigroup of the graph. This semigroup is the
ample semigroup of a topological groupoid associated with the graph, and the
semigroup analogue of the Leavitt path algebra of the graph.
