Equivalence of simple functions

A partial function F:Σ∗→Ω∗ is called a simple function if F(w)∈Ω∗ is the output produced in the leftmost derivation of a word w∈Σ∗ from a nonterminal of a simple context free grammar G with output alphabet Ω. In this paper we present an efficient algorithm for testing the equivalence of simple functions. Such functions correspond also to one-state deterministic pushdown transducers. Our algorithm works in time polynomial with respect to |G|+v(G), where |G| is the size of the textual description of G, and v(G) is the maximum of the shortest lengths of words generated by nonterminals of G.