Equivalence of simple functions

Abstract: A partial function is called a simple function if is the output produced in the leftmost derivation of a word from a nonterminal of a simple context free grammar 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 , where is the size of the textual description of , and is the maximum of the shortest lengths of words generated by nonterminals of . [Copyright &y& Elsevier]