Massimiliano Goldwurm

Versione italiana

Introduction Research Teaching

Dipartimento di Scienze dell'Informazione Università degli Studi di Milano Via Comelico 39, 20135 Milano - ITALY Phone: (+39) 02 5031 6233. Fax: (+39) 02 5031 6373 email: surname at dsi dot unimi dot it

Introduction

Massimiliano Goldwurm received a degree in Mathematics in 1982 and a PhD in Computer Science in 1988. He was researcher and professor at the Department of Computer Science of the State University of Milan. His research interests concern the area of formal languages, computational complexity and analysis of algorithms.
 

Research

• SOFSEM 2010, 36th International Conference on Current Trends in Theory and Practice of Computer Science, Špindleruv Mlýn (Czech Republic), January 23–29, 2010.
• DLT 2009, 13th International Conference on Developments in Language Theory, Stuttgart (Germany), June 30 - July 3, 2009.
• DLT 2007, 11th International Conference, Developments in Language Theory, Turku (Finland), July 3-6, 2007.
• STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003.

Recent papers

• 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.
  Also presented at WORDS 2009, International Conference, Salerno, September 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.



---

• A. Bertoni, M. Goldwurm, V. Lonati,

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 give a characterization, in terms of computational complexity, of the family REC1 of the unary picture languages that are tiling recognizable. We introduce quasi-unary strings to represent unary pictures and we prove that any unary picture language $L$ is in REC1 if and only if the set of all quasi-unary strings encoding the elements of $L$ is recognizable by a one-tape nondeterministic Turing machine that is space and head-reversal linearly bounded. In particular, the result implies that the family of binary string languages corresponding to tiling-recognizable square languages lies between NTIME$(2^n)$ and NTIME$(4^n)$. This also implies the existence of a nontiling-recognizable unary square language that corresponds to a binary string language recognizable in nondeterministic time $O(4^n \log n)$.


---

• M. Goldwurm, R. Radicioni,

Probabilistic models for pattern statistics. Internal report, March 2006 (file ps).
R.A.I.R.O. Theoretical Informatics and Applications, volume 40, pages 207-225, July 2006.

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.


---

• M. Goldwurm, V. Lonati,

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, June 2005 (file ps), also available at 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.


---

• M. Goldwurm, V. Lonati,

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

---

• A. Bertoni, C. Choffrut, M. Goldwurm, V. Lonati,

Local limit properties for pattern statistics and rational models.
Theory of Computing Systems, vol. 39 (1), 2006, 209-235 (available at link).

---

• C. Choffrut, M. Goldwurm, V. Lonati,

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.

---

• A. Bertoni, C. Choffrut, M. Goldwurm, V. Lonati,

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.

---

• A. Bertoni, C. Choffrut, M. Goldwurm, V. Lonati,

On the number of occurrences of a symbol in words of regular languages.
Theoretical Computer Science, Volume 302, Issues 1-3 (June 2003), pag. 431-456, available on line .
Preliminary version in Rapporto Interno n.274-02.

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.

---

• A. Bertoni, M. Goldwurm, M. Santini

Random generation for finitely ambiguous context-free languages (file ps).
R.A.I.R.O. Theoretical Informatics and Applications, volume 35 (2001), pag. 499-535.

---

• M. Goldwurm, B. Palano, M. Santini

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.

---

• M. Goldwurm, M. Santini

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.

---

• A. Bertoni, M. Goldwurm, M. Santini

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.

---

• C. Choffrut, M. Goldwurm,

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

  ---

• C. Choffrut, M. Goldwurm,

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.

  ---

• A. Avellone, M. Goldwurm,

Analysis of algorithms for the recognition of rational and context-free trace languages (file ps).
R.A.I.R.O. Theoretical Informatics and Applications 32 : 141-152, 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.

Courses and teaching activity

• Algoritmi e strutture dati
(corso di laurea di Informatica, dall'anno a. 1995/'96 in poi).

• Processi stocastici
(corsi di laurea magistrale di Informatica e di Informatica per la Comunicazione, dall'anno a. 2009/2010)

• Modelli stocastici Markoviani
(corsi di laurea magistrale di Informatica e di Tecnologie dell'Inform. e della Com., dall'anno a. 2006/07 al 2008/09).

• Linguaggi formali e automi
(corso di laurea di Informatica, anni a. 2001/02 e 2002/03).

• Teoria dei linguaggi
(corso di laurea di Matematica, anni a. 1993/'94, 1994/'95, 1995/'96).

• Documentazione automatica
(corso di laurea di Scienze dell'Informazione, svolto nel 1992/'93).