Computing the throughput of Concatenation State Machines

Concatenation State Machine (CSM) is a labeled directed And–Or graph representing a deterministic push-down transducer. In the high-performance version of CSM, labels associated to edges are words (rather than letters) over the input alphabet. The throughput of a path p is defined as the sum of the lengths of the labels of the path, divided by the number of edges of p. The throughput of a CSM M is defined as the infimum of the throughput of all accepting paths of M  . In this paper we give an O(nmlog(max−minε)) algorithm, computing an ε-approximation of the throughput of a CSM M, where n is the number of nodes, m is the number of edges, and max (min) is the maximum (respectively, minimum) of the lengths of the edge labels of M. While we have been interested in a particular case of an And–Or graph representing a transducer, we have actually solved the following problem: if a real weight function is defined on the edges of an And–Or graph G, we compute an ε-approximation of the infimum of the complete hyper-path mean weights of G. This problem, if restricted to digraphs, is strongly connected to the problem of finding the minimum cycle mean.