Hanlin Lu

Date of Award


Degree Type


Degree Name

Master of Science


Computer Science


Dr. Sheng Yu


Statecharts, which have been introduced by David Harel in 1987, provide compact and expressive visual formalisms for reactive systems and they are adopted by Uni- Hed Modeling Language (UML) as important modeling techniques. Currently, most descriptions consider that the computing power of Statecharts is the same as that of Finite State Machines (FSMs) or Finite Automata (FAs), though no accurate ar­ guments or proofs have been provided. Since Statecharts have been used in many application areas during the last twenty years, it is worthwhile to study accurately what Statecharts can do, i.e., what the computation power of Statecharts really is.

In the thesis, we Hrst review the essential elements of Statecharts and we Hnd that Statecharts cannot be modeled by FSMs. By analyzing the Statechart of an ATM model, we prove that Statecharts are not FSMs in general. Thus we make it clear for the Hrst time that Statecharts of more than twenty years old’s are not variations of FSMs or FAs.

P. Wegner claims that Turing machines (TMs) cannot model interaction behaviors. He introduces Interaction Machines (IMs) by extending TMs with interaction streams, which can model interactions during computations and historical dependencies among the interactions.

After study a number of IM models, we consider that the Interactive Turing Machines (ITM) provide more accurate descriptions on the relations between TMs’ computing and interactions and can be considered as theoretical representation for Statecharts. Also in the thesis, we introduce the interaction-based machine model,

which is inherited from ITM. After explore the linkage between Statecharts and the iii

interaction-based machines in detail, We claim that the Statecharts can be modeled by our interaction-based machines.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.