Date of Award
2009
Degree Type
Thesis
Degree Name
Master of Science
Program
Computer Science
Supervisor
Dr. Sheng Yu
Abstract
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.
Recommended Citation
Lu, Hanlin, "Interaction-Based Models for Statecharts" (2009). Digitized Theses. 4863.
https://ir.lib.uwo.ca/digitizedtheses/4863