GIS and vector cadastral map : a tool to detect and study roman cadastral frames

The french Rhône valley has traces of ancient roman parcels, testi ed by antique land registers 1ABCD called "Orange cadastre". This organization was highlighted on the left bank of the river. It seems to extend to the other side, in the Tave and Cèze valleys 1E. All these researches were conducted in the 80's from IGN (French National Institute of Cartography) aerial missions, with the method of optical ltering 2. In this study, we intend to use a GIS and the cadastral map in vector format 3C. Indeed, the cadastre enables the study of limits that have no materialization in the current landscape. The aerial photographs 3A or topographical maps 3B only give incomplete information, i.e. the perennial human forms: roads, paths, fences, channels, ditches. These documents are selective. The tool used in this study is the histogram of directions. It consists in calculating the azimuth of each parcel boundary 4 and drawing a histogram : the number of boundaries or their total length are shown as a function of azimuth 5. The interests of working with the cadastre are all information contained in these documents, whose precision allows a detailed study of cadastral frames. This method was rst validated on previously studied areas 6 and then extended to the Cèze and Tave lower valleys 7. This helped to detect the presence of "Orange cadastre" in these two valleys 8, where the method by optical ltering had not delivered convincing results. The use of these vector data for the detection of ancient cadastral frames remains to this day unique in France. However its implementation is simple and permits a detailed study of the boundaries structure. The results are encouraging and allow considering new approaches. It would be interesting to combine elevation and topographic data as well as ancient "Napoleonic cadastre", in the aim to eliminate 19th and 20th century boundaries. This will be the next step of this work.

F o r mul e Az i mut h

A_z = G_t -%gamma=arctan left ({E_2-E_1} over {N_2-N_1} right )-%gamma

A z =G t -γ=arctan ( E 2 -E 1 N 2 -N 1 ) -γ

  Antique land registers and the study area. A -«Orange A» land register (red), B -«Orange B» and «Orange B extended» land registers (blue), C -«Orange C» land register (green), D -«Orange D» land register (yellow), E -Cèze and Tave valleys. BDAlti®, © IGN ; M. Seguin, Inrap 2 Optical ltering «Orange B» orientations ltering from aerial photographies between Orange (Vaucluse) and Donzère (Drôme). A -Aerial photographies (IGN 1970 3040, n° 1 and 3 ; 1970, 3039, n° 13 and 16), B -Filtered images with roads and paths resulting. © P.-Y. Baurès, Optical laboratory -University of Besançon (Doubs, France) 3 Documentation A -Aerial photographies (BDOrtho®, © IGN), B -Topographical maps (Scan25®, © IGN), C -Cadastral maps (BDParcellaire®, © IGN). 4 Azimuth formula 5 Histogram of directions Number of boundaries function of azimuth in the Céze and Tave valleys 6 Assessment A -Perterson's results (around Bagnols-sur-Cèze), B -Cadastral map after ltering. J.W.M. Peterson 1992; BDParcellaire®, © IGN, M. Seguin,

Valleys Communes number of boun- daries cumulative length (m) number of boundaries isoclines B cumulative length of boun- daries isoclines B (m) % boundaries isoclines B % cumulative length isoclines B

				B
	A
		Bagnols-sur-Cèze	65293	1117219	10927	203706	17	18
	Cèze	Orsan Chusclan	8221 21036	254246 452874	557 2686	19243 64860	7 13	8 14
		Codolet	7519	231573	428	7639	6	3
		Laudun-L'ardoise	57797	1090217	7517	157795	13	14
		Saint-Victor-le-Coste	26634	586336	4739	110735	18	19
	Tave	Saint-Laurent-des-Arbres Saint-Geniès-de-Comolas	26761 12663	635161 379182	3300 1331	77930 39158	12 11	12 10
		Montfaucon	6142	138347	241	5890	4	4
		Roquemaure	35639	937217	3475	101900	10	11
		Cèze et Tave	267705	5822371	35201	78856	13	14
		Cèze	102069	2055912	14598	295448	14	14
		Tave	165636	3766459	20603	493408	12	13
	Valleys	Communes	number of boun-daries	cumulative length (m)	number of boundaries isoclines C	cumulative length of boun-daries isoclines C (m)	% boundaries isoclines C	% cumulative length isoclines C
		Bagnols-sur-Cèze	65293	1117219	5158	91500	8	8
	Cèze	Orsan Chusclan	8221 21036	254246 452874	1209 2475	34774 65524	15 12	14 14
		Codolet	7519	231573	1789	70468	24	30
		Laudun-L'ardoise	57797	1090217	8974	193999	16	18
		Saint-Victor-le-Coste	26634	586336	3507	79287	13	14
	Tave	Saint-Laurent-des-Arbres Saint-Geniès-de-Comolas	26761 12663	635161 379182	3489 1591	104065 50092	13 13	16 13
		Montfaucon	6142	138347	614	14139	10	10
		Roquemaure	35639	937217	6125	159720	17	17
		Cèze et Tave	267705	5822371	34931	863568	13	15
		Cèze	102069	2055912	10631	262266	10	13
		Tave	165636	3766459	24300	601302	15	16
	Valleys	Communes	number of boun-daries	cumulative length (m)	number of boundaries isoclines D	cumulative length of boun-daries isoclines D (m)	% boundaries isoclines D	% cumulative length isoclines D
		Bagnols-sur-Cèze	65293	1117219	3248	52559	5	5
	Cèze	Orsan Chusclan	8221 21036	254246 452874	1182 1898	35343 45026	14 9	14 10
		Codolet	7519	231573	878	32889	12	14
		Laudun-L'ardoise	57797	1090217	5368	97167	9	9
		Saint-Victor-le-Coste	26634	586336	1708	43109	6	7
	Tave	Saint-Laurent-des-Arbres Saint-Geniès-de-Comolas	26761 12663	635161 379182	2344 1819	61525 60210	9 14	10 16
		Montfaucon	6142	138347	1418	29792	23	22
		Roquemaure	35639	937217	5150	142724	14	15
		Cèze et Tave	267705	5822371	25013	600344	9	10
		Cèze	102069	2055912	7206	165818	7	8
		Tave	165636	3766459	17807	434527	11	12
	8
	5


Maxime Seguin Surveyor

Hervé Petitot
email: herve.petitot@inrap.frwww

1 Field evaluation for solar powerplant project A megalithe and many traces of human occupation were discovered. Stone by stone was not an option, due to time constraint and state of preservation. Santo-Pietro-di-Tenda

Preventive excavations and evaluations are documented with conventional techniques by topographic surveys, manual drawings and photographs. But when the amount and complexity of structures 1 makes it difficult for a classic recording, then a photogrammetric survey is performed. The objective is to record and document the excavation as quickly as possible.

An aerial photogrammetric survey is able to complete or replace a topographic survey and classical drawing operations (stone by stone). Unfortunately, using an unmanned aerial vehicle (UAV) is often unthinkable for security issues, 2 administrative permissions 3 and cost. This is why a pole is used to perform detailed vertical recordings of excavation sites.

The pole 4A is initially designed for sound recording. It is equipped with a three axes head 4B permitting to correctly adjust the vertical position of the camera. It has the advantage of being handy and light, allowing the activation of a remote triggering system while holding the pole in position. 5

The technique of photogrammetric survey has seen in recent years some significant progress. It is now possible to calculate three-dimensional models almost fully automatically from digital images. Preventive archaeology often requires exhaustive recording of huge datasets in a limited period. Digital photogrammetry enables to record complex elements in a simple and costless way. The originality of the implemented solution resides in the use of a free and open-source software (FOSS) and in the use of a low-cost hardware for photographic acquisition.

The National Institute of Geographic and Forest Information (IGN) has developed a software package dedicated to photogrammetry. This FOSS is designed to scientific use and can generate threedimensional models similar to those obtained by commercial softwares. The software package is well documented and has an active community of developers and users. Generated point clouds 6A can then be exploited by archaeologists with CloudCompare. It is a FOSS for processing point clouds with a great toolbox. Its main interest resides in its ability to process large point clouds.

Orthophotographs 6B are georeferenced and come with a digital terrain model (DTM) which enables direct measurement of the altitude of the elements through a geographic information system (GIS) interface. The GIS software used at Inrap is the free and open-source software QGis. Orthophotographs are directly integrated into the GIS, in addition to traditional surveying and vectorized manual drawings.

This methodology of acquisition and processing is now commonly used at Inrap and more particularly in Corsica. Indeed preventives excavations, in this offshore region, involve some logistical problems. Ultimately, this methodology tends to be used in other regions, when the use of an UAV is not possible.

  PETITOT Hervé, VIDAL Laurent -Inrap (National French Institute for Preventive Archaeology)Low-height and low-cost photogrammetric recording a reliable method for preventive


Maxime Seguin
email: maxime.seguin@inrap.fr

François Souq
email: francois.souq@inrap.fr

Kemal Stiti
email: kamstiti@yahoo.fr

Photogrammetric Recording in a Context of Preventive Archaeology : the "Place des Martyrs" Excavation (Algiers, Algeria)

Keywords: Digital Photogrammetry, Preventive Archaeology, GIS, Methodology

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

The extension of the subway network in the city of Algiers is a project that began in 2010 and still ongoing. On the North of this extension, two new stations will be created : the Ali Boumenjel and the Place des Martyrs stations (fig. 1). The construction of the station Place des Martyrs operation requires a preventive excavation. Indeed, the project lies at the foot of the ancient Casbah of Algiers. It's a historic district of the city of Algiers, founded on the ruins of old Icosium. A field evaluation [START_REF] Stiti | Place des Martyrs. Evolution depuis l'Antiquité d'un quartier de la basse Casbah d'Alger. Rapport final d'opération[END_REF]) was conducted in 2009 by a Franco-Algerian team under the aegis of UNESCO's World Heritage Center. It led to the detection of archaeological layers, almost six meters thick, bearing testament to two thousand years of Algiers' history. The excavation began mid-2013 and involves an area of about 2500 m 2 (fig. 2). Preventive archeology requires exhaustive recording of huge datasets in a limited period. This context led us to choose rapid recording methods. Digital photogrammetry enables to record complex elements in a simple and costless way. The originality of the implemented solution resides in the use of a free and open-source software suite. It is dedicated to scientific use and can generate three-dimensional models similar to those obtained by laser scanning.

METHODOLOGY

Images were acquired with a Nikon D3200 camera and a 18-55 mm zoom. Only the extreme values of focal lengths were used. The table 1 shows the characteristics of the material used. This type of camera allows use in manual mode. This last point is very important ; it will help to maintain the same optical configuration throughout the acquisition and will determine the quality

Camera

Data Acquisition

The excavation is documented with conventional techniques by topographic surveys, manual drawings and photographs. But the amount of built structures and their complexity make it difficult for a classical recording with the very short time allowed (fig. 3).

The objective was to perform a full close-range photogrammetric survey of elevated structures, in order to record and document them as quickly as possible. It was also necessary to perform an aerial photogrammetric survey in order to complete the topographic survey and classical drawing operations (stone by stone).

2. Scale-Invariant Feature Transform Using a UAV (Unmanned Aerial Vehicle) was unthinkable for security issues and administrative permissions. Platform of the building company crane was used to make the aerial survey of the site. A pole was also used to perform a more detailed vertical recording of certain items.

The pole is initially designed to sound recording. It is equipped with a two axes head permitting to correctly adjust the vertical position of the camera. It has the advantage of being handy and light, allowing the activation of a remote triggering system while holding the pole in position. It was not necessary to have a return video to the ground on the acquisition. The height of shooting and the focal length allow us to ensure a resolution of about 1 mm. Most images were acquired on the ground with a focal length of 18 mm, in order to reduce the amount of data. When the distance was adequate, pictures were taken at a focal length of 55 mm. Paper targets were glued on some walls to serve as ground control points. They were used in the bundle adjustment process.

It was not necessary to use natural points as ground control points because all parts of the structures were accessible. These points have been documented on record sheet and were measured precisely by topographic survey.

To have uniform illumination, most images were taken early in the morning or late in the afternoon. The presence of shadows may disrupt the correlation calculation and induce contrast making the finale images unaesthetic. Finally a total of 1500 photographs were acquired during the first measurement campaign. Indeed, to generate point clouds from images, the correlation technique needs a ratio B/H (base over distance to the photographed scene) around 0.2. This is what partly explains the high number of images.

Data Processing

Images acquired were designed to produce an extremely dense three-dimensional model and various orthophotographies. They were acquired at approximately 1.5 m from structures.

Corresponding points were extracted with Pastis. Before that, the images in RAW format were converted to TIFF format 8-bit and 16-bit, and then sub-sampled with a factor of 0.4. The high overlap between images generated a large number of tie points. This large number of tie points resulted in a long computation time.

The bundle adjustment has produced good results : an average image residual of 0.5 pixels.

The entire block of images (fig. 4) has been georeferenced in the Northern Sahara Lambert map projection. Ground control points were measured directly in the images using the graphical interface of the software suite. The absolute orientation has produced an average ground control points residuals of 3 millimeters.

MicMac was then used to produce depth maps which were then 2 14 th Congress of the Pan-African Archaeological Association for Prehistory and Related Studies 14-18 July 2014, Johannesburg, South Africa converted to point cloud. It is normally recommended to use the largest number of available images to calculate a depth map. But in our case, the images dataset was so large that it was chosen to optimize the number of images used for the correlation. After various tests it has been found that 3 to 5 images were enough to obtain a result with an acceptable level of noise. MicMac has the advantage of being highly configurable, allowing in this case to change the default values of some parameters to improve the final result.

The depth maps can be computed in different ways : "cartographic" geometry, suitable for aerial survey, and "image" geometry, suitable for close-range survey. The images taken from the pole and the crane have been processed in "cartographic" geometry, while the images acquired at ground level were treated in "image" geometry. The "image" geometry uses a master image from which the depth map is computed. It is also able to create a mask on this master image to restrict the area to compute. From a practical point of view, all the pictures have not led to the computation of a depth map. Master images were chosen to cover a maximum area while ensuring sufficient overlap with other depth maps, so that the final 3-D model doesn't show any hole. Given the complex geometry of some vestiges, it would be necessary to calculate all the depth maps and choose the best for each element to compute. However this would have led to a huge quantity of data to manage, too important to compute manually. There is no automatic tool developed yet, despite early research on this issue [START_REF] Gardon | Fusion de cartes de profondeurs en photogrammétrie architecturale. Rapport de TFE, Mastère Spécialisé Photogrammétrie[END_REF].

As point clouds are calculated from the images, their resolution is almost identical. Their density is about one point per millimeter or more in some cases (fig. 5). Radiometry of these clouds is directly drawn by master images after a radiometric equalization process (fig. 6). This allows no difference of contrast between point clouds. It was originally designed to make comparisons between clouds, but now has a whole toolbox. Its main interest arises from its ability to process large point clouds.

With this software archaeologists can produce orthophotographs of elevation structures (fig. 7). Point clouds were merged into a global cloud, sub-sampled at a point per centimeter (fig. 8). This light model allows general cross-sections in the excavation.

Orthophotography

An orthophotograph is a re-sampled photography for which the position of a point in the image is directly related to the position of a detail on the field. The difference with a plan is the absence of any human interpretation in his creative process. Interpretation is left to the final user. The orthophotograph, by its graphic aesthetic aspect, is also an excellent means of publication and communication to a non-specialist audience.

Creating an orthophotograph requires knowledge of the absolute

Fig. 1 .

 1 Fig. 1. Extension planned of the underground network (Maxime Seguin, Inrap)

Fig. 3 .

 3 Fig. 3. Aerial view of Ottoman vestiges (Maxime Seguin, Inrap)

Fig. 4 .

 4 Fig. 4. Bundle ajustment of 490 images (Maxime Seguin, Inrap)

th Congress of the Pan-African Archaeological Association for Prehistory and Related Studies 14-18 July 2014, Johannesburg, South Africa

Other campaigns of photogrammetric surveys are already scheduled. Ultimately, this method could be used on a regular basis on other projects of this importance.


Sergey Verlan
email: verlan@u-pec.fr

Using the Formal Framework for P Systems

In this article we focus on the model called the formal framework for P systems. This model provides a descriptional language powerful enough to represent in a simple way, via a strong bisimulation, most of the variants of P systems. The article presents a series of concrete examples of the application of the formal framework in order to understand, extend, compare and explain different models of P systems leading to new research ideas and open problems.

Introduction

The model called the formal framework for P systems (FF) was introduced in [START_REF] Freund | A formal framework for static (tissue) P systems[END_REF] and later developed in [START_REF] Freund | A formalization of membrane systems with dynamically evolving structures[END_REF]. It aims to provide a concrete variant of P systems that can act as descriptional language powerful enough to represent in a simple way most of the variants of P systems with the goal of better understanding and comparison of different models of P systems.

The formal framework permits to simulate most of variants of P systems. Moreover, in most cases it is a strong bisimulation, i.e. one step in the original system is done by one step in the formal framework. This becomes possible because the form of configurations and rules is close to multiset rewriting and generalizes most common configuration changes in P systems. Hence, most of existing models of P systems could be obtained by a restriction (eventually using a simple encoding) of FF with respect to different parameters. The strong bisimulation property also permits a discussion about the semantics of the target P system, although this is not the primary goal of FF.

Using FF mainly benefits for the following cases (a) understand the functioning of some variant of P systems; (b) compare variants of P systems; (c) explain points of the definition and semantics that can have different interpretations; (d) extend variants of P systems with new features.

The aim of this paper is not to present the framework itself, but rather several examples of its application for the description and the comparison of different variants of P systems with static structure, with probabilities and with dynamic structure. We also show how these investigations give a uniform view on P systems and lead to new research ideas and open problems.

A short presentation of the formal framework

We assume that the reader is familiar with basic notions on formal languages and on P systems and we refer to [START_REF]The Oxford Handbook Of Membrane Computing[END_REF] and [START_REF]Handbook of Formal Languages[END_REF] for missing details. We will use a string notation to denote multisets and we denote the set of finite multisets over an alphabet V as V • . For a multiset M we denote by |M | its size and by card(M ) its cardinal (i.e. the number of different occurring symbols in M ). By |M | x we denote the number of occurrences of symbol x in M .

Before giving the definition of the formal framework we would like to make some remarks about the definition of different variants of P systems. Informally speaking, a definition of a P system consists of:

a description of the initial structure (indicating the graph relation between the compartments and any additional information like labels, charges, etc), a list of the initial multisets of objects present in each compartment at the beginning of the computation, a set of rules, acting over objects and / or over the structure.

The configuration of a P system is generally representing the contents of each compartment and the current structure (if it can be modified).

A computation of a P system can be defined as a sequence of transitions between configurations ending in some halting configuration. To give a more precise description of the semantics we must define the following 4 notions (functions):

-Applicable(Π, C, δ) -the set of multisets of rules of Π applicable to the configuration C, according to the derivation mode δ. -Apply(Π, C, R) -the configuration obtained by the (parallel) application of the multiset of rules R to the configuration C. -Halt(Π, C, δ) -a predicate that yields true if C is a halting configuration of the system Π evolving in the derivation mode δ. -Result(Π, C) -a function giving the result of the computation of the P system Π, when the halting configuration C has been reached. Generally this is an integer function, however it is possible to generalize it, allowing, for example, Boolean or vector functions.

The transition of a P system Π according to the derivation mode δ (generally this is the maximally parallel mode) is defined as follows: we pass from a configuration C to C ′ (written as C ⇒ C ′ ) iff

C ′ = Apply(Π, C, R), for some R ∈ Applicable(Π, C, δ)
In general, the result of the computation of a P system is interpreted as the union of the results of all possible computations (in the same way as the language generated by a grammar is defined in formal language theory, gathering all possible derivations). Note that this is a theoretical (non-constructive) definition, since there may exist an infinite number of halting configurations reachable from a single initial configuration C 0 .

The precise definition of the four functions above depends on the selected model of P systems. The goal of works [START_REF] Freund | A formalization of membrane systems with dynamically evolving structures[END_REF][START_REF] Freund | A formal framework for static (tissue) P systems[END_REF][START_REF] Verlan | Study of language-theoretic computational paradigms inspired by[END_REF] is to provide a concrete class of P systems (hence with concrete definitions of these functions), called the formal framework, such that most of existing models of P systems could be obtained by a strong bisimulation of a restriction (eventually using a simple encoding) of this formal framework with respect to different parameters.

In the remainder of this section we give a summarized version of the definition of a network of cells, the class containing all networks of cells being the formal framework. We base the definitions on those given in [START_REF] Freund | A formal framework for static (tissue) P systems[END_REF] and we will call the obtained model FF1. This version takes into account only P systems where the membrane structure does not evolve in time (is static). In paper [START_REF] Freund | A formalization of membrane systems with dynamically evolving structures[END_REF], an extension of the formal framework to the case of P systems with dynamically evolving structure is proposed (we will call this version of the definition FF2 ). However, in order to have a more simple presentation, in this paper we will only consider the FF1 variant, except for Section 6 which is devoted to the dynamical extension of FF and therefore uses the FF2. We remark that in the case of static structures FF1 and FF2 variants coincide, although the notation is slightly different.

Definition 1 ([4]). A network of cells of degree

n ≥ 1 is a construct Π = (n, V, w, Inf, R)
where 1. n is the number of cells; 2. V a finite alphabet; 3. w = (w 1 , . . . , w n ) where w i ∈ V • , for all 1 ≤ i ≤ n, is the finite multiset initially associated to cell i; 4. Inf = (Inf 1 , . . . , Inf n ) where Inf i ⊆ V , for all 1 ≤ i ≤ n, is the set of symbols occurring infinitely often in cell i (in most of the cases, only one cell, called the environment, will contain symbols occurring with infinite multiplicity); 5. R is a finite set of rules of the form

(X → Y ; P, Q) where X = (x 1 , . . . , x n ), Y = (y 1 , . . . , y n ), x i , y i ∈ V • , 1 ≤ i ≤ n,
are vectors of multisets over V and P = (p 1 , . . . , p n ), Q = (q 1 , . . . , q n ), p i , q i , 1 ≤ i ≤ n are finite sets of multisets over V . We will also use the notation

(x 1 , 1) . . . (x n , n) → (y 1 , 1) . . . (y n , n) ; [(p 1 , 1) . . . (p n , n)]; [(q 1 , 1) . . . (q n , n)]
for a rule (X → Y ; P, Q); moreover, if some p i or q i is an empty set or some x i or y i is equal to the empty multiset, 1 ≤ i ≤ n, then we may omit it from the specification of the rule.

The semantics of the above rule is to rewrite objects x i from cells i into objects y j in cells j, 1 ≤ i, j ≤ n, if every cell k, 1 ≤ k ≤ n, contains all multisets from p k and does not contain any multiset from q k . In other words, the first part of the rule specifies the rewriting of symbols, the second part of the rule specifies permitting conditions and the third part of the rule specifies the forbidding conditions.

For a rule r of the form above, the set

{i | x i ̸ = λ or y i ̸ = λ or p i ̸ = ∅ or q i ̸ = ∅}
induces a (hypergraph) relation between the interacting cells. However, this relation need not give rise to a structure relation like a tree as in P systems or a graph as in tissue P systems.

A configuration C of Π is an n-tuple of multisets over V (u 1 , . . . , u n ) satis- fying u i ∩ Inf i = ∅, 1 ≤ i ≤ n.
Example 1. Consider the network of cells C having 5 cells and the configuration C = (ba, c, a, λ, λ). Suppose that C has the following rule:

r = (1, a)(2, c) → (1, c)(4, a)(5, b); [(1, b)]; [(3, d)]. Then C =⇒ r C ′ , where C ′ = (bc, λ, a, a, b).
The semantics of network of cells is defined as follows (see [START_REF] Freund | A formal framework for static (tissue) P systems[END_REF] for more details):

Applicable(Π, C, δ): An algorithm is used to compute Applicable(Π, C, asyn),
the set of multisets of all possible (parallel) applications of rules, which correspond to the set of multisets applicable in the asynchronous mode (asyn). Then this set is (set-)restricted according to δ. As well known examples of δ we can cite max, seq, min, min k .

Apply(Π, C, R):

The application is performed using an algorithm. In the dynamical case (in FF2 definition) there are several variants. Halt(Π, C, δ): This function is not specified in the definition and is defined separately. Several examples include total halting (no rule is applicable), signal halting (the configuration has some properties) and adult halting (no changes in the configuration occur). Result(Π, C): This function is not specified in the definition and is defined separately. Generally it is the contents of some cell.

Comparison with multiset rewriting

It is known that any variant of static P systems can be seen as multiset rewriting: an object x in membrane i corresponds to a symbol x i and each rule moving or rewriting x in membrane i, can be rewritten as corresponding multiset rewriting involving x i . For example an antiport P system with 3 membranes arranged in the structure [

1 [ 2 ] 2 [ 3 ] 3 ]
1 , the initial configuration (bc, λ, a) and a rule (a, out; b, in) in membrane 3 can be rewritten as the following multiset rewriting: starting multiset b 1 c 1 a 3 and a rule a 3 b 1 → a 1 b 3 . However, considering a P system like a multiset rewriting loses the important structural information. For example, try to figure out what happens in the system defined as follows.

Example 2. Consider the multiset rewriting system with the starting multiset a 1 b 2 c 3 and the rules a

1 b 2 → a 2 b 1 , a 1 c 2 → a 2 c 1 , a 2 c 3 → a 3 c 2 , a 2 b 3 → a 3 b 2 , a 3 c 1 → a 1 c 3 , a 3 b 1 → a 1 b 3 .
The formal framework groups the information in cells/membranes, does a group rewriting and represents the structure of the P system separately. So it is extremely close to the multiset rewriting, it just reorders objects and rules. This permits to keep the information about the static structure: rules induce a hypergraph. The communication graph can be deduced from this hypergraph. A similar approach is used in Petri nets, for example a multiset rewriting rule aabc → cde is represented as shown in Figure 1. Consider the hyperedge induced by the first rule: it goes from the cells 1 and 2 to cells 1 and 2. So we can make a supposition that we could have a communication graph that would contain an edge 1 -2. By looking at what the rule is doing we remark that it exchanges symbols a and b located in cells 1 and 2 respectively. Hence it corresponds to an antiport rule a/b on the edge 1 -2. By repeating this process for all above rules we obtain the antiport tissue P system shown in Figure 2. Hence it is clear that the system is moving symbol a in clockwise direction and symbols b and c in anticlockwise direction.

Implementing different features of P systems

In this section we discuss the implementation of some features of P systems that are not present by default in the framework.

New derivation modes

In order to define a new derivation mode for a P system it is sufficient to consider the network of cells equivalent to that system and to provide a set restriction for asynchronous (asyn) mode. Then, because of the bisimulation, the definition can immediately be interpreted in the corresponding P system.

Example 4. In this example we define two derivation modes: minimally parallel mode restricted to partitions of size 1 (min 1 ) and mixed set minimally parallel mode restricted to partitions of size 1 (msmin 1 ). In order to do this we assume that the ruleset R is divided into several sets R 1 , . . . , R m , m > 0, such that R = ∪ 1≤i≤m R i . Due to historical reasons we will call these sets partitions although this term is not accurate because the sets R 1 , . . . , R m are not necessarily disjoint.

The min 1 mode is defined as follows (see also [START_REF] Freund | P systems working in the k-restricted minimally parallel mode[END_REF]):

Applicable(Π, C, min 1 ) = {S ∈ Applicable(Π, C, asyn) : |S ∩ R i | ≤ 1, 1 ≤ i ≤ m and ̸ ∃S ′ ∈ Applicable(Π, C, asyn), with |S ′ ∩ R i | ≤ 1 such that S ′ S}
Hence, the min 1 mode is in some sense requiring to take at most one rule from each partition, when possible. It coincides with the definition of the minimally applicable multiset of rules from Section 1.9 of [START_REF]The Oxford Handbook Of Membrane Computing[END_REF].

For the msmin 1 mode we additionally classify the partitions into two categories: *-partitions and 1-partitions. In order to simplify the definition we suppose that R is divided into m partitions R 1 , . . . , R m and that the first k partitions are 1-partitions and the partitions from k + 1 until m are *-partitions. Then the mode is defined as follows:

Applicable(Π, C, msmin 1 ) = {S ∈ Applicable(Π, C, asyn) :
such that for all i, j where 1

≤ i ≤ k < j ≤ m, |S ∩ R i | ≤ 1 and card(S ∩ R j ) ≤ 1,
and

̸ ∃S ′ ∈ Applicable(Π, C, asyn), with |S ∩ R i | ≤ |S ′ ∩ R i | ≤ 1, card(S ∩ R j ) ≤ card(S ′ ∩ R j ) ≤ 1 and S ′ S}
The difference between the two definitions is that in msmin 1 mode one rule is chosen and applied from each 1-partition, if possible, and one rule is chosen and applied a maximal number of times from each *-partition, if possible.

Example 5. Consider a symport/antiport P system with a mode that ensures that a cell is used sequentially, only in a single operation. This can be done by using a partition of rules such that a rule involving cell i, will be a part of partition i. Hence, each rule will be in two partitions. The desired result is then obtained by applying the min 1 mode with the obtained partitions.

Membrane thinkness/polarization/labels

We remark that the notions of membrane thickness, polarization and label are related to each other and designate the property of a membrane to be in some finite state. In order to be able to simulate efficiently these concepts we introduce into each membrane a special object coding the state of the membrane. All rules involving a membrane will additionally have a permitting context (promoter) checking this state object.

Example 6. Consider following active membranes rules (1) [a → bc] h and (2)

a[] h → [b] h ′ in membrane k. They are simulated in the formal framework by the following rules: (k, a) → (k, bc); [(k, h)] and (k ′ , a)(k, h) → (k, bh ′ ), where k ′ is the parent of k.
As we can see the change of the state is done directly by the rule (case (2)). However, it should be noted that in the above implementation only one state change per membrane can occur in one step which is consistent with actual definitions used in P systems.

We remark that in the example above the rules (1) and ( 2) become cooperative after translation. This translates the intuitive idea that the object that is communicated/rewritten is cooperating with membrane state at the level of the rule.

We would like to remark that in FF2 the membrane state is an explicit part of the configuration, so no special object is needed for its representation. This is done because in P systems with dynamic structure the membrane labels are always used, so considering them as a part of configuration permits to save space in the description of the rule. However, it shall be noted that like in the case above there is an implicit cooperation between the membrane state and the objects used in the rule.

Priorities

Already in the first models of P systems a priority relation on the rules of the system was considered. The underlying relation is a strict partial order (i.e. an irreflexive, asymmetric, and transitive). We consider here two notions of priority following [START_REF] Ibarra | Deterministic catalytic systems are not universal[END_REF], the strong priority and the weak priority. Under the semantics of strong priority, if a rule with higher priority is used, then no rule of a lower priority can be used even if the two rules do not compete for objects. For weakly prioritized systems, a rule is applicable if it cannot be replaced by a higher priority one. In the original definition of transitional P systems from [START_REF] Gh | Membrane Computing. An Introduction[END_REF] the strong priority is used.

Example 7. Consider a transitional P system which has following three rules: r 1 : ab → cd, r 2 : ac → bd and r 3 : bc → aa. Let the priority relation be r 3 > r 1 . Suppose that the current configuration contains the multiset aabbc in the corresponding membrane. Then in the case of the strong priority only rules r 2 or r 3 are applicable. In the case of the weak priority it is possible to apply additionally rule r 1 , yielding the following applicable sets: {r 1 , r 2 } and {r 1 , r 2 }.

It is not difficult to see that the strong priority corresponds directly to forbidding conditions: indeed r 1 > r 2 corresponds to two rules (1) r 1 and (2) r 2 enriched with forbidding sets containing the left-hand sides of all rules r > r 2 .

Example 8. Consider the system from Example 7. We can translate the first rule to the formal framework as follows:

r ′ 1 : (k, ab) → (k, cd); []; [(k, bc)].
The case of weak priorities can be handled using a special derivation mode that keeps track of the relation between rules. It will choose those multisets where a rule of higher priority cannot be applied anymore even if all rules of a lower priority are not taken:

Applicable(Π, C, P ri w δ) = {R ∈ Applicable(Π, C, δ) |̸ ∃R ′ ∈ Applicable(Π, C, δ), such that r ∈ R ′ \ R and R ′′ ̸ ∈ Applicable(Π, C, δ), where R ′′ ⊇ R ∪ {r} \ {r ′ ∈ R | r > r ′ }}

Dissolution

We recall that the dissolution operation (denoted by δ) removes the membrane in which it occurred as well as all rules involving the dissolved membrane. All objects present in that membrane are transferred to its parent. In a general case this operation is handled in FF2 as a special operation acting on the structure like the creation or the division of membranes. However, if we consider the class of P systems where only dissolution is used (no creation/division of membranes) then it is obvious that such systems have a finite number of possible membrane structures (the dissolution operation can only decrease the number of membranes already present at the beginning of the computation). Hence, it is possible to mimic the effect of the dissolution by assigning a marker to each membrane in order to indicate if the membrane is dissolved or not, by using permitting and/or forbidding context in order to check this marker and by using a subset construction at the level of rules in order to capture all possible structure changes.

Example 9. Consider the following transitional P system (see Figure 3) In order to translate it to the formal framework we shall use 3 objects s 0 , s 1 and s 2 indicating that corresponding membranes are not yet dissolved. We place these objects in corresponding cells, although they all can be placed in a particular cell, e.g. cell 0. There are 4 possible membrane structures and they are encoded by the following combinations of objects

Π = ({a, b, c, d, #}, [ 0 [ 1 ] 1 [ 2 ] 2 ] 0 , {ac}, {c}, {a}, R 0 , R 1 , R 2 ), where R 0 = {r 01 : ac → λ, r 02 : da → #, r 03 : bc → #, r 04 : # → #}, R 1 = {r 11 : c → cc, r 12 : c → dδ}, R 2 = {r 21 : a → aa, r 22 : a → bδ}.
s i : {(0, s 0 )(1, s 1 )(2, s 2 )}, {(0, s 0 )(1, s 1 )}, {(0, s 0 )(2, s 2 )
} and {(0, s 0 )}. Now in order to finalize the translation we shall do a subset construction for all rules in membrane 0 in order to take into account that corresponding objects can originate from a dissolved membrane:

Rules from R 1 are translated as follows:

(1, c) → (1, cc); [(1, s 1 )] (1, s 1 )(1, c) → (0, d)
Rules from R 2 are translated as follows:

(

2, a) → (2, aa); [(2, s 2 )] (2, s 2 )(2, a) → (0, b)
Rules from R 0 are translated as follows:

(0, ac) → λ; [(2, s 0 )] (0, a)(1, c) → λ; [(0, s 0 )]; [(2, s 2 )] (0, c)(2, a) → λ; [(0, s 0 )]; [(1, s 1 )] (1, c)(2, a) → λ; [(0, s 0 )]; [(1, s 1 )(2, s 2 )] (0, da) → (0, #); [(0, s 0 )] (0, d)(2, a) → (0, #); [(0, s 0 )]; [(2, s 2 )] (0, bc) → (0, #); [(0, s 0 )] (0, b)(1, c) → (0, #); [(0, s 0 )]; [(1, s 1 )] (0, #) → (0, #); [(0, s 0 )]
We observe that for the translation of rule r 01 we had to consider 4 cases depending on the possible origin of symbols a and c. The difference between cases is done by corresponding permitting and forbidding conditions.

We also remark that is is possible to avoid forbidding conditions by considering that a state of the membrane i is defined by one of two (dual) objects s i or si , where the first one indicates that the membrane exists and the second one indicates that the membrane is dissolved. In this case the rule dissolving the membrane will rewrite s i to si and the forbidding contexts for s i are replaced by permitting for si . For example, in the case above the second rule from

R 1 becomes (0, s 1 )(1, c) → (0, d)(1, s1 ) and the second rule from R 0 becomes (0, a)(1, c) → λ; [(0, s 0 )(2, s2 )].
In some particular cases it is possible to simplify the above construction by assigning a number (hence a special object) to each of possible membrane structures and checking by permitting context the current structure. The drawback of this method is the difficulty to perform several dissolutions in parallel, as several rules should modify the same object at the same step. In some cases (e.g. if the maximally parallel or sequential derivation mode is used) it is possible to overcome this difficulty by using additional rules that perform all required dissolutions in one step.

Example 10. Consider system Π from Example 9. We encode by objects s i , 1 ≤ i ≤ 4, placed in cell 0, the four possible variants of the membrane structure (initial, membrane 2 dissolved, membrane 1 dissolved, membrane 1 and 2 are dissolved). In order to handle the parallel dissolution of membranes 1 and 2 a special rule is introduced.

Rules from R 1 are translated as follows:

(1, c) → (1, cc); [(0, s 1 )] (1, c) → (1, cc); [(0, s 2 )] (0, s 1 )(1, c) → (0, ds 3 ) (0, s 2 )(1, c) → (0, ds 4 )
Rules from R 2 are translated as follows:

(2, a) → (2, aa);

[(0, s 1 )] (2, a) → (2, aa); [(0, s 3 )] (0, s 1 )(2, a) → (0, bs 2 ) (0, s 3 )(2, a) → (0, bs 4 )
Rules from R 0 are translated as follows:

(0, ac) → λ (0, a)(1, c) → λ; [(0, s 3 )] (0, c)(2, a) → λ; [(0, s 2 )] (1, c)(2, a) → λ; [(0, s 4 )] (0, da) → (0, #) (0, d)(2, a) → (0, #); [(0, s 1 )] (0, bc) → (0, #) (0, b)(1, c) → (0, #); [(0, s 3 )] (0, #) → (0, #)
Additional rule for parallel dissolution:

(0, s1)(1, c)(2, a) → (0, bds 4 )
We remark that the above construction cannot be generalized to any case. For example, consider a P system evolving in a special derivation mode that requires to use exactly one rule from every membrane at each step. In this case the above construction would fail as the two dissolutions were replaced by a single rule performing both of them.

Flattening

We call a flattening of a P system Π the process of construction of a new P system Π ′ having only one cell such that N (Π) = N (Π ′ ). We remark that system Π ′ need not belong to the same class of P systems as Π. A strong flattening requires that Π and Π ′ belong to the same class.

In the case of P systems with static structure (that does not change in time) it can easily be seen that the flattening is very simple, because of the one-to-one relation with multiset rewriting grammars. If the dissolution is present, then it is possible to simulate it as described in previous subsection, hence the flattening procedure will require the use of permitting and eventually forbidding contexts. In the case of systems with dynamically evolving structure (with creation and/or dissolution of membranes) the flattening is not trivial as one should deal with an unbounded number of membranes. A trivial translation yields an unbounded alphabet and an unbounded number of rules, so encodings are necessary to represent the flattening correctly and it is a challenge to provide an algorithm that performs this task.

For the strong flattening it can easily be seen that it is not always possible. For example, any P system that does not allow rules corresponding directly to the multiset rewriting (e.g. symport P systems or minimal symport/antiport P systems) cannot be strongly flattened.

Another example of systems that do not admit strong flattening are systems that have dissolution and do not allow permitting and forbidding contexts, e.g. transitional P systems with dissolution. Because the algorithms eliminating the dissolution require at least a permitting context, it is clear that the flattening cannot be done if remaining inside the same model.

A longer discussion on flattening can be found in [START_REF] Freund | Flattening in (Tissue) P Systems[END_REF].

Examples of application of FF

In this section we consider three applications of the formal framework. The first one is the comparison of (purely) catalytic P systems with context-free transitional P systems. The second application consists in extending symport/antiport P systems with variable membrane thickness. The third application studies the model of P colonies and helps in understanding this model and allows to easily obtain some new results.

Catalytic P systems

The translation of (purely) catalytic P systems to FF can be done in a quite straightforward manner as follows: every rule ca → c(a 1 , tar 1 ) . . . (a k , tar k ) of cell i becomes (i, ca) → (F (i, tar 1 ), a 1 ) . . . (F (i, tar k ), a k ), where F (i, here) = i, F (i, in j ) = j and F (i, out) = m, where m is the parent of i. Now we remark that the inherent property of catalytic P systems is that at each step only one rule can be chosen among all rules involving the same catalyst. This property can be deduced from the form of rules of such systems. At the same time it is clear that this property relates more to the way the rules are used together, i.e. to the derivation mode, than to rules' action itself. In FF it is possible to consider a derivation mode that obeys the above restriction. It is not difficult to see that in the case of catalytic (resp. purely catalytic) P systems the above requirements are satisfied by the msmin 1 (resp. min 1 ) derivation mode. The (1-)partitions used for the definition of corresponding modes correspond to each catalyst. In the case of non-purely systems the *-partitions consist of single rules, those that are used in a context-free manner. From the above analysis we can also deduce that catalytic P systems having several membranes and one catalyst are a restricted variant of catalytic P systems with one membrane and using several catalysts.

Hence, we obtain that catalytic P systems evolving in the maximally parallel mode are equal to context-free transitional P systems working in the msmin 1 mode, where the 1-partitions correspond to catalysts and *-partitions to each context-free rule. The systems corresponding to purely catalytic P systems have the number of 1-partitions equal to the number of catalysts and no *-partitions, so they evolve in the min 1 mode. It immediately follows that the model of purely catalytic P systems is weaker than the general variant, as context-free rules add more complexity, that can be quantified by the increase of the number of partitions and by the increase of the degree of parallelism.

The usage of the msmin 1 mode may look a little bit artificial, so we remark that it is also possible to consider a special mixed mode derived in a straightforward way from the real semantics of catalytic P systems with k catalysts: using k + 1 partitions with k partitions working in the min 1 mode (corresponding to catalysts) and one special partition working in the maximally parallel mode.

Example 11. Consider the following catalytic P system

Π = (O, {c}, [ 0 [ 1 [ 3 ] 3 [ 4 ] 4 ] 1 [ 2 ] 2 ] 0 , {abc}, {aac}, {c}, {a}, ∅, R 0 , R 1 , R 2 , R 3 , R 4 ), where O = {a, b, c, d, e}, R 0 = {cb → ca in2 }, R 1 = {ca → cb in d in4 b out e out e here }, R 3 = {b → aa, a → bc}, R 2 = R 4 = ∅.
The straightforward translation of this system gives the following rules:

(0, cb) → (0, c)(2, a) (1, ca) → (0, be)(1, ce)(4, bd) (1, ca) → (0, be)(1, ce)(3, b)(4, d) (3, a) → (3, bc) (3, b) → (3, aa)
We remark that the translation of the in target is done as in k , for all k.

Now we construct the context-free network of cells Π ′ equivalent to Π. Consider following sets of rules:

P 1 = {(1, a) → (0, be)(1, e)(4, bd), (1, a) → (0, be)(1, e)(3, b)(4, d)}, P 2 = {(0, b) → (0, c)(2, a)}, P 3 = {(3, a) → (3, bc)}, P 4 = {(3, b) → (3, aa)}.
Let P 1 and P 2 form 1-partitions and let P 3 and P 4 form *-partitions. Then from the discussion above it is clear that Π ′ working in the msmin 1 mode is equivalent to Π. We remark that the obtained network of cells can easily be translated to a context-free transitional P system working in the msmin 1 mode.

Symport/antiport

In this subsection we discuss how it is possible to use the formal framework in order to extend an existing class of P systems.

Consider the class of symport/antiport P systems. We will extend it with two features: (1) membrane permeability -a symport rule can modify the membrane permeability (with δ or τ ). If the membrane is in state 2, then no antiport rule involving this membrane can be used. At each step only one permeability changing rule per membrane can be applied; (2) maximal objects: at each step if there are several maximally parallel evolutions choose the one having the maximal number of objects involved.

In order to define the semantics for both features we will translate symport/antiport P systems to the formal framework, then we will do the necessary transformations in order to accommodate the desired behavior. Then due to the strong bisimulation we can recover the desired semantics in symport/antiport P systems.

The translation of symport and antiport rules can be done in a quite simple way: each antiport rule (a, in; b, out) (resp. symport rule (a, out)) of membrane i is translated as (i, b)(j, a) → (i, a)(j, b) (resp. (i, a) → (j, a)), where j is the parent membrane of i; each symport rule (a, in) is translated as (i, a) → (j, a), for all child membranes j of i. Now in order to implement the first proposed extension, for each membrane i we consider an object in cell i taken from the triple (D, N, C) indicating the state of the membrane (dissolved, normal, closed). Each symport rule having δ or τ will modify this object (going to the left or right in the above sequence) and each antiport rule will check the permitting context if it is in state N . For example: the rule (ab, out); τ in membrane i will correspond to rules (i, abN ) → (i, C)(j, ab) and (i, abC) → (i, C)(j, ab). Now in order to satisfy the second requirement we consider the following derivation mode max obj max:

Applicable(Π, C, max obj max) = { R ∈ Applicable(Π, C, max) | ̸ ∃R ′ ∈ Applicable(Π, C, max) : ∑ r ′ ∈R ′ |lhs(r ′ )| > ∑ r∈R |lhs(r)| }
It should be clear that the network of cells obtained using the transformations above will be a strong bisimulation of the initial P system.

P colonies

We recall the definition of P colonies taken from [START_REF]The Oxford Handbook Of Membrane Computing[END_REF].

A P colony consists of n cells (agents) C i , 1 ≤ i ≤ n, each of them containing a multiset of exactly k symbols and an environment containing initially a distinguished symbol e in an unbounded number of copies. Each cell C i has a set of programs {p i,1 , . . . , p i,ki }, where each program p i,j consists of exactly k rules of the forms a → b (internal point mutation), c ↔ d (one object exchange with the environment), or r 1 /r 2 (priority rule, where r 1 and r 2 are arbitrary combinations of point mutation and/or exchange rules). The computation can be performed in the maximally parallel or in the sequential mode with respect to the programs of cells. If no more programs are applicable, the system halts and the result is collected as the number of distinguished symbols f in the environment. The number of cells, the maximal number of programs in a cell, and the maximal number of rules in each program in a given P colony Π are called the degree, the height, and the capacity of Π, respectively. The family of sets of numbers computed in the derivation mode x for x ∈ {par, seq} by P colonies of capacity k, degree at most n ≥ 1 and height at most h ≥ 1, without (resp. with) using priority rules in their programs, is denoted by N P Col x (k, n, h) (resp.

N P Col x K(k, n, h)).

We will construct a strong bisimulation of the P colony model in the formal framework:

-each rule a → b in p ij becomes r ij : (i, a) → (i, b); -each rule a ↔ b in p ij becomes r ij : (i, a)(0, b) → (i, b)(0, a); -each rule r 1 /r 2 in p ij is replaced by two rules: r 1 , and r2; [∅]; [{(i, a)}] if r 1 is a → b and r2; [∅]; [{(i, a)(0, b)}] if r 1 is a ↔ b.
For the derivation mode each program becomes a rule partition and then the derivation mode requires to be maximal, but using exactly k rules from each partition (or using all rules from a partition). In the sequential case, the derivation mode implies to use only one partition (but all rules from that partition). Figure 4 shows a graphical representation of this system. We translate this system to a network of cells Π ′ having 4 cells (numbered from 0 to 3), corresponding to the cells of Π, and having same initial contents as corresponding agents and Inf 0 = {e}. System Π ′ contains the following rules:

Rules simulating programs from the first cell: We remark that the derivation mode of P colonies groups rules corresponding to programs, uses maximal parallelism or sequentiality, and requires that all rules from a group shall be used. Since working with one symbol, the group r 111 and r 112 from example above is equivalent to the application of a single rule r 11 : (1, aa)(0, e) → (1, be)(0, a). Hence we obtain that a program corresponds to a more complicated rule, and k is the size of the LHS of this rule (and equal to RHS). By considering such rules, the evolution of a P colony becomes just maximally parallel or sequential.

Example 13. Consider the system Π from Example 12. Using the above remark it can be translated to the following network of cells Π ′′ :

r 11 : (1, aa)(0, e) → (1, be)(0, a) r 12 : (1, aa)(0, e) → (1, ce)(0, a) r 13 : (1, be) → (1, aa) r 21 : (2, be)(0, e) → (2, be)(0, b) r 31 : (3, ee)(0, ab) → (3, ab)(0, ee) r 32 : (3, ab) → (3, f b) r 33 : (3, bf )(0, a) → (3, ab)(0, f )
We can go further by remarking that the number of combinations of objects in an agent is finite, so it can be represented by a single symbol, the state. Symbol e from cell 0 can be ignored as it carries no information. This permits to deduce that a P colony corresponds to a cooperative rewriting with the size of LHS or RHS at most k + 1 and forbidding conditions (if checking rules are present). It can be also possible to consider it as a catalytic P system with catalysts having n-states.

Example 14. Consider system Π from Example 12. Consider the array of multisets A = (aa, be, ce, ee, ab, bf ) and the following encoding f (A[i]) = s i . Then the rules from Example 13 can be rewritten as follows:

r11 : (1, s1) → (1, s2)(0, a) r12 : (1, s1) → (1, s3)(0, a) r13 : (1, s2) → (1, s1) r21 : (2, s2) → (2, s2)(0, b) r31 : (3, s4)(0, ab) → (3, s5) r32 : (3, s5) → (3, s6) r33 : (3, s6)(0, a) → (3, s5)(0, f )
In order to highlight the original semantics (that only one program per cell can be executed), we can use catalysts: the rule r 11 : (1, s 1 ) → (1, s 2 )(0, a) becomes c 1 s 1 → c 1 s 2 a. Although using catalysts is not necessary as the state is unique, this permits to consider a restricted variant of the model of P colonies that uses only rules of the above type and therefore corresponds to specific purely catalytic P systems. This remark permits us to transpose results from P colonies to purely catalytic P systems and conversely. For example, from the results for P colonies (Remark after Theorem 23.1.1 and Theorem 23.1.2 from [START_REF]The Oxford Handbook Of Membrane Computing[END_REF]) we immediately obtain that: Proposition 1. The following results hold:

-Purely catalytic P systems with one catalyst and the size of the rule equal to 3 are not computationally complete. -Purely catalytic P systems of with rules of size 2, an unbounded number of catalysts and using at most 6 rules for each catalyst are computationally complete.

In the other direction we can also immeadiately obtain (Theorem 4.1 from [START_REF]The Oxford Handbook Of Membrane Computing[END_REF]) that: This follows from the fact that the corresponding model is identical to purely sequential multiset rewriting which is known to not be computationally complete.

Probabilistic P systems

In this section we extend the formal framework in order to take into account probabilities and thus become able to represent via bisimulation different variants of probabilistic P systems. This section closely follows [START_REF] Verlan | A note on the probabilistic evolution for P systems[END_REF]. To achieve the proposed goal we recall that in order to perform a computational step in a P system a set of multisets of applicable rules, denoted by Applicable(Π, C, δ), is computed according to the type of the system and the derivation mode δ, for any configuration of the system C. After that, one of the elements from this set is chosen, non-deterministically, for the further evolution of the system.

We remark that from the point of view of the computer simulation of P systems the non-deterministic choice can be considered equivalent to a probabilistic choice where each multiset of rules has an equal probability to be chosen. Permitting these multisets to have a different probability is the main idea of the extension that we discuss in this section. More precisely, for each multiset of rules R ∈ Applicable(Π, C, δ) we compute the probability p(R, C) based on the propensity function f : R • × (N × O • ) * → R, where R and O are the set of rules and objects of Π respectively. This function associates a real value for a multiset of rules with respect to a configuration. Hence the value f (R, C) depends not only on the multiset of rules R, but also on the configuration C.

The probability to choose a multiset R ∈ Applicable(Π, C, δ) is defined as the normalization of corresponding probabilities:

p(R, C) = f (R, C) ∑ R ′ ∈Applicable(Π,C,δ) f (R ′ , C) (1)

Discussion

So far we did not indicate the propensity function f , which is the main ingredient of the model. Below we will give examples of simple propensity functions each leading to different execution strategies.

Constant strategy: each rule r from R has a constant contribution to f and equal to c r :

f (R, C) = ∏ r∈R c r (2)
Multiplicity-dependent strategy: each rule r from R has a contribution to f proportional to the number of times this rule can be applied and to a stochastic constant c r that only depends on r:

N r (C) = min x∈lhs(r) [ |C| x |lhs(r)| x ]
(3)

f (R, C) = ∏ r∈R c r N r (C) (4)
Concentration-dependent strategy: each rule r from R has a contribution to f proportional to h r (C), the number of distinct combinations of objects from C that activate r, and to a stochastic constant c r that only depends on r (by

( a b )
we denote the binomial function):

h r (C) = ∏ x∈lhs(r) ( |C| x |lhs(r)| x ) (5) h R (C) = ∏ r∈R c r h r (C) (6) (R, C) = h R (C) (7)
Gillespie strategy: each rule r from R has a contribution to f that depends on the order in which it was chosen and it is equal to c r • h r (C ′ ), where C ′ is the configuration obtained by applying all rules that were chosen before r.

We remark that the concentration-dependent strategy is not equal to Gillespie strategy. More precisely, in a Gillespie run the probability to choose a new rule depends on the objects consumed and produced by previously chosen rules. We can consider a Gillespie run as a sequence of sequential (single-rule) applications using the concentration-dependent strategy.

We also remark that the Gillespie algorithm uses the notion of time that we do not consider in this paper. However, the definitions can easily be adapted for to handle this case.

Examples

Dynamical Probabilistic P Systems Dynamical probabilistic P (DPP) systems were introduced in [START_REF] Pescini | Dynamical probabilistic P systems[END_REF]. Below, we present the definition of the evolution step. For the sake of the simplicity we will consider only one compartment, however the discussion below can easily be generalized to several compartments.

Let C be the current configuration and R be the set of all rules. Then the system evolves from C to C ′ as follows.

1. For each rule r ∈ R, the propensity of a r (C) = c r * h r (C) (h r being defined as in Equation ( 5)) is computed.

2. The propensities are normalized giving a probability for a rule r to be chosen:

p r (C) = ar(c) ∑ r ′ ∈R a r ′ (C) .
3. The rules to be applied are chosen according to their probabilities. If a nonapplicable rule is chosen, the choice is repeated. 4. The process stops when a maximal (parallel) multiset of rules R is obtained. 5. The multiset of rules obtained at the previous step is applied and yields a new configuration C ′ .

It can be easily seen that, since the probabilities to apply a rule (p r ) are computed only at the beginning of each step, the maximal multiset of rules R then is composed from independent rules (the order in which the rules were chosen has no influence). Hence the probability to choose a multiset of rules R is equal to the product of the probabilities of each rule: p R (C) = ∏ r∈R p r . Now if we normalize this value with respect to all possible maximally parallel multisets of rules we obtain:

∏ r∈R p r (C) ∑ R ′ ∈Appl(Π,C,max) ∏ z∈R ′ p z (C) = ∏ r∈R ar(C) ∑ r ′ ∈R a r ′ (C) ∑ R ′ ∈Appl(Π,C,max) ∏ z∈R ′ pz(C) ∑ r ′ ∈R a r ′ (C) = ∏ r∈R a r (C) ∑ R ′ ∈Appl(Π,C,max) ∏ z∈R ′ a z (C) (8)
Since in the case of the concentration-dependent strategy we have that f (R, C) = ∏ r∈R a r (C), it follows that ( 8) equals ( 1). Hence we just showed that DPP systems can be translated to probabilistic P systems with a concentrationdependent strategy.

Probabilistic Functional Extended P Systems Probabilistic functional extended P (PFEP) systems where introduced in [START_REF] Cardona | A computational modeling for real ecosystems based on P systems[END_REF] as a part of a framework used to model eco-systems. In order to simplify the presentation we consider a flattening of the structure of the P system, thus using only multiset rewriting rules. We also consider that the rules having the same left-hand side form a partition of the set of rules R into

n subsets R = R 1 . . . R n , where r 1 , r 2 ∈ R i ⇒ lhs(r 1 ) = lhs(r 2 ), 1 ≤ i ≤ n.
The evolution of a PFEP system is done as follows:

1. A maximally parallel multiset of rules R is chosen. 2. R is partitioned into submultisets based on the left-hand side of rules:

R i = {r ∈ R | r ∈ R i }. 3.
For each non-empty partition R i , |R i | rules from R i are chosen according to the given probability f r (a), where r ∈ R i and a is a moment of time. 4. The resulting multiset of rules is applied yielding a new configuration.

From the description of the strategy it is clear that it corresponds to the multiplicity-dependent strategy for the maximally parallel derivation mode (and where the constant c r is replaced by f r (a)).

In this section we consider the FF2 model described in [START_REF] Freund | A formalization of membrane systems with dynamically evolving structures[END_REF]. The first change with respect to FF1 is the definition of the configuration, which now shall take into account the labels and the membrane structure. Hence, a configuration becomes a couple (L, ρ), where L is a list of "labeled cells" (i 1 , l 1 , w 1 ) . . . (i n , l n , w n ), with the id i j ∈ N, the label l j ∈ Lab (the set of labels) and the contents w j ∈ O * (O being the alphabet of the system), for 1 ≤ j ≤ n, such that all the cells' id's (the first element of each triple) are different from each other. The second component ρ ⊆ N × N is a relation that represents the connections between cells (it can be seen as a graph where the nodes are the cells id's).

Note that in a configuration each cell has an id which is unique and a label which is not necessarily unique.

The interpretation of relation ρ may differ depending on the selected P system model, but its goal is to capture how cells (or membranes) are organized in the "membrane structure". In cell-like P systems this corresponds to the parent relation, while in tissue P systems this corresponds to the communication graph of the system.

The simulation of most existing variants of active membranes can be done by rules that use following actions:

1. Rewriting of objects (in several cells simultaneously as it is done for the static case). 2. Label change. 3. Creation of a new cell. 4. Creation of a new cell having a contents of some existing cell (and also some additional object rewriting). 5. Deletion of a cell (loosing its contents). 6. Deletion of a cell and moving its contents to some other cell. 7. Arbitrary rewriting of the structure ρ using a graph transducer.

A rule of the network of cells is defined in terms of pattern-matching. First a pattern subgraph structure is given and all actions like rewriting, membrane deletion etc. are given in terms of the pattern structure. During the applicability check the pattern is matched to the actual structure given by the relation ρ. This procedure can yield several matches (instances), so all of them are considered. For each match the preconditions given by the rule (presence or absence of some objects in some cells) are checked and if all of them are satisfied then the rule is applicable. The applicability check is extended to a multiset of rules in a way that is consistent with individual instances of rules. The resulting set of all applicable rules (Applicable(Π, C, asyn)) is computed as the multisets of couples rule/instance that are applicable to C. Based on this set it is possible to define derivation modes as in the static case. However, additional possibilities related to instances of rules may be investigated, e.g. accepting only particular instances during the derivation (e.g. mandatory including cell number 1). Example 15. Consider a P system with active membranes having the configuration shown on Figure 5. Let r be the following rule (according to FF2):

r : Labels(r) = (z+, h); ρ(r) = {(1, 2)}; Rewrite(r) = (1, a)(2, c) → (1, c)(2, a).
In order to apply r we first should find a combination of two membranes having the labels z + and h. There are two such combinations. After that we check the relation ρ(r) which states that membrane 1 (the one identified by the label z + ) is the parent of membrane 2 (the one identified by h). Hence, only the couple at the left remains. We now can identify the numbers 1 and 2 with corresponding cells. Next, the rewriting part of the rule can be applied. It will exchange the symbols a and c, which are located in cells 1 and 2 respectively. It can easily be seen that the "maximally parallel" derivation mode for active membranes is not really maximally parallel. More precisely it is min 1 for rules involving membranes and max otherwise, so it can be seen as msmin 1 . This fact makes the active membrane model similar to catalytic P systems, so interesting links can be done. We also remark that even if it is not mentioned explicitly, membrane labels induce cooperation to all rules, thus they have a hidden promoter/permitting context. In the case of the minimally parallel derivation mode for active membranes (min), see Section 11.5 from [START_REF]The Oxford Handbook Of Membrane Computing[END_REF], there could be several interpretations of this concept depending on whether rewriting and membrane rules for a cell are considered to be in the same partition or not.

We would like to emphasize that the current definition of the derivation mode for active membranes allows only one rule per membrane (except rewriting). Using the formal framework it is possible to define in a consistent non-ambiguous way the application of several creation, communication and deletion rules involving the same membrane/cell.

The application Apply(Π, C, R) is defined using an algorithm that first applies the rewriting, then creation and then deletion parts of R. At the end, the structure can be modified in an arbitrary way by a graph transducer. We remark that we used the order rewrite, create, delete (RCD), which is consistent with actual definitions of active membranes. However, it is possible to define the application using other orders like RDC or DCR, yielding slightly different semantics. For example, in RDC order deleted membranes cannot be copied to newly created ones and in CDR order the newly duplicated membranes get the "old" contents, before rewriting. The application of rules in some sense is "global", because the applicability imposes the order of their application to be irrelevant. It is possible to relax this condition and to obtain new application strategies that will differ depending on whether the rules are applied from inside-out or not.

Example 16. Consider a P system with active membranes Π having the configuration shown in Figure 5. Suppose that Π has the following rules:

r 1 : a[] h → [b] h+ r 2 : [b] h → c[] h-r 3 : [c → da] h r 4 : [d] h → [e] h+ [f ] h
These rules are translated according to FF2 as follows (see [START_REF] Freund | A formalization of membrane systems with dynamically evolving structures[END_REF]). We suppose that h ′ is an arbitrary membrane label from the set Lab. We also use the following shorthand notation Ls for Labels, RW for Rewrite, LR for Label -Rename, GC for Generate -and -Copy and CR for Change -Relation. It can easily be seen that to the leftmost membrane labeled by h rules r 1 , r 3 , and r 4 are applicable, while to the rightmost membrane labeled by h only rules r 2 and r 3 are applicable. The result of the maximally parallel evolution can be seen in Figure 6.

We remark that this evolution does not correspond to a standard active membranes derivation, because, as it was mentioned above, P systems with active membranes evolve in the msmin 1 mode and therefore it is not possible to apply in parallel rules r 1 and r 4 to the leftmost membrane h.

Conclusion

In this article we described the model of P systems called the formal framework and we showed how it can be useful when dealing with the following questions:

(1) understanding an existing model of P systems; (2) extending a model of P systems with new features or using a different derivation mode; (3) compare two different models of P systems; and (4) explaining details of the semantics that can have several interpretations and raising questions related to these interpretations. The presented formalism permits to have a powerful language for the description of the features of P systems and is especially useful for making links and transposing results between different models of P systems like it is exemplified in Sections 4.3. Another advantage of the formalism is the ability to treat in a uniform way P systems with static structure, with dynamically evolving structure, and with priorities. This permits to share some basic concepts like derivation modes and may be useful in order to create new formalisms like P systems with active membranes and probabilities.

Fig. 1 .Example 3 .

 13 Fig. 1. A Petri net representation of the rule aabc → cde.

Fig. 2 .

 2 Fig. 2. The antiport system obtained in Example 3. The arc a ↔ b corresponds to the antiport rule a/b.

Fig. 3 .

 3 Fig. 3. The P system from Example 9.

Example 12 .

 12 Consider the following P colony Π having 3 cells. -C 1 contains the initial multiset aa and the following programs: p 11 : a → b, a ↔ e, p 12 : a → c, a ↔ e, p 13 : b → a, e → a. -C 2 contains the initial multiset be and the following program: p 21 : b ↔ e, e → b. -C 3 contains the initial multiset ee and the following programs: p 31 : e ↔ a, e ↔ b, p 32 : b → f, a → b, p 33 : f ↔ a, b → b.

Fig. 4 .

 4 Fig. 4. The P colony from Example 12.

r

  111 : (1, a) → (1, b) r 112 : (1, a)(0, e) → (1, e)(0, a) r 121 : (1, a) → (1, c) r 122 : (1, a)(0, e) → (1, e)(0, a) r 131 : (1, b) → (1, a) r 132 : (1, e) → (1, a) Rules simulating programs from the second cell: r 211 : (2, b)(0, e) → (2, e)(0, b) r 212 : (2, e) → (2, b) Rules simulating programs from the third cell: r 311 : (3, e)(0, a) → (3, a)(0, e) r 312 : (3, e)(0, b) → (3, b)(0, e) r 321 : (3, b) → (3, f ) r 322 : (3, a) → (3, b) r 331 : (3, f )(0, a) → (3, a)(0, f ) r 332 : (3, b) → (3, b)

Proposition 2 .

 2 N P Col par (3, 3, * ) = RE. Our representation of P colonies permits to answer the open question raised in Section 23.1.3 from [9]: Proposition 3. N P Col seq ( * , 1, * ) RE.

Fig. 5 .

 5 Fig. 5. The P system with active membranes from Example 15. The bold symbols represent the objects.

  Ls(r1) = (h ′ , h); ρ(r1) = {(1, 2)}; RW (r1) = (1, a) → (2, b); LR(r1) = {(2, h+)}; Ls(r2) = (h ′ , h); ρ(r2) = {(1, 2)}; RW (r2) = (2, b) → (1, c); LR(r2) = {(2, h-)}; Ls(r3) = (h); ρ(r3) = ∅; RW (r3) = (1, c) → (1, da); LR(r3) = ∅; Ls(r4) = (h ′ , h); ρ(r4) = {(1, 2)}; RW (r4) = (2, d) → (2, e); LR(r4) = {(2, h+)}; GC(r4) = {(1 ′ , h, 2, d → f )}; CR(r4) = {IN SERT -EDGE(1, 1 ′ )}.

Fig. 6 .

 6 Fig. 6. The result of the application of rules given in Example 16 on the configuration from Figure 5.

Acknowledgements The author would like to thank Rudi Freund for many interesting remarks and suggestions that permitted to improve this paper as well as the support of ANR project SynBioTIC.