Paper Authors

Abstract

NOTE: The first page of text has been automatically extracted and included below in lieu of an abstract

Session 3520

FROM FINITE STATE MACHINES TO COMPLEX 1 REACTIVE SYSTEMS WITH VISUAL FORMALISMS

Carl W. Steidley, Jeffrey W. Roule Department of Computer Science Southeastern Louisiana University Hammond, Louisiana 70402 Abstract

It is well known, that a digital computer stores information internally in binary form. At any instant, the computer contains certain data, so its internal storage is set in certain patterns of binary digits. We call this the state of the computer at that instant. Since the computer contains a finite amount of storage, there is a finite (although large) number of states that the computer can assume, thus a computer can be formally and abstractly defined and represented with a finite state machine of the form M=[S,I,O,fs,fo] where S is a finite set of states, I is the finite input alphabet, O is the finite output alphabet, fs:SxI->S, and fo:S->O. Another and generally more accessible way to define such machines is the visual formalism of a directed graph called a state graph or more often a state-transition diagram (or state diagram for short).

Generally, a transformational system is specified by a transformation or function, so that an input/output relationship is usually considered a sufficient specification. A reactive system, in contrast with a transformational system, is characterized by being, to a large extent, event-driven, continuously having to react to external and internal stimuli.

There has been a major problem in the specification and design of large and complex reactive systems. This problem is rooted in the difficulty of describing reactive behavior in ways that are clear and realistic, and at the same time formal and rigorous enough to be amenable to detailed computer simulation.

In this paper we will describe a broad extension of the conventional formalism of state machines and their visual formalism, state diagrams, developed by Harel, that is relevant to the specification and design of complex, discrete-event systems, such as multi-computer real-time systems, communications protocols, and digital control units.

Introduction

In a naive sense it may be said that computer scientists are interested in solving two questions: What problems can be solved with a computer, and if a problem is theoretically solvable, what is the most effective way to solve it? Answers to the first question arise through development and study of models of computation. During the undergraduate experience we introduce students to the foundations of computation, which address the first question through abstract models of the computer. This model is frequently the finite state machine or finite state automaton. Finite state _____________________ 1. Partial support for this project was provided by the National Aeronautics and Space

• Citation

• Format
  • APA
  • APA - LaTeX bibitem
  • MLA
  • MLA - LaTeX bibitem
  • Bibtex
  • EndNote - RIS

Roule, J. W., & Steidley, C. W. (1997, June), From Finite State Machines To Complex 1 Reactive Systems With Visual Formalisms Paper presented at 1997 Annual Conference, Milwaukee, Wisconsin. 10.18260/1-2--6583