Algebraic and informational aspects of Zielonka's Theorem
Alberto Bertoni, Giancarlo Mauri, Giovanni Pighizzini, Nicoletta Sabadini · BOA (University of Milano-Bicocca) · 1993
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.