Typical Paths of a Graph

Issue title: Theory that Counts: To Oscar Ibarra on His 70th Birthday

Article type: Research Article

Authors: Cui, Cewei | Dang, Zhe | Fischer, Thomas R.

Affiliations: School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA 99164, USA. ccui@eecs.wsu.edu; zdang@eecs.wsu.edu; fischer@eecs.wsu.edu

Note: [] Address for correspondence: School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA 99164, USA

Abstract: We introduce (finite and infinite) typical paths of a graph and prove that the typical paths carry all information with probability 1, asymptotically. An automata-theoretic characterization of the typical paths is shown: finite typical paths can be accepted by reversal-bounded multicounter automata and infinite typical paths can be accepted by counting Büchi automata (a generalization of reversal-bounded multicounter automata running on ω-words). We take a statechart example to show how to generate typical paths from a graph using SPIN model checker. The results are useful in automata theory since one can identify an information-concentrated-core of a regular language such that only words in the information-concentrated-core carry nontrivial information. When the graph is used to specify the system under test, the results are also useful in software testing by providing an information-theoretic approach to select test cases that carry nontrivial information of the system specification.

Keywords: graph, entropy, path

DOI: 10.3233/FI-2011-530

Journal: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 95-109, 2011