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 inve...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2016-02, Vol.246, p.20-29
Main Authors: Cui, Cewei, Dang, Zhe, Fischer, Thomas R., Ibarra, Oscar H.
Format: Article
Language:English
Subjects:
Automaton
Execution
Information rate
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2015.11.006