Sampling automata and programs

We study sampling schemes for executions of automata and programs, which can be used, based on Shannon information theory, to measure how much information flows from one variable to another. We show that the information rates of periodically sampled executions of a nondeterministic finite automaton and of a reversal-bounded nondeterministic multicounter machine are computable. Finally, through experiments, we use Lempel-Ziv compression algorithm to approximate information leakage in programs.