Finite Automata for SIR Epidemic Model

Finite Automata for SIR Epidemic Model

A. Senthil

Mody Institute of Technology and Science Lakshmangarh(Sikar),Rajasthan

Dr. V.P. Shukla

Mody Institute of Technology and Science Lakshmangarh(Sikar),Rajasthan

Dr. Sangappa R. Biradar Mody Institute of Technology and

Science Lakshmangarh(Sikar), Rajasthan

ABSTRACT

Epidemics is very important area of concern for most our living being family in the world. Any epidemic situation when properly not controlled could lead to a disaster when large amount of human population is involved. Here we propose a fundamental model of computation in terms of non-deterministic finite automata (NFA) for the Susceptible-Infectives-Recovered (SIR) model.

Through this model we could prove there could be certain languages which are epidemic regular since it could be compared with the normal regular languages for which we can have NFA or regular grammar. If we could classify how the epidemic model could behave then we could better develop strategies that could tackle a similar epidemic situation in future. This model has been tested with the data of H1N1 obtained from CDC USA.

Categories and Subject Descriptors

F.1.1 [Models of Computation]: Automata

General Terms

Computation, epidemics

Keywords

epidemics, SIR model, epidemic NFA.

1. INTRODUCTION

   Epidemics is one of the greatest concern for the living population since it creates a scene of uncertainty among people. If the epidemic situation is not properly handled then it could lead to loss of numerous lives. Kermack- Mckendrick gave the basic model named as SIR (Susceptible-Infected-Recovered) model for epidemics[4]. Susceptible are the group of population who are in all probability has a chance to get the infection of a disease. Infected are the group of population who are infected with the disease. Recovered are those group of population who are recovered from the infectious disease. The following block diagram illustrates the SIR model of epidemics.

   SI I

   S

   S

   I

   I

   R

   R

   Where S is the number of susceptible, I is the number of infected, R is the number of recovered, is the infection rate, and is the recovery rate. The objective of this work is to find an equivalent computation model in terms of non- deterministic finite automata (NFA) so that we could better understand the epidemic environment. The computation model could provide us certain knowledge about whether the epidemic model may fall into the category of the finite acceptors or automata.

   1.1 Non-Deterministic Finite acceptors

   Non-determinism means a choice of moves for an automaton. Rather than prescribing a unique move in each situation, we allow a set of possible moves. We achieve this by defining the transition function so that its range is a set of possible states. A non-deterministic finite automata (NFA) is defined by the quintuple [3,6]:

   M = (Q, , , q0, F) where

   Q is set of states of the automaton

   is the input alphabet

   is the transition function of the automaton defined by

   : Q x ( {}) 2Q.

   q0 Qis the start state of the automaton F Q is the set of final states

   The language accepted by an NFA is defined as the set of all strings which drives the automaton from start state to one of the final states. Acceptance of the string by NFA means after reading a string if the automaton is in one of the final states then the string is accepted or otherwise it is rejected. Formally,

   = { 0 , }

   using this as a fundamental baseline, we could build our automata for the SIR epidemic step by step.

2. EPIDEMIC NFA

   1. The States of the Epidemic Automaton

      The states define where the automaton would be in various discrete time intervals. When we consider our epidemic model there will be three basic states, those are Susceptible state S, Infected state I, and Recovered/ Removed state R. In additional to these three states there would be two more states in our model that would be a Dead state or a Trap state (D/T) for those who have end their lives in any state of the epidemic process and a start state when a person enters in to the epidemic environment. We can call this state as a simple epidemic start state (ES).

      Therefore the set of states for the epidemic NFA would be: Q={ES, S, I, R, D/T}

   2. The Input Alphabet

      The input alphabet for the epidemic automaton would be slightly more complex when compared to the ordinary NFA. For an ordinary NFA, the is the finite set of symbols but in case of epidemic automaton it could be slightly different. The reason being is here the input symbols are considered to be an individual person or a living being, so we could not restrict ourselves to a finite set. The epidemic environment[5,7] also says that when an individual is susceptible, after certain time duration the automaton takes him/her to infection state if he gets infected.

      The input alphabet for the epidemic automata would be an infinite set of tuples. Each tuple would contain two elements and of the form {ti, u} where ti refers to an individual with unique id i. So i can range from 1 to n. The element ti is infinite and the element u { ES, S, I, R, D/T} is a finite set. So input alphabet for the epidemic automaton would be combination of finite and infinite set. Therefore

      = { < ti, u >, < ti+1, u >,<tn, u> }, where ti to tn are unique ids for individuals and u { ES, S, I, R, D/T}.

   3. The Transition function

      The transition function of an automation defines the way in which an automaton moves from one state to another state upon a particular symbol from the input alphabet.

      formally, : Q x 2Q

      The range of is the power set of 2Q, so that its value is not a single element of Q, but a subset of it. This subset defines the set of all possible states that can be reached by the transition. If for instance the current state is S (susceptible), the symbol <t1, S> is read then

      (S, <t1, S>) = {S, I, D/T}

      means the automaton is in susceptible state and if an individual is in t1 is in susceptible state then either S , I or D/T could be the next state of the epidemic NFA.

   4. The Start State

      The start state of the epidemic NFA would be the ES state that is the epidemic start state. The automation would be in this state before reading any input symbol. The input would be presented in the input tape and the tape is divided into equal length cells. Each cell would hold a symbol (one tuple) in the form of <ti, u>. Whenever an individual comes in to epidemic environment the tuple would be added on the right side of the tape. The input would be read from left to right one tuple at a time.

   5. Final States

      The set of final states for the automaton considering the SIR epidemic model would be the Recovered and the Dead states respectively. This is because of the reason that an individual comes out of the epidemic environment in the SIR model either as a disease removed or become dead in various states of susceptible or as infected.

3. TRANSITION TABLE

   	<ti, ES>	<ti, S>	<ti, I>	<ti, R>	<ti, D/T>
   ES	S
   S		{S,I,D}
   I			{I,R,D}
   R				{R,D}
   D/T

   The column heads of the transition table denotes the input alphabet tuples in which ti represents individual ids and the other part represents one of the finite states of the epidemic automaton. The row heads represents the states of the epidemic automaton. The id value i can range from 1n which is infinite.

   The epidemic NFA transition diagram would be as following:

   Definition 1: Epidemic Language L: The language which is accepted by epidemic NFA. Set of all strings that drive the epidemic NFA from epidemic start state to one of the final states.

   Example. Let us consider a the following string w: <ti, S><ti, S><ti, I><ti, I><ti, R>

   The following diagram depicts how this string is being read by the automaton and how it behaves during each time step.

   As seen from the above figure at time step 5 the entire input has been read and the automaton is one of the final state. According the definition of acceptance of the epidemic NFA the string w is accepted.

   The transition from the susceptible state and infected state shows that if an individual dies during the period he is susceptible and during the infected period also. So without consuming an input symbol the automaton can make a move from S state to D state or I state to D state. After the death state of an individual there is no other progress so D

   state is also considered as one of the final state of the epidemic NFA.

4. EXPERIMENTAL SETUP

   The testing of this model with the real time data has been done using Matlab. Infection spread normally happens in the group of population over a geographical area. Here the assumption is the population is constant and the geographical area is divided in to grid of cells and each cell has got a constant population.

   The cellular space in the simulation will be performed by a two dimensional array of 10 x 10 cells and to simplify the simulation process, we can make it to three states which takes the following values:

   Color codes have been defined for the above three states as susceptible cells in green, infected cells are in red and recovered and immune cells are in black.

   1. The Data Set

      The simulation is performed with Matlab program using the data obtained from Center for Disease Control (CDC) United States for H1N1 disease during the year 2009 which is given below[1,2,8,9,10]

      Data from United States Center for Disease Control (CDC)
      Population	3050Lcs	3050Lcs	3050Lcs	3050Lcs
      Susceptible%	92.753	84.517	81.223	80.565
      Infective%	0.033	0.084	0.088	0.091
      Recovered%	7.213	18.033	18.689	19.344

   2. Results

Thefollowing figure shows the simulation results of the automation.

4. CONCLUSION

As we have seen the SIR epidemic model fits into the NFA that is one of the basic finite automata model, we can have all the properties satisfied for the epidemic model as that of NFA. We could also enhance this model by adding the time component into each transaction like an individual can take a transition from susceptible state to infective state after certain time. This option could be done when we implement in timed automata.

6. REFERENCES

1. WHO. A practical guide to harmonizing virological and epidemiological influenza surveillance. 2008. www.wpro.who.int/internet/resources.ashx/CSR/Publications/Guide ToHarmonizinginfluenzaSuiveillance-revised2302.pdf.

2. Center for Disease Control, Interim guidance on infection control measures for 2009 H1N1 Influenza in healthcare settings, including protection of healthcare personnel.

3. Theory of computation, Michael Sipser, Cengage Learning.

4. Kermack, W.O. & Mckendrick, A.G. A contribution to the mathematical theory of epidemics. Proceedings of the royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character, 115(772), 700-721.

5. Dushoff, J., Plotkin, J.B., Levin S.a., & Earn, D.J.D. Dynamical resonance can account for seasonality of influenza epidemics. Proceedings of the national academy of Sciences of the United states of America, 101(48), 16915-16916.

6. Alfred V. Aho and Jefrey D Ulman, Introduction to Automata Theory, Pearson Education

7. S. Hoya White, A. Martin del Rey, G. Rodriguez Sanchez, Using Cellular Automata to Simulate Epidemic Diseases. Applied Mathematical Sciences, Vol. 3, 2009, no. 20, 959-968.

8. Mathematical Modeling of H1N1, William E. Balbach, Nathan B. Frantz, Brett R. Mershman, William T. Weger, Departmant of mathematics, University of Dayton

9. D. Molisson, The dependence of epidemic and population velocities on basic paramenters, Math. Biosci., 107 (1991), 255-287.

10. Cecchini A. (1996) A General Automaton and some specialized Automata for Urban Modelling, Environment & Planning B, 23, 721-732.