Asmae Lguensat

Yassine Bentefour

Mohamed Bennis

Saadia Ba-M'hamed

René Garcia
email: rene.garcia@univ-amu.fr

Saadia Ba- M'hamed

Susceptibility and Resilience to PTSD-Like Symptoms in Mice Are Associated with Opposite Dendritic Changes in the Prelimbic and Infralimbic Cortices Following Trauma

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

Introduction

Post-traumatic stress disorder (PTSD) is a debilitating disorder that occurs after being exposed to one or multiple traumatic events. Clinical studies have highlighted that only a minority of trauma-exposed individuals develop PTSD [START_REF] Kessler | Posttraumatic stress disorder in the National Comorbidity Survey[END_REF][START_REF] Chilcoat | Investigations of causal pathways between PTSD and drug use disorders[END_REF][START_REF] Breslau | The stressor criterion in DSM-IV posttraumatic stress disorder: An empirical investigation[END_REF]. Like humans, laboratory mice [START_REF] Lebow | Susceptibility to PTSD-like behavior is mediated by corticotropin-releasing factor receptor type 2 levels in the bed nucleus of the stria terminalis[END_REF][START_REF] Sillivan | Susceptibility and resilience to posttraumatic stress disorder-like behaviors in inbred mice[END_REF] and rats [START_REF] Elharrar | Overexpression of corticotropin-releasing factor receptor type 2 in the bed nucleus of stria terminalis improves posttraumatic stress disorder-like symptoms in a model of incubation of fear[END_REF][START_REF] Toledano | Only susceptible rats exposed to a model of PTSD exhibit reactivity to trauma-related cues and other symptoms: An effect abolished by a single amphetamine injection[END_REF]) also display a great heterogeneity in their response to trauma exposure, with some animals developing PTSD-like (or stress) behaviors, while others displaying less symptoms or remaining symptom-free.

The factors that make certain individuals susceptible to develop PTSD and others resilient are still unknown. It has been hypothesized that the natural ability to adapt to stress may be damaged in those developing PTSD [START_REF] Lebow | Susceptibility to PTSD-like behavior is mediated by corticotropin-releasing factor receptor type 2 levels in the bed nucleus of the stria terminalis[END_REF][START_REF] Elharrar | Overexpression of corticotropin-releasing factor receptor type 2 in the bed nucleus of stria terminalis improves posttraumatic stress disorder-like symptoms in a model of incubation of fear[END_REF]. This idea has been so far supported by rodent studies showing that changes in corticotropinreleasing factor receptor type 2, in the bed nucleus of the stria terminalis, characterized susceptibility to PTSD-like state [START_REF] Lebow | Susceptibility to PTSD-like behavior is mediated by corticotropin-releasing factor receptor type 2 levels in the bed nucleus of the stria terminalis[END_REF][START_REF] Elharrar | Overexpression of corticotropin-releasing factor receptor type 2 in the bed nucleus of stria terminalis improves posttraumatic stress disorder-like symptoms in a model of incubation of fear[END_REF].

Studies on fear conditioning, as a key component of PTSD, have expanded our knowledge of brain circuits required for coping with stress [START_REF] Maier | Role of the medial prefrontal cortex in coping and resilience[END_REF][START_REF] Ago | Impaired extinction of cued fear memory and abnormal dendritic morphology in the prelimbic and infralimbic cortices in VPAC2 receptor (VIPR2)-deficient mice[END_REF][START_REF] Fucich | Activity in the ventral medial prefrontal cortex is necessary for the therapeutic effects of extinction in rats[END_REF]. By investigating, in rodents, changes in brain activity in these circuits, which include the medial prefrontal cortex (mPFC), other neurobiological features of susceptibility to stress may be revealed. Indeed, the mPFC controls subcortical regions, mainly the amygdala and hippocampus, to regulate appropriate conditioned fear [START_REF] Giustino | The role of the medial prefrontal cortex in the conditioning and extinction of fear[END_REF]. Findings on the mPFC also suggest that activity in its prelimbic area (PrL) is necessary to drive the expression of conditioned fear, while activity in its infralimbic area (IL) is important for the inhibition of conditioned fear [START_REF] Milad | Neurons in medial prefrontal cortex signal memory for fear extinction[END_REF][START_REF] Burgos-Robles | Sustained conditioned responses in prelimbic prefrontal neurons are correlated with fear expression and extinction failure[END_REF]. We therefore hypothesized that, following trauma exposure, stress-susceptible and stress-resilient subpopulations would manifest opposite changes in the PrL and IL.

The aim of the current study was to test this hypothesis in mice. Based on studies indicating that changes in neuronal excitability are associated with changes in dendritic morphology [START_REF] Muller | Spine changes associated with long-term potentiation[END_REF][START_REF] Monfils | Long-term potentiation induces expanded movement representations and dendritic hypertrophy in layer v of rat sensorimotor neocortex[END_REF], we hypothesized that examination of post-trauma alterations in the mPFC dendritic morphology would reveal opposite changes in the PrL and IL. Several animal models of PTSD have been developed to model different aspects of PTSD symptomatology. Among these models, there are restraint stress, forced swim stress, predator based psychosocial stress, social defeat stress, single prolonged stress and footshock stress. Here, we used the footshock stress, based on our previous studies [START_REF] Bentefour | Effects of paroxetine on PTSD-like symptoms in mice[END_REF][START_REF] Bentefour | Paroxetine treatment, following behavioral suppression of PTSD-like symptoms in mice, prevents relapse by activating the infralimbic cortex[END_REF][START_REF] Bentefour | High-frequency stimulation of the infralimbic cortex, following behavioral suppression of PTSD-like symptoms, prevents symptom relapse in mice[END_REF], which were based on passive avoidance training. Such training induces persistent avoidance, persistent fear sensitization and increased anxiety-like behavior.

Materials and methods

Animals

The experiments were performed on forty-seven young male Swiss mice obtained from the animal care facility of the faculty of Science Semlalia, Marrakech, Morocco.

Animals were group housed (3-6 per cage) and maintained under constant conditions of ambient temperature (22 ±2°C), under a 12h light/12h dark cycle with food and water available Ad libitum. The behavioral experiments were conducted between 8AM and 3PM in conformity with approved institutional protocols. All animal procedures were in strict accordance with the guidelines of European Council Directive (EU2010/63). All efforts were made to minimize animal suffering.

Behavioral protocols

Experimental timeline is shown in Figure 1. All behavioral apparatus and procedures are described in detail in our previous papers [START_REF] Bentefour | Effects of paroxetine on PTSD-like symptoms in mice[END_REF][START_REF] Bentefour | Paroxetine treatment, following behavioral suppression of PTSD-like symptoms in mice, prevents relapse by activating the infralimbic cortex[END_REF]. Briefly, on day 1, different aspects of stress behaviors (including avoidance behavior, fear sensitization and anxiety-like behavior) were induced using a passive avoidance apparatus consisting of two equally sized compartments with two independent stainless-steel grid floors (59×19×24-cm height, each), which were separated by a guillotine door (5×5 cm). Each grid floor was connected to an independent shocker unit delivering scrambled shock (Bioseb, LE10026). The light compartment was illuminated by a 50-W bulb. The apparatus was cleaned with a 70 % ethanol solution before each mouse was introduced. Mice were placed in the illuminated compartment to freely enter the dark compartment, where they received two 2-second footshocks (1.5 mA, separated by 6 seconds). The control group was similarly placed in the apparatus but did not receive any footshock. After a 14-day period, animals were submitted to classical fear conditioning (with three1-second foot-shocks, 0.4mA each, separated by 70 seconds) in a different context: a chamber (20×20×25-cm height) with a grid floor made of stainless steel connected to a link box for shock delivery (Bioseb, LE10026). The apparatus was cleaned with a lemon-scented liquid soap before each mouse was introduced. On day 15, avoidance behavior was scored in the morning (after the re-exposure to the passive avoidance apparatus), while fear sensitization was tested in the afternoon (after the re-exposure to the classical conditioning chamber for 60 seconds). For the avoidance testing, each mouse was introduced into the light compartment of the apparatus. Sixteen seconds later, the guillotine door, separated the light from the dark compartment, was opened and the time for the mouse to enter the dark compartment was determined. The guillotine door was closed for 60 seconds, then the mouse was taken from the apparatus and put back in its home cage. For fear sensitization, each mouse was placed in the classical fear conditioning context for 60 seconds to determine the time spent freezing. On day 16, anxiety-like behavior was assessed with an elevated plus maze (EPM). From days 17-21, mice were daily exposed to the avoidance apparatus, where they were left to freely enter the dark compartment, and then they were locked for 10 minutes/day to induce extinction.

Behavioral scoring and analysis

For avoidance behavior, step-through latency (to the dark compartment) was scored for each exposure to the avoidance apparatus. For fear sensitization, the amount of time spent freezing [START_REF] Fanselow | Differential effects of the N-methyl-Daspartate antagonist DL-2-amino-5-phosphonovalerate on acquisition of fear of auditory and contextual cues[END_REF] in the conditioning chamber was measured using a1-s time sampling technique. For anxiety-like behavior, the behavior of each animal was continuously recorded and rated later using Ethovision XT Noldus 8.5 video-tracking program. The anxiety index was calculated as elsewhere (Rao and Sadananda,2016)

: index = 1 -[(open-arm time/total time) + (open-arm entries/total entries)]/2.
After the completion of the behavioral study, the susceptible and resilient mice were distinguished following a method adapted from a rat study [START_REF] Verbitsky | Individual variability in behavior and functional networks predicts vulnerability using a predator scent model of PTSD[END_REF]. Briefly, when we examined the step-through latency time expressed by each mouse, we found a distinct distribution between the Control group and the trauma-exposed mice. Indeed, the Control group showed a unimodal distribution while the trauma-exposed mice displayed a bimodal distribution. Within the trauma-exposed group, animals in the top and bottom tertiles of stepthrough latency time were separated into high-avoiders (stress-susceptible) and low-avoiders (stress-resilient) subgroups (n = 14 and n=15 for each subgroup, respectively). Five mice who expressed step-through latency time between the two tertiles were excluded. Behavioral data were retrospectively analyzed and shown accordingly.

Golgi-Cox staining

At the end of the experiment, 5 mice from the Control group and 11 mice from the trauma-exposed group (including 5 stress-resilient individuals and 6 stress-susceptible individuals; individuals being randomly selected) were deeply anesthetized with an intraperitoneal injection of a lethal dose of urethane (>40 mg/kg) and transcardially perfused with 0.9% saline followed by 4% of paraformaldehyde. The brains were extracted, post-fixed overnight in 4% parafromaldehyde. For Golgi-Cox staining, the brains were immersed in a solution composed of 3% solution of potassium dichromate for 15 days. The solution was changed using a glass micropipette in the dark each 4 days. The brains were transferred in a 2% silver nitrate solution for 3 days. During all the staining phases, the brains were kept in an opaque container in room temperature. The tissue was serially cut into 100µm sections, which were mounted into gelatin coated slides and dehydrated in graded ethanol starting from 50%, then xylene, before coverslipping the slide.

Image acquisition and morphometric analysis

The regions of interest, the PrL and IL, were identified using the atlas of Paxinos and Waston (2008). The complete impregnation of several neurons was found in these regions.

Pyramidal neurons were recognized according to their triangular soma shape and apical and basilar dendrites. To reduce bias in neuron selection, we only took neurons that (i) were fully impregnated, (ii) had no morphological changes due to incomplete dendritic impregnation of Golgi-Cox staining, and (iii) had no truncated branches. In addition, each selected neuron was traceable and entirely visible. The mean of 5 to 8 whole neurons/region/animal were considered for analysis. Images of neurons were acquired using a 40-x objective. These images were taken along a z-axis while modifying the microscope focus manually to capture the whole detail of the dendritic arborization. Using image j software, images were stitched together in a 3-D stack allowing visualizing all the images in one window using a scrollbar. This method enabled us to visualize the full dendritic detail for each neuron [START_REF] Ago | Impaired extinction of cued fear memory and abnormal dendritic morphology in the prelimbic and infralimbic cortices in VPAC2 receptor (VIPR2)-deficient mice[END_REF]. We manually quantify, for each neuron, the number of apical dendrites from each visible order (primary, secondary, …). We summed up the number of dendrites to obtain the total number. The same procedure was followed to quantify the total number of basilar dendrites. All quantification was performed blindly.

Statistical analysis

Data analysis was performed using GraphPad Prism v7 software. The Student's t-test was used for two-sample comparisons. One-way ANOVA was used to assess the effect of a single parameter, while the effect of independent variables was assessed using two-way ANOVAs followed by Holm-Sidak post-hoc for multiple comparisons. The significance was set at p<0.05. Pearson's correlations were used to assess the association between avoidance behavior and dendritic morphology changes.

Difference in AIC (∆AIC) was calculated using GraphPad Prism v7 software. To obtain the Akaike weight for the model we used the following formula: exp (-0.5 * ∆AIC) divided by the sum of these values across all models [START_REF] Burnham | Model selection and multimodel inference: a practical information-theoretic approach[END_REF]. The 3D scatter plot for data visualization was run using Python.

Results

Labeling of mice as stress-susceptible or stress-resilient

All trauma-exposed mice acquired avoidance behavior, which was characterized by increases of step-through latency (Fig. 2A: Shocked group). Unpaired t-test revealed a significant difference between the Control and Shocked groups (t=2.70, p=0.009). After examining the frequency distribution of step-through latency time of mice (Fig. 2B), we found that the Control group showed a unimodal distribution while trauma-exposed mice showed a high variability with bimodal distribution (bimodal Gaussian function fit quality: ΔAIC = 0, Akaike weight for this model w=1). We later considered animals in the top and bottom tertiles of step-through latency time and separated them into high avoiders (stress-susceptible mice) and low avoiders (stress-resilient mice).

PTSD-like behaviors

Anxiety-like behavior

Among trauma exposed mice, only the High avoiders displayed a higher anxiety index (Fig. 3C). A one-way ANOVA performed on anxiety index (AI) revealed a significant difference between groups (F (2, 39) =3.906, p=0.028). The High avoiders had higher AI in comparison with the Control group (t=2.763, p=0.025) but they did not differ from the Low avoiders: t=1.682, p=0.1911). The Low avoiders and the Control group did not differ from each other (t=1.095, p=0.280).

Fear sensitization

During the sensitization test, the High avoiders froze significantly more than the two other groups (Control group and Low avoiders; Fig. 3D). A one-way ANOVA applied on these data revealed a significant difference between groups (F (2, 39) =4.012, p=0.026). The High avoiders froze significantly more than the Control group (t=2.499, p=0.049) and the Low avoiders (t=2.357, p=0.048). The difference between the Low avoiders and the Control group was not significant (t=0.854, p=0.184).

Avoidance extinction

All trauma-exposed mice exhibited decreases in step-through latency during repeated situational exposure in the absence of foot-shock application (Fig. 3E). A two-way repeated measures ANOVA on extinction data (groups x sessions) showed main effects of group (F(2,39)=15.570, p<0.001) and session (F(4,39)=41.060, p<0.001), and a significant group x session interaction (F(8,39)=17.960, p<0.001). During Day 17 (i.e. first extinction day), stepthrough latency time was significantly higher for both the Low and High avoiders compared to the Control group (Holm-Sidak post-hoc test: t=2.781, p=0.005 and t=7.124, p<0.001, respectively). Step-through latency was also significantly higher for the High avoiders compared to the Low avoiders (t=4.425, p<0.001). However, during Day 18 (i.e. 2th extinction day), only the High avoiders continued to exhibit significant higher step-through latency than the Control group and the Low avoiders (t=3.924, p<0.001 and t=2.319, p=0.042, respectively). From Day19 (i.e. 3th extinction day), the three groups showed no significant difference and displayed identical low levels of latency on Day 21 (5th extinction day), indicating full extinction in the two trauma-exposed groups.

3D-scatter plot for data visualization

The 3D visualization was based on the 3 measured variables in avoidance, EPM and sensitization tests. It enabled the representation of the position of each mouse according to the 3 measured variables (Fig. 2F), with x-axis representing avoidance test data, y axis representing EPM test data, and z-axis representing sensitization test data. The High avoiders emerged from a separate cluster, while clusters of the Control group and the Low avoiders overlapped.

Quantification of the Golgi-Cox material

Branching complexity of apical and basilar dendrites, dendritic length and branch order (Fig. 4A) were quantified in 106 PrL neurons (28, 33 and 45 neurons from the Control group, the Low avoiders and the High avoiders, respectively) and 73 IL neurons (24, 20 and 29 neurons the Control group, the Low avoiders and the High avoiders, respectively). The quantitative analysis was based on the branching patterns indicated on the drawing in Figure 3B.

Evaluation of the number of dendrites

Apical dendrites: A two-way ANOVA (groups x areas) performed on the total number of dendrites (Fig. 4A) revealed main effects of area (F (2,13) =6.472, p=0.017). The group factor was not significant (F(2,13) =0.859, p=0.434), but the group x area interaction was significant (F (4,13) =14.87, p<0.001). The Holm-Sidak post-hoc test on the PrL area showed that the Low avoiders had a significant reduction in the number of dendrites compared to the Control group and the High avoiders (t=2.655, p=0.026 and t=3.158, p=0.011 respectively).

The High avoiders did not differ from the Control group (t=0.384, p=0.703). The same test on the IL area showed that the High avoiders expressed a significant reduction of the number of apical dendrites compared to the Low avoiders (t=4.481, p<0.001). The latter group did not manifest a significant increase in the overall number of apical dendrites, compared with both the Control group and the High avoiders (t=2.238, p=0.066 and t=2.144, p=0.066 respectively).

Basilar dendrites:

A two-way ANOVA analysis (groups x areas), performed on the total number of basilar dendrites (Fig. 4B) revealed a main effect of group (F (2,13)=4.737, p=0.017), but no main effect of area (F(2,13)=0. 943, p=0.340). The interaction between the two factors was significant (F(4,13)=11.210, p<0.001). The Holm-Sidak post-hoc test on PrL data did not reveal any significant difference between the groups.

The same test on IL data indicated that the Low avoiders had a significant increase of the dendrites number as compared to the Control group (t=2.980, p=0.012). The High avoiders differed from both the Control and the Low avoiders (t=2.363, p=0.025 and t=5.476, p<0.001, respectively).

Evaluation of dendrite branch length

Apical dendrites: A two-way ANOVA (groups x areas) on the total branch length (Fig. 4C) showed no significant effect of area (F (2, 13) = 2.278, p=0.143), and no main effect of group (F (2, 13) = 1.204, p=0.143). However, the interaction between the two factors was significant (F (4, 13)=15.11, p<0.001). The Holm-Sidak post-hoc test on PrL data showed that the Low avoiders expressed a significant decrease of the total branch length when compared to the Control group and the High avoiders (t=2.466, p=0.040 and t=2.930, p=0.020, respectively). However, the High avoiders did not differ from the Control group (t=0.353, p=0.726). The same test on IL data revealed that the Low avoiders had a significant increase of the total branch length compared with the Control group and the High avoiders (t=2.247, p=0.044 and t=4.779, p<0.001, respectively). However, the High avoiders expressed a significant decrease compared with the Control group (t=2.247, p=0.044).

Basilar dendrites:

A two-way ANOVA on the total length dendrites in the IL (Fig. 4D) did not reveal any significant group effect (F (2, 13) =0.860, p=0.434), neither an area effect (F (2, 13) =0.774, p=0.386). However, a significant group x area interaction was found (F (4, 13) =12.71, p<0.001). The three groups differed from each other (Holm-Sidakpost-hoc test).

Regarding PrL data, the Low avoiders did not show any significant increase in the total length dendrites in comparison with the Control group (t=1.933, p=0.124). The difference was significant between the Low and High avoiders (t=2.591, p=0.045). However, the High avoiders did not differ from the Control one (t=0.571; p=0.512). The same trend was observed for IL data. The Low avoiders differed significantly from the Control group (t=2.759, p=0.020) and from the High avoiders (t=4.438, p<0.001). No significant difference was recorded between the High avoiders and the Control groups (t=1.557; p=0.131).

Correlation between behavior and dendritic morphology

PrL dendritic morphology

Pearson correlation analysis performed on avoidance data and the total number of apical dendrites in the PrL revealed a slight positive correlation between the two parameters (r=0.610, p=0.045). This means that the High avoiders tend to have more dendrites in the PrL (Fig. 5A). The same analysis concerning the basilar dendrites in the PrL did not reveal any clear correlation between the two parameters (r=0. 307, p=0.359). This means that the high or low avoidance status does not depend on the changes in the total number of basilar dendrites in the same region (Fig. 5B).

IL dendritic morphology

Pearson correlation analysis performed on avoidance data and the total number of apical dendrites in the IL revealed a strong negative correlation between the two parameters (r= -0.874, p<0.001). This means that the High avoiders tend to have less dendrites in the IL (Fig. 5C). Similarly, Pearson correlation on avoidance data and the total number of basilar dendrites in the IL showed a negative correlation (r=-0.816, p=0.002), which confirms that the high avoidance status is characterized by lower total number of basilar dendrites in the IL (Fig. 5D).

Discussion

In this study, we examined whether trauma exposure would cause opposite changes in the mPFC of mice that develop at least 3 PTSD-like symptoms (stress-susceptible group) and those developing less symptoms (stress-resilient group). To this end, a reliable evaluation method was used to allow the differentiation of trauma-exposed mice into susceptible and resilient groups. The Golgi-Cox method revealed significant decreases and increases in the total number of dendrites in the PrL and IL, respectively, in the stress-resilient group. As predicted, opposite changes were found in each mPFC area in the stress-susceptible group.

The differentiation of mice into susceptible and resilient groups

Several scoring methods have been used to estimate the inter-individual differences regarding stress reactivity [START_REF] Cohen | Setting apart the affected: The use of behavioral criteria in animal models of post traumatic stress disorder[END_REF][START_REF] Kanarik | Brain responses to chronic social defeat stress: Effects on regional oxidative metabolism as a function of a hedonic trait, and gene expression in susceptible and resilient rats[END_REF][START_REF] Nalloor | Predicting impaired extinction of traumatic memory and elevated startle[END_REF][START_REF] Toledano | Only susceptible rats exposed to a model of PTSD exhibit reactivity to trauma-related cues and other symptoms: An effect abolished by a single amphetamine injection[END_REF][START_REF] Febbraro | Neuronal substrates underlying stress resilience and susceptibility in rats[END_REF]. Some of these methods are prospective and others are retrospective. Regarding the prospective methods, reactivity to trauma are predicted (from pre-disposing factors), before trauma exposure. Examples of pre-disposing factors include an exaggerated startle response, a high level of anxiety-like behavior [START_REF] Nalloor | Predicting impaired extinction of traumatic memory and elevated startle[END_REF] and locomotor reactivity to novelty [START_REF] Cordero | Prior exposure to a single stress session facilitates subsequent contextual fear conditioning in rats: Evidence for a role of corticosterone[END_REF]. With respect to retrospective methods, the susceptible and resilient groups are distinguished only following trauma exposure [START_REF] Cohen | Setting apart the affected: The use of behavioral criteria in animal models of post traumatic stress disorder[END_REF][START_REF] Toledano | Only susceptible rats exposed to a model of PTSD exhibit reactivity to trauma-related cues and other symptoms: An effect abolished by a single amphetamine injection[END_REF], as in depression studies [START_REF] Kanarik | Brain responses to chronic social defeat stress: Effects on regional oxidative metabolism as a function of a hedonic trait, and gene expression in susceptible and resilient rats[END_REF]Fabbraro et al., 2017). Here, we choose a retrospective method, especially because it does not require behavioral scoring before trauma exposure. This avoids applying some behavioral tests before and after trauma, such as EPM as it is well-known that repeating this test increases open arm avoidance [START_REF] Carobrez | Ethological and temporal analyses of anxiety-like behavior: The elevated plus-maze model 20 years on[END_REF]. We found that avoidance in trauma-exposed mice followed a bimodal distribution that allowed us to distinguish two groups: the high and low avoiders (based on a method used recently by [START_REF] Verbitsky | Individual variability in behavior and functional networks predicts vulnerability using a predator scent model of PTSD[END_REF]. We also found that both groups expressed different behaviors related to trauma (anxiety, fear awareness and fear extinction) and therefore they displayed two different phenotypes related to trauma.

Behavioral results of the stress-susceptible and stress-resilient groups

Avoidance behavior

Avoidance is one of the core symptoms of PTSD [START_REF] Sheynin | Greater avoidance behavior in individuals with posttraumatic stress disorder symptoms[END_REF]. Our team has repeatedly shown that trauma exposure (using 1.5-mA foot-shocks) produces persistent avoidance behavior towards the trauma environment [START_REF] Bentefour | Effects of paroxetine on PTSD-like symptoms in mice[END_REF][START_REF] Bentefour | Paroxetine treatment, following behavioral suppression of PTSD-like symptoms in mice, prevents relapse by activating the infralimbic cortex[END_REF][START_REF] Bentefour | High-frequency stimulation of the infralimbic cortex, following behavioral suppression of PTSD-like symptoms, prevents symptom relapse in mice[END_REF].

However, in each of these studies, all trauma-exposed mice were included in a single traumaexposed group, without distinguishing susceptible from resilient mice. Here, we distinguished stress-susceptible individuals, characterized by a more pronounced avoidance response, and stress-resilient mice, characterized by less avoidance behavior. A similar finding has been recently reported in a rat study (Le Dorze and Gisquet-Verrier, 2016b).

Anxiety-like behavior

People with PTSD, in addition to their core symptoms (re-experiencing, avoidance and hyperarousal), often struggle with frequent and intense symptoms of anxiety [START_REF] Olatunji | Anxiety sensitivity and post-traumatic stress reactions: Effects of time-varying intrusive thoughts and associated distress[END_REF]. Almost all studies on rodent PTSD models include assessment of anxiety-like behavior. Here, we found that only mice with the susceptible phenotype spent lower time in the open arms and had a greater anxiety index compared to the no trauma-exposed mice.

Similar results have been reported by other authors [START_REF] Toledano | Only susceptible rats exposed to a model of PTSD exhibit reactivity to trauma-related cues and other symptoms: An effect abolished by a single amphetamine injection[END_REF]Le Dorze and Gisquet-Verrier, 2016a, b;[START_REF] Brodnik | Susceptibility to traumatic stress sensitizes the dopaminergic response to cocaine and increases motivation for cocaine[END_REF].

Fear sensitization

Hyperarousal, implicating non-associative fear learning processes [START_REF] Siegmund | A mouse model of posttraumatic stress disorder that distinguishes between conditioned and sensitised fear[END_REF], can be assessed in laboratories with the acoustic startle response in both PTSD patients [START_REF] Calhoun | The effect of nicotine and trauma context on acoustic startle in smokers with and without posttraumatic stress disorder[END_REF] and rodent models of PTSD [START_REF] Levkovitz | Early post-stressor intervention with minocycline, a second-generation tetracycline, attenuates post-traumatic stress response in an animal model of PTSD[END_REF]. In PTSD rodent models, hyperarousal can also be assessed as sensitized contextual fear established with a weak fear conditioning [START_REF] Rau | Exposure to a stressor produces a long lasting enhancement of fear learning in rats[END_REF][START_REF] Bentefour | Effects of paroxetine on PTSD-like symptoms in mice[END_REF], as in the present study, where only susceptible mice exhibited greater fear sensitization.

Avoidance extinction

Post-trauma symptoms, including avoidance, are considered part of the normal reactions to trauma exposure. Resilient individuals show steadily decreasing of these symptoms over time [START_REF] Rothbaum | Applying learning principles to the treatment of post-trauma reactions[END_REF]. Among vulnerable individuals, the most common trajectory is also progressive recovery [START_REF] Kessler | Posttraumatic stress disorder in the National Comorbidity Survey[END_REF]. In other words, complete recovery is often reached in less than 1-month post-trauma in resilient individuals and by 3 months post-trauma in vulnerable individuals [START_REF] Yehuda | Response variation following trauma: a translational neuroscience approach to understanding PTSD[END_REF]. One can, therefore, hypothesize that, during extinction training, avoidance would disappear more rapidly in resilient than in susceptible mice. Our data showed that all trauma-exposed mice successfully extinguished their avoidance response during extinction training, similarly to our previous study [START_REF] Bentefour | Paroxetine treatment, following behavioral suppression of PTSD-like symptoms in mice, prevents relapse by activating the infralimbic cortex[END_REF]). Nevertheless, the fact that extinction occurred earlier in resilient mice than in susceptible individuals does not confirm the above hypothesis because all trauma-exposed mice did not start extinction training with similar avoidance behavior.

Quantification of the Golgi-Cox material

The analysis of the total number and branch length of dendrites in the PrL showed that the susceptible phenotype was characterized by the elevation, of both parameters for apical and basilar dendrites mostly compared to the resilient mice. Similar morphological changes have previously been linked in rats with chronic stress [START_REF] Cook | Chronic stress alters dendritic morphology in rat medial prefrontal cortex[END_REF], mild and shortterm stress [START_REF] Brown | Mild, short-term stress alters dendritic morphology in rat medial prefrontal cortex[END_REF] and repeated stress [START_REF] Radley | Repeated stress induces dendritic spine loss in the rat medial prefrontal cortex[END_REF]. However, there are also other studies in rodents that have shown that stress causes a decrease in length and number of branches of apical dendrites [START_REF] Radley | Chronic behavioral stress induces apical dendritic reorganization in pyramidal neurons of the medial prefrontal cortex[END_REF] or even a lack of change in the PrL [START_REF] Izquierdo | Brief uncontrollable stress causes dendritic retraction in infralimbic cortex and resistance to fear extinction in mice[END_REF][START_REF] Febbraro | Neuronal substrates underlying stress resilience and susceptibility in rats[END_REF]. Nevertheless, beyond this discrepancy, none of these studies show dendritic plasticity, in the PrL, specific to the susceptible phenotype. The PrL is known to send extensive excitatory projections to the basolateral amygdala [START_REF] Cheriyan | Specific targeting of the basolateral amygdala to projectionally defined pyramidal neurons in prelimbic and infralimbic cortex[END_REF], a key region in expressing fear-related behavior. Increased activity in the PrL could, therefore, lead to stronger amygdala activation. Given the involvement of amygdala hyperactivation in the expression of PTSD symptoms, our data on the PrL may, at least in part, explain the higher levels of avoidance, the emergence of fear sensitization, and the higher levels of anxiety-like behavior observed with the susceptible mice. We can also conclude that a decreased PrL plasticity may lead, on the contrary, to a protection against the development of PTSD-like state. This corresponds to what we observed with the resilient phenotype.

Here, we also found that the susceptible phenotype was characterized by a reduced number and branch length of both apical and basilar dendrites in the IL, compared with both the Control and resilient groups. These data are consistent with previous reports indicating that exposure to stress induces a significant retraction of terminal branches of apical dendrites in this area [START_REF] Izquierdo | Brief uncontrollable stress causes dendritic retraction in infralimbic cortex and resistance to fear extinction in mice[END_REF][START_REF] Moench | Alterations in neuronal morphology in infralimbic cortex predict resistance to fear extinction following acute stress[END_REF]. Stress-susceptible rodents have also been found to display low immunoreactivity to c-fos [START_REF] Febbraro | Neuronal substrates underlying stress resilience and susceptibility in rats[END_REF], low expression of proBDNF (the molecular precursor of BDNF) [START_REF] Sun | Brain structural covariance network topology in remitted posttraumatic stress disorder[END_REF] and high expression of FKBP5 (a binding protein increasing the affinity of glucocorticoids with their cytoplasmic receptors) [START_REF] Criado-Marrero | Dynamic expression of FKBP5 in the medial prefrontal cortex regulates resiliency to conditioned fear[END_REF]. This further demonstrates that stress-related susceptibility is associated with dysfunctions in the IL. Moreover, studies based on synaptic plasticity have shown long-term depression in the IL of mice exposed to fear conditioning [START_REF] Herry | Cortical transmission in behaving mice plasticity in the mediodorsal thalamo-prefrontal[END_REF][START_REF] Herry | Prefrontal cortex long-term potentiation, but not long-term depression, is associated with the maintenance of extinction of learned fear in mice[END_REF]. In fact, this region is known to play a major role in suppressing fear response [START_REF] Milad | Neurons in medial prefrontal cortex signal memory for fear extinction[END_REF], via its projections to the amygdala [START_REF] Mcdonald | Projections of the medial and lateral prefontal cortices to the amygdala: a phaseolus vulgaris leucoagglutinin study in the rat[END_REF]. More specifically, the IL exerts, via GABAergic intercalated cells, feed forward inhibition of central amygdala output neurons, which triggers the expression of fear-related behavior [START_REF] Quirk | Stimulation of medial prefrontal cortex decreases the responsiveness of central amygdala output neurons[END_REF]. In addition, the IL sends direct excitatory projections to the basolateral amygdala, activating fear extinction neurons [START_REF] Cho | Synaptic encoding of fear extinction in mPFCamygdala circuits[END_REF][START_REF] Bloodgood | Fear extinction requires infralimbic cortex projections to the basolateral amygdala[END_REF]. Related to this, it has been suggested that resilient humans are less likely to consolidate emotional memories and have a greater ability to extinguish traumatic memories [START_REF] Charney | Psychobiological mechanisms of resilience and vulnerability: implications for successful adaptation to extreme stress[END_REF]. The decreased activity in the IL could have facilitated the development of PTSD-like state in mice with the susceptible phenotype, while increased activity in this area could have contribute to resilient responses.

Our results also highlighted the fact that there is a strong negative correlation between avoidance and the number of dendrites in the IL. We did not find any strong correlation between these two parameters in the PrL. Using avoidance training, Jinkes et al (1997) have shown that the IL is implicated in the inhibition of behaviors associated with aversive outcomes. Brain stimulation studies have demonstrated that electrical stimulation of this area during passive avoidance conditioning impairs the retention of the behavioral response [START_REF] Santos-Anderson | Stimulation of rat medial or sulcal prefrontal cortex during passive avoidance learning selectively influences retention performance[END_REF]. This indicates the importance of the IL in modulating stress-related responses. To our knowledge, our study, using morphological plasticity approach, is the first to show that higher number of dendrites in the IL is associated with less avoidance, and therefore with a state of resilience. Altogether, this suggests that the IL is more implicated in the process of stress resilience.

Conclusion

The current study demonstrates that trauma-exposure induces not only prefrontal changes in susceptible but also in resilient individuals. The study shows that resilience does not correspond to the maintenance of prefrontal cortex dendritic morphology in its pretraumatic state, nor to a rapid return to the pre-traumatic state of dendrites plasticity, but to the development of a protective prefrontal neuronal plasticity.

Figure 1 .

 1 Figure 1. Timeline of the behavioral experiments.

Figure 2 .

 2 Figure 2. Behavioral data. A) Step-through latency (as avoidance behavior indicator) as

Figure 3 :

 3 Figure 3: Dendrite organization in the PrL and IL of the Low and High avoiders. A)

Figure 4 :

 4 Figure 4: Trauma exposure-induced dendritic morphological changes in the mPFC. A)

Figure 5 :

 5 Figure 5: The relationship between avoidance behavior and the total number of dendrites in

  Figure 4:

Funding

This work was supported by a Marie Curie International Research Staff Exchange Scheme Fellowship within the 7th European Community Framework Programme (PIRSES-GA-2012-318997).

Notes

We acknowledge the support of the Centre National de la Recherche Scientifique et Technique (CNRST) of Morocco and the Université Cadi Ayyad in Marrakech.

Authors' Contributions


Jérôme Champavère

Rémi Gilleron

Aurélien Lemay

Joachim Niehren

Efficient Inclusion Checking for Deterministic Tree Automata and DTDs

We present a new algorithm for testing language inclusion L(A) ⊆ L(B) between tree automata in time O(|A| * |B|) where B is deterministic. We extend this algorithm for testing inclusion between automata for unranked trees A and deterministic DTDs D in time O(|A| * |Σ| * |D|). No previous algorithms with these complexities exist.

Introduction

Language inclusion for tree automata is a basic decision problem that is closely related to universality and equivalence [START_REF] Comon | Tree automata techniques and applications[END_REF][START_REF] Seidl | Deciding equivalence of finite tree automata[END_REF][START_REF] Seidl | Haskell overloading is DEXPTIME-complete[END_REF]. Tree automata algorithms are generally relevant for XML document processing [START_REF] Neumann | Locating matches of tree patterns in forests[END_REF][START_REF] Zilio | XML schema, tree logic and sheaves automata[END_REF][START_REF] Maneth | XML type checking with macro tree transducers[END_REF][START_REF] Schwentick | Automata for XML-a survey[END_REF]. Regarding inclusion checking, a typical application is inverse type checking for tree transducers [START_REF] Milo | Type checking XML transformers[END_REF]. Another one is schema-guided query induction [START_REF] Champavère | Towards schema-guided XML query induction[END_REF], the motivation for the present study. There, candidate queries produced by the learning process are to be checked for consistency with deterministic DTDs, such as for HTML.

We investigate language inclusion L(A) ⊆ L(B) for tree automata A and B under the assumption that B is (bottom up) deterministic, not necessarily A. Without this assumption the problem becomes DEXPTIME complete [START_REF] Seidl | Haskell overloading is DEXPTIME-complete[END_REF]. Deterministic language inclusion still subsumes universality of deterministic tree automata L(B) = T Σ up to a linear time reduction, as well as equivalence of two deterministic automata L(A) = L(B). The converse might be false, i.e., we cannot rely on polynomial time equivalence tests, as for instance, by comparing number of solutions [START_REF] Seidl | Deciding equivalence of finite tree automata[END_REF] or minimal deterministic tree automata.

In the case of standard tree automata for ranked trees, the well-known naive algorithm for inclusion goes through complementation. It first computes an automaton B c that recognizes the complement of the language of B, and then checks whether the intersection automaton for B c and A has a nonempty language. The problematic step is to complete B before complementing its final states, since completion might require to add rules for all possible left-hand sides. The overall running time may thus become O(|A| * |Σ| * |B| n ), which is exponential in the maximal rank n of function symbols in the signature Σ.

It seems folklore that one can bound the maximal arity of a signature to 2. This can be done by transforming ranked trees into binary trees, and then converting automata for ranked trees into automata for binary trees correspondingly. The problem is to preserve determinism in such a construction, while the size of automata should grow at most linearly. We show how to obtain such a transformation by stepwise tree automata [START_REF] Carme | Querying unranked trees with stepwise tree automata[END_REF][START_REF] Comon | Tree automata techniques and applications[END_REF]. Thereby we obtain an inclusion test in time O(|A| * |Σ| * |B| 2 ). This is still too much in practice with DTDs, where A and B may be of size 500 and Σ of size 100.

Our first contribution is a more efficient algorithm for standard tree automata on binary trees that verifies inclusion in time O(|A| * |B|) if B is deterministic. This bound is independent of the size of the signature, even though Σ is not fixed. As a second contribution, we show how to test inclusion between automata A for unranked trees and deterministic DTDs D in time O(|A| * |Σ| * |D|). Determinism is required by the XML standards. Our algorithm first computes the Glushkov automata of all regular expressions of D in time O(|Σ| * |D|), which is possible for deterministic DTDs [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]. The second step is more tedious. We would like to transform the collection of Glushkov automata to a deterministic stepwise tree automaton of the same size. Unfortunately, this seems difficult to achieve, since the usual construction of [START_REF] Martens | On the minimization of XML schemas and tree automata for unranked trees[END_REF] eliminates -rules on the fly, which may lead to a quadratic blowup of the number of rules (not the number of states). We solve this problem by introducing factorized tree automata, which use -transitions for representing deterministic automata more compactly. We show how to adapt our inclusion test to factorized tree automata and thus to DTDs. Related Work and Outline. Heuristic algorithms for inclusion between nondeterministic schemas that avoid the high worst-case complexity were proposed in [START_REF] Tozawa | XML schema containment checking based on semiimplicit techniques[END_REF]. The complexity of inclusion for various fragments of DTDs and extended DTDs was studied in [START_REF] Martens | Complexity and decision problems for XML Schemas and chain regular expressions[END_REF]. The algorithms presented there assume the same types of regular expressions on both sides of the inclusion test. When applied to deterministic DTDs, the same complexity results may be obtainable. Our algorithm permits richer left-hand sides.

We reduce inclusion for the ranked case to the binary case in Section 2. The efficient algorithm for binary tree automata is given in Section 3. In Section 4, we introduce deterministic factorized tree automata and lift the algorithm for inclusion testing to them. Finally in Section 5, we apply them to testing inclusion of automata for unranked trees in deterministic DTDs.

Standard Tree Automata for Ranked Trees

We reduce the inclusion problem of tree automata for ranked trees [START_REF] Comon | Tree automata techniques and applications[END_REF] to the case of binary trees with a single binary function symbol.

A ranked signature Σ is a finite set of function symbols f ∈ Σ, each of which has an arity n ≥ 0. A constant a ∈ Σ is a function symbol of arity 0. A tree t ∈ T Σ is either a constant a ∈ Σ or a tuple f (t 1 , . . . , t n ) consisting of a function symbol f of arity n and n trees t 1 , . . . , t n ∈ T Σ .

A tree automaton (possibly with -rules) A over Σ consists of a finite set s(A) of states, a subset final(A) ⊆ s(A) of final states, and a set rules(A) of rules of the form f (p 1 , . . . , p n ) → p or p → p where f ∈ Σ has arity n and p 1 , . . . , p n , p, p ∈ s(A). We write p → A p iff p → p ∈ rules(A), → reflexive transitive closure of → A , and → ≤1 A for the union of → A and the identity relation on s(A).

The size |A| of A is the sum of the cardinality of s(A) and the number of symbols in rules(A), i.e., f (p1,...,pn)→p∈rules(A) (n + 2). The cardinality of the signature can be ignored, since our algorithms will not take unused function symbols into account. Every tree automaton A defines an evaluator eval A :

T Σ∪s(A) → 2 s(A) such that eval A (f (t 1 , . . . , t n )) = {p | p 1 ∈ eval A (t 1 ), . . . , p n ∈ eval A (t n ), f (p 1 , . . . , p n ) → p ∈ rules(A), p → * A p} and eval A (p) = {p}. A tree t ∈ T Σ is accepted by A if final(A) ∩ eval A (t) = ∅.
The language L(A) is the set of trees accepted by A.

A tree automaton is (bottom-up) deterministic if it has no -rules, and if no two rules have the same left-hand side. It is complete if there are rules for all potential left-hand sides. It is well-known that deterministic complete tree automata can be complemented in linear time, by switching the final states.

We will study the inclusion problem for tree automata, whose input consists of a ranked signature Σ, tree automata A with -rules and deterministic B, both over Σ. Its output is the truth value of L(A) ⊆ L(B). We can deal with this problem by restriction to so-called stepwise signatures Σ @ , consisting of a single binary function symbol @ and a finite set of constants a ∈ Σ. A stepwise tree automaton [START_REF] Carme | Querying unranked trees with stepwise tree automata[END_REF] is a tree automaton over a stepwise signature.

Proposition 1. The above inclusion problem for ranked trees can be reduced in linear time to the corresponding inclusion problem for stepwise tree automata over binary trees.

We first encode ranked trees into binary trees via Currying. Given a ranked signature Σ we define the corresponding signature Σ @ = {@} Σ whereby all symbols of Σ become constants. Currying is defined by a function curry : T Σ → T Σ @ which for all trees t 1 , . . . , t n ∈ T Σ and f ∈ Σ satisfies: curry(f (t1, . . . , tn)) = f @curry(t1)@ . . . @curry(tn)

For instance, f (a, g(a, b), c) is mapped to f @a@(g@a@b)@c which is infix notation with left-most parenthesis for the tree @(@(@(f, a), @(@(g, a), b)), c). Now we encode tree automata A over Σ into stepwise tree automata step(A) over Σ @ , such that the language is preserved up to Currying, i.e., such that L(step(A)) = curry(L(A)). The states of step(A) are the prefixes of left-hand sides of rules in A, i.e., words in Σ(s(A)) * :

s(step(A)) = {f q1 . . . qi | f (q1, . . . , qn) → q ∈ rules(A), 0 ≤ i ≤ n} s(A)
Its rules extend prefixes step by step by states q i according to the rule of A. Since constants do not need to be extended, we distinguish two cases in Fig. 1.

Lemma 1. The encoding of tree automata

A over Σ into stepwise tree automata step(A) over Σ @ preserves determinism, the tree language modulo Currying, and the automata size up to a constant factor of 3.

As a consequence, L(A) ⊆ L(B) is equivalent to L(step(A)) ⊆ L(step(B))

, and can be tested in this way modulo a linear time transformation. Most importantly, the determinism of B carries over to step(B).

f (q1, . . . , qn) → q ∈ rules(A)

1 ≤ i < n f → f ∈ rules(step(A)) f q1 . . . qi-1@qi → f q1 . . . qi ∈ rules(step(A)) f q1 . . . qn-1@qn → q ∈ rules(step(A)) a → q ∈ rules(A) a → q ∈ rules(step(A))

Stepwise Tree Automata for Binary Trees

We present a new inclusion test that applies to stepwise tree automata over binary trees. We first characterize inclusion into deterministic tree automata, second, express the characterization in Datalog [START_REF] Dantsin | Complexity and expressive power of logic programming[END_REF] and third, turn it into an efficient algorithm. While the two first steps are easy, the last step is nontrivial.

Characterization of Inclusion.

We call a state p ∈ s(A) accessible if there exists a tree t such that p ∈ eval A (t). We call p co-accessible if there exists a tree t ∈ T Σ∪{p} with a unique occurrence of p such that eval A (t) ∩ final(A) = ∅. A tree automaton is productive if all its states are accessible and co-accessible. We denote the product of two automata A and B with the same signature by

A × B. The state set of A × B is s(A) × s(B).
For inferring its rules, we assume that B does not have -rules:

a → p ∈ rules(A) a → q ∈ rules(B) a → (p, q) p1@p2 → p ∈ rules(A) q1@q2 → q ∈ rules(B) (p1, q1)@(p2, q2) → (p, q) p → p ∈ rules(A) q ∈ s(B) (p , q) → (p, q)
We do not care about final states of A × B since these are useless in our characterization of inclusion.

Proposition 2. Inclusion L(A) ⊆ L(B) for a productive stepwise tree automaton A with -rules and a deterministic stepwise tree automaton B fails iff:

fail 0 : there exists a rule a → p ∈ rules(A) but no state q ∈ s(B) such that a → q ∈ rules(B), or fail 1 : there exist accessible states (p 1 , q 1 ) and (p 2 , q 2 ) of A × B and a rule p 1 @p 2 → p ∈ rules(A) but no state q ∈ s(B) such that q 1 @q 2 → q ∈ rules(B), or fail 2 : some accessible state (p, q) of A×B satisfies p ∈ final(A) but q ∈ final(B).

Proof. If one of the failure conditions holds, then failure of inclusion follows from the hypotheses that A is productive and B deterministic.

For the converse, let us consider a tree t such that t ∈ L(A) and t ∈ L(B). There are two cases to be considered, depending on eval B (t). (i) Assume eval B (t) = ∅. There exists a minimal subtree t of t such that eval B (t ) = ∅, too. If t = a is a leaf then eval A (a) = ∅, since t ∈ L(A), and eval B (a) = ∅, thus fail 0 holds. If t = t 1 @t 2 , then there exist p 1 ∈ eval A (t 1 ), p 2 ∈ eval A (t 2 ) and p 1 @p 2 → p ∈ rules(A), since t ∈ L(A). Since t is defined as a

(acc /1 ) a → p ∈ rules(A) a → q ∈ rules(B) acc(p, q). (acc /2 ) p →A p ∈ q ∈ s(B) acc(p, q) :-acc(p , q).
(acc /3 ) p1@p2 → p ∈ rules(A) q1@q2 → q ∈ rules(B) acc(p, q) :-acc(p1, q1), acc(p2, q2).

(frb) p1@p2 → p ∈ rules(A) q.q1@q2 → q ∈ rules(B) frb(p2, q2) :-acc(p1, q1). frb(p1, q1) :-acc(p2, q2). minimal subtree and B is deterministic, eval B (t 1 ) = {q 1 }, eval B (t 2 ) = {q 2 }, and since eval B (t ) = ∅, there is no rule q 1 @q 2 → q ∈ rules(B). This leads to fail 1 . (ii) If eval B (t) = ∅ then there exists q ∈ eval B (t); B being deterministic this q is necessarily unique. Since t ∈ L(B), q ∈ final(B). Moreover, since t ∈ L(A), there exists p ∈ eval A (t) ∩ final(A). This leads to fail 2 .

(fail0) a → p ∈ rules(A) q.a → q ∈ rules(B) fail0. (fail1) p ∈ s(A) q ∈ s(B) fail1 :-acc(p, q), frb(p, q). (fail2) p ∈ final(A) q ∈ final(B) fail2 :-acc(p, q).
Testing the Characterization. The following efficiency theorem for ground Datalog will be fundamental to all what follows. Given a Datalog program P (without negation), we write lfp(P ) for its least fixed point semantics.

Theorem 1 (Efficiency of Ground Datalog [6]). For every ground Datalog program P , the least fixed point semantics lfp(P ) can be computed in linear time O(|P |) where the size |P | is the number of symbols in P .

This result holds even without any bound on the arity of the relation symbols of P , which will be very useful later on. If relation symbols of higher arities are used, the number of their arguments is accounted for by the size of P .

Fig. 2 presents a Datalog program D 1 (A, B) that verifies the characterization of L(A) ⊆ L(B) in Proposition 2. Transformation rules (acc /1 ), (acc /2 ), and (acc /3 ) define clauses for accessibility in A×B through predicate acc. The clauses produced by transformation rule (frb) define forbidden states of A × B through predicate frb. These are states that lead to fail 1 when accessed. Transformation rules (fail 0 ), (fail 1 ), and (fail 2 ) define clauses for failures. The characterization of inclusion from Proposition 2 is captured in the following sense: Proposition 3. Let A and B be stepwise tree automata for binary trees. If A is productive and B deterministic then: Efficient Algorithm. This running time is not better than that of the naive algorithm. The square factor is due to the computation of forbidden states for capturing fail 1 . Since (frb) rules cannot be inferred efficiently enough with a Datalog program, we introduce a new predicate frb c that will group (frb) rules. Using an appropriate data structure, the frb predicates can be induced efficiently from frb c . The semantics of the latter is given below:

L(A) ⊆ L(B) ⇔ lfp(D 1 (A, B)) ∩ {fail 0 , fail 1 , fail 2 } = ∅ (frb c /2 ) p1@p2 → p ∈ rules(A) q1 ∈ s(B) Q2 = {q2 | q1@q2 → q ∈ rules(B)} frb c (p2, Q2) :-acc(p1, q1). (frb c /1 ) p1@p2 → p ∈ rules(A) q2 ∈ s(B) Q1 = {q1 | q1@q2 → q ∈ rules(B)} frb c (p1, Q1) :-acc(p2, q2).
A, B |= frb c (p, Q) ⇔ ∀q ∈ s(B) \ Q, A, B |= frb(p, q)
Formally, we impose an order < on s(B) and consider frb c (p, {q 1 , . . . , q n }) as (n + 1)-ary literals frb c (p, q i1 , . . . , q in ) such that {q i1 , . . . , q in } = {q 1 , . . . , q n } and q i1 < . . . < q in . In Fig. 3, we propose two transformations (frb c /1 ) and (frb c /2 ) for inferring frb c clauses, both of which group (frb) transformations. Note that for every state p, there may be several sets Q such that frb c (p, Q) gets inferred. Therefore, we will have to test efficiently whether a state belongs to the union of complements of those state sets. This will be further detailed.

Let us consider the transformation of tree automata A and B into a ground Datalog program D 2 (A, B) defined by transformation rules (acc /1 ), (acc /2 ), (acc /3 ), (frb c /1 ), (frb c /2 ), (fail 0 ), and (fail 2 ). The clauses producing acc, fail 0 , and fail /2 ) as shown in Fig. 4, such that the corresponding (acc /3 ) clauses are inferred simultaneously (and these don't overlap). Therefore the overall size of

D 2 (A, B) is in O(|A| * |B|). p1@p2 → p ∈ rules(A) q1@q 1 2 → q 1 ∈ rules(B) . . . q1@q n 2 → q n ∈ rules(B)     
all the rules for q1 frb c (p2, {q 1 2 , . . . , q n 2 }) :-acc(p1, q1). acc(p, q 1 ) :-acc(p1, q1), acc(p2, q 1 2 ). . . . acc(p, q n ) :-acc(p1, q1), acc(p2, q n 2 ). Otherwise, we test for fail 1 in a second step, by checking for all states acc(p, q) ∈ lfp(D 2 (A, B)) whether there is a

frb c (p, Q) ∈ lfp(D 2 (A, B)) such that q ∈ s(B) \ Q.
If so, false is returned, otherwise true. 0 q 1 q 2 q 3 q 4 q 5 . . . p 2 0 1 2 1 0 . . . When frb c (p, {q2, q3}) is set up, bad_state(p)(0), bad_state(p)(q2) and bad_state(p)(q3) are incremented. We have for instance frb(p, q 4 ) since bad_state(p)(q 4 ) = 1 is lower than bad_state(p)(0) = 2. In fact, the only not forbidden state is (p, q3) because q3 belongs to the intersection of {q2, q3} and {q3, q 4 }.

We have to prove that the second step can be done in time O(|A| * |B|). For every state p ∈ s(A), there are some state sets Q 1 , . . . , Q m such that for 1 ≤ j ≤ m, frb c (p, Q j ) ∈ lfp(D 2 (A, B)) and we have to check efficiently whether some state q is in It remains to test for all states acc(p, q) ∈ lfp(D 2 (A, B)) whether there exists a frb c (p, Q) ∈ lfp(D 2 (A, B)) such that q ∈ s(B) \ Q. This is done by checking whether T [q] < T [0] in bad_states(p) (see, e.g., Fig. 5). Indeed, if

{Q | frb c (p, Q) ∈ lfp(D 2 (A, B))} = {Q 1 , . . . , Q m } then bad_states(p) is defined such that T [q] = T [0] iff q ∈ j=m j=1 Q j , thus T [q] < T [0] iff q ∈ j=m j=1 s(B) \ Q j .

Each such test costs O(1) so the overall time is bounded by O(|A| * |B|).

This concludes the inclusion test for stepwise tree automata, for productive A and deterministic B. Every tree automaton can be made productive in linear time. Higher arities can be reduced to 2 by Proposition 1. This yields: Theorem 2. Let A and B be standard tree automata for ranked trees of some signature Σ possibly with -rules. If B is deterministic, inclusion L(A) ⊆ L(B) can be decided in time O(|A| * |B|) independently of the size of Σ.

Factorized Tree Automata

We next relax the determinism assumption on B in a controlled manner, that will be crucial to deal with DTDs. We replace B by deterministic factorized automata, that we introduce. These are automata with -rules, that represent deterministic automata in a compact manner. Definition 1. A factorized tree automaton F over a stepwise signature Σ is a stepwise tree automaton with -rules and a partition s(F ) = s 1 (F ) s 2 (F ) such that if q 1 @q 2 → q in rules(F ) then q 1 ∈ s 1 (F ) and q 2 ∈ s 2 (F ).

We say that q is of sort i in F if q ∈ s i (F ). The sort determines which states may be used in the i-th position of the binary symbol @ in rules of F .

Every factorized automaton F defines a tree automaton ta(F ) without -rules that recognizes the same language. Both automata have the same signature and states; the rules of ta(F ) are inferred as follows from those of F :

(E1) a → q ∈ rules(F ) a → q ∈ rules(ta(F )) (E2) q1 → * F r1 q2 → * F r2 r1@r2 → q ∈ rules(F ) q1@q2 → q ∈ rules(ta(F )) We set final(ta(F )) = {q | q → * F r, r ∈ final(F )}. Note that the size of ta(F ) may be O(|rules(F )| * |s(F )| 2
) which is cubic in that of F in the worst case. Besides their succinctness, the truly interesting bit about factorized tree automata is their notion of determinism.

Definition 2. A factorized tree automaton F is (bottom-up) deterministic if:

d 0 : the -free part of F is (bottom-up) deterministic; d 1 : for all q ∈ s(F ) and sorts i ∈ {1, 2}, there is at most one state r of sort i such that q → * F r.

Nonredundant -rules must change the sort: if q → F r for two states of the same sort then r = q by d 1 and q → * F q. A similar argument shows that all proper chains of -rules are redundant so that → * F is equal to → ≤1 F . Proposition 4. The tree automaton ta(F ) represented by a deterministic factorized tree automaton F is deterministic.

Proof. Let B = ta(F ) which by construction is free of -rules. For every constant a ∈ Σ, the uniqueness of q such that a → q ∈ rules(B) follows from d 0 . For every q 1 @q 2 → q in rules(B) we have to show that q is uniquely determined by q 1 and q 2 . By d 1 there is at most one state r 1 of sort 1 such that q 1 → * F r 1 at most one r 2 of sort 2 such that q 2 → * F r 2 . Condition d 0 implies that there exists at most one state q such that r 1 @r 2 → q ∈ rules(F ).

(acc /3a ) p1@p2 → p ∈ rules(A) q1@q2 → q ∈ rules(F ) acc(p, q) :-f.acc(p1, q1), f.acc(p2, q2).

(f.acc) p ∈ s(A) q → ≤1 F r f.acc(p, r) :-acc(p, q). (f.frb c 2 ) p1@p2 → p ∈ rules(A) q1 ∈ s1(F ) f.frb c 2 (p2, Q F 2 (q1)) :-f.acc(p1, q1). (f.frb c 1 ) p1@p2 → p ∈ rules(A) q2 ∈ s2(F ) f.frb c 1 (p1, Q F 1 (q2)) :-f.acc(p2, q2). (frb c 2 ) p1@p2 → p ∈ rules(A) q1 ∈ s(F ) frb c 2 (p2, R F 2 ) :-acc(p1, q1). (frb c 1 ) p1@p2 → p ∈ rules(A) q2 ∈ s(F ) frb c 1 (p1, R F 1 ) :-acc(p2, q2). (frb c /1a ) p1@p2 → p ∈ rules(A) q2 ∈ R F 2 frb c (p1, ∅) :-acc(p2, q2). (frb c /2a ) p1@p2 → p ∈ rules(A) q1 ∈ R F 1 frb c (p2, ∅) :-acc(p1, q1). (fail2a) p ∈ final(A) ∀r. q → ≤1 F r ⇒ r ∈ final(F ) fail2 :-acc(p, q).
The clauses from (acc /1 ), (acc /2 ) and (fail0) in D2(A, F ) belong to D3(A, F ), too. We use sets of states

Q F 2 (q1) = {q | q1@q → q ∈ rules(F )}, Q F 1 (q2)
symmetrically, and sets of states reaching a sort We fix a stepwise tree automaton A and a deterministic factorized tree automaton F , and let us B = ta(F ). We now show how to test language inclusion L(A) ⊆ L(B) from A and F without computing B. This is done by the ground Datalog program D 3 (A, F ) of Fig. 6.

R F i = {q | ∃r ∈ si(F ). q → ≤1 F r}.
We need new predicates for properties of F in order to infer corresponding properties of B. The accessibility predicate f.acc for F subsumes the accessibility predicate acc for B. Subsumption may by proper as stated by the rule (f.acc) of D 3 (A, F ). Vice versa, we infer accessibility in F from accessibility in B according to the rule (acc /3a ). Rules (acc /1 ) and (acc /2 ) of D 2 (A, F ) remain valid for accessibility in B, too.

Lemma 2.

acc(p, q) ∈ lfp(D 3 (A, F )) iff acc(p, q) ∈ lfp(D 2 (A, B))

We need to refine predicate frb into predicates frb 1 and frb 2 that take sorts into account, and corresponding predicates f.frb 1 and f.frb 2 in the factorized case. Their semantics can be defined as follows, where A, B are tree automata and F is a factorized tree automaton.

A, B |= frb2(p2, q2) ⇔ ∃p, p1, q1. A, B |= acc(p1, q1), p1@p2 → p ∈ rules(A), q2 / ∈ Q B 2 (q1) A, F |= f.frb2(p2, r2) ⇔ ∃p, p1, r1. A, F |= f.acc(p1, r1), p1@p2 → p ∈ rules(A), r2 / ∈ Q F 2 (r1)
The semantics of frb 1 and f.frb 1 are symmetric. The relation to the previous predicate frb is that A, B |= frb(p, q) if and only if A, B |= frb 1 (p, q) ∨ frb 2 (p, q). The Datalog program D 3 (A, F ) infers for sorts i ∈ {1, 2} literals with predicates f.frb c i that are to be understood by grouping of f.frb i literals, and similarly frb c i by grouping of frb i . These grouping mechanisms account for sorts, since complementation is with respect to sorts.

A, F |= f.frb c i (p, Q) ⇔ ∀q ∈ si(F ) \ Q. A, F |= f.frbi(p, q) A, F |= frb c i (p, Q) ⇔ ∀q ∈ si(F ) \ Q. A, F |= frbi(p, q)
The clauses produced by (f.frb c i ) and (frb c i ) are sound with respect to this semantics for deterministic F 's. This is easier to see for (f.frb c i ) than for (frb c i ). We prove it by the next lemma. For states p, q, r and sorts i ∈ {1, 2} we define: f.frb i (p, r) from lfp(D 3 (A, F )) can be done by the same clever algorithm as before for deducing all A, B frb(p, q) given lfp(D 2 (A, B)). Note, however, that we now need two different data structures for the two sorts.

A, B frbi(p, q) iff ∃Q ⊆ s(B) \ {q}. frb c (p, Q) ∈ lfp(D2(A, B)) via (frb c /i ) A, F f.frbi(p, r) iff ∃R ⊆ s(F ) \ {r}. f.frb c i (p, R) ∈ lfp(D3(A, F )) A, F frbi(p, r) iff ∃R ⊆ s(F ) \ {r}. frb c i (p, R) ∈ lfp(D3(A, F )) or frb c (p, ∅) ∈ lfp(D3(A, F )) via (frb c /ia )

Automata for Unranked Trees and DTDs

We lift our results to deterministic tree automata for unranked trees possibly with factorization, so that they become applicable to deterministic DTDs.

An unranked signature Σ is a finite set of symbols (without arity restrictions). The set T u Σ of unranked trees over Σ is the least set that contains all pairs a(t 1 , . . . , t n ) where a ∈ Σ and (t 1 , . . . , t n ) is a possibly empty sequence of unranked trees in T u Σ . Currying carries over literally from ranked to unranked trees. This yields a bijection curry : T u Σ → T Σ @ . Thus, we can reuse stepwise tree automata to recognize languages of unranked trees, and as before, we can factorize them. So, as a corollary of Theorem 3 we have:

Corollary 2. For a stepwise tree automaton for unranked trees A and a deterministic factorized tree automaton for unranked trees F over the same signature Σ, L(A) ⊆ L(F ) can be decided in time O(|A| * |F |) independently of |Σ|.

Note that hedge automata [START_REF] Comon | Tree automata techniques and applications[END_REF] can be translated in linear time to stepwise tree automata with -rules [START_REF] Martens | On the minimization of XML schemas and tree automata for unranked trees[END_REF]. The automata of [START_REF] Raeymaekers | Information Extraction from Web Pages Based on Tree Automata Induction[END_REF] support factorization, too. We finally show how to convert deterministic DTDs D to deterministic factorized tree automata in time O(|Σ| * |D|), so that we can reuse our algorithm for testing inclusion in deterministic DTDs. Factorization avoids the quadratic blowup from translating hedge to stepwise automata [START_REF] Martens | On the minimization of XML schemas and tree automata for unranked trees[END_REF]. A DTD D with elements in a set Σ is a function mapping letters a ∈ Σ to regular expressions e over Σ, what we write a → D e in this case. One of these elements is the distinguished start symbol. The language L a (D) ⊆ T u Σ of elements a of a DTD D is the smallest set of unranked trees such that:

La(D) = {a(t1, . . . , tn) | a →D e, a1 . . . an ∈ L(e), ti ∈ La i (D) for 1 ≤ i ≤ n}
The language of a DTD D is L(D) = L a (D) where a is the start symbol of D. The size of D is the total number of symbols in the regular expressions of D. An example in XML syntax is given in Fig. 7. The set of elements of D is Σ = {doc, block, text, link}, of which the element doc is the start symbol. The regular expression for #PCDATA recognizes only the empty word.

A DTD is deterministic if all its regular expressions are one-unambiguous [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]. This is equivalent to say that all corresponding Glushkov automata are deterministic, which is a requirement by the W3C. See Fig. 7 for the example. We transform a collection of Glushkov automata for a deterministic DTD D into a single factorized tree automaton F as follows. The set of states of sort 1 of F is the disjoint union of the states of the Glushkov automata. The states of sort 2 of F are the elements of D. For every element a, we connect all final states q of its Glushkov automaton to the state a, i.e., q → a ∈ rules(F ). The only final state of F is the start symbol of the DTD D. The result is a finite automaton, that represents a factorized tree automaton, as for instance in Fig. 8. This needs time of at most O(|Σ| * |D|). Note that the size of the example automaton would grow quadratically, when eliminating -edges. For every a ∈ Σ, there is a → q ∈ rules(F ) for the unique initial state q of the Glushkov automaton of a. For every transition q a → q of one of the Glushkov automata, we add a rule q@a → q ∈ rules(F ).

Note that F is deterministic as a factorized automaton. The -free part of F is deterministic since all Glushkov automata are: d 0 . Let q be a state of the Glushkov automaton for some letter a. The only state of sort 1 q can reach by -edges is a and the only state of sort 2 is q itself. All other states of F are elements of a ∈ Σ, which have no outgoing -edges: d 1 .

Fig. 1 .

 1 Fig. 1. Transforming ranked tree automata into stepwise tree automata.

Fig. 2 .

 2 Fig. 2. Transforming tree automata A and B into a Datalog program D1(A, B).

Fig. 3 .

 3 Fig. 3. Grouping (frb) transformations.

  2 of D 1 (A, B) and D 2 (A, B) are identical and their number is in O(|A| * |B|). The number of frb c clauses introduced by rule (frb c /1 ) is in O(|A| * |s(B)|) but the size of each such clause is n + 1 which in the worst case could be |s(B)| + 1, and symmetrically for (frb c /2 ). The overall size of all frb c clauses, however, is bounded by the overall number of acc clauses, which in turn is bounded by O(|A| * |B|), too! To see this, we can rewrite (frb c

Fig. 4 .

 4 Fig. 4. Rewriting grouping rules for complexity analysis of (frb c /2 ) clauses.

Fig. 5 .

 5 Fig. 5. Data structure bad_state. Here, it has been set up frb c (p, {q2, q3}) and frbc (p, {q3, q 4 }). When frb c (p, {q2, q3}) is set up, bad_state(p)(0), bad_state(p)(q2)and bad_state(p)(q3) are incremented. We have for instance frb(p, q 4 ) since bad_state(p)(q 4 ) = 1 is lower than bad_state(p)(0) = 2. In fact, the only not forbidden state is (p, q3) because q3 belongs to the intersection of {q2, q3} and {q3, q 4 }.

  j=m j=1 s(B) \ Q j . For this, we define a data structure bad_states(p) as an array T of size |s(B)| + 1. Counters are indexed by elements in s(B) and one counter is indexed by 0. All counter values are set to 0 initially. The initialization of all bad_states(p) can be done in O(|s(A)| * |s(B)|). For every p and every Q j such that frb c (p, Q j ) ∈ lfp(D 2 (A, B)), counter T [0] is incremented by 1 and counter T [q] is incremented by 1 for all q ∈ Q j , which can be done in time O(|Q j |). As the overall size of frb c clauses in lfp(D 2 (A, B)) is in O(|A| * |B|), the computation of all bad_states(p) can be done in time O(|A| * |B|).

Fig. 6 .

 6 Fig. 6. Inferring clauses of Datalog program D3(A, F ) simulating D2(A, B).

Theorem 3 .

 3 For a stepwise tree automaton with -rules A and a deterministic factorized tree automaton F over the same signature, inclusion L(A) ⊆ L(F ) can be decided in time O(|A| * |F |).

Fig. 7 .

 7 Fig. 7. An example DTD and the corresponding Glushkov automata.

Theorem 4 (

 4 Brüggemann-Klein [1]). The collection of Glushkov automata for a deterministic DTD D over Σ can be computed in time O(|Σ| * |D|).

Fig. 8 .

 8 Fig. 8. The deterministic factorized tree automaton for the DTD in Fig. 7.

Theorem 5 .Corollary 3 .

 53 Deterministic DTDs D over Σ can be translated to deterministic factorized tree automata that recognize the same language in time O(|Σ| * |D|). Language inclusion of hedge automata A over Σ in deterministic DTDs D with elements in Σ can be decided in time O(|A| * |Σ| * |D|).

  Lemma 3 (Core).A, B frb i (p, q) iff A, F frb i (p, q) or the unique state r of sort i with q → ≤1 F r exists and satisfies A, F f.frb i (p, Since the size of D 3 (A, F ) is in O(|A| * |F |) we can compute the set of all f.frb c 1 (p, R) and f.frb c 2 (p, R) literals in lfp(D 3 (A, F )) in time O(|A| * |F |). It remains to infer the induced literals f.frb i (p, r) literals in an efficient manner. Computing all A, F


Gilbert Greefrath

Lena Frenken

Keywords: assessment, technology, digital competence

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

TBA IN A GERMAN STANDARDIZED ASSESSMENT INSTRUMENT -A PILOT PROJECT ANALYZING DIGITAL MATHEMATICAL COMPETENCIES IN GRADE 8

Gilbert Greefrath, Lena Frenken 1 , Carola Schnitzler 2 1 University of Muenster, 2 IQB Berlin German Educational Standards already describe digital mathematical competencies such as the use of dynamic geometry software and spreadsheets to solve mathematical problems in parts. However, the current national assessment strategy is still based on paper-and-pencil tests using simple calculators. Here, a pilot project of the German Institute for Educational Quality Improvement (IQB) has initiated the investigation of innovative test items that not only transfer the paper-and-pencil tests into a TBA format, but at the same time develop items that assess subject relevant digital competencies described in the standards and focus on opportunities of digital assessment. In this project, items with dynamic

Introduction

After the unsatisfactory PISA results for Germany in 2000 (OECD, 2001) a strategy for improving educational quality was implemented in the following years. For the first time in Germany, uniform educational standards were introduced that apply to all federal states. These educational standards describe which competencies students should gain until the finalization of different grades by means of a three-dimensional and subject-related competence structure model [START_REF] Leuders | Outcome standards and core curricula: A new orientation for mathematics teachers in Germany[END_REF]. Based on this model, an overall monitoring strategy of the educational system has been introduced in 2006. In addition to international school performance studies (PISA, TIMSS), there are national school performance studies (Stanat, Schipolowski, Mahler, Weirich, & Henschel, 2019) and, based on the same competence model as the national school performance studies, yearly assessments called VERA are performed. The latter are conducted nationwide in grade three (primary school) and grade eight (secondary school) in all general education schools in order to monitor which competencies students have gained at a certain point of time. The aim of VERA is to give teachers differentiated feedback which requirements their classes have already mastered in relation to the educational standards. In Germany, the national educational standards already take into account digital mathematical competencies [START_REF] Geraniou | Towards a definition of "mathematical digital competency[END_REF] such as the use of dynamic geometry software and spreadsheet calculation for solving mathematical problems [START_REF] Kmk | Bildungsstandards im Fach Mathematik für den Mittleren Schulabschluss[END_REF]. Nevertheless, the current delivery of comparative tests is still paper-and-pencil-based whereby a simple calculator is the only permitted auxiliary.

The TBA-Project

Identifying the discrepancy described above the German Institute for Educational quality improvement (IQB) in cooperation with the University of Münster investigated the feasibility of assessing mathematical competency including digital competencies relevant for mathematics by means of technology-based assessment (TBA). The use of TBA can affect many aspects such as the test system including multi-media environments, test construction and adaptive testing (Scheerens, Glas, & Thomas, 2003, pp. 98, 118). In our case, the primarily aim is to develop test items that exploit the potential of TBA. We focus on the development of innovative test items that are technology-based and do not just transfer paper-and-pencil tests into a TBA format. Thus, the focus is both on competencies that can be assessed better or even at all in a TBA format. The project was coordinated by the IQB and technically supported by the Leibniz Institute for Research and Information in Education (DIPF). Five task developers with teaching experience and expertise with the use of digital media developed maths problems and items, respectively. The task developers were also trained in using the item authoring tool ItemBuilder [START_REF] Rölke | The ItemBuilder: A Graphical Authoring System for Complex Item Development[END_REF] which enables them to create tasks in a TBA format from the start. Not only a wide spectrum of media but also automatic scoring [START_REF] Drijvers | Digital assessment of mathematics: Opportunities, issues and criteria[END_REF] was embedded. The item construction process partly followed the established one of creating paper-based items [START_REF] Rupp | National educational standards in Germany: Methodological challenges for developing and calibrating standards-based tests[END_REF].

Items with Technology

Assessment with and through technology [START_REF] Stacey | Technology and Assessment in Mathematics[END_REF]) should be combined. Analyzing the national educational standards, according to [START_REF] Brown | Computer Algebra Systems and Mathematics Examinations: A comparative study[END_REF] the following distinction was undertaken: competencies for which the TBA format is not necessary (which was not the focus of the project), competencies that can be assessed better in a TBA format than with paper-andpencil (e. g. because the situation can be described more authentically and clearly or the data can be presented better) and competencies which can only be assessed in a TBA format -such as "students draw and construct geometric figures using [...] dynamic geometry software" and "describe changes in quantities by means of functions, also using a spreadsheet software" (cf. KMK, 2004, p. 11,12). Overall, the digital media embedded into the tasks were dynamic geometry software, spreadsheets and an online calculator, which are digital tools rather specific to mathematics, and as more general digital media videos, audios and photos. The tasks were technically realized by the ItemBuilder [START_REF] Rölke | The ItemBuilder: A Graphical Authoring System for Complex Item Development[END_REF] and distributed online.

Pilot study

A selection of the innovative TBA items was subject to a trial in nine German schools in 2019 with assumed typical technical equipment. It has to be considered that German schools are equipped below the international average in terms of technology [START_REF] Fraillon | Preparing for life in a digital world: IEA International Computer and Information Literacy Study[END_REF]. Therefore, it was not surprising that some of the participating schools dropped out of the study due to insufficient internet connection. A total of nine schools (229 students) participated in the test. The testing time was 45 minutes. The pilot study aimed at investigating the extent to which the standards' competencies can be measured using digital media and incorporating a variety of digital tools presumably familiar to the students. Here, both the content and the technical aspects were taken into account. We also analyzed students' answers to dynamic geometry software items and categorized their solving processes according to different solution approaches. The following questions were addressed: (1) To what extent can students' competencies be technically captured using items with integrated digital tools? (2) Which categories of student solutions of a TBA task with integrated dynamic geometry software can be identified? To answer the first question, the students' answers were examined with regard to technical features. To answer the second question, all answers of one GeoGebra item were analyzed. In total 101 snapshots from the GeoGebra applet could be restored with a custom program written with Java. Within the framework of a qualitative analysis [START_REF] Mayring | Knowledge and Skills for Life. First Results from the OECD Programme for international Student Assessment[END_REF] categories were developed to describe the solutions.

Results

The tasks were suitable to assess various mathematical competencies including the use of digital tools specifically relevant to mathematics. Students were generally comfortable with the general online test interface (e. g. navigating to different pages, scrolling, typing into an input field). However, the students encountered also difficulties that can possibly affect the measurement of competencies, especially when using input fields for describing calculation methods and working with figures into a GeoGebra application. For example, entering rather simple formulas like a product term seems to be more difficult than in paper-and-pencil tests because not all operators (like the German multiplication sign ·) are available on the keyboard. When using provided GeoGebra constructions, it was apparently not clear to all students that they could also move the given figures [START_REF] Frenken | Evaluating Educational Standards using Assessment "with" and "through" Technology[END_REF]. Many students did not solve the GeoGebra item with by means of the actually expected specific construction (which would have been an angle bisector to measure the exact distance between two given points). They performed an approximate estimation of the distance. This leads to incorrect solutions in most cases because the correct point including a small area around it were not hit exactly (25%); only a few students succeeded in their approach to estimate the correct position of the point (7%). Many other solutions showed mathematical activity but the result was not correct (22%). At least 22% of the students solved the task correctly using the expected tools within GeoGebra to undertake a construction. Those solutions were also automatically scored as correct by the test system (Frenken, Libbrecht, Becker, & Greefrath, submitted).

Discussion

In principle, the innovative items developed within this project can be used to assess mathematical competencies including the use of digital tools. In order to avoid confounding variables due to problems of using TBA elements and to improve the test validity, a general toolbar should be added to input fields for inserting formulas and further instructions for embedded GeoGebra applications should be implemented, since the handling is apparently not always well-known or intuitive. Deeper insights into the possibilities of automatic coding and analyzing item solution processes were presented by the evaluation of the GeoGebra task. Here it became clear that some students did not choose the expected approach via a construction, but estimated the position of the point they were looking for relatively well. As a result, only a few answers were scored as correct and most as incorrect. Hence, it may be necessary to describe certain requirements for the construction in the task's instruction directly or to adjust the tolerance for correct solutions when coding, so that students rather use the same approach and are treated equally in scoring. Of course, these are only individual results of a small pilot study. However, it can be stated that special challenges arise through testing with technology due to the requirements of the testing environment in the school networks. Moreover, new task types are possible through testing with technology [START_REF] Stacey | Technology and Assessment in Mathematics[END_REF] which create new additional requirements for the item construction process compared to the established one [START_REF] Rupp | National educational standards in Germany: Methodological challenges for developing and calibrating standards-based tests[END_REF]. In general, however, we conclude that it is worthwhile to pursue the described implementation of a comprehensive TBA tool for the current educational standards in Germany.