Automatic Complexity

3 Edge complexity and digraphs

3.1 Edge-counting automatic complexity

Shallit and Wang counted states in their definition of automatic complexity, although for (complete) DFAs one could equivalently count edges (Theorem 3.2). For NFAs, edge counting is worth considering separately from state counting and is preferable in some ways. For instance, the edge complexity of a word w is bounded below by the number of distinct symbols of w, and the case where this bound is an equality is interesting.

Definition 3.1.

We define three notions of edge complexity for a word x, analogous to ${\mathit{A}}_{\mathit{N}}$, ${\mathit{A}}^{-}$, and A.

• The nondeterministic edge complexity ${\mathit{E}}_{\mathit{N}}\mathrm{(}\mathit{x}\mathrm{)}$ is the minimum number of edges in the digraph of an NFA that uniquely accepts x, i. e., accepts x along ...