Economy of description for single-valued transducers.

*(English)*Zbl 0826.68065Summary: Questions of economy of description are investigated in connection with single-valued finite transducers. The following results are shown. (1) Any single-valued real-time transducer \(M\) with \(n\) states can be effectively transformed into an equivalent unambiguous real-time transducer having at most \(2^n\) states. (2) Let \(M\) be a single-valued real-time transducer with \(n\) states and output alphabet \(\Delta\) which is equivalent to some deterministic real-time or subsequential transducer \(M'\). Then, \(M\) can be effectively transformed into such an \(M'\) having at most \(1+2^n \cdot \max\{2, \#\Delta \}^{2n^3 l}\) states, where \(l\) is a local structural parameter of \(M\). (3) For any single-valued real-time transducer \(M\) it is decidable in deterministic polynomial time whether or not it is equivalent to some deterministic real-time transducer (to some subsequential transducer, respectively). The results (1)–(3) can be extended to the case where \(M\) is not necessarily real time. The upper bound in (1) is at most one state off the optimal upper bound. Any possible improvement of the upper bound in (2) is greater than or equal to \(2^n-1\).

##### MSC:

68Q30 | Algorithmic information theory (Kolmogorov complexity, etc.) |