Sage Journals: Discover world-class research

Abstract

This paper introduces the Timed Sequential Machine (TSM) formalism. The TSM formalism is based on well-known sequential machines. It is less expressive than the Discrete Event System Specification formalism or Timed Automata, and it offers a set of concepts well adapted to intermediate abstraction levels that appear in the design or analysis processes of discrete event systems. In addition, timed extensions of testing and simplification methods for sequential machines can be defined and used in finite-state TSMs. After presenting the formal definition of a TSM and its behavior, methods are proposed for the minimization of completely specified finite-state TSMs and for the simplification of incompletely specified finite-state TSMs. Finally, it is demonstrated that the TSM formalism has the property of being closed under coupling. That is, any coupled TSM model can be described in terms of an atomic TSM model.

Keywords

Sequential machines timed discrete event formalism state minimization Discrete Event System Specification Timed Automata

Get full access to this article

View all access options for this article.

References

Alur

Dill

. A theory of timed automata. Theor Comput Sci 1994; 126: 183–235.

Alur

Fix

Henzinger

. Event-clock automata: a determinizable class of timed automata. Theor Comput Sci 1999; 211: 253–273.

Giambiasi

Escude

Ghosh

. GDEVS: a generalized discrete event specification for accurate modelling of dynamic systems. Tran SCSI 2000; 17: 120–134.

Henzinger

Manna

Pnueli

. Timed transition systems in real time: theory in practice. Berlin: Springer, 1991, pp.226–251.

Hamri

ME-A

Giambiasi

Frydman

. Min-max DEVS modeling and simulation. Simul Modell Pract Theor 2006; 14: 909–929.

Merritt

Modugno

Tuttle

. Time–constrained automata. In: Baeten

JCM

Groote

(eds) Proceedings on Concurrency Theory, Volume 527 of LNCS. Berlin: Springer, 1991, pp.408–423.

Puri

. Dynamical properties of timed automata. Discrete Event Dyn Syst 2000; 10: 87–113.

Zeigler

. Multifaceted modelling and discrete event simulation. London: Academic Press, 1984.

Zeigler

Praehofer

Kim

. Theory of modelling and simulation. 2nd ed. London: Academic Press, 2000.

10.

Giambiasi

. From sequential machines to DEVS formalism. In: international simulation multi-conference (ISMc’09), 13–16 July 2009.

11.

Kohavi

. Switching and finite automata theory. New York: McGraw-Hill, 1978.

12.

Lee

Yannakakis

. Principles and methods of testing finite state machines—a survey. Proc IEEE 1996; 84: 1090–1126.

13.

Lynch

Vaandrager

. Forward and backward simulations—Part II: timing-based systems. Technical Report, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, August1995.

14.

Rho

J-K

Hachtel

Somenzi

. Exact and heuristic algorithms for the minimization of incompletely specified state machines. IEEE Trans Comput Aided Des Integrated Circ Syst 1994; 13: 167–177.

15.

Lee

. The L-map method for sequential machine state minimization. Kybernetes 1998; 27: 1036–1052.

16.

Biswas

. State minimization of incompletely specified sequential machines. IEEE Trans Comp 1974; C-23: 80–84.

17.

Alur

Courcoubetis

Halbwachs

. Minimization of timed transition systems. Lect Notes Comput Sci 1992; 630: 340–354.

18.

Hwang

. Equivalence and minimization of output augmented DEVS. In: Proceedings of 2003 IEEE conference on systems, man, and cybernetics, Washington D.C., October 2003, pp.409–414.

19.

Dacharry

Giambiasi

. DEVS and timed automata for the design of control systems. In: Guo

(ed.) Robotics research trends. New York: Nova Science Publishers, 2008, pp.193–222.

An introduction to Timed Sequential Machines

Abstract

Keywords

Get full access to this article

References