CURRICULUM
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.