Nondeterministic X-Machine - Free Essay Example

CHAPTER 5 Formal Modeling 5.1 Overview To achieve the maximum benefits from formal techniques, integration of approaches is required. In this chapter we present the integration of X-machine models and Z notation. The X-machine models sued to give the relationship between Z and X-machine are: (a) nondeterministic X-machine, (b) deterministic X-machine, (c) nondeterministic stream X-machine, (d) deterministic stream X-machine, (e) communicating stream X-machine, and (f) communicating stream X-machine system. The informal definitions of all these machines are taken from [1], [2], [3]. 5.2 Design of Nondeterministic X-Machine A Nondeterministic X-Machine is 10-tuple NXM = (X, Y, Z, , , Q, , F, I, T) where: 1. X is a fundamental dataset on that the machine operates. 2. Y is a finite set of input alphabets. 3. Z is a finite set of output alphabets. 4. and are input and output partial functions, used to convert the input into the output sets from the fundamental sets, i. e., : Y X and : X Z. 5. Q is a finite nonempty set of states. 6. is type of M, a set of relations on X, i. e., : P (X X). The notation (XX) denotes a set of all possible partial functions from X to X. 7. F is a next state partial function, a transition function, i. e., F: Q x P Q, which takes a state a partial function and produces a new set of states. 8. I is a set of initial states, a subset of Q, and T is a set of terminal states, a subset of Q. NXM state: Q alphaIn: SigmaIn alphaOut: SigmaOut memory: Memory alpha: (SigmaIn Memory) beta: (SigmaOut Memory) function: Memory Memory trans: Q Memory Memory Q I: Q T: Q state I state T state q, q1: Q; m, m1: Memory; i: SigmaIn; o: SigmaOut q state q1 state m memory m1 memory i alphaIn o alphaOut m m1 function i m alpha o m1 beta s, s1: Q s state s1 state q m m1 s trans q1 m m1 s1 trans q m m1 = q1 m m1 s = s1 Invariants: a) The set of states states is a nonempty set. b) The set of initial states I is a subset of states. c) The set of final states T is a subset of states. d) For each input alphabet i and states q and q1, o an output alphabet, (i, m) belongs to elpha, (o, m1) belongs to beta (m, m1) belongs to set of partial functions trans ((q, (m, m1)), s) where transaction function acting on q and partial function gives a set of states. And the trans ((q1,( m, m1)), s1) gives a set of states. In the formal specification of NXM, Memory, SigmaIn, SigmaOut and Q are defined as abstract data types over which we cannot define any operation. To specify the NXM, we introduced a variable states to define the set of states of the NXM. Each element q in set states is of type Q therefore states is a type of power set of Q. To describe the sets of input and output alphabets, variables alphaIn and alphaOut of type of power set of SigmaIn and SigmaOut are defined respectively. Similarly, for memory the variable memory is of type of power set of Memory is introduced. Moreover, alpha and beta are the power set of partial functions of type (SigmaIn Memory) and (SigmaOut Memory) respectively, which converts an input alphabet s into an output alphabet g, by altering the memory. The variable function of type power set of (Memory Memory) is introduced to describe the set of all possible partial functions from Memory to Memory. The transition function trans of type (Q function) PQ is intr oduced to describe the transitions of the machine for each input (q, function), where q is a state and function is a partial function from memory to memory there must be a unique output q1 of type power set of Q. The set of initial states I is of type power set of Q and the set of final states T is of type PQ. 5.3 Design of Deterministic X-Machine A Deterministic X-Machine is 10-tuple DXM = (X, Y, Z, , , Q, , F, I, T) where: 1. X is a fundamental dataset on that the machine operates. 2. Y is a finite set of input alphabets. 3. Z is a finite set of output alphabets. 4. and are the input and output partial functions, used to convert the input into the output sets from the fundamental sets, i. e., : Y X and : X Z. 5. Q is a finite nonempty set of states. 6. is type of M, a set of relations on X, i. e., : P (X X). The notation (XX) denotes the set of all possible partial functions from X to X. 7. F is next state partial function, a transition function, i. e., F: Q x Q. It takes a state a partial function and deterministically produces a new state or the same state. 8. q0 is an initial state and T is a set of terminal states, a subset of Q. The above definition describes the deterministic X-machine because for each state q and for every partial function, there is a state q, i. e., F (q, ) = q. DXM states: Q alphaIn: SigmaIn alphaOut: SigmaOut memory: Memory alpha: SigmaIn Memory beta: SigmaOut Memory function: Memory Memory trans: Q Memory Memory Q q0: Q T: Q states q0 states T states q, q1: Q; m: Memory; i: SigmaIn; o: SigmaOut q states q1 states m memory i m alpha o m beta m m function trans q m m = q1 Invariants: a) The set states is a nonempty set. b) The q0 is an initial state. c) The set of final states T is a subset of states. d) For each input alphabet i and states q and q1, o is an output alphabet, (m, m1) is a relation on X to X, where (i, m) belongs to elpha, (o, m1) belongs to beta and (m m1) belongs to . The trans ((q, function), q1) describes the transaction function acting on q and the partial function giving the state q1. In the schema DXM the abstract data types, X, Y, Z and Q are denoted by Memory, SigmaIn, SigmaOut and Q respectively. In this schema we introduced variable states to define the set of states of the DXM. Each element q in set states is of type Q therefore states is a type of power set of Q. To describe the sets of input and output alphabets, variables alphaIn and alphaOut of type of power set of SigmaIn and SigmaOut are defined respectively. Similarly, for memory the variable memory of type of power set of Memory is introduced. Moreover, alpha and beta are the power set of partial functions of type (SigmaIn Memory) and (SigmaOut Memory) respectively, which converts an input alphabet s into an output alphabet g by altering the memory. The variable function of type power set of (Memory Memory) is introduced to describe the set of all possible partial functions from Memory to Memory. The transition function trans of type (Q function) PQ is introduced to describe the transitions of t he machine for each input (q, function), where q is a state and function is a partial function from memory to memory there must be a unique output q1 of type Q. The initial state q0 is of type Q and the set of final states T of type power set of Q. 5.4 Behavior of X-Machine To check the behavior of the machine, we get a sequence of input alphabets and checks that there exists a successful path for that particular sequence of inputs. This behavior checker accepts a deterministic X-machine a sequence of input alphabets and returns a sequence of output alphabets. Let DXM = (X, Y, Z, , , Q, , F, I, T) is a deterministic X-machine and a sequence of input alphabets seq Yi = y1, y2, , yn, where i = 1, 2,, n we say that there exist a sequence of partial function i = 1, 2, , n, where i = 1, 2,, n. Then we can say that DXM accepts the inputs when there exist a sequence of states si = s1, s2 sn, where i = 1, 2. . . n. In schema BDXM the variable stringIn? belongs to strings. The variable stringOut! belongs to messages. The length of input alphabets and output alphabets are equal. For all i belonging to the elements of cardinality of stringIn?, when the value of i is equal to 1 then there exists q, q1 states and m, m1 are memory states, q is the initial state, m1 b elongs to memory, for i-th element of stringIn? and m belongs to alpha there is a message of type SigmaOut which is the i-th element of stringOut!, and the transition function trans acting on state and and partial function (m, m1) gives a new state q1. It repeatedly reads the input from stringIn? and writes the messages on stringOut! by altering the memory until the final state is not reached or the there is no element in stringIn?. If the last state of the sequence of visited states is a final state then the whole string is accepted otherwise rejected. BDXM DDXM stringIn?: seq SigmaIn stringOut!: seq SigmaOut strings: seq SigmaIn messages: seq SigmaOut stringIn? strings stringOut! messages # stringIn? = # stringOut! i: i 1 .. # stringIn? i = 1 q, q1: Q; m, m1: Memory q = q0 q1 states m memory m1 memory stringIn? i m alpha stringOut! i m1 beta q m m1 dom trans q1 ran trans 1 i # stringIn? q, q1: Q; m, m1: Memory q states q1 states m memory m1 memory stringIn? i m alpha stringOut! i m1 beta q m m1 dom trans q1 ran trans i = # stringIn? q, q1: Q; m, m1 : Memory q = q0 q1 T m memory m1 memory stringIn? i m alpha stringOut! i m1 beta q m m1 q1 trans 5.5 Design of Nondeterministic Stream X-Machine A particular class of X-machine is Stream X-Machine which is defined as 8-tuple NSXM = (, , Q, M, , F, q0, m0), where: 1. is a finite set of input alphabets. 2. is a finite set of output alphabets. 3. Q is a finite nonempty set of states. 4. M is possibly finite set of memory on which the machine operates. 5. is a finite set of partial functions that map an input and a memory state to an output and a new memory state, i. e., : x M x M. 6. F is next state partial function that gives a state and a function from the type , P Q denotes the set of next states. F is often described as a transition state diagram, i. e., F: Q x PQ. For each state q and for every partial function , there is a power set of states P Q such that F (q1, ) = P Q. 7. The q0 is an initial state. 8. The m0 is an initial memory. NSXM states: Q alphaIn: SigmaIn alphaOut: SigmaOut memory: Memory function: SigmaIn Memory SigmaOut Memory trans: Q SigmaIn Memory SigmaOut Memory Q q0: Q m0: Memory states q0 states m0 memory q, q1: Q; m, m1: Memory; i: SigmaIn; o: SigmaOut q states q1 states m memory m1 memory i alphaIn o alphaOut i m dom function o m1 ran function s, s1: Q s states s1 states q function s trans q1 function s1 trans q function = q1 function s = s1 Invariants: a) The set states is a nonempty set. b) The state q0 is an initial memory. c) The memory element m0 is the initial memory. d) For each partial function ((i, m), (o, m1)) where i belongs to input alphabet, o belong to output alphabet, m and m1 of type memory, there exists a transition function trans ((q, function), s) acts on q and a partial function and return a set of states. In the formal specification of nondeterministic stream X-machine the description of the variables states, alphaIn, alphaOut, memory and q0 is same as previously defined in section 5.2. The variable function of type (SigmaIn Memory SigmaOut Memory) is introduced to describe the set of all possible partial functions from (SigmaIn Memory) to (SigmaOut Memory), which receives an input alphabet of type SigmaIn and returns an output alphabet of type SigmaOut by altering the memory. The transition function trans of type (Q function) PQ) is introduced to describe the transitions of the machine for each input (q, function), where q is a state and function is a partial function from (SigmaIn Memory) to (SigmaOut Memory), there must be a unique output q1 of type Q. The initial state q0 is of type Q and m0 is an initial memory of type Memory. 5.6 Design of Stream X-machine A particular class of X-machine is Stream X-Machine which is defined as 9-tuple SXM = (, , Q, M, , F, start, finals, m0) where: 1. is a finite set of input alphabets. 2. is a finite set of output alphabets. 3. Q is a finite nonempty set of states. 4. M is a possibly finite set of memory on which the machine operates. 5. a finite set of partial functions that map an input and a memory state to an output and a new memory state, i. e., : x M x M. 6. F is next state partial function that takes a state and a function from the type and gives next state. F is often described as a transition state diagram, i. e., F: Q x Q. For each state q1 and for every partial function , there is a new state q such that F (q1, ) = q. 7. The start is initial state and m0 is an initial memory. The symbols Q, Memory, SigmaIn and SigmaOut are the fundamental data types respectively. All the 9 tuples of stream X-machine are defined as: states of type Q, alphaIn of type SigmaIn is a set of input alphabets alphaOut of type SigmaOut is a set of possible messages that a machine can send, memory of type Memory which is possibly finite set of memory elements which can be a stack, queue, register, RAM or any type of memory. Set of partial functions is defined as function of type (SigmaIn Memory SigmaOut Memory), each element of function takes an input and memory element and returns a new memory state and message. The trans is the set of transitions of SXM of type (Q function) PQ which takes a function and state, returns a new state and message. The start is the initial state of type Q, and m0 is the initial memory of type Memory. The formal specification of stream X-machine in Z is given below. SXM states: Q alphaIn: SigmaIn alphaOut: SigmaOut memory: Memory function: SigmaIn Memory SigmaOut Memory trans: Q SigmaIn Memory SigmaOut Memory Q q0: Q m0: Memory states q0 states m0 memory q, q1: Q; d, d1: Memory; i: SigmaIn; o: SigmaOut q states q1 states d memory d1 memory i alphaIn o alphaOut i d dom function o d ran function q function dom trans q1 ran trans Invariants: a) The set of states is a nonempty set. b) The q0 is in set states. c) The memory element m0 is in set memory. d) For each partial function ((i, m), (o, m1)) where i belongs to input alphabet, o belongs to output alphabet and m, m1 of type memory there exists a transition function trans ((q, ((i, m), (o, m))), q1) where trans acts on q and partial function ((i, m), (o, m1)) returns a new state q1. 5.7 Design of Path of Stream X-machine A path is a connected sequence of arcs through the machine starting from one state and ending at another, possibly the same one. A successful path is one in which first state is the start state and last state belongs to final states. The behavior of X-machine is defined as the union of all the successful paths. To specify the PATH we declare XSXM which indicates that this is an operation in which the state does not change the values of states, alphaIn, alphaOut, memory, function, transition, q0 and m0 variables respectively. The variable arc of type of power set of (Q Q) is defined to denote the edge from q to q of type Q, and path is introduced to define the sequence of states from q0 to q where q is a final state. PATH XSXM arc: Q Q path: seq Q q, q1: Q q states q1 states sf: seq function; i: i # sf i 1 .. # path i + 1 # path path i states i dom path q function q1 trans q q1 arc path i path i + 1 arc sf i function Invariants: a) If q, q1 belong to states, belongs to and (q1, (q, )) belongs to trans, we say that function is the arc from q to q1, represented function: q q1. If q, q1 belong to Q such that there exist q1,, qn-1 in Q and 1,, n belonging to with 1: q q1, 2: q1 q2,, n:qn-1 q1 we say that we have a path p = 1 n from q to q1 and write p : q q1. 5.8 Design of Stream X-machine Computation The computation of stream X-machine is defined as stream X-machine and paths are accessed as read only which are defined in section 5.5 and 5.6. The input and output streams are defined as streamIn and streamOut of type sequence of SigmaIn and sequence of SigmaOut respectively. The variable epsiI is a nil input alphabet of type SigmaIn and epsiO nil output alphabet of type SigmaOut. SXM_Computation XSXM XPATH streamIn: seq SigmaIn streamOut: seq SigmaOut epsiI: SigmaIn epsiO: SigmaOut epsiI ran streamIn streamIn epsiO ran streamOut ran streamIn alphaIn ran streamOut alphaOut q: Q; m: Memory q states m memory epsiI m epsiO m function q function q trans q: Q; m, m1: Memory; g: SigmaOut; i: 1 i # streamIn i # path i + 1 # path q states m memory m1 memory g alphaOut i = 1 q = q0 q1: Q q1 states q0 q1 arc path i = q0 path i + 1 = q1 streamIn i m g m function q0 function q1 trans streamOut = streamOut g 1 i # streamIn q1: Q q1 states q q1 arc path i = q path i + 1 = q1 streamIn i m g m function q function q1 trans streamOut = streamOut g i = # streamIn q T q1: Q q1 states q q1 arc path i = q path i + 1 = q1 streamIn i m g m function q0 function q trans streamOut = streamOut g Invariants: a) The symbols streamIn and streamOut are the sequences of input and out respectively. b) The symbols epsiI and epsiO are the nil input and output alphabets respectively. c) Each element of input sequence belongs to the set of input alphabets of SXM and each element of output sequence must be from the set of output alphabets of SXM. d) The transition function for each state have the initial value as ((q, epsiI, m), (epsiO, m, q)) which shows it takes no input and gives no output. e) For each state q and q1 which belongs to arc there exists a path from q to q1 which give rise to a new function. f) Each element s of input sequence streamIn acting on memory m will give a new memory m1 and a new output element g which is concatenated with streamOut sequence (streamOut ^ g) at each iteration. In computation of stream X-machine the inputs and outputs are the streams of input and output alphabets. At each state a function is applied, the selection of next state depends upon the first input symbol, memory status and current state. The function computes the new memory state by updating the memory and produces output message which is concatenated at the tail of output stream. The first input alphabet is removed from the head of the input stream. This process continues in this way, while traversing the path and generating the output stream until the input stream is empty and a final state is reached. 5.9 X-Machine Model of an Ant Here we take the biological inspired intelligent agent as case study. The stream X-machine model of ant agent is given in Fig 5.1. The goal of the agent is to find food and carry it to their nest. This goal can be achieved by searching for food at random or follow the pheromone trails. When food is found it should leave pheromone trail moving back to its nest, when nest is found again it drops the food [16]. 1. Input alphabet is defined as ({space, nest} U FOOD) x COORD x COORD). 2. The set of outputs is defined as set of messages {moving_freely, moving_to_nest, dropping_food }. 3. The set of states Q in which agent can be are {At Nest, Moving Freely, At Food, Going Back to Nest, Looking for Food}. 4. Memory M of the agent is (FOOD U {none}) x (COORD x COORD) x sequence (COORD x COORD). 5. Initial memory m0 is defined as (none, (0, 0), nil). 6. Start state q0 is At Nest, (0, 0) is assumed the position of the nest. 7. The type is a set of functions of the form function_name (input_tuple, memory_tuple) (output, memory_tuple). [FOOD] Q ::At_Nest Moving_Freely At_Food Back_to_Nest Looking_for_Food SigmaOut ::moving_freely moving_to_nest moving_to_food lifting_food more_food dropping_food found_nest_again got_lost ignoring_food staying_at_nest FOOD is a basic type, Q is a set of states of an Ant and SigmaOut is a set of messages that an ant can send. Instruction: FOOD Instruction LOC: a, b: 0 a 0 b a b LOC SigmaIn: Instruction LOC SigmaIn LOC is a set of two dimensional locations, and SigmaIn is of type input alphabet which contains instruction and location. The Instruction is the set of all the possible instructions to the agent, which is either the name of a food item, belongs to FOOD or Space. The Space indicates that currently agent have no information about any food item or it have to stay at nest or ignore the food. The second element of each order pair is the location where the agent should have to move. CARRY: FOOD CARRY Memory: CARRY LOC seq LOC Memory Memory is the memory of agent where CARRY shows what the agent is carrying, LOC is the current location of the agent and seq LOC is the list of food items locations. Function: SigmaIn Memory SigmaOut Memory Function is the axiomatic definition of partial function which it gets an input alphabet and a memory element and returns a message as output alphabet and a new memory state by altering the memory. The Function is defined as an abstract data type to define all the possible operations that an Ant can perform. ANT DSXM none: FOOD nest: FOOD space: FOOD lift_food: Function move: Function move_to_food: Function move_to_nest: Function find_food: Function drop_food: Function find_nest: Function gotlost: Function ignore_food: Function stay_at_nest: Function m0 = none 0 0 q0 = At_Nest function = lift_food move move_to_nest move_to_food move_to_nest find_fooddrop_food find_nest gotlost ignore_food stay_at_nest i: Instruction; a, b, x, y: ; c: CARRY; list: seq LOC; o: SigmaOut; in: SigmaIn; m, m1: Memory; fpx, fpy: ; f: FOOD o alphaOut m memory m1 memory in = space x y o = moving_freely m = none a b m1 = none x y in m o m1 = move in = space x y o = moving_to_food m = none a b list m1 = none x y list fpx fpy in m o m1 = move_to_food in = space x y o = moving_to_nest m = f a b list m1 = f x y list in m o m1 = move_to_nest in = f x y o = lifting_food m = none a b list m1 = f x y list m1 = f x y list x y in m o m1 = lift_food in = f fpx fpy o = more_food m = f x y list m1 = f x y list x y in m o m1 = find_food in = nest 0 0 o = dropping_food m = f x y list m1 = none 0 0 list in m o m1 = drop_food in = nest 0 0 o = found_nest_again m = none x y list m1 = none 0 0 list in m o m1 = find_nest in = nest fpx fpy o = got_lost m = none x y fpx fpy m1 = m0 in m o m1 = gotlost in = f 0 0 o = ignoring_food m = none 0 0 list m1 = m in m o m1 = ignore_food in = nest 0 0 o = staying_at_nest m = none 0 0 list m1 = none 0 0 list in m o m1 = stay_at_nest q: Q; f: Function f function q states q = At_Nest f = ignore_food q f q trans q = At_Nest f = stay_at_nest q f q trans q = At_Nest f = move At_Nest f Moving_Freely trans q = At_Nest f = move_to_food q f Looking_for_Food trans q = Moving_Freely f = move q f q trans q = Moving_Freely f = find_nest q f At_Nest trans q = Moving_Freely f = lift_food q f At_Food trans q = Looking_for_Food f = gotlost q f Moving_Freely trans q = Looking_for_Food f = lift_food q f At_Food trans q = Looking_for_Food f = find_nest q f At_Nest trans q = Looking_for_Food f = move_to_food q f q trans q = At_Food f = move_to_nest q f Back_to_Nest trans q = Back_to_Nest f = find_food q f q trans q = Back_to_Nest f = move_to_nest q f q trans q = Back_to_Nest f = drop_food q f At_Nest trans Invariants: a) lift_food, move, move_to_food, move_to_nest, find_food, drop_food, find_nest, gotlost, ignore_food, stay_at_nest are the functions of an Ant. All the functions have the same type as the function of SXM. Each function is an element of function. b) The memory element m0 is an initial memory state which shows that agent carrying nothing currently, its current location is At_Nest and the list of food elements is empty. c) The state q0 is an initial state which is At_Nest. d) The function is the new state of function of SXM which is the set of all the possible actions that an ant can perform. e) All the possible operations an agent can perform are defined as functions in which it takes an input of type Instruction, LOC and a MEMOEY element of type FOOD U {none}, current location of the agent and list of food items, and generates a new memory status by altering the current memory and returns a message. f) For each input in of type (Instruction LOC) in the set of alphaIn of SXM a memory element m in memory of SXM, m1 in new state of memory memory and output alphabet o in set of SigmaOut, there exist a partial function of type Function in function where (in, m) in set domain of function and (o, m1) is in set range of function. g) For each partial function f in function where in is input alphabet, o is output alphabet and m, m1 of type memory, and q, q1 of type Q in set states of an Ant, there exists a transition function trans ((q, f), q1) where trans acts on q and partial function f and returns a new state q1. The SXM imposed all the general constraints that an Ant should posses, but the specific data types and functions of an Ant are different from a general SXM. Therefore there is a need to define all the functions and other required data types which are used in an Ant specification. By using the we can reuse the SXM schema in ANT schema. Further there is no need to redefine all the SXM data types. We only define the following abstract data types SigmaIn, SigmaOut, Memory, Q and functions. The variable none of type FOOD describes that currently the agent is carrying nothing, nest and space of type FOOD indicate where the agent have to move, i. e., either stay at nest of moving freely. All the operations that an agent can perform are define as lift_food, move, move_to_nest, move_to_food, find_food, drop_food, find_nest, goltlost, ingnore_food and stay_ at_nest are of type Function. The formal specification of agent Ant is given below. 5.10 Design of Communicating Stream X-Machine A communicating stream machine is a stream X-machine with the following four different types of functions of type, i: (s, m) = (m, g), where s i, g i, m, m Mi. a). Functions that read the input from the standard input stream and write their output to the standard output stream, i. e., i: (s, m) = (m, g). b). Functions that read the input from a communication input stream and write their output to the standard output stream, i. e., i: (sj, m) = (m, g). c). Functions that read the input from the standard input stream and write their output to a communication output stream, i. e., i: (s, m) = (m, gk). d). Functions that read the input from a communication input stream and write their output to a communication output stream, i. e., i: (sj, m) = (m, gk). These functions are named as SISO, ISSO, SIOS and ISOS which are defined below. SISO: SI is the standard input stream and SO is the standard output stream. The function SISO read the input from the standard input stream and write their output to the standard output stream, i. e., SISO: ((s, m) = (m, g). ISSO: IS is the input stream of another machine j and SO is the standard output stream. The function ISSO read the input from a communication input stream and write their output to the standard output stream, i. e., ISSO: (sj, m) = (m, g). SIOS: SI is the standard input stream and OS is the communicating output stream. The function SIOS read the input from standard input stream and write their output to communicating output stream k, i. e., SIOS: (s, m) = (m, gk). ISOS: IS is the communicating input stream and OS is the communicating output stream. The function ISOS read the input from communicating input stream j and write their output to communicating output stream k, i. e., ISOS: (sj, m) = (m, gk). The formal specification of communicating stream X-machine is described in schema CSXM. CSXM DSXM SISO: SigmaIn Memory SigmaOut Memory SIOS: SigmaIn Memory SigmaOut Memory ISSO: SigmaIn Memory SigmaOut Memory ISOS: SigmaIn Memory SigmaOut Memory ist: seq SigmaIn ost: seq SigmaOut is: seq seq SigmaIn os: seq seq SigmaOut ist ran is ost ran os function = SISO SIOS ISSO ISOS i: ; isq: seq SigmaIn i 1 i isq is j: 1 j j # isq isq j alphaIn i: ; osq: seq SigmaOut i 1 i osq os j: 1 j j # osq osq j alphaOut i, j, k: 1 i i # ist 1 j j # ost 1 k k j m, m1: Memory; sq: seq SigmaIn; gq: seq SigmaOut m memory m1 memory sq ran is sq = ist gq ran os gq = ost # sq I # gq i sq i m dom SISO gq i m1 ran SISO m, m1: Memory; sq: seq SigmaIn; gq: seq SigmaOut m memory m1 memory sq ran is sq = ist gq ran os # sq I # gq k sq i m dom SIOS gq k m1 ran SIOS m, m1: Memory; sq: seq SigmaIn; gq: seq SigmaOut m memory m1 memory sq ran is gq ran os gq = ost # sq j # gq i sq j m dom ISSO gq i m1 ran ISSO m, m1: Memory; sq: seq SigmaIn; gq: seq SigmaOut m memory m1 memory sq ran is gq ran os # sq j # gq k sq j m dom ISOS gq k m1 ran ISOS Invariants: a) The ist belongs to the range of is. b) The ost belongs to the range of os. c) The function is the new state of set of functions which is the union of the above mentioned four types of functions. d) Each element of each communicating input stream is in the set of input alphabets alphaIn. e) Each element of each communicating output stream belongs to the set of output alphabets alphaOut. f) For each input and output there exist m belongs to memory and m1 belongs to new state of memory memory. For each i, j and k are integers from 1 to the length of input sequence, there exists m and m memory elements and if gq and sq belong to standard output and input streams then (sq i, m) belongs to domain of SISO and (gq i, m1) belongs to range of SISO. If gq belongs to communicating output stream k then (sq i, m) belongs to domain of SIOS and (gq k, m1) belongs to range of SIOS. Whenever sq belongs to communicating input stream j then (sq j, m) belongs to domain of ISSO and (gq i, m1) belongs to range of ISSO, further when sq and gq are communicating input and output streams j and k respectively then (sq j, m) belongs to domain of ISOS and (gq k , m1) belongs to range of it. The formal specification of communicating stream X-machine is same as stream X-machine except these four functions. So, we reuse the specification of SXM and define these four functions and relationship between communicating functions and SXM which becomes a CSXM. Data and communication are modeled separately, data is modeled in SXM and communication is modeled in CSXM which provide the benefit of reusability of SXM models. The variables SISO, SIOS, ISSO and ISOS of (SigmaIn Memory) (SigmaOut Memory) are defined to describe the four different combinations of input and output streams. The ist and ost are the standard input and out streams of type sequence of SigmaIn and sequence of SigmaOut respectively. The variable is is introduced to define the sequence of input streams of type sequence of SigmaIn and os is defined to describe the sequence of output streams of type sequence of SigmaOut. 5.11 Design of Communicating Stream X-machine System A communicating X-machine system consists of a number of X-machines that can exchange messages with each other. A CSXMS is defined as Z= ((Ci)i=1,, n, CR) where: 1. Ci is a i-th communicating X-machine component. 2. CR is a relation which defines the communication between the communicating X-machine components, i. e., CR C C and C = {C1, , Cn}. A tuple (Ci, Ck) CR denotes that the X-machine component Ci can output a message to a corresponding input stream of the X-machine component Ck for any i, k {1, . . . , n}, i k. Z C: CSXM CR: CSXM CSXM c, c1: CSXM c C c1 C c c1 CR c c1 m, m1: c . memory; s: SigmaIn; g: SigmaOut s ran c . ist g ran c . ost s m dom c . SISO g m1 ran c . SISO m, m1: c . memory; s: SigmaIn; g: SigmaOut s ran c . ist g ran c1 . ost s m dom c . SIOS g m1 ran c . SIOS m, m1: c . memory; s: SigmaIn; g: SigmaOut s ran c1 . ist g ran c . ost s m dom c . ISSO g m1 ran c . ISSO m, m1: c . memory; s: SigmaIn; g: SigmaOut s ran c1 . ist g ran c1 . ost s m dom c . SIOS g m1 ran c . SIOS Invariants: For each c and c1 of type CSXM where (c, c1) is in relation CR, there exists m, m1 of type memory of machine c. Input and output alphabets s and g are of type SigmaIn and SigmaOut respectively. If s belongs to the range of standard input stream ist of machine c and g belongs to the range of standard output streams ost of machine c then the partial function (s, m), (g, m1) belongs to function SISO. Further if g belongs to the output stream of machine c1 then the partial function (s, m), (g, m1) belongs to SIOS. Similarly, if s belongs to the input stream of machine c1 then the partial function (s, m),(g, m1) belongs to ISSO, otherwise the partial function (s, m), (g, m1) belongs to ISOS. The formal specification of CSXMS is described in schema CSXM where we introduced a variable C of type power set of CSXM to define a set of communicating stream X-machines. CR is a relation of type power set of (CSXM CSXM), where c and c1 are communicating stream X-machines which can communicate with each other. 5.12 Traffic Control System We take the case study of traffic control system to use the complete proposed formal modeling technique on an agent-based system. The case study is selected to demonstrate the applicability of the integrated formal modeling approach. This is accomplished by using the traffic control system which is derived from an original text written in [4]. The traffic control system is composed of the following components, queue of cars, traffic signal lights and controller as illustrated in Fig 5.1. The scenario of the problem is as follows: a) To make sure the safe depart of the cars that arrive at the traffic junction. b) The cars are waiting in the queue to depart. If the signal is red then cars wait until the signal becomes green. c) When a new car arrives it is added at the tail of the queue and when a car leaves it leaves from the front of the queue. 5.12.1 Components of the System The traffic control system is composed of the following components called agents. a) Traffic queue agent b) Traffic signal agent and c) Controller agent. 5.12.2 Traffic Queue Agent The traffic queue agent is characterized by following elements. a) A queue of traffic holds the sequence of cars arrived at the junction. b) Traffic arrived at queue are added at the tail of the queue. c) Traffic leaves the queue when signal is green. d) Make sure the safe depart of traffic at the junction. The X-machine model of traffic queue is illustrated in Fig. 5.2, where the input set of X-machine is: = {arrive, leave}. The input alphabet is a composite type that contains an input and a car. The output of the system consists of a set of messages that may displayed on the screen = {FirstArrived, NextArrived, CarLeft, LastCarLeft, NoCarInQueue}. The set of states is: Q= {empty, queuing}. The machines memory M is a sequence of cars. The set of function is {first_arrives, arrives, leaves, last_leaves, reject}. TrafficQueue DSXM first_arrives: FUNCTION arrives: FUNCTION leaves: FUNCTION last_leaves: FUNCTION reject: FUNCTION q0 = empty m0 = function = first_arrives arrives leaves last_leaves reject i: Input; c: CAR; g: SigmaOut; s: SigmaIn; m, m1: Memory i c SigmaIn s SigmaIn m memory m1 memory s = arrive c m = m0 m1 = c s m FirstArrived m1 = first_arrives s = arrive c m m0 m1 = m c s m NextArrived m1 = arrives s = arrive head m m m0 m1 = tail m s m CarLeft m1 = leaves s = arrive head m m m0 m1 = m0 s m LastCarLeft m1 = last_leaves s = arrive c m = m0 m1 = m0 s m NoCarInQueue m1 = reject q: Q; f: FUNCTION q states f function q = empty f = first_arrives q f queuing trans q = queuing f = arrives q f queuing trans q = queuing f = leaves q f queuing trans q = queuing f = last_leaves q f empty trans q = empty f = reject q f empty trans Invariants: a) The state Empty is the start state. b) Initial memory is an empty sequence of cars. c) The function is the new state of functions of queue. d) All the functions of X-machine take an input alphabet and memory element and return a message by altering the memory value. e) All the transitions of the machine take a state and a function and return a new state by altering the memory, read the input and return a message. [CAR] Q ::empty queuing Input ::arrive leave SigmaOut ::FirstArrived NextArrived CarLeft LastCarLeft NoCarInQueue Memory: seq CAR SigmaIn: Input CAR Function: SigmaIn Memory SigmaOut Memory CAR is a fundamental data type and Input is of type instruction. Memory is a set of sequences of cars. SigmaIn of type power set of (Input CAR), which contains an instruction and a car. Function is an abstract type of function which is defined to describe the functions of the queue. To define all the tuples of queue we reuse the general specification of stream X-machine SXM as defined in section 5.5. The formal specification of X-machine of a queue is presented above using Z notation. The function of the machine takes an input alphabet and a memory element, and returns output alphabet and new memory state. In the formal specification of traffic queue agent, we write SXM to denote the schema SXM that defines all the tuples of the general stream X-machine. The variables first_arrives, arrives, leaves, last_leaves and reject are the functions of type Function which traffic queue agent can perform. 5.12.3 Communicating Traffic Queue Agent The previously defined X-machine of a queue of cars can communicate with signal light in such a way: when the traffic light becomes green, the queue is notified to leave a car, and cars can depart one by one until there is least one car in the queue. More cars can arrive to the queue, waiting for a signal to depart. Whenever there is a green signal from the traffic light but there is no car in the queue the machine ignores the signal. Functionality of the communicating X-machine is defined as: The first_arrives and arrives functions read from standard input stream and write on standard output streams. The functions leaves, last_leaves and reject read from the communication stream of signal light instead of standard input stream and write the output to the standard output stream of TrafficcQueue. In this way every car leaves the queue whenever thers is a message from the signal light to leave that makes sure the safe depart of the car from junction. It may also write to a communicating input stream of another X-machine. The normal output of the functions is not affected. The definition of function in TrafficQueue changes from that in the definition of CommTrafficQueue. To specify the communicating traffic queue agent we reused the specification of TrafficQueue and CSXM schema. There is only need to define the communicating functions of the machine through which it can communicate with other agents of the system. CommTrafficQueue XTrafficQueue DCSXM SISO = first_arrives arrives SIOS = SIOS ISSO = leaves last_leaves reject ISOS = ISOS is = is os = os Invariants: a) In communicating X-machine of traffic queue, the definition of functions first_arrives and arrives remain same. The set of function SISO which read from and write on standard input and output streams respectively. It becomes SISO which contains two functions first_arrives and arrives. b) The definition of functions leaves, last_leaves and reject are changed as it reads from communication input stream and writes on standard output stream. The set of functions ISSO contains three function leaves, last_leaves and reject. c) The set of functions SIOS and ISOS remains same as SIOS and ISOS. d) The standard input and output streams is and os remains unchanged as is and os. 5.12.4 Traffic Light Agent A traffic light agent is characterized by the following elements: a) Two light signals red and green, b) Holds the total number of ticks elapsed since the last change of signal, c) Holds the number of ticks that a signal should be displayed, d) Holds the number of ticks before start the working and e) Switch between the signals. All the tuples of X-machine of traffic light agent are defined as: a) Set of input alphabets is a set of time unit called ticks. b) A set of output alphets = {Red, Green, Statrup}. c) The memory of the agent is defined as: (timeelapsed, delay, DurGreen, DurRed), where timeelpased shows the number of ticks elapsed since last signal changed, delay defines the times required to start, and DurGreen and DurRed are used to define the period of a signal to be displayed respectively. d) The set of functions of the agent are defined as: function = {delay, change_green, keep_green, change_red, keep_red}. The functions are activated by reading the input of type TICK. e) The transition functions of the agent are illustrated in Fig 5.4. f) The set of states is defined as = {red, green}. g) The state red is an initial state and m0 is the initial memory of agent. Q ::red green SigmaOut ::RedColour GreenColour StartUp Memory: i, j, k, l: 0 i 0 j 1 k 1 l i j k l Memory SigmaIn: TICK TICK is the abstract data type which is introduced to define the set of input alphabet SigmaIn of type power set of TICK. A TICK indicates a clock tick. Q is the set states of the agent. Memory is a set of possible memory elements of the agent which is defined as a power set of type (Z Z Z Z), where Z is a non negative integer value. To formally specify the traffic light agent we reuse the specification of SXM which defines all the tuples of the agent. Here we only define the particular functions of the agent which are delay, change_green, change_red, keep_green and keep_red of type Function. TrafficLight DSXM delay: Function change_green: Function change_red: Function keep_green: Function keep_red: Function q0 = red m0 = 0 20 60 40 function = delay change_green change_red keep_green keep_red g: SigmaOut; s: SigmaIn; m, m1: Memory; w, x, y, z: s alphaIn g alphaOut m memory m1 memory 0 w 0 x 1 y 1 z w x y z Memory m = m0 x 0 x = x 1 m1 = w x y z s m StartUp m1 = delay w z w = w + 1 m1 = w x y z s m RedColour m1 = keep_red w y w = w + 1 m1 = w x y z s m GreenColour m1 = keep_green w = z m1 = 0 0 y z s m GreenColour m1 = change_green w = y w = w + 1 m1 = 0 0 y z s m RedColour m1 = change_red q: Q; f: Function q states f function q = red f = keep_red q f red trans q = red f = change_green q f green trans q = red f = delay q f red trans q = green f = keep_green q f green trans q = green f = change_red q f red trans q = green f = delay q f green trans Invariants: a) The state red is the start state. b) Memory is initialized as (0, 20, 60, 40). c) The function is the new state of functions of traffic light. d) All the functions of x-machine are defined as: it takes an input alphabet and memory element and returns a message by altering the memory value. The transition of the machine takes a state and a function and returns a new state by altering the memory, read an input and write an output. 5.12.5 Communicating Traffic Light Agent A communicating traffic light agent communicates with traffic queue agent and controller agent. It sends a message to traffic queue agent which will be an input to the agent. It receives messages from controller agent to switch the signal as illustrated in Fig 5.5. The change_green function receives a message from controller and changes the signal from read to green and send a message to traffic queue agent to allow the cars to leave the queue one by one. It is assumed that one car leaves the queue in one tick. The change_red function receives a message from the controller agent and writes on its standard output stream. In formal specification of communicating traffic light agent the specification of stand alone light agent is reused to define the communicating agent. Further predefined specification of abstract communicating stream X-machine is also reused which defines the communicating functions of the agent. The formal specification of communicating traffic light agent is given below. CommTrafficLight XTrafficLight DCSXM SISO = delay keep_red SIOS = keep_green ISSO = change_red ISOS = change_green is = is os = os Invariants: a) In communicating X-machine of traffic light, the definition of functions delay and keep_red remain same. The set of functions SISO which reads and writes on standard input and output streams respectively becomes SISO that contains two functions delay and keep_red. b) The definition of functions keep_green is changed as it reads from standard input stream and writes on communication output stream. The set of functions SIOS contains a function keep_green. c) The set of functions ISSO and ISOS contains function change_red and change_green respectively. d) The standard input and output streams is and os remain unchanged as is and os. 5.12.6 Controller Agent The controller agent is used to control a number of traffic light agents. In our case study we assume that there are four traffic light agents with their corresponding traffic queue agent and hence there must be a need of controller that controls the light agents. The controller agent controls the multiple light agents by scheduling on the basis of round robin scheduling technique as illustrated in Fig 5.6. The controller is also responsible for the synchronization and allocation of time share to traffic lights. Q ::schedule_light1 schedule_light2 schedule_light3 schedule_light4 Memory: SigmaOut: SigmaIn ::clock_pulse switch_device Q is the set of states which contains schedule_light1, schedule_light2, schedule_light3 and schedule_light4. Memory and SigmaOut are of type power set of natural numbers. SigmaIn is a set of input alphabets which contains clock_pulse and switch_device. Controller DSXM operate: FUNCTION switch: FUNCTION q0 = schedule_light1 m0 = 0 function = operate switch g: SigmaOut; s: SigmaIn; m, m1: Memory s alphaIn g alphaOut m memory m1 memory s = clock_pulse g = m + 1 m1 = m + 1 s m g m1 = operate s = switch_device g = m m1 = m s m g m1 = switch q: Q; f: FUNCTION q states f function q = schedule_light1 q operate schedule_light1 trans q = schedule_light1 q switch schedule_light2 trans q = schedule_light2 q operate schedule_light2 trans q = schedule_light2 q switch schedule_light3 trans q = schedule_light3 q operate schedule_light3 trans q = schedule_light3 q switch schedule_light4 trans q = schedule_light4 q operate schedule_light4 trans q = schedule_light4 q switch schedule_light1 trans Invariants: a) The state schedule_light1 is the start state. b) Memory is initialized as (0). c) The variable function is the new state of functions of controller agent. d) All the functions of x-machine are defined as: it takes an input alphabet and memory element and returns a message by altering the memory value. All the transitions of the machine take a state and a function and return a new state by altering the memory, read an input and write an output. The formal definition of controller agent is defined as: The set of input alphabets = {clock_pulse, switch_light}. The output alphets are defined as a set of natural numbers. The memory of the agent is defined as a set of natural numbers. The set of functions of the agent are defined as: function = {operate, switch}. The transition functions of the agent are illustrated in Fig 5.4. The set of states is defined as {S1, S2, S3, S4}, where S1, S2, S3 and S4 are the instances of the traffic light agent. S1is the initial state and (0) is the initial memory of agent. 5.12.7 Communicating Controller Agent The communicating controller agent communicates with traffic lights to change the signal. It sends message tick to light agent and receives the message switch_device from the traffic light agent which provides a synchronization mechanism. In formal specification of communicating controller agent, the predefined stand alone controller agents specification is reused to define the communicating controller agent. Further predefined specification of abstract communicating stream X-machine is also reused which defines the communicating functions of the controller agent. The formal specification of communicating traffic light agent is given below. ComController XController DCSXM SISO = operate SIOS = SIOS ISSO = ISSO ISOS = switch is = is os = os Invariants: a) In communicating X-machine of controller agent the function operate remains same as defined in CSXM. The set of functions SISO which read from and write on standard input and output streams respectively becomes SISO that contain a function operate. b) The definition of function switch is changed as it reads from standard input stream and writes on communication output stream. The function ISOS contain a function switch. c) The set of functions SIOS and ISSO remain unchanged. d) The standard input and output streams is and os remain unchanged as is and os. 5.11.8 Agent based Traffic Control System The agent-based traffic control system (ABTCS) consists at a controller agent and four traffic light agents with corresponding traffic queue agents. The controller agent switches the signals of the traffic light agents. The traffic light agent communicates with controller agent and also with its corresponding traffic queue agent. The traffic queue agent only communicates with a single traffic light agent. To formally specify the ABSTCS we redefine the communicating stream X-machine system because there are three types of agents which communicate with each other. Therefore the existing definition cannot be used to define the ABTCS. In schema TrafficControlSystem the variables C1 of type power set of CommTrafficQueue is introduced to define the set of communicating traffic queue agents, C2 of type power set of CommTrafficLight to describe the set of communicating traffic light agents and C3 of type ComController to introduce the communicating controller agent. The variable CR is defined as a relation of type (CommTrafficQueue CommTrafficLight ComController) which defines a relationship between traffic queue agent, light agent and controller agent and provides a mechanism in which they can exchange messages. TrafficControlSystem C1: CommTrafficQueue C2: CommTrafficLight C3: ComController CR: CommTrafficQueue CommTrafficLight ComController cq: CommTrafficQueue; cl: CommTrafficLight; cc: ComController cq C1 cl C2 cc C3 cq cl cc CR In the above specification the invariant is defined as for all cq of type CommTrafficQueue, cl of type CommTrafficLight and cc of type ComController such that cq belongs to C1, cl belongs to C2 and cc belongs to C3 which holds that (cq,cl, cc) belongs to relation CR which indicates that these three agents can communicate with each other. To specify the ABTCS we introduced the variables queue1, queue2, queue3 and queue4 to define the four queue agent of type communicating queue agents. Similarly, light1, light2, light3 and light4 are introduced to describe the four traffic light agents which can communicate with other agents of the system. The controller agent is defined as controller. The variables nilq, nils and nilc are introduced to define the null value of sets C1, C2 and C3. This specification shows that we are not defining all the agents from scratch we just specify a single agent of one type and then we can create instance of these agent with different initial memory values an d start state according to the requirements. AgentBasedTrafficControlSystem DTrafficControlSystem queue1, queue2, queue3, queue4, nilq: CommTrafficQueue light1, light2, light3, light4, nils: CommTrafficLight controller, nilc: ComController queue1 . q0 = empty queue2 . q0 = empty queue3 . q0 = empty queue4 . q0 = empty light1 . q0 = green light2 . q0 = red light3 . q0 = red light4 . q0 = red light1 . m0 = (0, 0, 20, 60) light2 . m0 = (0, 20, 20, 60) light3 . m0 = (0, 20, 20, 60) light4 . m0 = (0, 20, 20, 60) queue1 . m0 = queue1 . m0 = queue1 . m0 = queue1 . m0 = C1 = {queue1, queue2, queue3, queue4, nilq} C2 = {light1, light2, light3, light4, nils} C3 = {controller, nilc} Invariants: a) In this specification we define the four instance of traffic queue agent. The initial state q0 and initial memory m0 of all the traffic queue agent is initialized by empty and empty sequence respectively. b) The initial state q0 of traffic light agent light1 is initialized by green which means that when the system starts the signal of traffic light1 must be green and the signal of the remaining light agent light2, light3 and light 4 must be read. c) The initial memory m0 of traffic light agent 1 is set to (0,0,20,60) which shows that at the startup it immediately starts working without waiting a single tick, it must remains green and red till 20 and 60 ticks respectively. d) The traffic light agents light2, light3 and light4 are defined with initial memory (0, 20, 20, 60). e) The set of communicating traffic queue agents is changed from C1 to C1 and consists of queue1, queue2, queue3 and queue4 agents. f) The set of communicating traffic light agents is changed from C2 to C2 and consists of queue1, queue2, queue3 and queue4 agents g) C3 the set of controller agents contains a single agent controller.