Carlo Mereghetti

Prof. Carlo Mereghetti

Dipartimento di Informatica, Università degli Studi di Milano
orcid

Research Focus & Metrics

Academic Career Length

33Years (1994-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2001 in SIAM Journal on Computing
Verified
Journal Article
Closed access
CMCarlo Mereghetti
Carlo Mereghetti
GPGiovanni Pighizzini
Giovanni Pighizzini
We consider the problem of computing the costs---{ in terms of states---of optimal simulations between different kinds of finite automata recognizing unary languages. Our main result is a tight simulation of unary n-state two-way nondeterministic automata by $O({{\rm e}^{\sqrt{{n}\ln{n}}}})$-state one-way deterministic automata. In addition, we show that, given a unary n-state two-way nondeterministic automaton, one can construct an equivalent O(n 2 )-state two-way nondeterministic automaton performing both input head reversals and nondeterministic choices only at the ends of the input tape. Further results on simulating unary one-way alternating finite automata are also discussed.

1 February 2003 in Theoretical Computer Science
Verified
Journal Article
Closed access
VGViliam Geffert
Viliam Geffert
CMCarlo Mereghetti
Carlo Mereghetti
GPGiovanni Pighizzini
Giovanni Pighizzini

1 August 2007 in Information and Computation
Verified
Journal Article
Closed access
VGViliam Geffert
Viliam Geffert
CMCarlo Mereghetti
Carlo Mereghetti
GPGiovanni Pighizzini
Giovanni Pighizzini

18 June 2003
Verified
Book Chapter
Closed access
PDF file
ABAlberto Bertoni
Alberto Bertoni
CMCarlo Mereghetti
Carlo Mereghetti
BPBeatrice Palano
Beatrice Palano

1 June 2005 in Theoretical Computer Science
Verified
Journal Article
Closed access
ABAlberto Bertoni
Alberto Bertoni
CMCarlo Mereghetti
Carlo Mereghetti
BPBeatrice Palano
Beatrice Palano

1 April 2006 in RAIRO - Theoretical Informatics and Applications
Verified
Journal Article
Closed access
PDF file
CMCarlo Mereghetti
Carlo Mereghetti
BPBeatrice Palano
Beatrice Palano
Bertoni et al. introduced in Lect. Notes Comput. Sci. 2710 (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances of binary regular languages on which 1qfc's are proved to be more succinct (i.e. , to have less states) than the corresponding classical (deterministic) automata.