RATIONAL TRANSDUCTIONS AND COMPLEXITY OF COUNTING PROBLEMS

This work presents an algebraic method, based on rational transduction s, to study the sequential and parallel complexity of counting problem s for regular and context-free languages. This approach allows us to o btain old and new results on the complexity of ranking and unranking a s well as on other problems concerning the number of prefixes, suffixe s, subwords, and factors of a word which belongs to a fixed language. Other results concern a suboptimal compression of finitely ambiguous c ontext-free languages, the complexity of the value problem for rationa l and algebraic formal series in noncommuting variables, and a charact erization of regular and Z-algebraic languages by means of ranking fun ctions.