IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca

IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.

AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.

We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa's in the following sense: For any positive integer $d$, there exists a unary $d$-cyclic language such that any pfa for it requires $d$ states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa's smaller than nfa's which, in turn, are smaller than deterministic automata.

Probabilistic vs. nondeterministic unary automata / M.P. Bianchi, C. Mereghetti, B. Palano, G. Pighizzini - In: Non-Classical Models for Auomata and Applications / [a cura di] H. Bordihn, R. Freund, M. Holzer, M. Kutrib, F. Otto. - Vienna : Austrian Computer Society, 2010. - ISBN 9783854032564. - pp. 33-44 (( Intervento presentato al 2. convegno Non-Classical Models for Auomata and Applications tenutosi a Jena nel 2010.

Powered by IRIS-about IRIS-Utilizzo dei cookie

 Copyright © 2021