 Open Access
 Total Downloads : 253
 Authors : A. Senthil, Dr. V.P. Shukla, Dr. Sangappa R. Biradar
 Paper ID : IJERTV2IS90886
 Volume & Issue : Volume 02, Issue 09 (September 2013)
 Published (First Online): 25092013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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 nondeterministic finite automata (NFA) for the SusceptibleInfectivesRecovered (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.

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 (SusceptibleInfectedRecovered) 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 NonDeterministic Finite acceptors
Nondeterminism 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 nondeterministic 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.

EPIDEMIC NFA

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}

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}.

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.

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.

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.


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.

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.

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

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

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

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

Theory of computation, Michael Sipser, Cengage Learning.

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), 700721.

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), 1691516916.

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

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, 959968.

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

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

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