Execution information rate for some classes of automata

We study the Shannon information rate of accepting runs of various forms of automata. This rate is a complexity indicator for executions of these automata. Accepting runs of finite automata and reversal-bounded nondeterministic counter machines, as well as their restrictions and variations, are investigated and are shown, in many cases, to have computable execution rates. We also study the information rate of behaviors in discrete timed automata. We conduct experiments on C programs showing that estimating the information rates for their executions is feasible in many cases.