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 LempelZiv compression algorithm to approximate information leakage in programs.
sampling information rate finite automata