Alberto
Bertoni was born in
He
taught the courses of Theory end Application of Computer, Algorithms and Data
Structures, Formal Languages and Compilers, Algebra, Signal Processing, Neural
Networks, Theoretical Computer Science, Digital Signal Processor, Formal
Languages and Automata to the graduate students in Computer Science and
Mathematics, and courses of Theory of Complexity, Algorithms and Combinatorics, Signal Processing, Combinatorial
Optimization to the PhD students in Computer Science.
He
was advisor of more than 150 thesis of degree in Computer Science, Mathematics,
Physics and more than 15 PhD thesis in Computer
Science, Mathematics and Engineering.
He
was co-promoter of Italian Association of Theoretical Computer Science (ICh-EATCS) and first President of this association for 6
years. He was for 6 years the Italian member in the Council of the European
Association of Theoretical Computer Science.
He
was member of the Academic Senate for the revision of the Statute of the
He
was the Director of the PhD school in Computer Science, Milano-Torino
and President of the Faculty of Computer Science,
He
is member of the Editorial Board of Theoretical Informatics and Applications and it
is was member of the PC of several International Conferences (CAAP, STACS, AdPeNets,
DLT, ...).
The
research activity is in the area of theoretical Computer Science, mainly in
computability and complexity, probabilistic and quantum machines, formal
languages, computational learning, neural networks and genetic models. The
research is documented by more than one hundred international papers.
In
particular, in complexity theory he studied problems of simulations among
computational models and the classification of counting and ranking problems.
In the concurrency, he studied from the point of view of formal languages
theory problems related to trace languages. The activity in learning concerns
distribution dependent PAC learning and neural networks. Neural and evolutive algorithms for combinatorial optimization
problems have been proposed and analyzed.
Recent
activity is described in more details.
Theory
and Application of Computational Complexity
Problems
on “gap” are analyzed: these problems require to evaluate
the minimum quantity of resources to recognize non regular languages. In
[BeMePi94] [BeMePi95]
same models of Turing Machines are considered and resources such
as space, head inversion and nondeterminism degree
are studied.
In [AnBe94] the behaviour of two way
probabilistic automata is studied: the accepting probability is obtained as Hadamard quotient of
rational power series in noncommutative variables.
As a consequence, the membership problem for languages recognized by such
automata is in NC2.
Results
presented in [BeCaMo94][BeCaGaPo97] are an interesting application of
computational complexity to the solid state physics. In particular, results in
classification of combinatorial optimization problems imply that is difficult
to find energy level “near” to that of ground state.
In
[BeMa94] efficient algorithms for symbolic manipulation of holonomic
function are shown, while in [BeCBFi95]
a result in computational learning is obtained: union of linear
subspaces on finite fields is proved learnable in the PAC model. In [BeMa98]
decidability result for inclusion problems in regular trace languages are
shown.
In
the area of random generation and counting algorithms, in [BeMaRa03] is designed a
linear algorithm for random generation of words in regular languages with fixed
number of occurrences of the symbols, while in [BGS01]
random generation of words in ambiguous context free languages is discussed. Asymptotic estimation of the number of words in regular
languages with fixed number of occurrences of the symbols are given in
[BeChGoLo04] [BeChGoLo03],
with application to pattern statistics.
Design,
analysis and applications (i.e. bioinformatics) of algorithms in the area of
neural networks, genetic model and quantum computing
Quantum
computing explores the advantages of using quantum devices in the computation.
In [BeCa01a][BeCa01b][BeMePa03c] new models of quantum
automata are introduced and discussed. Descriptional
complexity methods in the area of quantum automata are studied in [BeMePa03]
[BeMePa03b] [BeMePa03c].
Neural
network are model of
distributed computation, useful in the area of learning and
optimization. The paper
[BePa02] is a survey
of on recent development of the
applications of computational and communication complexity in multilayered perceptrons, while [BeCaGr01] [BeCaGr02] show applications of Hopfield networks in
combinatorial optimization. In particular in [ABCGP97] a simple neural algorithm for Max 2SAT
is shown; such an algorithm has been
implemented on FPGA (Field Programmable Gate Array). In [BeFoVa04]
[BeFoVa04a] [BeFoVa04b] are
presented applications of the random subspace ensambles
for the biomolecular diagnosis.
In
[BaCaGr01] a genetic model is presented and analyzed in the thermodynamic
limit; a genetic algorithm for solving Max CUT is derived, and the performances
are experimentally compared with neural solutions. Applications to the problem
of finding stable models in programming logic are presented in [BGPKT01].
At
the end, in [BeCu94] the solution of a measure problem in mathematical analysis
is given. Such a problem is not in my main research area; it has been proposed
by prof. Cugiani, dean of our faculty, and I
remember with pleasure the stimulating discussion in his drawing-room.
Riferimenti
[BeFoVa04b] A. Bertoni, R.Folgieri,
G.Valentini, Random Subspaces Ensembles for the biomolecular diagnosis of tumors,
NETTAB 2004.
[BeFoVa04a] A.Bertoni, R.Folgieri,
G.Valentini, Feature selection combined with random
subspace ensemble for gene expression based diagnosis of malignancies, WIRN
2004
[BeFoVa04] A. Bertoni, R.Folgieri,
G.Valentini, Biomolecular
cancer prediction with random subspaces ensembles of Support Vector Machines, accettato per pubblicazione su Neurocomputing, 2004.
[BeChGoLo04] A. Bertoni, C. Choffrut, M. Goldwurm, V. Lonati, Local limit
distributions in pattern statistics: beyond the Markovian
models,Proceedings STACS 2004, 21th
Symposium on Theoretical Aspects of Computer Science, Montpellier (France),
March 2004, V. Diekert and M.Habib
Editors, Lecture Notes in Computer Science n. 2996, Springer-Verlag (2004), 117-128
[BeMaRa03] A. Bertoni, P. Massazza, R. Radicioni, Random generation
of words with fixed occurences in regular languages. Proceedings of WORDS ’03, 4th International Conference
on Combinatorics on Words. Turku, Finland, september 2003. pages 332-343.
[BeChGoLo03] A. Bertoni, C. Choffrut, M. Goldwurm, V. Lonati, On the
number of occurrences of a symbol in words of regular languages, Theoretical
Computer Science, vol. 302 (2003), 431-456.
[BeMePa03c]
A. Bertoni, C. Mereghetti e B.
Palano. Quantum Computing: 1-way quantum automata.
In Developments in Language Theory,
7th International Conference, LNCS 2710, pp. 1--20, Springer, 2003.
[BeMePa03]
A. Bertoni, C.
Mereghetti e B. Palano. Golomb Rulers and Difference Sets for Succinct Quantum Automata. International Journal of Foundations of Computer Science, Vol.14,
pp. 871-888, 2003.
[BeCaGr02] A. Bertoni, P. Campadelli, G. Grossi, A Neural Algorithm for the Maximum Clique Problem:
Analysis, Experiments and Circuit Implementation, Algoritmica 33 (1),
pp.71-88, 2002.
[BePa02]
A. Bertoni e
B. Palano. Structural Complexity
and Neural Networks, Proc. 13th WIRN, LNCS 2486, pp.190-216, Springer, 2002.
[BeCaGr01]
A. Bertoni, P. Campadelli,G.
Grossi. An Approximation Algorithm for the Maximum Cut Problem
and its Experimental Analysis, Discrete Applied Mathematics 110
, pp.3-12, 2001.
[BeCa01a] A. Bertoni and M. Carpentieri, Analogies and Differences between Quantum and
Stochastic Automata, Theoretical Computer Science, vol. 262, pp. 69-81, 2001
[BeCa01b] A. Bertoni
and M. Carpentieri, Regular Languages Accepted by Quantum
Automata, Information and Computation. vol. 165, pp. 174-182, 2001
[BGS01].
A. Bertoni, M. Goldwurm,
M. Santini, Random generation for finitely ambiguous
context-free languages, Theoretical Informatics and applications, Vol. 35,
pp.499-512, 2001.
[BGPKT01] A. Bertoni, G.Grossi, A.Provetti, V.Kreinovich, L.Tari, The
Prospect for Answer Sets Computation by a Genetic Model, AAAI Spring Symp., pp.1-5, AAAI Press, 2001.
[BeMa98]
A. Bertoni, M. Massazza, On the inclusion problem for finitely amboguous
rational trace languages, Theo. Info. and Appl., vol. 32, pp.79-98, 1998.
[BeCaGaPo97]A. Bertoni, P. Campadelli, G. Gangai, R. Posenato, Approximability of the
Ground State Problem for Ising Spin Glasses, Journal
of Complexity, 13, pp. 326-339, 1997.
[ABCGP97]
M.A. Alberti, A. Bertoni,
P. Campadelli, G. Grossi,
R. Posenato, A Neural Algorithm for MAX-2SAT:
Performance, Analysis and Circuit Implementation, Neural Networks, 10, pp.
555-560, 1997.
[BeMePi95]
A. Bertoni, C. Mereghetti,
G. Pighizzini, Strong optimal lower bounds for Turing
machines that accept nonregular languages, MFCS 95, LNCS
969, pp.309-318, 1995.
[BeCBFi95]
A. Bertoni, N. Cesa
Bianchi, G. Fiorino, Efficient learning with
equivalence queries of conjunction of modulo functions, Info. Pro. Lett., 56, pp.15-17, 1995.
[AnBe94]
M. Anselmo, A. Bertoni, On 2pfa’s and the Hadamard
quotient of formal power series, Bull. Bel. Math. Soc. 1,
pp.165-173, 1994.
[BeCaMo94]
A. Bertoni, P. Campadelli,
G. Molteni, On the approximability
of energy function in Ising spin glasses, Journal of
Physics A:Math. Gen., 27, pp.6719-6729, 1994.
[BeMePi94]
A. Bertoni, C. Mereghetti,
G. Pighizzini, An optimal lower bound for nonregular languages, Info.Pro.Lett.,
50, pp.289-292, 1994
[BeMa94]
A. Bertoni, P. Massazza, A
parallel algorithm for the Hadamard product of holonomic formal series, Int. Journ.of Alg.
And Comp., Vol.4, N.4, pp.561-573,
1994.
[BeCu94]
A.Bertoni, M.Cugiani, Sulla
natura dell’insieme di una copertura dei punti razionali, Istituto Lombardo Radice
(Rend. Sci.) A 127, pp. 227-232, 1994.