Decoupled Fitness Criteria for Reactive Systems

The correctness problem for reactive systems has been thoroughly explored and is well understood. Meanwhile, the efficiency problem for reactive systems has not received the same attention. Indeed, one correct system may be less fit than another correct system. We propose a novel and highly general framework which assigns comparable fitness scores to reactive systems. We intentionally decouple the parameters of the framework from the systems to be measured. This decoupling makes the fitness scores more interpretable. It also places a smaller burden on the user than some existing frameworks, which would otherwise require the user to manually annotate systems with numerical values in one way or another. We state the computational problem of evaluating a system with respect to some instances of this framework and propose a method for computing fitness scores of finite labeled transition systems. Finally, we illustrate our approach by measuring and comparing two versions of a simple communication protocol as well as four versions of the well-known Alternating Bit Protocol.