(a.a. 2014/15, corso complementare, laurea triennale di Informatica, 6 crediti).
Articoli recenti
M. Goldwurm, J. Lin, F. Saccà
On the complexity of clustering with relaxed size constraints in fixed dimension,
Theoretical Computer Science,
vol. 717, pp. 37-46, 2018,
versione temporanea on-line .
M. Goldwurm, J. Lin, F. Saccà
On the complexity of clustering with relaxed size constraints ,
Proceedings AAIM 2016, 11th International Conference,
Algorithmic Aspects in Information and Management,
Lecture Notes in Computer Science n.9778, pp. 26-38, 2016.
J. Lin, A. Bertoni, M. Goldwurm,
Exact Algorithms for Size Constrained 2-Clustering in the Plane,
Theoretical Computer Science,
vol. 629, pp. 80-95, 2016.
A. Bertoni, M. Goldwurm, J. Lin,
Exact algorithms for 2-clustering with size-constraints in the Euclidean plane,
Proceedings SOFSEM 2015,
41st International Conference on Current
Trends in Theory and Practice of Computer Science,
Lecture Notes in Computer Science n.8939, pp. 128-139,
Gennaio 2015.
A. Bertoni, M. Goldwurm, J. Lin, L. Pini,
Size-constrained 2-clustering in the plane with Manhattan distance,
Proceedings 15th ICTCS, Italian Conference on Theoretical Computer Science, Perugia, September 2014,
http://ceur-ws.org/Vol-1231/, pp. 33-44, 2014.
A. Bertoni, M. Goldwurm, J. Lin, F. Saccà
Size constrainted distance clustering: separation properties and some complexity results,
Fundamenta Informaticae, vol. 115 (1), pp. 125-139, 2012.
L. Breveglieri, S. Crespi Reghizzi, M. Goldwurm,
Efficient recognition of trace languages defined by repeat-until loops(file pdf),
Information and Computation, vol. 208 (8), pp. 969-981, 2010.
Anche presentato a WORDS 2009, International Conference, Salerno, Settembre 2009.
A. Bertoni, M. Goldwurm, V. Lonati,
The complexity of unary tiling recognizable picture languages: nondeterministic and unambiguous cases.
Fundamenta Informaticae, vol. 91 (2), pp. 231-249, 2009.
L. Breveglieri, S. Crespi Reghizzi, M. Goldwurm,
Integer compositions and syntactic trees of repeat-until programs(file pdf),
Workshop DNTTT'08,
Devolopments and New Tracks in Trace Theory, Cremona, 9-11 Ottobre 2008.
Rapporto interno n. 323-08,
Dip. Scienze dell'Informazione, Università degli Studi di Milano.
I. Cattinelli, M. Goldwurm, N.A. Borghese,
Interacting with an artificial partner: the role of emotional aspects.
Biological Cybernetics, vol. 99, pp. 473-489, 2008.
M. Goldwurm, R. Radicioni,
Average value and variance of pattern statistics and rational models.
Proceedings C.I.A.A. 2007,
24th International Conference on Implementation and Application of Automata,
Lecture Notes in Computer Science n. 4783 (Springer-Verlag), pp. 62-72.
On the complexity of unary tiling-recognizable picture languages.
Proceedings of STACS 2007,
24th International Symposium on Theoretical Aspects of Computer Science,
Lecture Notes in Computer Science n. 4393 (Springer-Verlag), pp. 381-392.
Abstract
We study some probabilistic models for the random generation of words over a given alphabet
used in the literature in connection with pattern statistics.
Our goal is to compare models based on Markovian processes (where the occurrence of a symbol in a given position
only depends on a finite number of previous occurrences) and the stochastic models that
can generate a word of given length from a regular language under uniform distribution.
We present some results that show the differences between these two stochastic models and their
relationship with the rational probabilistic measures.
Pattern statistics and Vandermonde matrices.
Theoretical Computer Science, volume 356 (N.1-2), pages 153-169, May 2006
(file ps).
Abstract
In this paper, we determine some limit distributions of pattern statistics
in rational stochastic models.
We present a general approach to analyze these statistics in rational models
having an arbitrary number of strongly connected components.
We explicitly establish the limit distributions in most significant cases;
they are characterized by a family of unimodal density functions defined by means of confluent Vandermonde matrices.
M. Goldwurm, Jean-Guy Penaud, Nasser Saheb-Djahromi,
Frequency of pattern occurrences in Motzkin words.
Rapport interne du LaBRI n.1368-05, Laboratoire Bordelais de Recherche en Informatique, Universite' Bordeaux I, Giugno 2005
(file ps), anche disponibile presso
Publications LaBRI.
Abstract
We show that the number of horizontal steps in a Motzkin word of length $n$,
drawn at random under uniform distribution, has a Gaussian limit distribution.
We also prove a local limit property for the same random variable
which stresses its periodic behaviour.
Similar results are obtained for the number of peaks in a word of given length drawn at random from the same language.
Pattern statistics in multicomponent models.
(file ps) Proceedings of
S.T.A.C.S. 2005,
22nd International Symposium on Theoretical Aspects of Computer Science,
V. Diekert and B. Durand Editors,
Lecture Notes in Computer Science n. 3404 (Springer-Verlag), pp. 680-692
(original publication available at link).
On the maximum coefficients of rational formal series in commuting variables(file ps) .
Proceedings of
DLT'04 , 8th Int. Conf. on Developments in
Language Theory.
Lecture Notes in Computer Science n. 3340 (Springer-Verlag), pp. 114-126
(original publication available at link).
Preliminary version appeared as Rapport de Recherche n. 2004-002,
L.I.A.F.A ,
Université Denis Diderot , May 2004.
D. de Falco, M. Goldwurm, V. Lonati,
Frequency of symbol occurrences in bicomponent stochastic models
Theoretical Computer Science, Volume 327 (September 2004), pag. 269-300.
Preliminary version appeared as Rapporto Interno n. 299-04
(file ps), Dip. Scienze dell'Informazione,
Università degli Studi di Milano, April 2004.
Joint version of two papers by the same authors appeared respectively in
Proceedings DLT 03, 7th International Conference "Developments in Language Theory",
Szeged (Hungary), July 2003, Z. Esik and Z. Fulop Editors,
Lecture Notes in Computer Science n.2710, pag. 242-253, and in
Proceedings Words'03 , Turku (Finland), T. Harju and J. Karhumäki Editors,
TUCS General Publication n. 27 (August 2003), pag. 344-357.
Local limit distributions in pattern statistics: beyond the Markovian models(file ps).
Rapport de Recherche n. 2003-019, L.I.A.F.A ,
Université Denis Diderot , December 2003.
Reduced version appeared in Proceedings
S.T.A.C.S. 2004, ,
21st International Symposium on Theoretical Aspects of Computer Science,
Montpellier (France), March 2004, V. Diekert and M. Habib Editors,
Lecture Notes in Computer Science n.2996, pag. 117-128.
Abstract
Motivated by problems of pattern statistics, we study the limit
distribution of the random variable counting the number of
occurrences of the symbol a in a word of length n chosen at
random in {a,b}*, according to a probability distribution
defined via a finite automaton equipped with positive real
weights. We determine the local limit distribution of such a
quantity under the hypothesis that the transition matrix naturally
associated with the finite automaton is primitive. Our
probabilistic model extends the Markovian models traditionally
used in the literature on pattern statistics.
This result is obtained by introducing a notion of symbol-periodicity
for irreducible matrices whose entries are polynomials in one variable
over an arbitrary positive semiring.
This notion and the related results we prove are of interest in their
own right, since they extend classical properties of the
Perron--Frobenius Theory for non-negative real matrices.
It includes the paper
A. Bertoni, C. Choffrut, M. Goldwurm, V. Lonati,
The symbol-periodicity of irreducible finite automata(file ps).
Rapporto Interno n. 277-02, Dip. Scienze dell'Informazione,
Università degli Studi di Milano, Aprile 2002.
Abstract
Given a rational formal series r in the noncommutative variables a, b with positive real coefficients,
let Y_n be the random variable representing
the number of occurrences of a in a word w\in {a,b}^*
of length n chosen
at random with probability
(r,w)/c_r(n) where c_r(n)=\sum_{|x|=n}(r,x) .
We give asymptotic estimates for the mean value and the
variance of Y_n together with a central limit theorem for its distribution
whenever r is recognized by a weighted finite automaton with primitive transition matrix.
Assuming an additional condition on such a matrix,
we also prove a local limit theorem for Y_n
showing that its probability function approaches
a normal density function as
n\rightarrow +\infty .
As a consequence, if r is the characteristic series of a (regular) language L\subseteq\{a,b\}^*, then the maximum number of words of length n in L having the same number of a
is of the order of growth \lambda^n / \sqrt{n} ,
for some constant \lambda > 1 .
The method used in the proof is based on the discrete Fourier transform
and the Perron--Frobenius theory for nonnegative matrices.
On the circuit complexity of random generation problems
for regular and context-free languages(file ps).
Proceedings of STACS 2001,
18th Annual Symposium on Theoretical Aspects of Computer Science,
February 15-17, 2001, Dresden (Germany),
A. Ferreira and H. Reichel Eds., Lecture Notes in Computer Science n.2010,
pag. 305-316.
Abstract
We study the circuit complexity of generating at random a word of
length n from a given language under uniform distribution. We
prove that, for every language accepted in polynomial time by
1-NAuxPDA of polynomially bounded ambiguity, the problem is solvable
by a logspace-uniform family of probabilistic boolean circuits of
polynomial size and O(log^2 n) depth. Using a suitable notion of
reducibility (similar to the NC^1-reducibility), we also show the
relationship between random generation problems for regular and
context-free languages and classical computational complexity
classes such as DIV, L and DET.
Clique polynomials have a unique root of smallest modulus(file ps).
Rapporto Interno n. 247-00, Dip. Scienze dell'Informazione,
Università degli Studi di Milano, Febbraio 2000;
also appeared in Information Processing
Letters, Volume 75, Issue 3 (August 2000), pag. 127-132.
Abstract
The clique polynomial of an undirected graph G is the polynomial
P_G = 1-c_1 z+c_2 z^2 - c_3z^3 + .... , where c_i is the number of cliques
of size i in G. We show that, for every G, the polynomial
P_G has only one root of smallest modulus.
Clique polynomials are related to trace monoids. Indeed,
1/P_G is the generating function of the sequence
{t_n}, where t_n is the number of traces of size n in the
trace monoid defined by G. Our result can be applied to derive
asymptotic expressions for {t_n} and other sequences arising
from the analysis of algorithms for the recognition of trace languages.
Random generation and approximate counting of ambiguously described
combinatorial structures(file ps).
Rapporto Interno n. 236-99, Dip. Scienze dell'Informazione,
Università degli Studi di Milano, Settembre 1999.
Reduced version appeared in
Proceedings STACS 2000,
Symposium on Theoretical Aspects
of Computer Science, 17-19 Febbraio 2000, Lille (France),
H. Reichel e S. Tison Eds., Lecture notes in Computer Science n.1770,
pag. 567-580.
Abstract
This paper concerns the uniform random generation and the
approximate counting of combinatorial structures admitting an
ambiguous description. We propose a general framework to study the
complexity of these problems and present some applications to
specific classes of languages. In particular, we give a uniform
random generation algorithm for finitely ambiguous
context-free languages of the same time complexity as the best
known algorithms for the unambiguous case. Other applications
include a polynomial time uniform random generator and approximation
scheme for the census function of (i) languages recognized in
polynomial time by one-way nondeterministic auxiliary pushdown
automata of polynomial ambiguity and (ii) polynomially ambiguous
rational trace languages.
Timed automata with periodic clock constraints(file ps).
Rapport LIAFA 99/28, Université Paris VII - Denis Diderot,
Dicembre 1999.
Also appeared in
Journal of Automata, Languages and Combinatorics,
vol. 5, n. 4, pag. 371-403 (2000).
Ricerca svolta nell'ambito del Programma di Ricerca Scientifica MURST
Modelli di calcolo innovativi: metodi sintattici e combinatori.
Abstract
The traditional constraints on the clocks of a timed automaton are based on
real intervals. Here, we introduce a
new set of constraints, which we call "periodic", and which are based on regularly
repeated real intervals.
Automata with these new constraints have greater expressive power than the
automata with traditional sets while satisfiability remains decidable.
We address questions concerning $\epsilon$-moves and determinism:
simulation of automata with periodic constraints by automata with
traditional constraints, properties of deterministic automata with periodic constraints
(like closure under Boolean operations and decidability of the inclusion problem)
and removal of $\epsilon$-moves under certain conditions.
Then, we enrich our model by introducing "count-down" clocks and show that
the expressive power is not increased.
Finally, we study three special cases: 1) all transitions reset clocks, 2) no
transition reset clocks, and 3) the time domain is discrete and prove the
decidability of the inclusion problem under each of these hypotheses.
Proceedings of the Workshop on Trace Theory and Code Parallelization, Milano 1-2 Giugno 2000
(zip archive of a ps file).
Determinants and Moebius functions in trace monoids(file ps).
Rapport LITP 97/11, Laboratoire d'Informatique Théorique
et Programmation, Université Paris VII.
Also appeared in Discrete Mathematics
194 : 239-247, 1999.
Abstract
We show that the independence relation defining a trace monoid M
admits a transitive orientation if and only if the characteristic series
X of a lexicographic cross section of M is the inverse of
the determinant of Id-A,
where A is a matrix representing the minimum finite automaton
recognizing X and Id is the identity matrix.
This implies that, if the independence relation of a trace monoid M admits
a transitive orientation, then any unambiguous lifting of the
Moebius function of M is the determinant of a matrix defined by the
smallest acceptor of the corresponding cross section.
M. Goldwurm, L. Saporiti,
Clique polynomials and trace monoids(file ps).
Rapporto Interno n. 222-98, Dip. Scienze dell'Informazione,
Università degli Studi di Milano, Maggio 1998.
Abstract
We present an algorithm for the recognition of rational trace languages
that has a time complexity at most proportional to the number of prefixes of the input
trace.
In the worst case it requires $O(n^{a})$ time and $O(n^{a-1})$ space,
where $a$ is the size of the maximum clique in the independence alphabet;
in the average case, it works in $O(n^k)$ time, where $k$ is the number of
connected components of the dependence alphabet.
This algorithm is based on a dynamic programming technique that can also
be applied for the recognition of context-free trace languages: we present
an extension of the classical CYK algorithm that requires $O(n^{3a})$ time
and $O(n^{2a})$ space in the worst case, and $O(n^{3k})$ time and
$O(n^{2k})$ space in the average case.