Computational aspects of the Mobius transformation of graphs

Mobius transformations are defined and studied in the framework of general binary relations. From the application point of view fast Mobius transformation algorithms are presented for computing the Mobius transformation of the Boolean lattice. It is proved that they are actually the best algorithms among a large class of algorithms. These algorithms have a polynomial routine, whereas the usual algorithms have an exponential routine. From a theoretical point of view, the major point of the study is the functoriality of the Mobius transformation, which implies that it is recursive. An algorithm for computing Dempster´s rule of combination that is much faster than the usual one is obtained. A series of related fast algorithms for Dempster-Shafer theory is included