Dissertation
Complexity Analysis of Communicating Objects using Gurevich Free Energy
Doctor of Philosophy (PhD), Washington State University
01/2017
Handle:
https://hdl.handle.net/2376/109972
Abstract
We propose a novel method to analyze the closeness of a set of communicating objects. Under the restriction that the set of messages between objects comprises a regular language, we represent the communication-states graph as a DFA that accepts this language. We adapt the Gurevich free energy from thermodynamic formalism to measure the free energy of a finite automaton. We then define shared free energy between two communicating objects based on their Gurevich free energy. The all-pairs shared free energy matrix is then a similarity matrix that represents communication closeness over the set of objects. We apply standard similarity clustering techniques to group objects into equivalence classes.
We extend this approach to estimate communication closeness from a single long run of observations only, i.e. without knowing the finite automaton specification of the set of communicating objects. To empirically assess a candidate estimator of Gurevich free energy, we generate long sequences by simulating a random walk on a known DFA using the Parry measure. We assess two estimators, (1) Koslicki-Thompson’s estimated topological pressure on finite sequences, and (2) our estimator for a stationary ergodic Markov source using Lempel-Ziv compression, which converges to the theoretical Gurevich free energy with probability 1.
Separately, we derive a quantitative relationship between the maximal entropy rate achieved by a blackbox software system’s specification graph, and the probability of faults P_n obtained by testing the system, as a function of the length n of a test sequence. By equating “blackbox” to the maximal entropy principle, we model the specification graph as a Markov chain that, for each distinct value of n, achieves the maximal entropy rate for that n. We prove that, for nontrivial specification graphs, the probability of finding
faults goes asymptotically to zero as the test length n increases, regardless of the evolution of the transition probability matrices T_n.
We further apply Gurevich free energy to efficiently compute an approximate maximal entropy rate, and prove that it converges to the theoretical rate, while being essentially constant-time in n.
Metrics
11 File views/ downloads
25 Record Views
Details
- Title
- Complexity Analysis of Communicating Objects using Gurevich Free Energy
- Creators
- Eric Shing-Suan Wang
- Contributors
- Zhe Dang (Advisor)Thomas R. Fischer (Committee Member)Carl H. Hauser (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- School of Electrical Engineering and Computer Science
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Number of pages
- 122
- Identifiers
- 99900581628601842
- Language
- English
- Resource Type
- Dissertation