Sulla complessità di alcuni problemi di conteggio

This paper is intended to show that an algebraic approach can give useful suggestions to design efficient algorithms solving combinatorial problems. The problems discussed are: counting strings of given length generated by a regular grammar. For this problem, the authors give an exact algorithm whose complexity is O(log n) (with respect to the number of executed operations), and an approximate algorithm which however still has the same order of complexity; counting trees recognized by a tree automaton. For this problem, they give an exact algorithm of complexity O( n) and an approximate one of complexity O(log n). For this approximate algorithm the relative error is shown to be O(1/n).