VITAE Prof. Renzo Pinzani
Renzo Pinzani graduated in Mathematics from the
In 1969 he was appointed to be a Professor of Theory and
Applications of Computers at
- National Group for Functional Analysis and its Applications (GNAFA);
- National Group for Informatics and Mathematics (GNIM) ;
- Institute for the Applications of Mathematics and Informatics (IAMI) .
He served as a member of the Scientific Committees of
the latter two of these institutes. In 1981 he was Full Professor of the
Theory and Applications of Computers at the University of Florence.
From 1992 to 1995 he served as Director of the Department of Systems and Informatics. Presently, he is again Director of the same Deprtment. His research activity has concerned principally the following area of computer science:
a) Semantics of programming languages;
b) Design of databases;
c) Algorithms and data structures;
d) Combinatorial analysis.
In the area of the semantics of programming languages, Pinzani defined the ``Algorithmic Programming System'' that, generalizing Markov's algorithms, permits one to define the operational semantic of programming languages. This system has been implemented on computers and used in many applications. By studying the techniques defining programming languages and formal languages he improved the performances of Markov's algorithms (see ``An Algorithmic Approach to the Semantics of Programming Languages", Automata, Languages and Programming (M. Nivat ed.), North-Holland, 1972, and ``Improvements in the Execution of Markov Algorithms", Bollettino dell'Unione Matematica Italiana, 11(4), 1975).
Concerning his work in the design of databases, Pinzani dealt with the definition of a new relational operation in a particular physical organization of data that substantially improved the traditional procedures for the evaluation of queries (see ``A Physical Structure for Efficient Processing of Relational Queries", Foundations of Data Organization (S.P. Gosh, Y Kambayashi, K. Tanaka eds.), Plenum Press, New York, 1987). Moreover, he was interested in the problem of selecting an optimal set of indexes on a relational database. This problem, which is NP-complete, was solved both in the centralized case and in the distributed one by using the properties of a function that takes into consideration all the operations performed on the database. These properties permitted the definition of an heuristic algorithm, performing in polynomial time, that assures in most cases that the selected set is effectively the optimal set (see ``Optimal Selection of Secondary Indexes", IEEE Transactions on Software Engineering, vol. 16, 1990 and ``Index Selection in a Distributed Relational Database", Computers and Artificial Intelligence, vol. 10, 1991).
In the study of algorithms and data structures, Pinzani worked on balanced trees, in particular B-trees and (a,b)-trees, evaluating their performances according to parameters such as the average height and the probability of division of a page (see ``On Some Properties of (a, b)-trees", Lecture Notes in Computer Science, n. 401, 1989). He has also studied the random generation of directed animals. Random generation permits one to study, in a experimental way, the properties of the animals, for example their average height, which are not amenable to analytical methods. By means of encoding each animal in terms of a left factor of a Motzkin word, the computational complexity of this algorithm is linear in the size of the generated animals. This algorithm was then extended to the generation of sub-diagonal walks, displaying under which conditions it still works in linear time.
In enumerative combinatorics, Pinzani has studied the properties of
directed animals and their sub-classes, such as the vertically convex animals,
both by coding them as algebraic languages and by using the recurrence
relations (see ``Une séries géneratrice pour la hauteur des polyominos dvc'',
C. R. Acad. Sci., Paris, t.321, Series I, 259-264, 1995 and ``The average
height of directed column-convex polyominoes having square, hexagonal and
triangular cells'', Mathematical and Computer Modelling, Special
issue Combinatorics and Physics, vol.26 No. 8-10, 27-36, 1997). He had studied
also the property of trinomial coefficients, Motzkin numbers, sums and
alternate sums on the lines of the Motzkin triangle, and the relations between
these numbers (see ``The Motzkin Family", Pure Mathematics and
Applications, Ser. A, vol. 2, 1991). More recently he has dealt with the
problems of reconstruction of convex polyominoes from their projections on the
axes, giving limitations on the number of polyominoes having the same
projection and giving also a polynomial-time algorithm for their reconstruction
(see ``Reconstructing convex polyominoes from their vertical and horizontal
projections'', Theoretical Computer Science, 155, 321-347, 1996). Pinzani
has developed a method for the enumeration of combinatorial objects called ECO,
which permits the study several classes of combinatorial objects such as planar
trees, directed animals, and permutations with forbidden subsequences, according
to different parameters (see ``ECO: A Methodology for Enumeration of
Combinatorial Objects '', Journal of Difference Equations and
Applications 1-56, 1999; ``Directed animals, forests and permutations'',
Discrete Mathematics, 204, 41-71, 1999; ``Some permutations with forbidden
subsequences and their inversion Number'', Discrete Mathematics,
234, 1-3,1 -15, 2001 and ``From Motzkin to Catalan Permutations'', Discrete
Mathematics, 217, 33-49, 2000). Moreover, he has successfully applied ECO
to different subclasses of lattice paths (see ``ECO method and Hill-free
Generalized Motzkin Paths'', submitted, ``ECO-systems for Dyck and Schröder
Paths'', to appear in Pure Mathematics and Applications). Later he has
studied the ECO method from an algebraic point of view, both by interpreting
succession rules for some classical operations on generating functions (see ``A
Set of Well-defined Operations on Succession Rules'', Mathematics and
Computer Science (D.Gardy and A.Mokkadem, eds), Birkhauser, 141-152, 2000) and
by approximating algebraic generating functions by means of rational ones
through ECO-systems (see ``Approximating Algebraic Functions by Means of
Rational Ones'', to appear in Theoretical Computer Science).
More recently Pinzani has worked on bijective combinatorics. His result (see ``A Combinatorial Interpretation of the Area of Schröder Paths'', Electronic Journal of Combinatorics, Vol. 6 ,1999) furnishes a combinatorial proof of the recursive relations for the total area of elevated Schröder paths. Generalizations of this work are contained in ``A Bijective Approach to the Area of Generalized Motzkin'', to appear in Advances in Applied Mathematics. He has also developed a neat, unified approach to study the moments of generalized Motzkin paths (see ``Lattice Path Moments by Cut and Paste'', 13-th FPSAC 2001). He has also developed a new bijective technique for the paths on the slit plane counted by Catalan numbers (see ``A Bijection for some Paths on the Slit Plane'', Advances in Applied Mathematics, 26, 89-96, 2001) and for the involutions in vexillary permutations counted by the Motzkin numbers (see ``Vexillary permutations are enumerated by Motzkin Numbers'',to appear in Annals of Combinatorics).
He is the Editor in Chief of the section Algebra and Theoretical Computer Science of PUMA journal and is in the permanent Program Committee of FPSAC (Formal Power Series and Algebraic Combinatorics).
He is the author of about one hundred pubblications, half of them published on international journals. Presently, his research fields deal with Discrete Tomography, Enumerative Combinatorics and Random and Exhaustive Generation. The definition of a polynomial algorithm for the reconstruction of convex digital designs starting from their horizontal and vertical projections, the definition of a method enumerating combinatorial objects (called ECO) and allowing to determine the generating function of several combinatorial classes (trees, lattice paths, words of a language, permutations, polyominoes) and a method for the random uniform generation of sub-diagonal walks in linear time, are only a few important results he obtained.