Search

For a set A={A1,…, Am} of nX nmatrices with nonnegative integer entries, let P(A) be the set of all finite products of matrices in A. We show that there is a square space algorithm to decide, given A, whether or not P(A) is finite. As a corollary, we show that there is an exponential space algorithm to decide, given a nondeterministic Mealy sequential machine Mwith accepting states, whether there exists an integer d⩾0 such that on every input, the number of accepting computations of Mproducing distinct outputs is at most d. If dexists, the smallest such dcan be computed in space exponential in size(M)+log d. The space bound reduces to polynomial for the analogous problem of ambiguity of nondeterministic finite acceptors.