1. Sulla complessità di alcuni problemi di conteggio
- Author
-
Alberto Bertoni, Giancarlo Mauri, M. Torelli, Bertoni, A, Torelli, M, and Mauri, G
- Subjects
Discrete mathematics ,Algebra and Number Theory ,Numerical analysis ,INF/01 - INFORMATICA ,Combinatorics ,Computational Mathematics ,Exact algorithm ,Approximation error ,Theory of computation ,Order (group theory) ,Regular grammar ,Tree automaton ,Algebraic number ,complessità computazionale, problemi di conteggio ,Mathematics - Abstract
This paper is intended to show that an algebraic approach can give useful suggestions to design efficient algorithms solving combinatorial problems. The problems we discusses in the paper are: a) Counting strings of given length generated by a regular grammar. For this problem, we give an exact algorithm whose complexity is 0 (logn) (with respect to the number of executed operations), and an approximate algorithm which however still has the same order of complexity; b) counting trees recognized by a tree automaton. For this problem, we give an exact algorithm of complexity 0(n) and an approximate one of complexity 0 (logn). For this approximate algorithm the relative error is shown to be 0 (1/n).
- Published
- 1980