The geometrical visualisation is through the following picture:

n-Ex =1,x =Mx =1,x =i j i j x i x j Mx =0,x =i j Mx =1,x =i j n-Ex =1,x =n-i j Ex =0,x =i j n-Ex =0,x =i j It follows from the above theorem that the steepest vectors of each layer L, Lmin L Lmax of n provide m+the description of all vectors from belonging to that layer.

m 5. Description through the Boundary Steepest Elements On one hand, can be described through the set of all upper boundary vectors, and on the other hand - m through the set of all “steepest” vectors. Below we prove that can be described having only the intersection m of these two sets – which is the set of all “boundary steepest” vectors.

The theorem below states that if some layer of n contains more than one upper boundary vector, then only m+the steepest ones of them are necessary for the description of, or the same – if among the steepest vectors m are both boundary and non-boundary, then only the boundary ones are necessary to describe the whole set of partitioning characteristic vectors.

Theorem 2. If a layer of contains a boundary vector, then it can be obtained by operations of flattening from m only an other boundary vector.

The theorem has been proved by contradiction, considering all possible cases.

Fourth International Conference I.TECH 2006 Conclusion Any set system can be represented as a subset of n -cube vertices set. For a given subset it is important to know the partition sizes, - the coordinates of partitioning characteristic vectors. Smaller generating sets are known as “boundary” and “steepest” sets and finally we prove that the intersection of these two sets is also generating for the partitioning characteristic vectors.

Bibliography [S, 1997] H. Sahakyan. On a class of (0,1)-matrices connected to the subsets partitioning of En, Doklady NAS Armenia, v. 97, 2, 1997, pp. 12-16.

[B, 1988] Billington D., Conditions for degree sequences to be realisable by 3-uniform hypergraphs”. The Journal of Combinatorial Mathematics and Combinatorial Computing”. 3, 1988, pp. 71-91.

[D, 1999] Durr Ch., Chrobak M., Reconstructing hv-convex polyominoes from orthogonal orojections. Information Processing Letters 69 (1999) pp. 283-291.

[R, 1966] H. J. Ryser. Combinatorial Mathematics, 1966.

[H, 1997] G.T. Herman and A. Kuba, editors. Discrete Tomography: Foundations, Algorithms and Applications. Birkhauser, 1999.

[B, 1996] E. Barcucci, A. Del Lungo, M. Nivat, and R. Pinzani. Reconstructing convex polyominoes from horizontal and vertical projections. Theoret. Comput. Sci., 155:321{347, 1996.

[W, 2001] G.J. Woeginger. The reconstruction of polyominoes from their orthogonal projections. Inform. Process. Lett., 77:225{229, 2001.

Author’s Information Hasmik Sahakyan – Institute for Informatics and Automation Problems, NAS Armenia, P.Sevak St. 1, Yerevan-14, Armenia; e-mail: hasmik@ipia.sci.am A HW CIRCUIT FOR THE APPLICATION OF ACTIVE RULES IN A TRANSITION P-SYSTEM REGION Victor J. Martinez, Luis Fernandez, Fernando Arroyo, Abraham Gutierrez Abstract: P systems or Membrane Computing are a type of a distributed, massively parallel and non deterministic system based on biological membranes. They are inspired in the way cells process chemical compounds, energy and information. These systems perform a computation through transition between two consecutive configurations. As it is well known in membrane computing, a configuration consists in a m-tuple of multisets present at any moment in the existing m regions of the system at that moment time. Transitions between two configurations are performed by using evolution rules which are in each region of the system in a non-deterministic maximally parallel manner.

This work is part of an exhaustive investigation line. The final objective is to implement a HW system that evolves as it makes a transition P-system. To achieve this objective, it has been carried out a division of this generic system in several stages, each of them with concrete matters. Within this division, in this paper the stage is developed by obtaining the part of the system that is in charge of the application of the active rules. These ones have been reached in a previous circuit [Fernndez, 2005b] and they become the input to this circuit.

Keywords: Membrane Computing, Evolution Rules, Circuit design, Digital systems, Transition P System.

Information Models Introduction The Membrane Computing or P Systems (created by [Pun, 1998]) are computation systems based on the biomolecular processes of living cells. According to this, the investigations are based on the idea that the imitation of the procedures that take place in Nature and their application to machines, can lead to discover and to develop new computation models that will give place to a new generation of intelligent computers. These systems perform a computation through transition between two consecutive configurations. Transitions between two configurations are performed by using evolution rules present in each region. If the system reaches a configuration in which there are no applicable rules at any membrane, it is said that the system reaches a halting configuration and, hence, the computation is successful.

There are many papers about software tools implementing different P-system variants [Arroyo 2003], [Arroyo 2004b] and [Fernandez, 2005a]. However, they are very interesting in order to define hardware implementation of these kinds of systems. Moreover, evolution of transition P- systems is very complicate to translate into hardware devices due mainly to the membrane dissolving or membrane division capabilities of rules. Besides that, the nondeterministic maximally parallel manner in which rules are applied inside membranes is much appropriated to be implemented in digital hardware devices. In the case of P-systems hardware implementations only can find a few of papers: a Hardware Circuit for Selecting Active Rules [Fernandez 2005b], connectivity arrays for membrane processors [Arroyo 2004a], a multisets and evolution rules representation in membrane processors [Arroyo 2004b] or even a hardware membrane system description using VHDL [Petreska 2003].

This work is a part of a very ambitious project: to find and carry out a Hardware System able to simulate P systems evolution. This generic system has been divided into several stages. The first stage one develops a circuit able to determine active rules in a determined configuration for the membrane [Fernndez 2005b]. In this document, the second stage is developed: as a circuit for the application of the active rules obtained in the first stage.

In order to proceed in an appropriate way, it is needed to define a data structure containing information about the initial membrane state, that is, the initial multiset of objects, the set of evolution rules and the corresponding priority relation among them. The circuit takes these data inputs and produce, as output, a set of evolution rules, active rules, which are able to produce the needed changes into the system in order to make evolve it to into the next configuration. Obviously, there are some needed constrains for the hardware design, and they are the following:

a. The cardinality O = {a,b,c,d,e,f,g,h,i,j} of the alphabet is limited to 10.

b. The multiset of objects associated to the membrane i, i. It is represented in a hardware register of 4bits words of length 10.

c. The finite set of evolution rules Ri associated to the membrane I (10 per membrane).

d. The priority relation among the rules Ri.

i e. Extra information to determine applicability of rules: existence register, for determining whether or not there exist children membranes for the next evolution step.

Therefore, the previous Circuit for Selecting Active Rules determine which of the evolution rules present inside a membrane are active (in binary positive logic) accordingly to the multiset of objects present in the membrane.

The objective of the work that now shows up will consist in obtaining a HW circuit that indicates the rules to be applied to a Transition P System. The inputs are the following registers: multiset of objects associated to the membrane i; Evolution Rules antecedents and Initial Active Rules. The output will be a register that contains the number of times that each rule (See Fig.1) should be applied. These values associated to each rule will serve to carry out, in a later process, the communication of elements among regions.

Fourth International Conference I.TECH 2006 Fig. 1: General structure of the circuit for Application of Active Rules.

Application of the Active Rules The application of the active evolution rules is a repetitive process that can be carried out in different ways.

The paper [Fernandez, 2006] allows us to obtain circuits or systems optimized as for level of complexity and resources utilization. A first option to apply the rules could consist on the step-by-step application of the group of active rules. In this case, we choose in an aleatory way a single time each rule until draining all the possible applications.

However, it can be proven that one obtains the same result if we apply an evolution rule a certain number of times. The maximum number of times a rule can be applied into a multiset i of state of the cell in an evolution step will be called "value MAX." This value is obtained considering that you apply only this rule, that is to say, without keeping in mind the other rules.

The following example illustrates the concept of value MAX: If we have a multiset of objects =a10b5c7 and the i following active rules R =a1, R =b2c and R =bc2;el value MAX of R is 10, the value MAX of R is 2 and the value 1 2 3 1 MAX of R is 3.

The fact of applying a rule a value bigger than one implies that it consumes, in an evolution step, a bigger number of elements from the multiset. Hence, the whole process requires a minor number of steps and, therefore, the end of the process will be reached in a shorter length of time. The following pseudo-code sequence illustrates the necessary process to obtain the number of times that each active rule should be applied in a region:

(1) R InitialActiveRules (2) BEGIN (3) DO (4) ri Aleatory(R) (5) MAX Applicability(ri,) (6) N Aleatory(1,MAX ) (7) ( -(N Antecedent(ri))) (8) counts(N,ri) (9) R ActiveRules (10) WHILE | R | (11) END Information Models Explanation of the algorithm:

• (1)The process uses the group of active available rules initially R.

• (4)At each iteration, one of the rules ri of this group will be applied. Such rule will be randomly obtained.

• (5)On the selected rule, the value of applicability MAX is obtained and it is applied with an aleatory multiplicity N between 1 and the value MAX(6) • (7)The application of selected rule ri will consist in subtracting from the starting multiset, the values of the antecedent elements multiplied by the value N of rule application. In turn, we will increase N times the particular accountant that counts the number of times that rule has been applied (8).

• (9)On the new obtained multiset it has been proved again the applicability of the available rules.

• (10)Every time the group of applicable rules is upgraded, the end of the process has been controlled. The stop condition is obtained when the number of applicable rules is zero. While R is bigger or the same as the unit, it executes, once more, a new iteration of the process.

Basic Functional Units (F.U.) This section defines the previous step to design the complete circuit of active rules application to the evolution of a transition P system. It will consist on obtaining certain basic operative functional units. These functional units will solve each one of the simple tasks needed to obtain the complete application. The design of the final circuit will be based on the assembling of these modules together with the corresponding combinational and sequential logic which allows their integrated operation.

Applicability MAX F.U.:

In this case, we will obtain the design of the circuit that obtains the MAX applicability of a rule. This value supposes the largest number of times that a rule can be applied independently of the other ones. To do so, we will only keep in mind the multiplicities of their elements and the multiplicities of the elements of the multiset.

Therefore, the inputs into this circuit will be two registers: one with the content of the values of the multiset of state of the membrane and another with the antecedent of the rule we want to get their value MAX. The output will be the value MAX of this rule.

To obtain this value we should carry out the division among each couple of elements similar of the multiseti with ri. From each division, we will participated the maximum that will represent the largest number of times that mentioned element could be consumed in an evolution step without bearing in mind the other elements. We will take the smallest value out of all the partial results of these divisions.

1 Aleatory Active Rule F.U.

This circuit will randomly select a rule from the ActiveRules register to be applied. The ActiveRules register contains binary values indicating, with positive logic, the active rules from existing rules of the system. The output of this circuit will be a register in which only one rule will be randomly selected. One input Enable “E” will activate the starting of the clock that attacks the random generator. This generator will select decimal numbers aleatory in a serial way until getting some one that corresponds with the number of the active rule. When this value is obtained, the aleatory number generation should stop.

The main part of the circuit will be a 1 bit Decimal Multiplexer. The selection inputs of the Multiplexer correspond with the outputs from the Decimal aleatory generator. This generator will stop when some of the outputs of the Multiplexer are set to 1. The position that indicates this output corresponds with the randomly selected active rule.

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.