Topic: state machine

topics > computer science > computer hardware > Group: machine model

coordination system
program control

automated tests of specifications and designs
computer as state machine
conditional statement language
data-driven design
enumerated data types
event controlled processing
formal methods and languages
global declarations and variables
goto statement
ladder diagram
model checker
modes in a user interface
Petri net
Petri net transitions and events
problems with the von Neumann architecture
programmable controller
proving concurrent programs
reduction machines
replacement as moving information
requirement specification by behaviors
semantics by an abstract machine
symbolic execution
temporal relationships
variables as objects which remember a value
von Neumann computer


A state machine is a set of states, a set of externally defined states, and a set of rules governing transitions from one state to the next. State machines are often embedded within programs as global variables. For instance in sequential processing, a state machine can accumulate information about the structure of each sequence. State machines are widely used in control applications such as robotics and process control. Some programming languages are used as state machines. Others have their semantics defined by a state machine. In functional programming the current state is an association dictionary, and the result of one program step is a new state dictionary.

Advantages -- A universal machine which gives programs a "memory". A model can test for safety and liveness properties. (cbb 5/80)

Subtopic: automaton up

Quote: an automaton's operation is determined by finite, internal states; i.e., stable states of the machine at discrete time intervals; nothing else matters [»rabiMO4_1959]
Quote: an automaton is a black box that answers "yes" or "no" to arbitrary, finite sequences of symbols from a fixed, finite alphabet [»rabiMO4_1959]
Quote: intermediate states matter only if they immediately preceed the reading of a symbol from a finite tape [»rabiMO4_1959]

Subtopic: state machine as legal ordering, interface up

Quote: a state machine defines the legal ordering of states over time; how the current behavior depends on the past [»boocG_1999]
Quote: a system behavior is an alternating sequence of states (interface) and agents (system or environment) [»abadM1_1993]
Quote: represent a reactive system by a higraph, state-transition chart; gives allowed sequences of actions and conditions [»hareD5_1988]

Subtopic: control flow as state machine up

Quote: control flow must be explicitly represented separately from class behaviors; use state-transition matrix [»mariB5_1996]
Quote: conditional chains are equivalent to propositional logic; compare binary numbers
Quote: Scat has a control section of labeled state descriptions and state change clauses [»polsPG3_1973, OK]
Quote: Lucent uses virtual finite-state machines (VFSM) to separate the control behavior of a software module from its data manipulation; formal, executable, early error checking, 50% fewer defects, automatic documentation [»florAR1_1997]
Quote: specify control flow and abstract system behavior with a virtual finite state machine (VFSM); may be executed [»wagnF5_1992]

Subtopic: state machine as names and enumeration up

Quote: a virtual finite state machine (VFSM) is state, action, and condition names combined with AND and OR; names and enumerations are primary [»wagnF5_1992]

Subtopic: event-driven as state machine up

Quote: use @-format to implement control states in event-driven software; labels to suspend and resume execution
Quote: event-driven state-machine programming (ESP) for programmable devices; generates a C program and SPIN model; 90% fewer lines of code, low overhead [»kumaS6_2001]
Quote: ESP uses whole program analysis to generate code for event-driven state-machines; independent processes with context switch [»kumaS6_2001]
Quote: an ESP context switch only saves the program counter; no stack needed for a state machine
Quote: ESP language for writing firmware using event-driven state machines; fast, easily programmed, easily debugged, memory management [»kumaS6_2002]
Quote: for each key, FAST defines an action and a new state; the state may change key definitions [»willRA12_1977, OK]
Quote: like a programmed textbook, FAST moves through predetermined sets of key definitions that correspond to the system's state [»willRA12_1977]

Subtopic: acyclic control up

Quote: acyclic, embedded control systems do not have zero-delay loops; e.g., sample-driven, compute outputs on each clock tick [»benvA1_2003]

Subtopic: continuation-driven state machine up

Quote: a continuation is a linear list of instructions; an interpreter of continuations is a state-transition machine, somewhat like Landin's SECD machines [»reynJC8_1972]
Quote: during evaluation of an applicative expression, a state is a stack, environment, control, and a dump; (S, E, C, D) [»landPJ1_1964]

Subtopic: labeled transition system up

Quote: define TCP/IP and Sockets with a host labeled transition system; operational semantics, flat definition, few transition premises, no parallel composition, no internal synchronization [»bishS1_2006]

Subtopic: state machine for verification up

Quote: a verification model must identify control states, event types, and event responses as code fragments [»holzGJ5_1999]
Quote: desired properties for state machines--absence of deadlock, completeness, and liveness; catch basic flaws and unwarranted assumptions [»holzGJ5_1999]

Subtopic: state machine as model up

Quote: model userids as a finite state automata; each process tracks its privilege level with a real, effective, and saved uid; transitions are system calls [»chenH8_2002]
Quote: build a finite state model by 1) identifying states as kernel variables and 2) finding transitions by trying every system call; collapse equivalent states [»chenH8_2002]
Quote: double check the finite state model by setting and getting the user ids [»chenH8_2002]
Quote: build model-extraction algorithm from getstate(), setstate(), and getallstates(); for each state, determine effect of each system call [»chenH8_2002]
Quote: the operating system must behave deterministically relative to its finite state model; if not, add global variables to state; each state represented by an equivalence class [»chenH8_2002]
Quote: verifying a finite state model is much easier that fully understanding a system's behavior; e.g., only four operations on user IDs [»chenH8_2002]
Quote: model system evolution with events, states, and conditions
Quote: modeling with a finite state machine is as difficult as programming; will report inconsistencies between model and implementation [»hendP9_1975]
Quote: modeling with finite state machines is practical; TOPD discourages elaborate models by full expression of state transitions [»hendP9_1975]
Quote: Metal is a state machine language for analyzing programs; like yacc [»englD10_2001]
Quote: TOPD models a program by a set of abstract values for objects (i.e., states) and the effects of operations (i.e., transitions); used by tester/checker [»hendP9_1975]
Quote: specify requirements by a mode machine; each modeclass describes one aspect of system behavior by modes and transitions [»atleJM1_1993]

Subtopic: program as state machine up

Quote: a program defines the initial conditions of a computer or state machine [»cbb_1973, OK]
Quote: a program is a nondeterministic mechanism that changes the state of the machine it controls
Quote: mechanical evaluation of state machine; current state is stack of temporaries, environment, control, and dump [»landPJ_1966, OK]
Quote: AST applies 'SYSTEM' to the input and obtains its meaning from the current set of definitions D; produces output and a new D' [»backJ8_1978a]
QuoteRef: parnDL5_1972 ;;330 program module as switch inputs and readout indicators (functions) i.e. deterministic machine)

Subtopic: brain as state machine up

Quote: design a mechanical brain with binary digits, conditional chains, storage unit, and stored plans [»zuseK_1984]

Subtopic: names and state machine up

Quote: while a programming language uses names, state machine semantics do not [»backJ_1972, OK]
Quote: need conventions to reduce uncertainty about a machine's state; computers have very great flexibility [»turiA3_1951]

Subtopic: hierarchical state machine up

Quote: meta-level compilation through extensible compiler with high-level state machines applied down every path; transitions triggered by patterns [»chouA11_2000]

Subtopic: states and transitions up

Quote: associated with each atomic object is a set of possible states and a set of possible transitions [»holtAW11_1980]
Quote: the left side of a procedure's transition defines the object states necessary for execution; the right side gives the resulting states [»hendP9_1975]
Quote: state-machine paradigm represents state by values of storage variables; must handle simultaneous assignment [»floyRW8_1979]
QuoteRef: kuznOP6_1972 ;;958 items: situations as nodes and transitions as sides boolean-exp/ transition.
Note: a state variable is a radio button [»cbb_1990, OK]

Subtopic: simplifying a state machine up

Quote: efficient algorithm to convert timestamps into event clocks; reduces state space for model checker of distributed protocols [»dereF3_2001]
Quote: SPIN uses partial order reductions that preserve the correctness property; 10-90% space and saving [»holzGJ5_1997]
Quote: used the theorem prover HOL to prove the correctness of SPIN's partial order reduction
Quote: automatically propagate redundant information in a mode transition table; e.g., simultaneous mode transitions [»atleJM1_1993]

Subtopic: lexical analysis by state machine up

Quote: use acyclic finite automata as compact recognizers of a lexicon; time and space efficient; better than tries [»ciurMG9_2001]

Subtopic: state messages up

Quote: state messages for single-writer multiple-reader; short, non-blocking, circular buffer; 1/4 the overhead for small messages [»zubeKM10_2001]

Subtopic: distributed state machine up

Quote: except for total partition, the Internet masks all transient failures; must protect the state about an on-going conversation [»clarDD8_1988]
Quote: fate-sharing--can loss state about an entity only if lose the entity itself; e.g., store synchronization information with the hosts and not the gateways, trust the host instead of the network
Quote: CATOCS message ordering easily replaced by straight-forward, state-based solutions [»cherDR12_1993]
Quote: the applicable messages for a finite message machine depends on the current state [»katzL_1981]
Quote: a marked graph shows where items flow and what they meet, while a state transition diagram shows their function [»holtAW_1970]
Quote: subsumption architecture for intelligent robots: fixed-topology layers of finite state machines; higher layers can replace or inhibit messages of lower layers [»brooRA1_1991]
Quote: associated with each role is a set of possible states; an activity changes the states of the corresponding actors [»holtAW_1979]

Subtopic: stateless systems up

Quote: the EROS kernel does not maintain state; user-allocated storage stores the security and execution state; may be cached [»shapJS1_2002]

Subtopic: problems with state machine up

Quote: finite automata do not support hierarchical design or concurrency; large, real-time systems are impossible to understand [»benvA9_1991]
Quote: in paper solutions that referred to past events, 50% used the present tense to mention a past event, 20% used the word 'after', 10% used a state variable

Related Topics up

Group: coordination system   (8 topics, 217 quotes)
Group: program control   (27 topics, 547 quotes)

Topic: automated tests of specifications and designs (12 items)
Topic: computer as state machine (20 items)
Topic: conditional statement language (5 items)
Topic: data-driven design (41 items)
Topic: enumerated data types (17 items)
Topic: event controlled processing (46 items)
Topic: formal methods and languages (53 items)
Topic: global declarations and variables (33 items)
Topic: goto statement (25 items)
Topic: ladder diagram (5 items)
Topic: model checker (49 items)
Topic: modes in a user interface (40 items)
Topic: Petri net (44 items)
Topic: Petri net transitions and events (21 items)
Topic: problems with the von Neumann architecture (11 items)
Topic: programmable controller (9 items)
Topic: proving concurrent programs (37 items)
Topic: reduction machines (14 items)
Topic: replacement as moving information (4 items)
Topic: requirement specification by behaviors (16 items)
Topic: semantics by an abstract machine (38 items)
Topic: state (35 items)
Topic: symbolic execution (9 items)
Topic: temporal relationships (40 items)
Topic: variables as objects which remember a value (10 items)
Topic: von Neumann computer
(14 items)

Updated barberCB 4/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.