Extended finite state machine

In a conventional finite state machine, the transition is associated with a set of input Boolean conditions and a set of output Boolean functions. In an extended finite state machine (EFSM) model, the transition can be expressed by an “if statement” consisting of a set of trigger conditions. If trigger conditions are all satisfied, the transition is fired, bringing the machine from the current state to the next state and performing the specified data operations. [cite web
title = Computer Programming Software Terms, Glossary and Dictionary - EFSM: Extended Finite State Machine Model
work =
publisher = Network Dictionary.com
date =
url = http://www.networkdictionary.com/software/e.php?PHPSESSID=9926acc9b2e4f8f05ced05a620abcfe9
format = Web
doi =
accessdate = 2006-12-13


An EFSM is defined [cite conference
first = K-T
last = Cheng
coauthors = Krishnakumar, A.S.
title = Automatic Functional Test Generation Using The Extended Finite State Machine Model
booktitle = International Design Automation Conference (DAC)
publisher = ACM
pages = 86-91
year = 1993
] as a 7-tuple M=(I,O,S,D,F,U,T) where
* S is a set of symbolic states,
* I is a set of input symbols,
* O is a set of output symbols,
* D is an n-dimensional linear space D_1 imes ldots imes D_n,
* F is a set of "enabling functions" f_i : D ightarrow {0,1},
* U is a set of "update functions" u_i : D ightarrow D,
* T is a transition relation, T : S imes D imes I ightarrow S imes D imes O


EFSM Architecture: An EFSM model consists of three major combinational blocks and a few registers.

FSM-block: A conventional finite state machine that realizes the state transition graphs of the EFSM model.

A-block: an arithmetic block for performing the data operation associated with each transition. The operation of this block is regulated by the output signals of the FSM block.

E-block: A block of evaluating the trigger conditions associated with each transition. The input signals of this block are the data variables, while the output is a set of binary signals taken as the inputs by the FSM-block. The information of redundant computation is extracted by analyzing the interactions among the three basic blocks. Using this information, certain input operands of the arithmetic block and evaluation block can be frozen through input gating under specific run time conditions to reduce the unnecessary switching in the design. At the architecture level, if each trigger evaluation & data operation is regarded as an atomic action, then the EFSM implies an almost lowest-power implementation.

The cycle behavior of an EFSM can be divided into three steps:
# In E-block, evaluate all trigger conditions.
# In FSM-block, compute the next state & the signals controlling A-block.
# In A-block, perform the necessary data operations & data movements.

ee also

Abstract state machine


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Finite-state machine — State machine redirects here. For infinite state machines, see State transition system. For fault tolerance methodology, see State machine replication. SFSM redirects here. For the Italian railway company, see Circumvesuviana. A finite state… …   Wikipedia

  • Finite state machine — A finite state machine (FSM) or finite state automaton (plural: automata ) or simply a state machine, is a model of behavior composed of a finite number of states, transitions between those states, and actions. A finite state machine is an… …   Wikipedia

  • Finite state transducer — A finite state transducer (FST) is a finite state machine with two tapes: an input tape and an output tape. This contrasts with an ordinary finite state automaton (or finite state acceptor), which has a single tape. OverviewAn automaton can be… …   Wikipedia

  • Stream X-Machine — The Stream X machine (SXM) is a model of computation introduced by Gilbert Laycock in his 1993 PhD thesis, The Theory and Practice of Specification Based Software Testing .Gilbert Laycock (1993) The Theory and Practice of Specification Based… …   Wikipedia

  • X-Machine Testing — The (Stream) X Machine Testing Methodology is a complete functional testing approach to software and hardware testingM. Holcombe and F. Ipate (1998) Correct Systems Building a Business Process Solution . Springer, Applied Computing Series.] that… …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

  • X-machine — The X machine ( XM ) is a theoretical model of computation introduced by Samuel Eilenberg in 1974.S. Eilenberg (1974) Automata, Languages and Machines, Vol. A . Academic Press, London.] The X in X machine represents the fundamental data type on… …   Wikipedia

  • Turing machine equivalents — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Abstract state machines — In computer science, an abstract state machine (ASM) is a state machine in which the number of states need not be finite and in which the states are not mere points in the state space. More precisely, an ASM state is a structure in the sense of… …   Wikipedia

  • Oracle machine — In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.