Algebraic and informational aspects of Zielonka's Theorem
Alberto Bertoni, Giancarlo Mauri, Giovanni Pighizzini,
and Nicoletta Sabadini
Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
via Comelico 39 -- 20135 Milano, Italy
Abstract
Zielonka's Theorem characterizes
recognizable subsets of free partially commutative monoids
in terms of asynchronous automata.
Here, we prove two results closely related to Zielonka's Theorem:
first, we give a new representation theorem for finite monoids;
next, we characterize the class of recognizable
subsets of free partially commutative
monoids in terms of a new model of distributed system with
bounds on space and communication complexity.
Download
Compressed postscript
Compressed dvi