Benjamin Bourel
email: bourel@cerege.fr

Ross Marchant

Thibault De Garidel-Thoron

Martin Tetard

Doris Barboni

Yves Gally

Luc L Beaufort

Automated recognition by multiple convolutional neural networks of modern, fossil, intact and damaged pollen grains

Keywords: Damaged pollen, Fossil pollen, Machine learning, Image analysis, Z-stacking, Amaranthaceae

come   L'archive ouverte pluridisciplinaire

Introduction

Since the late 1960s, the palynologist community has been interested in the automation of pollen grain recognition [START_REF] Flenley | The problem of pollen recognition[END_REF]. This desire comes from a real need to reduce the long and tedious process of pollen grain identification and counting, which requires an extended knowledge of palynofloras in order to obtain accurate and statistically valid paleovegetation inferences. Pollen counting and recognition process is an important limiting factor that makes it difficult to build large databases. To date, with the advances of large datasets for paleoenvironmental studies to resolve high spatial and/or temporal resolution, there is a crucial need to reduce the time involved in pollen data acquisition. Palynology is also a discipline at risk today because acquiring sufficient knowledge of palynofloras requires years of experience, particularly in tropical regions where plant diversity is highest. Despite the fact that pollen grains are still the only paleovegetation proxies allowing plant identifications up to the genus and species levels, their study is easily supplemented by other indicators such as δ 13 C. They require less physical presence of scientists in the acquisition although they do not allow such fine environmental reconstitutions.

In the East African Rift, many paleontological areas have preserved abundant fauna, including hominin remains of Pliocene and Pleistocene age, but few have preserved paleobotanical remains. Yet, pioneering pollen studies in the early 70s have proved to be a powerful tool for inferring paleoenvironments associated with early hominins in Africa [START_REF] Bonnefille | Methode palynologique et reconstitutions paleoclimatiques au Cenozoique dans le Rift est-africain[END_REF]. Among these, the Australopithecus afarensis-bearing Hadar formation in the North Ethiopian Rift was extensively studied, and several levels proved to be rich in pollen grains [START_REF] Bonnefille | Palynology, stratigraphy and palaeoenvironment of a pliocene hominid site[END_REF][START_REF] Bonnefille | High-resolution vegetation and climate change associated with Pliocene Australopithecus afarensis[END_REF][START_REF] Bonnefille | Cenozoic vegetation, climate changes and hominid evolution in tropical Africa[END_REF]. Those levels were analyzed by palynologists of Bonnefille's team, usually over several weeks, in order to obtain adequate pollen counts (generally between 300 and 1000 grains depending on the pollen diversity of each sample) as the depositional and arid climate contexts were not favorable to pollen preservation (R. Bonnefille, pers. com.). Recently, the Hominin Sites and Paleolakes Drilling Project (HSPDP) drilled in this area to obtain paleoenvironmental records with high temporal resolution of the variations of the local hominin environment between 2.9 and 3.6 million years (Ma) ago [START_REF] Cohen | The Hominin Sites and Paleolakes Drilling Project: inferring the environmental context of human evolution from eastern African rift lake deposits[END_REF]. We have been studying two of those HSPDP cores, collected from near the lacustrine depocenter of Hadar Basin, the Northern Awash Osi-Isi (NAO, 11.31518°N, 40.73689°E) and from a location 3 km east of NAO, the Northern Awash Woranso (NAW, 11.32535°N, 40.76491°E). NAO and NAW were cored respectively to a depth of 187 and 245 meters below surface [START_REF] Mohan | Three novel species of Bacillariophyta (Diatoms) belonging to Aulacoseira and Lindavia from the Pliocene Hadar Formation, Afar Depression of Ethiopia[END_REF]. Analysis of 8 samples out of 175 from these two cores took one of the authors (B.B.) several months to complete, because both the preservation and concentration of pollen grains were low. A high-resolution pollen record at this site would give a fantastic record of paleovegetation changes during the time when Australopithecus afarensis thrived and when the first representatives of the Homo genus emerged [START_REF] Maslin | A synthesis of the theories and concepts of early human evolution[END_REF][START_REF] Villmoare | Early Homo at 2.8 Ma from Ledi-Geraru, Afar, Ethiopia[END_REF], but such a study would require more than one scientist working full time over several months. It is a classic case of "arid" sedimentary archives with very important environmental pollen data that cannot be correctly studied due to human limitations. Testing and exploring the potential of automated recognition to pollen taxa is, therefore, crucial.

In the 1960s, computer performance, image processing, and machine learning techniques were not sufficiently developed to realize Flenley (1968)'s visionary concepts of pollen recognition. During the last decade, however, dramatic improvements opened the way to automated recognition of pollen, through different approaches such as (1) feature extraction, (2) texture analysis, and (3) the combination of both. (1) Regarding feature extraction, the first breakthrough study by [START_REF] García | Pollen Grains Contour Analysis on Verification Approach[END_REF] combined morphological methods based on contour feature extraction of light microscopy (LM) images with a hidden Markov model (HMM) classifier. This approach allowed classifying 17 different pollen types from 11 different botanical families of honey bee's plants with 98.8% accuracy. [START_REF] Kaya | An expert classification system of pollen of Onopordum using a rough set approach[END_REF] used morphological measurements (polar axis length, equatorial axis length, colpus weight, exine thickness, etc.) with a data mining classifier to predict group membership for data instances. This approach allowed 20 very similar species of pollen grains in the genus Onopordum to be classified with an accuracy of 90.6%. The work is impressive but requires an initial manual/subjective definition of the recognition characteristic features and is only applicable to intact pollen grains. In addition, the accuracy of [START_REF] Kaya | An expert classification system of pollen of Onopordum using a rough set approach[END_REF]'s model is dependent of the choice of characteristic features [START_REF] Treloar | Towards automation of palynology 1: analysis of pollen shape and ornamentation using simple geometric measures, derived from scanning electron microscope images[END_REF].

(2) Another set of studies focused on texture analysis, with texture features derived from gray level patterns of the grain surface [START_REF] Fernandez-Delgado | Improved Classification of Pollen Texture Images Using Svm and Mlp[END_REF]. Using a combination of local linear transformation (LLT) feature vectors and a support vector machine (SVM) classifier, [START_REF] Fernandez-Delgado | Improved Classification of Pollen Texture Images Using Svm and Mlp[END_REF] were able to classify LM images of fresh pollen of five pollen types (in four different families) with an accuracy of 76%. Later, a more complex approach was developed by [START_REF] Marcos | Automated pollen identification using microscopic imaging and texture analysis[END_REF] using a texture feature vector composed of gray-level co-occurrence matrices (GLCM), log-Gabor filters (LGF), local binary patterns (LBP) and discrete Tchebichef moments (DTM), and Fisher's discriminant analysis (FDA) and k-nearest neighbor (KNN) to reach a final classification at the family level. This study achieved an accuracy of 94.8% for LM images of fresh pollen grains of 15 pollen types in 12 families [START_REF] Marcos | Automated pollen identification using microscopic imaging and texture analysis[END_REF], but the texture approach has been shown to be sensitive to grain rotation, lighting, image noise and the quality of texture preservation [START_REF] Han | Local Decimal Pattern for Pollen Image Recognition[END_REF]. To circumvent these problems, [START_REF] Han | Local Decimal Pattern for Pollen Image Recognition[END_REF] proposed to use local decimal patterns (LDP) instead of LBP, an approach robust to the noise and rotation of pollen images but which nevertheless could not tackle the challenge of recognizing damaged pollen.

(3) A combination of texture features and morphological analyses represents the last development. [START_REF] Rodriguez-Damian | Automatic detection and classification of grains of pollen based on shape and texture[END_REF] developed a classification system using both shape and texture analysis of LM images of pollen grains directly extracted from plants. Using a minimum distance classifier (MDC), multilayer perceptron (MLP) and SVM, three morphologically similar pollen types of Urticaceae were classified with an accuracy of 89%. Later, [START_REF] Chudyk | Development of an Automatic Pollen Classification System Using Shape, Texture and Aperture Features[END_REF] used a combination of 15 morphological features and five textures features on a set of LM images including one pollen type of Poaceae, one of Asteroideae and three of Betulaceae. By using SVM and Random Forest classifiers, they reached a success rate of 89% for intact pollen grains. However, this approach still performed poorly on damaged pollen.

Recently, the development of convolutional neural networks (CNNs) has opened a new era in image recognition. CNNs automatically extract the features of interest in an image that are relevant to the classification task [START_REF] Daood | Pollen Grains Recognition Based on Computer Vision Methods[END_REF]. For pollen, CNNs with different topology were tested to classify 23 pollen types with large morphological differences [START_REF] Sevillano | Improving classification of pollen grain images of the POLEN23E dataset through three different applications of deep learning convolutional neural networks[END_REF]. They achieved an accuracy of 97.2% with a LM images dataset [START_REF] Gonçalves | Feature Extraction and Machine Learning for the Classification of Brazilian Savannah Pollen Grains[END_REF] of intact pollen grains. [START_REF] Daood | Pollen Grains Recognition Based on Computer Vision Methods[END_REF] recognized z-stacked LM images of intact pollen by combining CNN feature vectors with recurrent neural networks (RNN). They achieved an accuracy of 100% for the classification of 10 pollen types of different families. Comparisons of these methods and their success rates on the same data set of images showed that the approaches based on CNNs are always the most accurate, and point toward the efficiency of CNNs in classifying natural objects such as pollen.

All these approaches proved to be efficient only on fresh or generally intact pollen grains, far from the reality faced by palynologists who must deal with damaged pollen due to taphonomic processes. [START_REF] Holt | Progress towards an automated trainable pollen location and classifier system for use in the palynology laboratory[END_REF][START_REF] Holt | Principles and methods for automated palynology[END_REF] and recently [START_REF] Khanzhina | Pollen grain recognition using convolutional neural network[END_REF] noticed the absence of a system adapted to "broken, deformed and clumped pollen" and explained it by technological limitations. [START_REF] Han | Local Decimal Pattern for Pollen Image Recognition[END_REF] pioneered the analysis on damaged pollen grains, unfortunately their approach did not succeed. [START_REF] Punyasena | Classifying black and white spruce pollen using layered machine learning[END_REF], however, successfully classified fossil grains of two Picea species (P. mariana and P. glauca) with an accuracy of 93.8%. They used a KNN with layered learning systems based on kernel density, applied to extracted shape and texture features from 3D fluorescence microscope (FM) images. Using the same set of pollen grains as [START_REF] Punyasena | Classifying black and white spruce pollen using layered machine learning[END_REF], [START_REF] Kong | Spatially Aware Dictionary Learning and Coding for Fossil Pollen Identification[END_REF] also obtained a high accuracy of 86.1% in classifying fossil grains of three Picea species (P. mariana, P. glauca and P. critchfieldii) using dictionary learning sparse coding (DLSC) on shape and texture features extracted from confocal FM images. However, the performances were largely dependent on the selection and quality of sample blocks [START_REF] Kong | Spatially Aware Dictionary Learning and Coding for Fossil Pollen Identification[END_REF][START_REF] Han | Local Decimal Pattern for Pollen Image Recognition[END_REF]. These results are nonetheless very promising, but we note that the deterioration of the Picea pollen considered in those two studies is very subtle (as is generally observed in peat sediments, e.g. [START_REF] Curry | The late-glacial and early Holocene geology, paleoecology and paleohydrology of the Brewster Creek Site, a proposed wetland restoration site, Pratt's Wayne Woods Forest Preserve and James[END_REF], and far from resembling the Pliocene pollen records of Eastern Africa.

The aim of this study is to develop a new system of automated identification of pollen that could be applied to down core fossil pollen grains. This system should be able to handle damaged and broken pollen grains, and should be easily applicable to images obtained with light microscopy (LM), as is commonly done in palynological laboratories. It should also allow identifications at higher taxonomical levels when identification at the species level is not reached.

Following recent developments in machine learning we chose to develop our system using sequential multiple CNNs. As a proof of concept for this study we chose eight pollen types: six among the Amaranthaceae, as they have very similar overall shape (spherical, periporate), one Poaceae (undifferentiated taxa), and one Cyperaceae (undifferentiated taxa), that is two Monocotyledonae with heterogeneous and varying surface patterns (psilate to finely verrucate). We focused on Amaranthaceae, Poaceae, and Cyperaceae because these three families represent 50% to 90% of the total pollen assemblage in both terrestrial and marine archives from Eastern Africa [START_REF] Bonnefille | Palynology, stratigraphy and palaeoenvironment of a pliocene hominid site[END_REF][START_REF] Bonnefille | Cenozoic vegetation, climate changes and hominid evolution in tropical Africa[END_REF]. Pollen-based biome reconstruction for Africa also largely rely on the presence and relative abundance of Amaranthaceae pollen [START_REF] Sobol | Predictive pollen-based biome modeling using machine learning[END_REF]. Amaranthaceae species, despite exhibiting very similar pollen morphologies are important ecological markers ('African Plant Database ', 2019). Being able to identify and count separately different Amaranthaceae could definitely improve paleoenvironment inferences. As a first step, this study makes no attempts to separate types among Poaceae and Cyperaceae, also because such discriminations have only been achieved so far using with Scanning Electron Microscopy [START_REF] Mander | Accuracy and consistency of grass pollen identification by human analysts using electron micrographs of surface ornamentation[END_REF].

Material and Methods

Datasets and image acquisition

We prepared one training and three validation datasets by taking pictures of pollen grains under light microscopy (LM) (Supporting Information, Table S1). The training dataset consists of 1102 globally intact pollen grains (hereafter referred to as the training dataset). The three validation datasets consist of 1) 276 grains of intact pollen (hereafter referred to as the intact dataset), 2) 223 deformed, folded, fragmented and/or broken grains (hereafter referred to as the damaged dataset), and 3) 97 pollen grains from Holocene and Pliocene age (hereafter referred to as the fossil dataset) (Fig. 1). In the fossil dataset, pollen grains also have an altered exine and mineral inclusions (Fig. 1). Eight pollen types were imaged with specimens taken from the reference collection of East African pollen species hosted at CEREGE, Aix-en-Provence, France (Supporting Information, Table S1) to constitute the training dataset, the intact dataset, and the damaged datasets: Achyranthes-type aspera, Aerva-type javanica, Aerva-type lanata, Celosia-type argentea, Cyathula-type orthacantha, Digeratype muricata, Poaceae, and Cyperaceae). The fossil pollen dataset includes only five of the eight pollen types available in the reference collection due to the limited availability of fossil material: Achyranthestype aspera, Aerva-type javanica, Digera-type muricata, Cyperaceae, and Poaceae (for sampling locations, depth, and ages see Supporting Information, Table S1). The damaged and fossil datasets were built using samples which were not considered for the training and intact pollen datasets to avoid biases in the estimation of the effectiveness of our approach.

Each pollen grain was imaged under natural light by taking a stack of pictures at 1 µm steps between the top and bottom surfaces of the grain, using an automated custom Leica DMRBE microscope controlled with a software. This step is semi-automated, whereby the image stack movement (z-axis) is automatic but setting the position (x and y axes) is performed manually. Since the stacking step is fixed to 1µm, the number of fused images is proportional to the size of the pollen. The number of images in the stack ranged from 20 to 40 depending on pollen type. Each stack was split into two halves, and only the half corresponding to the top hemisphere of each pollen grain was kept. The image stack was fused to create a single in-focus image (z-stacked imaging process) with the Helicon Focus 6 software, using the "depth map" method with radius set to 50 pixels and smoothing set to 10 pixels. We chose 1 µm steps empirically, as above this threshold the morphological information was less visible in the fused images and below this value, aberrations appeared into fused images. Each fused image was analyzed using a custom script written for the Fiji image analysis software, to center and crop the pollen into a square image [START_REF] Schindelin | Fiji: an open-source platform for biological-image analysis[END_REF]. Finally, all reframed fused images were resized to 128x128 pixels.

Image classification

Our system of automatic recognition is developed in the Python language [START_REF] Pérez | Python: An Ecosystem for Scientific Computing[END_REF] and principally uses the Keras and TensorFlow open-source software libraries [START_REF] Abadi | TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems[END_REF][START_REF] Chollet | Keras[END_REF]. It uses convolutional neural networks (CNNs) with a linear architecture similar to VGGNet [START_REF] Simonyan | Very Deep Convolutional Networks for Large-Scale Image Recognition[END_REF] We added an augmentation procedure to most of our trainings to generate new images at each epoch. This procedure generates new images by modifying the originals through random rotations (0°to 90°), random horizontal and vertical flips, and random width and height shifts (0% to 25%). But learning often did not progress when using augmentation because the generation of new images at each epoch made it difficult for the CNN to extract features. To solve this problem, we pre-trained the CNN without augmentation to extract features in its initial layers, then continued training using augmented images. By using this pretrained network for the training with augmentation, the CNN learns to combine these features at the end of the initial layers. This process is commonly called transfer learning [START_REF] Daood | Pollen Grains Recognition Based on Computer Vision Methods[END_REF] (Supporting Information, Fig. S1).

The CNNs trained with augmentation are integrated in a decision tree to form a multiple convolutional neural network (multi-CNNs) (Fig. 2). The multi-CNNs is composed of five main steps.

Step 1 aims at isolating Amaranthaceae from Monocotyledoneae.

Step 2 is made to evaluate if pollen identified as Monocotyledonae in step 1 could be altered Amaranthaceae. Indeed, altered pollen of Dicotyledoneae which have lost their ornamentations and part or all their outer layer (ectexine) may show similarities with Monocotyledonae that only have one layer of exine. To do this in step 2, we used a finer mapping with a separation of Poaceae and Cyperaceae which exhibit different morphologies when intact or slightly altered. Altered Monocotyledonae such as Poaceae and Cyperaceae may easily lose parts of their exine and be deformed or broken, because they are made of a single thin layer. To optimize the chances of recognition of altered pollen, two networks with the same mapping were used but with different augmentation, one focused on shape (CNN 2.1), and the other on texture (CNN 2.2). In step 3A, several CNNs were used; each one being specialized in the recognition of one pollen type of Amaranthaceae to maintain CNN high accuracy. The results of all these specialized CNNs are then compiled, the pollen is classified into one Amaranthaceae pollen type or as Amaranthaceae uncertain. In step 3B, the same logic is used as for step 2: two networks with the same mapping are used with different augmentation to separate Poaceae and Cyperaceae. If the results of the two CNNs are incongruous, the pollen is classified as an uncertain Monocotyledoneae. Finally, in step 4, we use the results of the CNNs 2.1 and 2.2 to classify Monocotyledoneae uncertain and Amaranthaceae uncertain in Monocotyledoneae indeterminable, Amaranthaceae indeterminable, or indeterminable pollen.

To evaluate the efficiency of augmentation and multi-CNNs, we tested three other approaches: (i) one using multi-CNNs without augmentation in step 1 and 3A, (ii) one simple-CNN without augmentation, and (iii) another simple-CNN with full augmentation of random rotation of 0-90°, random horizontal and vertical flip, and random width and height shift of 0-25%. The number of palynomorphs analyzed for each pollen type in the intact, damaged, and fossil sets is unbalanced. The number of fossil grains for each type, in particular, is low. As such, we used the average per-class accuracy (APC%) as it is more appropriate for the evaluation of the algorithm performance in this case [START_REF] Zheng | Evaluating Machine Learning Models: A Beginner's Guide to Key Concepts and Pitfalls[END_REF].

Results

Global comparison of used/unused augmentation and single-CNNs/multi-CNNs

The four different classification setups yield misclassification rates of 0% to 5.9% for intact pollen, 2.8% to 22.5% for damaged pollen, and 3.7% to 45.3% for the fossil pollen.

The multi-CNNs including augmentation always gives the best results (Fig. 3). Compared with the three other setups, the one using augmentation and multi-CNNs increases the success rate for classification in the lowest taxonomic levels (Achyranthes-type aspera, Aerva-type javanica, Aerva-type lanata, Celosia-type argentea, Cyathula-type orthacantha, Digeratype muricata, Poaceae, and Cyperaceae) and keeps classification rates at 99.3% for intact pollen, 85.7% for damaged pollen, and 80.8% for fossils pollen (Fig. 3).

In detail, augmentation increases the success rate for classification in lowest levels for simple-CNN and multi-CNNs by +3.1% and +2.7% for intact pollen, +3.1% and +16.3% for damaged pollen, and +10.5% and +43.8% for fossil pollen, respectively. Image augmentation also reduces misclassification rates for simple-CNN and multi-CNNs by -3.1% and -0.8% for intact pollen, -3.1% and -7.3% for damaged, and -10.5% and -12.6% for fossil pollen, respectively (Fig. 3). Similarly, the use of multi-CNNs reduces misclassification rates, for the scripts without augmentation (-5.1% for intact pollen, -12.4% for damaged, and -29% for fossil pollen), and for those with augmentation (-2.8% for intact pollen, -16.6% for damaged, and -31.1% for fossil pollen) (Fig. 3).

Multi-CNNs with augmentation also increase the detection of Amaranthaceae and Monocotyledonae misclassification in step 1 and 2. For the damaged dataset, five misclassified pollen grains of Monocotyledonae were directed into step 3A normally reserved to Amaranthaceae (Supporting Information, Fig. S2a). All of these five misclassified pollen grains of Monocotyledonae were identified as Amaranthaceae uncertain in step 3A (Supporting Information, Fig. S2a) then classified as pollen indeterminate in final step 4 (Fig. 2). This is also observed for fossil data in Step 3A and Step 3B (Supporting Information, Fig. S2c,d).

Details of efficiency of Multi-CNNs with augmentation

Our Multi-CNNs with augmentation classified the intact pollen grains with misclassification rates of 0%. All intact pollen are correctly classified (Fig. 3). We show that within the Amaranthaceae family, six types with similar morphologies can be distinguished. Over 208 images of intact Amaranthaceae pollen, 99.3% were successfully classified within different Amaranthaceae types and only 0.7% (two Cyathula-type orthacantha) could not be clearly identified but could still be defined as Amaranthaceae indeterminable (Fig. 3 and4a). For Poaceae and Cyperaceae, all were correctly classified as Poaceae and Cyperaceae despite the heterogeneity of textures and features, and the complex shape of Cyperaceae grains.

The damaged pollen grains, however, show a higher misclassification rate than intact pollen with 2.8% misclassification (Fig. 3). Like for intact pollen, the misclassifications are evenly distributed to different classes (Fig. 4b). 85.7% of the damaged pollen have been successfully classified to the lowest taxonomic levels (Achyranthes-type aspera, Aerva-type javanica, Aerva-type lanata, Celosia-type argentea, Cyathula-type orthacantha and Digera-type muricata, and Poaceae and Cyperaceae) and 6.6% have been successfully classified to higher taxonomic ranks (5.6% in Amaranthaceae indeterminate, and 1% in Monocotyledonae indeterminate), that is -13.6% and +5.9% than intact pollen, respectively. Of the 167 pollen classified as Amaranthaceae, only 6.6% were classified as Amaranthaceae indeterminate, 6.6% were classified as pollen indeterminate, and none were misclassified as Monocotyledonae indeterminate (Fig. 3 and4b).

The fossil grains were classified with 3.7% misclassification, a +0.9% increase compared to damaged pollen (Fig. 3). In this case, misclassifications are also evenly distributed into different classes (Fig. 4c). 80.8% of total pollen are successfully classified to the lowest taxonomic levels, compared to -4.9% for damaged pollen. We have one increase of pollen classified to higher taxonomic ranks (+4.8%) compared with damaged pollen. We also show a slight decline of pollen classified as pollen indeterminate with a rate of 4% (Fig. 3). The presence of mineral inclusions does not seem to interfere with identification (Fig. 1). Finally, out of the 30 pollen classified as Amaranthaceae, 17% were classified as Amaranthaceae indeterminate.

Discussion

Our model has been tested on several datasets with success. The overall computing time required to setup automatic recognition (time required to do all trainings) was about 11 hours using the Nvidia Titan X GPU for the computing. After the training, each test (inference) takes less than a minute on the same machine, and reproducibility tests show slight variations of <2 APC% (not shown). Our study uses image datasets for the "training dataset", "intact dataset", and "damaged dataset" which sizes are in the range of the automatic recognition studies mentioned above, but some may argue that our "fossil dataset" is relatively small. It is, however, a good test for our model because the proportions of Amaranthaceae, Cyperaceae, and Poaceae pollen in the fossil image dataset are close to proportions that are usually observed in modern and fossil pollen assemblages of about 300-400 grains from arid areas of northeastern Africa. The results on the fossil data give a good overview of what can be obtained on real fossil samples. One caveat, not addressed in our study, is that usually, not all pollen types in the fossil/modern sediment or aerial trap are known. As such, the future automatic recognition systems will have to include in the training dataset pollen types that are not related to any of the analyzed/tested types. We are confident, however, that our system should perform well because in our experiment on the fossil pollen dataset, which had none Aerva-type lanata, Celosiatype argentea, and Cyathula-type orthacantha, we reached significant levels, suggesting that including unknown pollen types should not be a major problem in future applications.

Our study shows that a single CNN is not able to manage the recognition of 8 pollen types when the dataset includes damaged or fossil pollen. With a single CNN, misclassification considerably increases with increased grain deterioration. The origin of this problem is linked to the attempt to classify into low taxonomic ranks highly degraded pollen which have lost most of their surface features and ornamentation. This loss of information complicates the recognition by the CNN when the CNN has been trained to recognize eight pollen types. The new approach we designed and which combines the use of augmentation and multi-CNNs, increases the accuracy of classification for the damaged and fossil pollen. This is principally related to the reclassification of highly degraded pollen into higher taxonomic ranks, and the use of CNNs with augmentation and specialized in the recognition of only one pollen type at a time for the lower taxonomic ranks. The multi-CNNs system is also useful for identifying and self-correcting a significant part of these misclassifications at the high taxonomic level in steps 1 and 2, with the support for the systems set up in steps 3A and 3B. The need for this self-correction is negligible for intact pollen due to the absence of misclassification at the high taxonomic level, but is important for the damaged and fossil pollen which do have misclassification at the high level due to their deteriorated features. Consequently, it is very relevant to use augmentation and a multi-CNNs system for the recognition of fossil or damaged pollen grains.

Our approach based on multi-CNNs with augmentation classifies each class of intact pollen with 0 APC% error. This is as good as in recent studies on intact pollen with a similar number of pollen types [START_REF] Khanzhina | Pollen grain recognition using convolutional neural network[END_REF][START_REF] Sevillano | Improving classification of pollen grain images of the POLEN23E dataset through three different applications of deep learning convolutional neural networks[END_REF][START_REF] Daood | Pollen Grains Recognition Based on Computer Vision Methods[END_REF][START_REF] Daood | Sequential Recognition of Pollen Grain Z-Stacks by Combining CNN and RNN[END_REF]. For the damaged pollen, we achieved misclassification rate of 2.7 ACP%, which is slightly higher than that of intact pollen (Fig. 1). To our knowledge, this is the first time that such good accuracy on highly damaged pollen grains has been reached [START_REF] Holt | Principles and methods for automated palynology[END_REF][START_REF] Han | Local Decimal Pattern for Pollen Image Recognition[END_REF][START_REF] Khanzhina | Pollen grain recognition using convolutional neural network[END_REF]. Based on all human-made pollen counts of actual soil and mud samples in the African Pollen Database available for Ethiopia (115 samples), we find that indeterminable (i.e. damaged) pollen represent on average about 8% of total pollen count, and that indeterminable Amaranthaceae are most common: they represent about 35% out of total Amaranthaceae ('African Pollen Database', 2019). Our percent of indeterminable pollen out of the total pollen (2.7 APC%) and of indeterminable Amaranthaceae out of the total Amaranthaceae (5.6 APC%) are thus better than the human counts, for modern damaged pollen in the Ethiopian dataset [START_REF] Bonnefille | Associations polliniques actuelles et quaternaires en Ethiopie (vallées de l'Awash et de l'Omo[END_REF][START_REF] Buchet | Transport des pollens dans les fleuves Omo et Awash (Ethiopie): étude des vases actuelles[END_REF]'African Pollen Database', 2019).

As mentioned before, [START_REF] Punyasena | Classifying black and white spruce pollen using layered machine learning[END_REF] and [START_REF] Kong | Spatially Aware Dictionary Learning and Coding for Fossil Pollen Identification[END_REF] obtained good results for fossil pollen of Picea, but the grains in their study came from a peat; altered pollen in peat cores are far from resembling altered fossil pollen grains from lacustrine Pliocene samples. Our approach is the first to present successful results (only 4.1% misclassification) for fossil pollen with important deterioration, typical for arid areas. In the human-made Pliocene pollen dataset of about 25 samples obtained for the Hadar formation by Bonnefille's team [START_REF] Bonnefille | Palynology, stratigraphy and palaeoenvironment of a pliocene hominid site[END_REF] indeterminable pollen may account for up to about 30% of total pollen counts (10% in average). Of these 25 samples, 19 have Amaranthaceae of which about 80% on average were classified as "Amaranthaceae indeterminable" [START_REF] Bonnefille | Palynology, stratigraphy and palaeoenvironment of a pliocene hominid site[END_REF]. The percentage of fossil pollen indeterminate that we obtained with our automated system is of 4%, i.e. well within the average of [START_REF] Bonnefille | Palynology, stratigraphy and palaeoenvironment of a pliocene hominid site[END_REF], and the taxonomic precision is better as only 17% of Amaranthaceae were classified as indeterminable. Our method, therefore, has the potential to be applied to both damaged, fossil, and modern pollen grains from arid areas, and may even improve pollen taxa identifications within the Amaranthaceae.

Using our multi-CNNs with augmentation, we were able to classify both morphologically similar pollen (pollen types of Amaranthaceae) at the species or genus level, and morphologically different pollen (Amaranthaceae versus Poaceae versus Cyperaceae), without having significant misclassification for intact, damaged, and fossil pollen (Fig. 4).

For the Monocotyledonae, we can observe an increase in fossil pollen classified as indeterminable Monocotyledonae (+6.8%) in comparison to the damaged pollen, but we do not have significant increases for Amaranthaceae (Fig. 3). The fossil grains of Monocotyledonae have more mineral inclusions than Amaranthaceae, but we discard the hypothesis that mineral inclusions in pollen is the origin of these increases because fossil pollen of Monocotyledonae bearing mineral inclusions are correctly identified (Fig. 1). We see on the images that fossil pollen of Monocotyledonae is often "stuck" in residual sediments (Fig. 1). This is very similar to images of "contaminated grains" of [START_REF] Han | Local Decimal Pattern for Pollen Image Recognition[END_REF], who suggested that this hinders identification. Our study shows that our system overcomes the sediment contamination and is able to correctly identify fossil pollen of Amaranthaceae even when sediment is attached to the grains. The deformation of pollen grains is another hindrance to identification [START_REF] Holt | Progress towards an automated trainable pollen location and classifier system for use in the palynology laboratory[END_REF][START_REF] Han | Local Decimal Pattern for Pollen Image Recognition[END_REF][START_REF] Khanzhina | Pollen grain recognition using convolutional neural network[END_REF] but our fossil grains of Monocotyledonae are no more deformed than damaged grains of Monocotyledonae or fossil grains of Amaranthaceae (Fig. 1). We posit that, within the biodiversity range we investigated, this issue stems from the structural weakness of Monocotyledonae (in the pollen studied) as this family shows a thinner and weaker exine than Amaranthaceae. As for human eyes, automated pollen recognition requires that the exine texture must be relatively well preserved. This agrees with the idea of [START_REF] Li | Towards automation of palynology 2: the use of texture measures and neural network analysis for automated identification of optical images of pollen grains[END_REF] that the "surface texture is frequently characteristic, even when grains are damaged or fragmented" for the pollen.

Our multi-CNNs with augmentation is operational. At CEREGE, it is used occasionally to assist with identification of fossil Amaranthaceae when identification to type is not straightforward. The main bottleneck to an extended use of our recognition system is the acquisition time, which is manual and therefore, timeconsuming, preventing an easy addition of new pollen types. Adding an automated acquisition step would therefore provide a complete automatic pollen counting system, saving a lot of time for palynologists of arid areas and possibly elsewhere. With such a system, it would probably be easy to acquire images of large pollen reference collections within in a few months. The prospect of a fully automated pollen counting system for paleoclimatic and paleoenvironmental reconstructions, similar to the operating systems developed for other microfossils like coccoliths or foraminifera [START_REF] Beaufort | Automatic recognition of coccoliths by dynamical neural networks[END_REF]Marchant et al., in preparation), can be foreseen in the very near future. These automated systems will pave the way to high-throughput palynology studies, including morphometric studies.

Conclusions

In this study, we proposed a robust system for classification of very damaged and badly preserved fossil grains. We have developed a classification topology that has flexibility in the choice of taxonomic levels used for classification. It can, like a palynologist, assign higher taxonomic ranks if the characteristics of the image are not sufficient for robust identification at a lower taxonomic level. Moreover, if images cannot be properly classified, it can declare them as indeterminable. Our system has the advantage of using simple LM images and does not require the implementation of complex and expensive systems such as confocal fluorescence microscopes. With the damaged pollen, we have obtained results similar to or better than those obtained from human pollen counting performed by CEREGE palynologists on modern soils and Pliocene sediments of the Awash Valley in Ethiopia.

The system developed here does not yet allow a complete count of fossil pollen. It remains limited to a few families and to a very limited number of taxa in comparison to overall pollen diversity. Evaluating and improving how the system reacts to pollen types or other grains not included in the training set is also important because usually not all pollen types in the sediment core are known. To handle this, one solution may be the addition of an "unknown" category. Our results, based on a limited dataset but representing a wide range of biases affecting pollen grains from their production to their fossilization, allow the possible development of automatic pollen recognition for routine palynological studies of samples coming from multiple depositional environments and with different degrees of pollen alteration. It would also be interesting to see if it is possible to increase the accuracy of our system with the use of a much larger number of training images.

It is also important to specify that the system presented here cannot be directly extended to other pollen families as it relies more on the morphology of the pollen types than on the taxonomic relationship, although the two are related. It is also important to have a good knowledge of how the morphology of each type of pollen changes with degradation or fossilization in order to build relevant mappings and logical steps in the classification system to cover all stages of pollen grain degradation. The expertise of paleo-palynology is therefore critical to the extension of this system. The next step of this work will be to extend the system to automatically take pictures of pollen grains from microscope slides. The automatic acquisition will be inspired by the processing software developed for coccoliths at CEREGE [START_REF] Beaufort | Automatic recognition of coccoliths by dynamical neural networks[END_REF]) and modified by Martin Tetard and Yves Gally for Radiolaria tests (Martin Tetard, personal communication). It can be summarized in 6 steps: (1) color pollen grains with Safranin for easier segmentation, (2) take grayscale images of microscope fields of view (FOVs) by incrementally stepping through the slide (1 µm step), (3) segment each pollen grains in each stacked FOV (saving their x and y coordinates on the original unstacked FOV), (4) generate sub-stacks for each previously recorded pollen grain from each original unstacked FOV, (5) remove the unfocused pollen images from each pollen sub-stack using a grey level threshold, and (6) apply the method in the second paragraph of part 2.1 for finalizing image processing prior to automated recognition. With this automatic acquisition, it will be possible to fully scan reference pollen collections and thus quickly build a large database of pollen images to develop an automatic pollen counting system (acquisition and recognition) for modern and fossil pollen from eastern Africa, for example.

(wihout_augm).py, 16.5 Ko), and multi-CNNs without augmentation (Multi-CNN_test_V3.5.2(wihout_augm).py, 40.9 Ko). In the CNN_solo folder, we have for each CNN model parameters, a folder with file of CNN model parameter used in .ckpt, histograms of accuracy, loss and learning rate during the training in .bmp and table of accuracy, loss and learning rate during the training in .csv. The folder "intact", "damaged" and "fossil" contain respectively the images for "training dataset"/"intact pollen dataset", "damaged dataset", and "fossil dataset". The User_manual.pdf explains how to use these scripts to reproduce our results.

These scripts have been developed by Benjamin BOUREL (chebenjamin@laposte.net ; +33 6 63 49 85 24) with the help of Ross MARCHANT. These scripts were first available the 13 th October 2019. They were created in the open-source Anaconda 3 v.5.2.0 (https://www.anaconda.com) with Spyder v. 3.3.6 in python v.3.6 (Pérez et al.,2011). We also used NumPy [START_REF] Oliphant | A guide to NumPy[END_REF], Scikitimage (van der Walt et al., 2014), Scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF]Matplotlib (Hunter, 2007)

CaptionsFigure 1 :

 1 Figure 1: Pollen images with automatic zstack of 128x128 pixels for all pollen types of the intact, damaged, and fossil pollen datasets. The name under each image is the final label assigned by the multiple convolutional neural networks (multi-CNNs) with augmentation.

Figure 2 :

 2 Figure 2: Schematic of the classification system based on multiple convolutional neural networks (multi-CNNs) with augmentation. aa: Achyranthes-type aspera; aj: Aerva-type javanica; al: Aerva-type lanata; amar: Amaranthaceae; c: Cyperaceae; ca: Celosia-type argentea; co: Cyathula-type orthacantha; dm: Digera-type muricata; mono: Monocotyledonae; p: Poaceae; uncert: uncertain; indet: indeterminable.

Figure 3 :

 3 Figure 3: Results of our classification system (multi-CNNs with augmentation) as a function of pollen dataset and in comparison with other setups. Pollen types of the lowest taxonomic levels: Achyranthes-type aspera, Aerva-type javanica, Aerva-type lanata, Celosia-type argentea, Cyathula-type orthacantha and Digera-type muricata, and Poaceae and Cyperaceae.indet.: indeterminable. The APC% is the percentages based on average per-class.

Figure 4 :Figure S1 :

 4S1 Figure 4: Confusion matrix for the intact (a), damaged (b) and fossil (c) pollen dataset for final classes.aa: Achyranthes-type aspera; aj: Aerva-type javanica; al: Aerva-type lanata; amar: Amaranthaceae; c: Cyperaceae; ca: Celosia argentea; co: Cyathula-type orthacantha; dm: Digera-type muricata; mono: Monocotyledonae; p: Poaceae; indet: indeterminable.Supporting Information captionsFigure S1: Effect of transfer learning (the use of pretrained CNN) on the training with augmentation of CNN. Dataset: training pollen dataset; mapping: Achyranthes-type aspera, Aerva-type javanica, Aerva-type lanata, Celosia-type argentea, Cyathula-type orthacantha, Digera-type muricata, Cyperaceae, and Monocotyledonae.

Figure S2 :

 S2 Figure S2: Confusion matrix for the damaged pollen dataset (classes of step 2A (a) and classes of step 2B (b)) and the fossil pollen dataset (classes of step 2A (c) and classes of step 2B (d)). aa: Achyranthes-type aspera; aj: Aerva-type javanica; al: Aervatype lanata; amar: Amaranthaceae; c: Cyperaceae; ca: Celosia-type argentea; co: Cyathula-type orthacantha; dm: Digera-type muricata; mono: Monocotyledonae; p: Poaceae; indet: indeterminable.

Figure 1 Figure 2 Figure 3 Figure 4

 1234 Figure 1

Table S1 :

 S1 Origin of pollen grains and distribution in the datasets. ka: thousand years.

Table S2 :

 S2 Excel file with detailed calculations for percentages of average perclass accuracy (APC%).

Acknowledgments

We thank J-C. Mazur of the CEREGE's micropaleontology platform for help during pollen sample preparations, and F. Chalié letting us use the automated microscope. We also thank G. Gassier for help with the server, and M. Djamali for his pollen slides from Urima Lake (Iran). This work was supported by Aix-Marseille University (doctoral fellowship to BB), the research grant ANR PRCE FIRST ANR-15-CE04-0006-01. The research leading to these results has received funding from the People Program (Marie Curie Actions) of the European Union 's Seventh Framework Program (FP7/2007-2013) under REA grant agreement n. PCOFUND-GA-2013-609102, through the PRESTIGE program coordinated by Campus France.

Computer code availability

All files and folders presented here are downloadable at https://github.com/Beniofh/Multi-CNN. We used the script Multi-CNN_test_V3.5.2.py (40.9 Ko) to recognize pollen types using multi-CNNs with augmentation. Multi-CNNs with augmentation is compared to single-CNN with augmentation (script CNN_test_v2.1.0.py, 16.5 Ko), single-CNN without augmentation (CNN_test_v2.1.0


Mnacho Echenim

Radu Iosif

Nicolas Peltier

Entailment is Undecidable for Symbolic

  L'archive ouverte pluridisciplinaire

Introduction

Separation Logic (SL) is widely used in program verification to reason about programs manipulating dynamically allocated data structures [START_REF] Reynolds | Separation Logic: A Logic for Shared Mutable Data Structures[END_REF].It forms the basis of several industrial-scale static program analyzers [START_REF] Calcagno | Moving fast with software verification[END_REF][START_REF] Berdine | Slayer: Memory safety for systems-level code[END_REF][START_REF] Dudka | Predator: A practical tool for checking manipulation of dynamic data structures using separation logic[END_REF]. SL formulae describe heaps, i.e. finite partial functions mapping locations (memory addresses) to tuples of locations (records) of a fixed size. A formula x → (y 1 , . . . , y κ ) states that the image of the location associated with x in the heap is the tuple of locations associated with (y 1 , . . . , y κ ), whereas φ 1 * φ 2 states that the heap can be split into two disjoint parts satisfying φ 1 and φ 2 , respectively. Describing unbounded data structures (lists, trees, etc.) is possible by the use of predicate symbols, the interpretation of which is given by a set of userdefined inductive rules. These SL formulae, in which boolean conjunction does not occur and negation is restricted to disequalities, are commonly called symbolic heaps.

Testing entailment between symbolic heaps is known to be decidable for a class of inductive definitions satisfying three natural conditions [START_REF] Iosif | The tree width of separation logic with recursive definitions[END_REF]: [START_REF] Iosif | The tree width of separation logic with recursive definitions[END_REF] progress, stating that every inductive rule allocates exactly one memory cell, (2) connectivity, ensuring that the locations allocated during the unfolding of a predicate form a tree-like connected structure and (3) establishment, stating that all the existentially quantified variables introduced during the unfolding of inductive predicates must be eventually allocated.

These conditions play very different rôles. Condition (1) is actually not restrictive and is considered for simplicity only. In contrast, Condition (2) is crucial for decidability: entailments are undecidable for inductive definitions that are not connected, because then the inductive definitions may be used to encode context-free languages, the inclusion of which is known to be undecidable. The remaining question is whether condition (3) is actually required for decidability or whether it can be ignored. We show that discarding this condition leads to undecidability.

The precise rôle of establishment for decidability of entailments between symbolic heaps has been an open problem since establishment was identified as a condition ensuring, with progress and connectivity, decidability of entailments between symbolic heaps [START_REF] Iosif | The tree width of separation logic with recursive definitions[END_REF]. The proof of [START_REF] Iosif | The tree width of separation logic with recursive definitions[END_REF] used a reduction of the entailment between symbolic heaps to the (decidable) satisfiability of monadic second order logic on graphs with bounded treewidth [START_REF] Courcelle | The monadic second-order logic of graphs. I. Recognizable sets of finite graphs[END_REF] and establishment was crucial to ensure that the considered heaps have a bounded treewidth. We recently showed that establishment can be replaced by a strictly more general condition restricting the form of the disequations in the system [START_REF] Echenim | Decidable entailments in separation logic with inductive definitions: Beyond established systems[END_REF]. The undecidability proof for non-established definitions given here implies the undecidability of entailments for definitions that cannot be transformed into the restricted disequations form [START_REF] Echenim | Decidable entailments in separation logic with inductive definitions: Beyond established systems[END_REF].

Separation Logic

Let κ ≥ 0 be a natural number(denoting the number of record fields), V and C be two disjoint sets of symbols (denoting respectively variables and constants 1 , and P be a set of predicate symbols. Each symbol p ∈ P is associated with a unique arity #(p) ≥ 1.

The set of separation logic symbolic heaps φ is inductively defined as follows, where

x, x , y 1 , . . . , y κ , z 1 , . . . , z #(p) ∈ V ∪ C , u ∈ V and p ∈ P : φ ::= x ≈ x | x ≈ x | x → (y 1 , . . . , y κ ) | φ * φ | p(z 1 , . . . , z #(p) ) | ∃u . φ.
A formula is predicate-free if it contains no symbols from P . We denote by var(φ) the set of variables freely occurring in φ. A substitution is a partial mapping from V to V ∪ C . The substitution of domain {x 1 , . . . , x n } mapping every variable x i to t i is denoted by

[x i ← t i | 1 ≤ i ≤ n].
For every formula φ and substitution σ, φσ denotes the formula obtained by replacing each free occurrence of a variable x in φ by σ(x) (bound variables are renamed to avoid collisions).

Let U be a countably infinite set of locations, with C ⊆ U. A structure is a pair (s, h) where s is a store, i.e., a total mapping from V ∪ C to U that is the identity on C ; and h is a heap, i.e., a partial finite mapping from U to U κ . Two heaps h 1 and h 2 are disjoint iff dom(h 1 ) ∩ dom(h 2 ) = / 0, and in this case h 1 h 2 denotes the union of disjoint heaps.

A system of inductive definitions (SID) R is a set of rules p(x 1 , . . . , x #(p) ) ⇐ φ, where x 1 , . . . , x #(p) are pairwise distinct variables and φ is a symbolic heap with var(φ) ⊆ {x 1 , . . . , x #(p) }. A system R is progressing and connected if every rule in R is of the

form p(x 1 , . . . , x #(p) ) ⇐ ∃y 1 , . . . , y m . x 1 → (u 1 , . . . , u #(p) ) * * m i=1 p i (y i 1 , . . . , y i #(p i ) )
, where for all i ∈ 1, m , we have y i 1 ∈ {u 1 , . . . , u #(p) }. For any formula φ, we write φ → R ψ if ψ is obtained from φ by replacing an occurrence of a predicate atom p(x 1 , . . . ,

x #(p) ) by ρ[y i ← x i | 1 ≤ i ≤ #(p)],
where R 1 Constants are introduced only to improve readability. One could replace them by variables added as parameters to every predicate symbol, and adding disequality constraints x ≈ y for all x, y ∈ C , stating that all constants are mapped to distinct locations. Hence the undecidability result holds also for C = / 0. contains a rule p(y 1 , . . . , y #(p) ) ⇐ ρ and the existential variables of ρ are α-renamed to avoid collisions. As usual, → * R denotes the reflexive and transitive closure of → R . A formula ψ such that φ → * R ψ is called an R -unfolding of φ. A SID R is established if, in every predicate-free R -unfolding ψ of a predicate atom p(x 1 , . . . , x #(p) ), each existentially quantified variable in ψ is asserted equal to a variable x, where x → (y 1 , . . . , y κ ) is a an atom of ψ.

For all structures (s, h), symbolic heaps φ containing no predicate atom and SIDs R , we write (s, h) |= φ iff one of the following holds:

(i) φ ≡ x ≈ x (resp. φ ≡ x ≈ x ), dom(h) = / 0 and s(x) = s(x ) (resp. s(x) = s(x )); (ii) φ ≡ x → (y 1 , . . . , y κ ), dom(h) = {s(x)} and h(s(x)) = (s(y 1 ), . . . , s(y κ )); (iii) φ ≡ φ 1 * φ 2 and h = h 1 h 2 where (s, h i ) |= φ i ,
for all i ∈ {1, 2}; (iv) φ ≡ ∃x . φ and there exists a store s coinciding with s on all variables and constants distinct from x such that (s , h) |= φ . This definition is extended to formulae containing predicate symbols as follows:

(s, h) |= R φ iff (s, h) |= R ψ, for some predicate-free R -unfolding ψ of φ.

Encoding the Post Correspondence Problem

The undecidability proof uses a reduction from a variant of Post's Correspondence Problem (PCP). We denote by w[i] the i-th character2 of the word w, and by |w| its length, so that w = (w[1], . . . , w[|w|]). For readability, we shall use the following convention: when a capital letter (say, A) is used to denote a natural number, then the corresponding lower case letter a will denote a natural number ranging over the interval 1, A . Further, the variable i will range over the set {1, 2}. We recall that the PCP asks, given two sequences u i = (u i 1 , . . . , u i N ) (with i = 1, 2) of words on the same alphabet V, whether there exists a nonempty sequence s = (s 1 , . . . , s K ) of elements of 1, N (called a solution of the PCP) such that u 1 s 1 . . . . .u 1 s K = u 2 s 1 . . . . .u 2 s K . The latter word is called a witness of the PCP and its length will be denoted by L. PCP is a well-known undecidable problem. We assume that all the words in u i are nonempty (which does not impact the undecidability proof of the PCP). We consider a slightly adapted version of the PCP, in which: (i) The last element of both sequences of words is a special character $ = u 1 N = u 2 N , not occurring in the words u i n , for i ∈ {1, 2}, n ∈ 1, N -1 ; and (ii) any solution must be such that K > 1, s K = N and s k = N if k < K. In other words, in this adapted version, the witness must end with the special element $. It is clear that the standard PCP can be reduced to the adapted version, which is thus also undecidable. We denote by M i the maximal length of the words in

u i , i.e. M i def = max{|u i n | | n ∈ 1, N }, for i ∈ {1, 2} and let M def = max({M 1 , M 2 }).
We consider two special constants nil and ⊥, and we associate all natural numbers m ∈ 1, M and all elements a ∈ V with pairwise distinct constants also distinct from nil and ⊥. These constants will be, for the sake of readability, also denoted by m or a (assuming, w.l.o.g., that V ∪ N ∪ {⊥, nil} ⊆ C and V ∩ N = / 0). We assume next that κ = 6, i.e. we fix the number of record fields. The encoding could easily be adapted for any κ ≥ 2, using binary trees to represent tuples of elements, but this would greatly hinder readability, because of the progress condition which requires that every rule allocates exactly one location. For readability, we shall actually consider elements referring to tuples of any length n ≤ 6, where missing elements are implicitly replaced by the constant ⊥. Hence the notation x → (y 1 , . . . , y n ) for n ≤ 6 stands for x → (y 1 , . . . , y n , ⊥ 6-n ). Similarly, h( ) = ( 1 , . . . , n ) stands for h( ) = ( 1 , . . . , n , ⊥ 6-n ).

For the sake of conciseness, we allow disjunctions in the right-hand side of the inductive rules: a rule p( x)

⇐ φ * (ψ 1 ∨ ψ 2 ) stands for {p( x) ⇐ φ * ψ 1 , p( x) ⇐ φ * ψ 2 }.
We begin by showing that the solutions of the PCP can be encoded by structures of a specific form. Definition 1. A heap h is a PCP-encoding if there exists a word w with L def = |w| > 1, a natural number K > 1 and pairwise distinct locations 1 , . . . , L+1 and 1 , . . . , K+1 with L+1 = K+1 = nil, such that:

1. dom(h) = { 1 , . . . , L , 1 , . . . , K }. 2. For every l ∈ 1, L , h( l ) is of the form ( l+1 , w[l], 1 l , p 1 l , 2 l , p 2 l ), for locations 1 l , 2 l and integers p 1 l , p 2 l ∈ 1, M , with 1 1 = 2 1 = 1 , 1 L = 2 L = K and p 1 1 = p 2 1 = p 1 L = p 2 L = 1. 3. For every k ∈ 1, K , h( k ) is of the form ( k+1 , s k ) for some s k ∈ 1, N , with s K = N and s k = N if k < K.
The location 1 is called the root of h. We denote w(h) def = w and s(h) def = (s 1 , . . . , s K ); clearly h uniquely defines w(h) and s(h).

nil s 1 s 2 N w[1] w[2] w[L] 1 l 1 l 2 l p 1 l p 2 l • • • • • • • • • • • • • • • 1 1 L K Figure 1:
Encoding of a PCP Solution by a Heap

The sequence 1 , . . . , L encodes the linked sequence of characters w[1],. . . , w[L] in a witness w. Each location l refers to a tuple containing the next element of the sequence l+1 as well as the character w[l], and locations 1 l , p 1 l , 2 l , p 2 l , which will be used to denote the position of the character within the words u 1 s 1 . . . . .u 1 s K and u 2 s 1 . . . . .u 2 s K (see Definition 2). The sequence 1 , . . . , K represents the solution s. Each location k points to a tuple containing the next element of the sequence k+1 and the k-th component of s (see Fig. 1). The next definition states conditions ensuring that a PCP-encoding indeed encodes a solution of the PCP.

Definition 2. A PCP-encoding h is i-consistent for i = 1, 2 if, for all l ∈ 1, L , there exists k ∈ 1, K such that, with the notations of Definition 1, i l = k and: 1. w[l] is the p i l -th character of the word

u i s k (i.e., w[l] = u i s k [p i l ]). 2. If l = L and p i l < |u i s k | then i l+1 = k and p i l+1 = p i l + 1. 3. If l = L and p i l = |u i s k | then k < K, i l+1 = k+1 and p i l+1 = 1.
Example 3. We consider the following instance of the PCP: N

= 3, u 1 1 = ab, u 2 2 = c, u 2 1 = a, u 2 2 = bc and u 1 3 = u 2 3 = $.
The following heap, of domain { 1 , 2 , 3 , 4 , 1 , 2 , 3 } is a PCP-encoding that is i-consistent for i = 1, 2. It encodes the solution (1, 2, 3) of the above PCP, with witness abc$. Locations 1 , 2 , 3 , 4 encode the witness whereas locations 1 , 2 , 3 encode the solution.

1 → ( 2 , a, 1 , 1, 1 , 1) 1 → ( 2 , 1) 2 → ( 3 , b, 1 , 2, 2 , 1) 2 → ( 3 , 2) 3 → ( 4 , c, 2 , 1, 2 , 2) 3 → (nil, 3) 4 → (nil, $, 3 , 1, 3 , 1)
Lemma 4. A PCP admits a solution iff there exists a PCP-encoding that is both 1consistent and 2-consistent.

Proof. Assume that the PCP admits a solution s of length K, with witness w and let L = |w|. We construct a PCP-encoding as follows. Let 1 , . . . , L , 1 , . . . , K be pairwise distinct locations distinct from all constants. Let

L+1 def = K +1 def = nil, and let h be a heap of domain { 1 , . . . , L , 1 , . . . , K }, such that: (i) For every l ∈ 1, L , h( l ) def = ( l+1 , w[l], k 1 l , p 1 l , k 2 l , p 2 l ),
where k i l is the greatest element in 1, K with |u i s 1 . . . . .u i

s k i l -1 | < l, and p i l def = l -|u i s 1 . . . . .u i s k i l -1 |. (ii) For every k ∈ 1, K , h( k ) def = ( k+1 , s k ). It is straightforward to check that h is a PCP-encoding.
Conversely, let h be a PCPencoding that is i-consistent for all i = 1, 2, and let w

s k i l -1 .u i s k i l [1]. . . . .u i s k i l [p i l ]
(1). Note that, in particular, for l = L, Equation 1 entails that w = u i s 1 . . . . .u i s K (i.e. s is indeed a solution of the PCP). Indeed, we have p i L = 1 and i L = K , so that k i L = K; moreover s K = N and u i N = $ is of length 1. The proof goes by induction on l.

• If l = 1 then we have k i 1 = 1 and p i 1 = 1, by Definition 1 (2). Further, w[1] = u i s 1 [START_REF] Iosif | The tree width of separation logic with recursive definitions[END_REF], by Condition 1 in Definition 2. • Assume that Equation 1 holds for some l < K. We distinguish two cases.

-

If p i l < |u i k i l
|, then by Definition 2 (2), applied on l with k = k i l , this entails that i l+1 = i l (hence k i l+1 = k i l ), and p i l+1 = p i l + 1. Moreover:

w[1]. . . . .w[l + 1] = u i s 1 . . . . .u i s k i l -1 .u i s k i l [1]. . . . .u i s k i l [p i l ].w[l + 1].
By Definition 2 (1), applied on l + 1 with k = k i l+1 , we have w

[l + 1] = u i k i l+1 [p i l+1 ] = u i k i l [p i l + 1], hence w[1]. . . . .w[l + 1] = u i s 1 . . . . .u i s k i l -1 .u i s k i l [1]. . . . .u i s k i l [p i l + 1],
and the proof is completed.

-Otherwise, by Definition 2 (3) applied on l with k = k i l , we have that k i l+1 = k i l + 1 and p i l+1 = 1. By Equation (1), since [START_REF] Iosif | The tree width of separation logic with recursive definitions[END_REF]. Thus:

p i l = |u i k i l |, we get: w[1]. . . . .w[l] = u i s 1 . . . . .u i s k i l By Definition 2 (1), applied on l + 1 with k = k i l+1 , we have w[l + 1] = u i k i l+1 [p i l+1 ] = u i k i l +1
w[1]. . . . .w[l + 1] = u i s 1 . . . . .u i s k i l .u i s k i l [1],
and the proof is completed.

Let π = (u 1 , u 2 ) be an instance of PCP, where u i = (u i 1 , . . . , u i N ), i = 1, 2. We show how to transform i-consistent PCP-encodings into SL formulae. Let R π be the set of rules in Fig. 2, we show that I defines the PCP-encodings of π (Def. 1):

Lemma 5. (s, h) |= R π I(x 1 ) iff h is a PCP-encoding of root s(x 1 ). Proof. (s, h) |= R π I(x 1 ) iff (s, h) |= φ for some predicate-free formula φ with I(x 1 ) → * R π φ. By Rule (2), I(x 1 ) → * R π φ iff there exist a 1 ∈ V such that ∃x 2 , y 1 , z. x 1 → (x 2 , a 1 , y 1 , 1, y 1 , 1) * W (x 2 , z) * S(y 1 , z) → * R π φ. Any → R π -derivation from W (x 2 , z)
starts by a sequence of application of Rule (3) followed by one application of (4). Thus

I(x 1 ) → * R π φ iff there exists L ∈ N, a 1 , . . . , a L-1 ∈ V, p 1 2 , p 2 2 , . . . , p 1 L-1 , p 2 L-1 ∈ 1, M s.t. ∃x 2 , . . . , x L , y 1 , z. x 1 → (x 2 , a 1 , y 1 , 1, y 1 , 1) * ψ * S(y 1 , z) → * R π φ, where ψ def = * L-1 l=2 x l → (x l+1
, a l , y 1 l , p 1 l , y 2 l , p 2 l ) * x L → (nil, $, z, 1, z, 1). Applying Rule (5) K -1 times and then Rule (6), we deduce that I(x 1 ) → * R π φ iff there exists L ∈ N, K ∈ N, a 1 , . . . , a L-1 ∈ V, p 1 2 , p 2 2 , . . . ,

p 1 L-1 , p 2 L-1 ∈ 1, M , n 1 , . . . , n K-1 ∈ 1, N -1 s.t. ∃x 2 , . . . , x L , y 1 , . . . , y K . x 1 → (y, a 1 , y 1 , 1, y 1 , 1) * ψ * ψ → * R φ where ψ def = * K-1 k=1 y k → (y k+1 , n k ) * y K → (nil, N) * y K ≈ z.
Using the previous equivalence, it is straightforward to check that (s, h) |= I(x 1 ) iff h is a PCP-encoding with root s(x 1 ), where, using the notations of Definition 1, l and k are the locations associated to x l and y k , respectively. Predicate B defines the PCP-encodings that are not i-consistent, for some i = 1, 2 (Def. 2). Such structures necessarily contain locations l and k contradicting one of Condition 1, 2 or 3 from Definition 2. Rule (11) is applied when k is such that k > 1. It allocates the first element 1 of the witness, then invokes A(y) to allocate all elements 1 , . . . , k-1 , and the predicate B(x ) to allocate the remaining elements. Note that A allocates arbitrary linked structures, with the link on the first record field (the resulting list does not necessarily end with nil). Predicate C is similar to A, but has 6 additional parameters denoting the heap image of the first allocated location. Rule (12) is applied l -2 times to allocate locations 2 , . . . , l-1 and also to allocate 1 in the case where k = 1 (this case must be considered apart since the sequence 1 , . . . , k-1 is empty, thus there is no element to allocate). The remaining rules allocate the faulty location l . Rules (13-15) handle the case where the heap is not 1-consistent. Rule (13) allocates a location contradicting Condition 1 in Definition 2. Afterwards, the predicates A(y) and C(z 1 , y , n, ⊥, ⊥, ⊥, ⊥) are used to allocate locations l+1 , . . . , L , and k , . . . , K , respectively. Similarly, Rules ( 14) and (15) allocate a location contradicting Condition 2 or 3 in Definition 2, respectively. The rules corresponding to the case where the heap is 2-consistent are defined in a similar way (they are omitted for conciseness). Lemma 6. Let h be a PCP-encoding and let s be a store such that s(x) is the root of h. The following equivalence statement holds: (s, h) |= R B(x) iff h is not i-consistent, for some i = 1, 2.

Proof. We use the same notations as in Definition 1. ⇒: ⇒: ⇒: Assume that (s, h) |= R π B(x). Then there exists a predicate-free unfolding φ of B(x) such that (s, h) |= R π φ. By definition of the rules defining B, this entails that one of rules (13), ( 14) or (15) (or the corresponding rules for i = 2) must have been applied at some point in the derivation, since these are the only rules that can eliminate the predicate. By symmetry we assume that one of the rules corresponding to i = 1 is applied. If Rule (13) is applied, then there exist locations l, l , l , l 1 and l 2 such that h(l) = (l , a, l 1 , p 1 , l 2 , p 2 ) and h(l 1 ) = (l , n), where a ∈

V, n ∈ 1, N , a = u 1 n [p 1 ]. Since h is a PCP-encoding, this is possible only if l = l , for some l ∈ 1, L and l 1 = k , for some k ∈ 1, K . Then h falsifies Condition 1 of Definition 2, hence h is not 1-consistent. If Rule (14) is applied then there exist locations l, l , l , l 1 , l 2 , l 1 , l 2 and l 1 such that h(l) = (l , a, l 1 , p 1 , l 2 , p 2 ), h(l ) = (l , a , l 1 , p 1 , l 2 , p 2 ) and h(l 1 ) = (l 1 , n), where 1 ≤ p 1 < |u 1
n |, and either l 1 ≈ l 1 or p 1 = p 1 + 1. Since h is a PCP-encoding, we must have l = l and l = l+1 for some l ∈ 1, L , and l 1 = k , for some k ∈ 1, K . Therefore, Condition 2 of Definition 2 is falsified. The proof is similar if Rule (15) is applied: we have p 1 = |u 1 n |, and either l 1 ≈ l 1 or p 1 = 1, which entails that Condition 3 of Definition 2 is falsified.

⇐ ⇐ ⇐: Assume that h is not i-consistent, for some i = 1, 2. We assume that i = 1, the proof for i = 2 is symmetric. By definition of a PCP-encoding, there exists a store s such that s(x) = s (x) and:

(s , h) |= R π * L l=1 x l → (x l+1 , a l , y 1 l , p 1 l , y 2 l , p 2 l ) * * K k=1 y k → (y k+1 , n k ), where x l , y i l , y k ∈ V , a l ∈ V, p i l ∈ 1, M and n k ∈ 1, N , for all l ∈ 1, L , k ∈ 1, K and i ∈ {1, 2}. The location s(x 1 ) is the root of the heap, thus we have s(x) = s(x 1 ), and we may assume, w.l.o.g., that x = x 1 . Since by hypothesis h is not 1-consistent, there exist l ∈ 1, L and k ∈ 1, K such that one of the conditions in Definition 2 is falsified. Observe that, according to Definition 2, this entails that s(y 1 l ) = s(y k ). We also have l < L; indeed, it is easy to check that the faulty location cannot be the last one, since, by definition of a PCP-encoding, this location is associated with the special character $ and index n K = N, with u i N = $ and p i L = 1. We therefore have:

  def = w(h) and s def = s(h). By induction on l, we can show, by a case analysis on whether p i l < |u i s k i l | or not, and using Conditions 2 and 3 of Def. 2 that for every i ∈ {1, 2} and l ∈ 1, L , the following equality holds: w[1]. . . . .w[l] = u i s 1 . . . . .u i

(: φ 1 def= * l- 1 l 1 l , p 1 l , y 2 l , p 2 l ) ψ 1 def= * k- 1 k

 1111211 s , h) |= R π φ 1 * x l → (x l+1 , a l , y 1 l , p 1 l , y 2 l , p 2 l ) * φ 2 * ψ 1 * y k → (y k+1 , n k ) * ψ 2 , where=1 x l → (x l +1 , a l , y =1 y k → (y k +1 , n k ) φ 2 def = * L l =l+1 x l → (x l +1 , a l , y 1 l , p 1 l , y 2 l , p 2 l ) ψ 2 def = * K k =k+1 y k → (y k +1 , n k )

Since words will often be indexed, using the notation w i would be confusing.

It is clear that φ 2 |= R π A(x l+1 ) ( ) using Rule [START_REF] Echenim | Decidable entailments in separation logic with inductive definitions: Beyond established systems[END_REF] L-l times and Rule (8) once. Further, if l < L -1 then φ 2 |= R π x l+1 → (x l+2 , a l+1 , y l+1 1 , p l+1 1 , y l+1 2 , p l+1 2 ) * A(x l+2 ). We also have φ 2 |= R π C(x l+1 , x l+2 , a l + 1, y l+1 1 , p l+1 1 , y l+1 2 , p l+1 2 ) ( †), using Rule (9) if l < L -1 and Rule (10) otherwise. Similarly,

Assume first that Condition 1 is falsified. Then a l = u 1 k [p 1 l ], hence, by Rule (13), using the relations ( ) and ( ‡), we deduce that

). If Condition 2 or 3 are falsified, then we get the same result, using the rules ( 14) and (15), instead of (13), and Relation ( †) instead of ( ). If k = 1, then, by applying Rule (12) k -1 times, we deduce that (s, h) |= R π B(x 1 ). If k > 1, then we get the same result by applying Rule (11) once and Rule (12) k -1 times, using the fact that

Putting everything together, we get the stated result: Theorem 7. The entailment problem is undecidable for systems of inductive definitions satisfying the progress and connectivity condition, but not the establishment condition.

Proof. Consider an instance π of the (adapted) PCP. By Lemma 4, the PCP has a solution iff there exists a PCP-encoding that is i-consistent, for i = 1, 2. By Lemmas 5 and 6, we can compute a system of inductive rules R π such that h is a PCP-encoding iff

, such that the PCP has a solution iff I(x 1 ) |= R π B(x 1 ). It is easy to check that R π is progressing and connected but not established, see for instance Rules ( 7), ( 8) and (12) in Fig. 2. Since the PCP is undecidable, the proof is completed.

S(y, z) ⇐ y → (nil, N) * y ≈ z (6)