B Chomet

) D Gacemi

) O Lopez

) L Del Balzo

) A Vasanelli

) Y Todorov

) B Darquié

C Sirtori

Highly coherent phase-lock of an 8.1 µm quantum cascade laser to a turnkey mid-IR frequency comb

A continuous-wave Fabry-Perot quantum cascade laser (QCL) emitting at 8.1 μm operating in single mode regime has been coherently phase locked to a turn-key low-noise commercial mid-Infrared (mid-IR) optical frequency comb. The stability of the comb used as a reference is transferred to the QCL resulting in an integrated residual phase error of 0.4 rad. The laser linewidth is narrowed by more than two orders of magnitude reaching 300 Hz at 1ms observation time, limited by the spectral purity of the mid-IR comb. Our experiment is an important step towards the development of both powerful and metrologygrade QCLs as well as fully-stabilized QCL frequency comb, and opens perspectives for precision measurements and frequency metrology in the mid-IR.

Introduction

High-spectral-purity narrow-linewidth continuous-wave (cw) lasers are crucial for both fundamental research and technological applications in many fields of science, such as atomic, molecular, quantum and optical physics. They play in particular a major role in precision measurement physics, in the development of quantum technologies, and in time and frequency metrology. For these applications, the free-running linewidth determined by the laser short-term stability is often not adequate and active frequency stabilization is required. In the near-infrared and visible domain, this is routinely achieved by locking the laser to the resonance of a high-finesse Fabry-Perot cavity, or to a narrow atomic or molecular resonance.

Frequency-stabilized sources in the mid-infrared (mid-IR, from 3 to 20 µm) domain are also needed, in particular for conducting ultra-high resolution molecular spectroscopy measurements in the so-called molecular fingerprint region with far-reaching applications ranging from fundamental physics [START_REF] Cancio Pastor | Testing the validity of Bose-Einstein statistics in molecules[END_REF][START_REF] Barontini | Measuring the stability of fundamental constants with a network of clocks[END_REF][START_REF] Fiechter | Toward Detection of the Molecular Parity Violation in Chiral Ru(acac)3 and Os(acac)3[END_REF][START_REF] Mudiayi | Linear Probing of Molecules at Micrometric Distances from a Surface with Sub-Doppler Frequency Resolution[END_REF][START_REF] Diouf | Lamb-dips and Lamb-peaks in the saturation spectrum of HD[END_REF][START_REF] Segal | Studying fundamental physics using quantum enabled technologies with trapped molecular ions[END_REF] and metrology [START_REF] Benabid | Compact, stable and efficient all-fibre gas cells using hollow-core photonic crystal fibres[END_REF][START_REF] Gatti | Frequency-combcalibrated Doppler broadening thermometry[END_REF][START_REF] Fischer | The Boltzmann project[END_REF] to astrophysics, remote sensing and Earth sciences [START_REF] Roueff | The Spectroscopic Atomic and Molecular Databases at the Paris Observatory[END_REF][START_REF] Galli | Spectroscopic detection of radiocarbon dioxide at parts-per-quadrillion sensitivity[END_REF] .

Quantum cascade lasers (QCLs) are a robust technology that cover the mid-IR spectrum, offer wide tuning capabilities and have cw output powers as high as several watts but QCLs show substantial frequency fluctuations [12][START_REF] Myers | Freerunning frequency stability of mid-infrared quantum cascade lasers[END_REF][START_REF] Bartalini | Observing the Intrinsic Linewidth of a Quantum-Cascade Laser: Beyond the Schawlow-Townes Limit[END_REF][START_REF] Tombez | Frequency noise of freerunning 4.6 μm distributed feedback quantum cascade lasers near room temperature[END_REF][START_REF] Bartalini | Measuring frequency noise and intrinsic linewidth of a room-temperature DFB quantum cascade laser[END_REF][START_REF] Cappelli | Intrinsic linewidth of quantum cascade laser frequency combs[END_REF][START_REF] Mills | Coherent phase lock of a 9 μm quantum cascade laser to a 2 μm thulium optical frequency comb[END_REF][START_REF] Galli | Comb-assisted subkilohertz linewidth quantum cascade laser for high-precision midinfrared spectroscopy[END_REF] . Phase/frequency stabilized QCLs have been demonstrated [START_REF] Consolino | QCL-based frequency metrology from the mid-infrared to the THz range: a review[END_REF] , either by phase-locking to a CO 2 laser [START_REF] Bielsa | Narrow-line phase-locked quantum cascade laser in the 9.2 μm range[END_REF][START_REF] Sow | A widely tunable 10-μ m quantum cascade laser phase-locked to a state-of-the-art mid-infrared reference for precision molecular spectroscopy[END_REF] , frequency locking to a sub-Doppler molecular transition [START_REF] Cappelli | Subkilohertz linewidth room-temperature mid-infrared quantum cascade laser using a molecular sub-Doppler reference[END_REF] , optical injection locking [START_REF] Borri | Direct link of a mid-infrared QCL to a frequency comb by optical injection[END_REF] or phase-locking to an optical frequency comb, either calibrated to a commercial Rb frequency standard or H-Maser steered to a global navigation satellite system (GNSS) [START_REF] Mills | Coherent phase lock of a 9 μm quantum cascade laser to a 2 μm thulium optical frequency comb[END_REF][START_REF] Galli | Comb-assisted subkilohertz linewidth quantum cascade laser for high-precision midinfrared spectroscopy[END_REF][START_REF] Gambetta | Direct phase-locking of a 8.6-μm quantum cascade laser to a mid-IR optical frequency comb: application to precision spectroscopy of N 2 O[END_REF][START_REF] Borri | Frequency-comb-referenced quantum-cascade laser at 4.4 μm[END_REF][START_REF] Gambetta | Absolute frequency measurements of CHF 3 Doppler-free rovibrational transitions at 8.6 μm[END_REF][START_REF] Gambetta | Frequency metrology in the near-infrared spectrum of H217O and H218O molecules: testing a new inversion method for retrieval of energy levels[END_REF][START_REF] Hansen | Quantum cascade laser-based mid-IR frequency metrology system with ultra-narrow linewidth and 1 × 10 -13 -level frequency instability[END_REF] , or stabilized to a near-infrared metrology-grade frequency reference traceable to primary frequency standards [START_REF] Insero | Measuring molecular frequencies in the 1-10 μm range at 11-digits accuracy[END_REF][START_REF] Santagata | Highprecision methanol spectroscopy with a widely tunable SI-traceable frequency-comb-based mid-infrared QCL[END_REF][START_REF] Argence | Quantum cascade laser frequency stabilization at the sub-Hz level[END_REF] . References [START_REF] Santagata | Highprecision methanol spectroscopy with a widely tunable SI-traceable frequency-comb-based mid-infrared QCL[END_REF][START_REF] Argence | Quantum cascade laser frequency stabilization at the sub-Hz level[END_REF] report ultimate sub-Hz stabilities and accuracies, and linewidth narrowing down to the 0.1 Hz level. Locking to a frequency comb typically necessitates sophisticated non-linear optical setups requiring very delicate alignment procedures, and often penalizing the QCL output power, most of it being required for generating non-linear signals.

In this Letter, we measure the free-running frequency noise power spectral density of an 8.1 µm Fabry-Perot QCL operating in single mode regime and demonstrate coherent phase locking of this source to a tooth of a commercially available low-noise mid-IR optical frequency comb synthesizer (OFCS), by processing a beat-note signal generated directly in a mid-IR photodetector. This allows the spectral performances of the OFCS to be transferred to the QCL without the need to pass the QCL beam through a complex dedicated non-linear optical setup, thus allowing less than 1% of its optical power to be used for locking, keeping most of it at disposal for further experiments. Locking to such a low-noise comb results in a linewidth narrowing of the QCL by of factor of 250, from ~100 kHz down to the few hundreds of hertz level. This corresponds to a 2 orders of magnitude linewidth improvement compared to reference [START_REF] Gambetta | Direct phase-locking of a 8.6-μm quantum cascade laser to a mid-IR optical frequency comb: application to precision spectroscopy of N 2 O[END_REF] that reports phase locking of a distributed feedback QCL to a home-built mid-IR comb. Locking the OFCS to a remote near-infrared ultra-stable frequency reference traceable to the atomic fountain clocks of the French metrology institute, as demonstrated in reference [START_REF] Santagata | Highprecision methanol spectroscopy with a widely tunable SI-traceable frequency-comb-based mid-infrared QCL[END_REF][START_REF] Argence | Quantum cascade laser frequency stabilization at the sub-Hz level[END_REF] will eventually provide a both powerful and metrology-grade QCL to be used in different applications such as high precision spectroscopy, quantum optics measurements or LIDAR (light detection and ranging).

Experiment

The experimental setup is shown in Fig. 1(a). A turn-key offset-free mid-IR OFCS from Menlo Systems, spanning the 7.4 to 9.4 µm spectral window (full-width-half-maximum FWHM ~4.29THz), is used as an optical reference. The mid-infrared comb is generated by difference frequency mixing in a non-linear crystal between a low noise 1.5 μm Erbium doped fiber frequency comb and its extension in a wavelength shifting fiber towards the 1.8 μm window. The mid-IR comb delivers an average output power of 2.2 mW, resulting in tens of nanoWatts comb modes. The comb repetition rate, 𝑓 100 𝑀𝐻𝑧, is stabilized against a radio-frequency (RF) synthesizer using the electronic control unit of the comb. This corrects the slow frequency drift without affecting the laser linewidth. The QCL is a Fabry-Perot source grown and processed at ETH Zürich

Free-running Fabry-Perot QCL frequency noise

The frequency noise power spectral density (FNPSD) of the free-running QCL is derived from the beat-note signal f beat + f rep does not consider the frequency noise that could be added by non-linear processes involved in the generation of the mid-IR OFCS which is assumed to be negligible.

For Fourier frequencies below 300 kHz, the blue curve (I) in Fig. 2(a) corresponds to the free-running QCL FNPSD, all other contributions being negligible. The level of frequency noise measured is similar to that reported in ref [START_REF] Cappelli | Intrinsic linewidth of quantum cascade laser frequency combs[END_REF] , another measurement carried out on a Fabry-Perot QCL. Yet, the expected white frequency noise level corresponding to the QCL Schawlow-Townes limit does not seem to be reached above 300 kHz due to our SNR value. However, an upper limit of 10 3 Hz 2 /Hz (and a corresponding upper limit of ~3 kHz on the intrinsic laser linewidth) can be inferred. The free-running QCL emission line shape is calculated from the measured FNPSD for a 1 ms integration time (IT) following [START_REF] Elliott | Extracavity laser band-shape and bandwidth modification[END_REF] and shows a FWHM Δν , QCL ∼72 kHz (see Fig. 2(a) inset). A similar calculation based on curve (III) in Fig. 2 As illustrated in Fig. 1(a), to coherently phase-lock the QCL to a tooth of the mid-IR-OFCS, a phase-error signal is generated by comparing the phase of the filtered and amplified beat signal with a reference signal typically at 140 MHz from a synthesizer (Zurich Instrument UHFLI). A phase-lock servo loop is used to apply a correction signal directly to the QCL's current. Note that much less than 1% of the QCL power (<100µW) is used for locking, keeping most of it at disposal for different experiments

In closed-loop operation, a significant narrowing of the beat-note signal linewidth is observed and a maximum signal-to-noise ratio of about 55 dB at 1 kHz resolution-bandwidth was obtained, as shown in the inset of Fig. 3. The beat signal spectrum is recorded on a RF spectrum analyzer after detection with a second out-of-loop photodetector (detector 2 in Fig. 1(a)), similar to the one in-loop, in order to avoid errors brought by the detection setup and associated electronics. A ∼250 kHz phase-lock feedback bandwidth can be inferred from the spectral shape. Figure 3 shows the measured phase noise PSD of the beat signal between the Mid-IR-OFCS and the phase locked QCL. The latter is generated by comparing the phase of the beat signal at the output of detector 2 with a synthesized reference signal at 140 MHz (UHFLI Zurich Instrument) and processed with a FFT spectrum analyzer. A 0.39-rad rms residual phase noise is obtained in a 1 Hz to 1 MHz integration bandwidth, indicating that more than 85% of the power is concentrated in the coherent carrier of the beat signal [START_REF] Zhu | Stabilization of optical phase/frequency of a laser system: application to a commercial dye laser with an external stabilizer[END_REF] . This is the signature of a highly coherent phase-lock and of the very good transfer of the mid-IR OFCS spectral features to the QCL. Therefore, this results in a QCL linewidth ultimately set by the mid-IR comb tooth linewidth. Exploiting the OFCS FNPSD displayed in Fig. 2 (dashed red line (III)), we calculate a linewidth of respectively ~300 Hz (see above) and ∼800 Hz at 1 ms and 100 ms integration time, which is 2 to 3 orders of magnitude lower than in the free-running regime. Our phaselocked Fabry-Perot QCL shows a 2 orders of magnitude narrower linewidth compared to a similar work using a 8.6 µm DFB QCL phase-locked to a home-built 250 MHz mid-IR comb [START_REF] Gambetta | Direct phase-locking of a 8.6-μm quantum cascade laser to a mid-IR optical frequency comb: application to precision spectroscopy of N 2 O[END_REF] .

Conclusion

We characterized the frequency noise of an 8.1 µm free-running Fabry-Perot QCL operating in single mode regime. It was then phase-locked to a low-noise commercial mid-infrared comb, itself generated from a near-infrared comb. We achieved a QCL linewidth reduction from ~100 kHz to the few 100 Hz level, limited by the linewidth of the mid-IR comb used as a reference, improving on previous studies. Locking the comb to an ultra-stable frequency reference calibrated to the primary frequency standards of the French metrology institute [START_REF] Santagata | Highprecision methanol spectroscopy with a widely tunable SI-traceable frequency-comb-based mid-infrared QCL[END_REF][START_REF] Argence | Quantum cascade laser frequency stabilization at the sub-Hz level[END_REF] will eventually result in ultimate sub-Hz stabilities, accuracies and linewidths.

One advantage of our method lies on the generation of a beat-note signal directly in the mid-IR without the need to pass the QCL beam through a sophisticated non-linear optical setup. As a result, much less than 1% of the QCL optical power is used for locking, allowing almost all of the QCL power to be exploited. We obtain a QCL that is both powerful and highly stablepotentially ultra-stable -to be exploited in a range of applications from fundamental research in quantum optics and highresolution spectroscopy to quantum technologies or LiDAR. When driven at higher currents, our Fabry-Perot QCL operates in optical-frequency-comb regime (see supplementary materials). Our work thus also paves the way toward the development of powerful and fully stabilized metrology-grade QCL frequency combs.

SUPPLEMENTARY MATERIAL

See Supplementary material for supporting content.

(

  more details about this laser are given in the supplementary material). It is typically operated close to threshold at a temperature of 263 K (threshold current is 400 mA), and delivers up to 45 mW in a continuous wave single mode oscillating at a wavelength of ~8.16 µm. Fig. 1(b) shows the optical spectrum of the mid-IR comb that overlaps with the single longitudinal mode of the QCL. The QCL and the mid-IR-OFCS beams are superimposed by means of a 70/30 germanium beam splitter. Both beam splitter outputs are optically filtered with a 50 GHz resolution monochromator, and focused onto an 800-MHz bandwidth mercury-cadmium-telluride (MCT) detector (VIGO System PVI-4TE-10.6) (see supplementary material). The QCL beam is attenuated and a total power of about only 100 µW is hitting the detector. The resulting beat-note signals obtained on detector 1 and 2 in Fig. 1(a) oscillate at: 𝑓 𝑣 𝑛 𝑓 with ν QCL the QCL frequency and n~ 370 000 the tooth number of the mid-IR-OFCS. Note that in our case the carrier-envelope offset fCEO = 0, as the mid-IR comb is generated by frequency difference. Fig. 1(c) shows the RF spectrum of the signal measured at the output of detector 1 when the QCL operates in a free-running regime. Four main peaks emerge from the noise between DC and 150 MHz: the beat-note signal between the QCL mode and the nearest comb tooth at f beat ≃ 23 MHz, a peak at the comb repetition rate of 100 MHz, and the beat-note signals between the QCL mode and the second-and third-nearest comb teeth at f rep ± f beat (≃77 MHz and ≃ 123 MHz). The OFC/QCL beat signals are observed with a signal-to-noise ratio (carrier power to phase noise power density ratio) of SNR = 26 dB at 1MHz resolution bandwidth and are processed to either measure the frequency noise of the free-running QCL, or for phase-locking it to the OFCS. To characterize the residual phase fluctuations of the locked QCL, a second out-of-loop detector (detector 2) is used.

FIG. 1 .

 1 FIG. 1. (a) Experimental setup for measuring the frequency noise of the free-running QCL and for coherently phase-locking it to a low-noise mid-IR OFCS. FP-QCL, Fabry-Perot Quantum Cascade Laser; mid-IR OFCS, mid-infrared-optical frequency comb synthesizer; BS, beam splitter; OF, optical filtering monochromator build from a diffractive grating with 150 grooves/mm; PLL, phase lock loop; OI, optical isolator; VCO, voltage controlled oscillator; FFT, fast Fourier transform (b) Optical spectra of the FP-QCL and the mid-IR OFCS recorded with a 2 GHz resolution optical spectrum analyzer (the modes of the 100 MHz repetition rate OFCS are not resolved). (c) RF spectrum of the beat signal between the mid-IR OFCS and the free running QCL (1 MHz resolution bandwidth, RBW).

measured on detector 1 ,Fig. 2 (

 12 Fig.2(a) shows the resulting FNPSD of the free-running QCL/mid-IR comb beat-note signal (blue line (I)). It has a 1/f trend at low frequency up to ~300 kHz. Above 300 kHz, the frequency noise increases up to approximately 4 MHz, beyond which we observe a decrease due to the finite tracking oscillator bandwidth. The increase of the frequency-noise above 300 kHz is the consequence of the finite beat-note signal-to-noise ratio of 86 dB/Hz, limited by our detector background noise (see supplementary material). The corresponding white phase noise around the optical carrier gives rise to a double-sided contribution of (2/SNR 1Hz ) × f² in our FNPSD measurement, with SNR 1Hz the SNR in a 1 Hz bandwidth. To validate this, the black curve (IV) in Fig.2(a) shows the FNPSD obtained by blocking the mid-IR-OFCS beam and by replacing fbeat with a low phase noise artificial signal yielding the same SNR1Hz generated by modulating the QCL current with a RF generator. The flat plateau in the range 1 Hz-100 kHz is due to the FFT-analyzer background noise, and above 100-kHz the effect of the SNR can be seen as it matches the blue curve (I). The grey line (II) in Fig.2(a)shows the contribution of the low-noise current source, obtained by multiplying the measured driver's current noise spectrum (~300 pA/Hz 1/2 above 100Hz) by the laser DC currentto-frequency response (-235 MHz/mA). Finally, the red dashed line (III) in Fig.2(a) gives the contribution from the OFCS tooth frequency noise to the heterodyne signal. The FNPSD of this tooth at frequency 𝑛 𝑓 is determined from typical noise measurements of the repetition rate of the OFCS 1.55 µm main oscillator provided by Menlo Systems. Note that this estimation

  (a) leads to a linewidth Δν, OFCS = 300 Hz (1ms IT) for the OFCS tooth, once again confirming the negligible contribution of the OFCS noise in our measurement. Fig.2(b)shows the evolution of Δν, QCL calculated for different integration times. It decreases with decreasing integration time and reaches a minimum of 15 kHz at 200 µs IT. For the shortest integration times (< 100 µs), the linewidth is Fourier limited: the contribution from the frequency noise is lower than the Fourier uncertainty.

FIG. 2 .

 2 FIG. 2. (a) Frequency noise power spectral density (FNPSD) of the free-running 8.1 µm QCL/mid-IR comb beat-note signal (blue line (I)).The contributions from the laser driver current noise (grey line (II)) and from the mid-IR OFCS tooth contributing to the beat-note signal (red dashed line (III)) are also plotted for comparison. The black line (IV) corresponds to our noise floor, see text (with the black dashed line corresponding to the contribution from the limited beat-note signal-to-noise ratio of 86 dB/Hz). The tracking oscillator bandwidth is also shown (vertical red dashed line). The inset shows the free-running QCL emission line shape calculated from the measured FNPSD (I) for a 1 ms integration time (IT). (b) Blue line: free-running QCL FWHM emission line width as a function of integration time calculated from FNPSD (I) (the slight excess of noise of technical origin visible on curve (I) between 40 Hz and 100 Hz has been purposely removed for this calculation); the grey line corresponds to the Fourier limit resulting from the resolution bandwidth.

FIG. 3 .

 3 FIG.3. Phase-noise power spectral density (PSD) of the beat signal between the phase-locked QCL and the mid-IR comb. Inset: Beat signal spectrum between the mid-IR OFC and the phase-locked QCL taken with a RF spectrum analyzer (1 kHz resolution bandwidth, RBW).

Fabry-Perot QCL phase locking and linewidth narrowing

ACKNOWLEDGMENTS

This work has been supported by the Region Ile-de-France in the framework of DIM SIRTEQ, by the Agence Nationale de la Recherche (project CORALI ANR-20-CE04-0006) and project COLECTOR ANR-19-CE30-0032) and by ENS-Thales Chair.

The authors thank MenloSystems for fruitful discussions and for providing typical phase noise measurements of the OFCS repetition rate.


R Proietti

G Pezzulo

A Tessari

Anna M Borghi
email: anna.borghi@uniroma1.it

Angelo Mattia Gervasi

Claudio Brozzoli

Language as a means to reduce uncertainty Comment on "An active inference model of hierarchical action understanding, learning and imitation" by

Keywords: Language, Action, Uncertainty, Active inference, Affordance

The paper "An active inference model of hierarchical action understanding, learning and imitation" [START_REF] Proietti | An active inference model of hierarchical action understanding, learning and imitation[END_REF] provides an interesting and comprehensive overview and a compelling model of how action understanding, learning, and imitation might occur. Rather than focusing on the approach, with which we are fully sympathetic, or the model's detail, in the following, we will highlight some points that the authors might want to incorporate or address.

One aspect not addressed in the model is the role language might play in this framework. The authors mention language only tangentially when they say "prior information can come from different sources: it can be provided exogenously (for example, via verbal or contextual cues) or be generated endogenously, on the basis of the learner's own motor knowledge." (pag. 98). We agree that language can be a cue conveying previous information like context does, but we think that it can be more than a cue. Language not only helps grounding in the environment through simulation of sensorimotor (exteroceptive, proprioceptive, and interoceptive) experiences, a mechanism the authors mention (p. 101), but it also extensively contributes to action preparation and implementation. Language can help construct predictions in relation to which sensory signals can be evaluated [START_REF] Lupyan | Words and the World: predictive coding and the language-perception-cognition interface[END_REF]. Language can be a powerful tool to reduce uncertainty in action selection (on the role of language overall, see [START_REF] Borghi | The freedom of words: abstractness and the power of language[END_REF]).

Once a label is used, for example, to name an action, the action representation becomes more compact, its differentiation from similar actions increases, and its boundaries from other actions become less fuzzy [START_REF] Cangelosi | The emergence of a 'language' in an evolving population of neural networks[END_REF]. Providing new labels for new tools facilitates their use [START_REF] Foerster | Labels strengthen motor learning of new tools[END_REF]. Providing a new label to a novel action might help strengthen its salience and memorability, enhance its recognition, make its execution smoother, and facilitate its imitation. Notably, previous studies have shown that potentiating language abilities, for example, syntactic ones, might impact the ability to perform sequential, hierarchical actions [START_REF] Brozzoli | Language as a tool: motor proficiency using a tool predicts individual linguistic abilities[END_REF][START_REF] Thibault | Tool use and language share syntactic processes and neural patterns in the basal ganglia[END_REF]. The role of language in the context of action learning might not be limited to overt language. During action learning, a special role is played by inner language or self-talk: it can help maintain action-related information in working memory, it can motivate and even support action endurance [START_REF] Latinjak | Self-Talk: an interdisciplinary review and transdisciplinary model[END_REF][START_REF] Nedergaard | Verbal interference paradigms: a systematic review investigating the role of language in cognition[END_REF].

Aside from tangentially mentioning "verbal cues", the authors extensively discuss the distinction between a direct and a semantic route to action. Importantly, however, semantic knowledge does not necessarily involve language -we might form a concept without a corresponding label. Labels represent an additional layer that might further facilitate action planning, recognition, and execution. This is related to affordances, and particularly how language encodes and reflects them. While distinguishing between the direct and semantic routes, the authors mention different affordances, e.g., functional and structural ones. Similarly, studies on stable and variable affordances [START_REF] Borghi | Stable and variable affordances are both automatic and flexible[END_REF][START_REF] Sakreida | Affordance processing in segregated parieto-frontal dorsal stream sub-pathways[END_REF] have shown that the processing of variable affordances, like the current orientation of objects, activates a direct, automatic vision-to-action route implemented in dorso-dorsal circuits. By contrast, a more ventral representation (dorso-ventral circuit) concerns actions evoked by stable affordances, like size, and texture. Importantly, actions prompted by stable affordances are also those encoded linguistically.

Another aspect that the authors might want to discuss further and eventually implement in the model is the distinction between different kinds of actions and the relative mechanisms of motor resonance when imitating. We might learn novel actions that we have previously recurrently observed but not executed. For example, one could be an eager spectator of tennis matches without having ever played tennis. Also, we might learn novel actions after having previously executed some chunks or components of them. The motor resonance mechanisms elicited in the two cases might differ consistently. In addition, although the focus of the model is on imitation, we wonder why the authors do not mention the fact that, in some cases, observing actions might lead to activate not a similar but a complementary action to the one we observe. Notably, the mirror neuron system is activated also in the second case [START_REF] Newman-Norlund | The mirror neuron system is more active during complementary compared with imitative action[END_REF], and the authors themselves have provided important contributions both on imitation and joint action.

One further point concerns the role of visual attention in relation to body parts. In the first simulation, the authors claim: "The learner can only make saccades to one body part at a time but can integrate this information over time to infer the current movement segment of the teacher." Our impression is that visual attention might be more diffuse and less focused on single body parts and that the visuospatial expertise of the observer might modulate its role. For example, an expert player might more easily connect single body parts with global bodily movements, weighting differently each step's solution in the hierarchical model.

A final remark concerns the choice of tennis as a paradigmatic example. While we appreciate that the authors investigated a sports activity and do not question the example's generalizability, we believe there could be clearer examples. Consider, for example, the intention of preparing coffee and the proximal scopes related to the single actions that compose it -opening the coffee pot, pouring water, inserting coffee, etc. In the case of tennis, the distinction between intentions and proximal goals, although present, is sometimes blurred and not clearly distinguishable as in the case of other actions.

Acknowledgements

Funding: Concepts in Interaction with Others and with Ourselves. Sapienza Excellence Projects, grant n. RG12117A5D1EB0B3 (Pi AMB).

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.


Slow, low-dimensional dynamics in balanced networks with partially-symmetric connectivity

Xiaoyu Yang, Giancarlo La Camera, Gianluigi Mongillo Summary: Cortical dynamics are slow and low dimensional. Relaxation, as measured for instance by the auto-correlation of the spike counts, is slow compared to single neuron and synapse time constants, i.e., seconds vs. hundreds of milliseconds. Spiking activity is coordinated across the network despite weak, zero-lag cross-correlations between pairs of neurons. Thus, the network dynamics are described by a small, compared to the number of observed neurons, number of collective variables. By which mechanism(s) slow and low-dimensional dynamics arise in cortical networks? How these features are related to each other? Existing theories explain them as a result of precise adjustments of the synaptic connectivity. Slow relaxation is obtained, for instance, when the network operates close to the edge of stability, which requires tuning the variance of the synaptic efficacies. Low-dimensional dynamics are obtained, for instance, if the connectivity matrix is rank-deficient, which seems to require some form of synaptic plasticity. We note that the rank of a matrix and the variance of its elements can be independently adjusted. Here, we show that slow and low-dimensional dynamics naturally arise in balanced networks in the presence of partially-symmetric synaptic connectivity, consistent with experimental observations. The symmetry leads to an effective retarded self-interaction that slows down the dynamics and it tends to induce strong cross-correlations between pairs of neurons. These, however, are actively suppressed in the balanced regime, leading to strongly-correlated network states with weak pair-wise correlations. We illustrate the computational relevance of this regime by showing that the network can dynamically retain the memory of a random stimulation over long time intervals, in the presence of temporal noise. Taken together, our results suggest that slow and low-dimensional dynamics are a generic feature of cortical networks. In turn, such a dynamics lead to robust, long-lived memory traces even in the absence of learning-related synaptic plasticity.

Additional detail:

We shortly describe the model network and the main results of our analysis. Shortly, the network consists of N all-to-all connected inhibitory neurons, described as threshold-linear rate units (Berlemont & Mongillo, 2022). Synaptic connectivity is described by the correlation between the synaptic efficacies in pairs of neurons, ρ w (level of symmetry), and by the standard deviation of the synaptic efficacies, σ w (synaptic gain). The network also receives a constant excitatory input from outside. A standard set of coupled, first-order differential equations for the time evolution of the synaptic inputs describes the network dynamics. The network operates in the balanced regime in the limit of N→∞, regardless of the value of ρ w and σ w . However, other aspects of the dynamics critically depend on their value. In particular, when the rescaled gain, g w =-1+[σ w (1+ρ w )] 2 /2, is positive, the network dynamics do not converge to a fixed point (unlike the case g w <0) and single neurons' activities keep fluctuating in time. Roughly speaking, g w quantifies the distance from the critical line (i.e., g w =0) so that the larger g w the farther from the critical line. For g w >0, the dynamics can be studied with an extension of cavity method described in (Berlemont & Mongillo, 2022). We quantify the dimensionality of the collective dynamics for g w >0 by numerically estimating the participation ratio (PR), see, e.g., (Engelken et al., 2020). For a fixed synaptic matrix, we run the dynamics for 500 time constants, starting from 100 different initial conditions (ICs), randomly and independently chosen. We sample the synaptic inputs of 250 neurons (out of N=4000) at every time constant. Finally, we perform a standard PCA analysis on the resulting time series. The results are illustrated in Fig. 1 for g w =1 and ρ w =0, 0.8 and 1.0. The PR significantly decreases (Fig. 1a) and the dynamics significantly slows down (Fig. 1b-c) at increasing ρ w . For ρ w =0.8, the projections of the dynamics on the first 2 principal components are well separated suggesting that the dynamics spend a significant amount of time in restricted regions of the phase space (depending on the IC). This is reminiscent of the weak ergodicity breaking occurring in mean-field models of spin and structural glasses (Cugliandolo & Kurchan, 1995).

To probe the computational relevance of the observed dynamics, we present the network with 5 different stimuli. Each stimulus consists of N external inputs, randomly and independently drawn from a standardized Gaussian distribution. The stimuli are transiently applied for 50 time constants. We also inject Gaussian white noise for the duration of the simulation (500 time constants). Then, we train a maximum-margin perceptron at each time point and use a one-vs-one strategy to decode the 5 stimuli. The decoding accuracy with cross-validation provides a simple way to quantify memory lifetime. Fig. 2 shows the decoding accuracies, averaged over folds and pairs of stimuli, for various network parameters and noise intensities. As can be seen (bottom row), for ρ w =0.6 the decoding accuracy stays above chance for ~100 time constants. Far from the critical line, furthermore, it is weakly dependent on noise intensity. This is in dramatic contrast to what happens at ρ w =0, i.e., in a random network (Fig. 2 top row).

Fig. 1 :

 1 Fig. 1: (a) fraction of explained variance as a function of the number of principal components (PCs). (b)-(c)Projections of the network dynamics onto the first 2 PCs for 5 randomly selected initial conditions.

Fig. 2 :

 2 Fig. 2: Decoding accuracy at varying distance from the critical line for 2 levels of symmetry and 3 levels of temporal noise (σext). Accuracies are averaged over folds and pairs of stimuli. Gray bars indicate the interval during which the stimulus is present.


Cyril Nicaud
email: nicaud@univ-mlv.fr

On the Average Size of Glushkov's Automata

Glushkov's algorithm builds an ε-free nondeterministic automaton from a given regular expression. In the worst case, its number of states is linear and its number of transitions is quadratic in the size of the expression. We show in this paper that in average, the number of transitions is linear.

Introduction

Kleene's Theorem states that regular expressions and automata describe the same objects, regular languages. They both are finite objects which encode infinite sets of words and they play a key role in formal language theory as well as in its many fields of application.

One can often take advantage of having this two different representations, the algorithmic problems of transforming one representation into another are therefore fundamental. They have been widely studied and are still improved nowadays, as one can see in a recent survey by J. Sakarovitch [START_REF] Sakarovitch | The language, the expression, and the (small) automaton[END_REF].

In this paper we focus on one particular such transformation, Glushkov's algorithm [START_REF] Glushkov | The abstract theory of automata[END_REF], an algorithm that builds an ε-free nondeterministic automaton from a given regular expression. Starting from a regular expression with n letters, it builds an automaton with n + 1 states and O(n 2 ) transitions. In [START_REF] Hromkovic | Translating regular expressions into small epsilon-free nondeterministic finite automata[END_REF], J. Hromkovic, S. Seibert and T. Wilke proposed a variation on this algorithm where the produced automaton has O(n log 2 n) states. They also proved a lower bound of Ω(n log n) states for this general problem. Based on this work, C. Hagenah and A. Muscholl proposed in [START_REF] Hagenah | Computing epsilon-free NFA from regular expressions in O(n log 2 (n)) time[END_REF] an algorithm of time complexity O(n log 2 n) to achieve the construction. See also [START_REF] Ilie | Constructing NFA s by optimal use of positions in regular expressions[END_REF][START_REF] Champarnaud | Computing the follow automaton of an expression[END_REF] for some efficient related algorithms.

Our contribution is to give an average case analysis of the size of Glushkov's automata. Using the framework of analytic combinatorics, we prove that for the uniform distribution of regular expressions, the average number of transitions is linear.

The use of generating functions and complex analysis have proved to be useful in average case analysis of algorithms [START_REF] Flajolet | Analytic Combinatorics[END_REF]. The methodology we shall use here can be summarized as follows:

1. Find an unambiguous specification of the objects, which can be recursive. The paper is organized as follows. In Section 2, we recall the basic definitions and present some analytic tools. In Section 3, we study the generating function associated to regular expressions. Section 4 is devoted to our main result. Finally, a short discussion about the distribution is presented in Section 5.

Note that due to the lack of space, we can not show all the details of the computations, but most of them are easily done with the help of a computeralgebra system.

Preliminaries

Automata and Regular Expressions

An automaton defined on a finite alphabet A is a tuple (A, Q, T, I, F ) where Q is the finite set of states, T ⊂ Q × A × Q is the set of transitions, I ⊂ Q is the set of initial states and F ⊂ Q is the set of final states. We refer the reader unfamiliar with basic notions of automata and regular languages to [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF] for definitions and fundamental results.

The set of nonempty regular expressions R on a finite alphabet A is a set of words on the alphabet {ε, •, * , ∪, (, )} ∪ A defined inductively by: ε

∈ R, A ⊂ R, (R) * ∈ R for all R ∈ R, (R 1 •R 2 ) and (R 1 ∪R 2 ) for every R 1 , R 2 ∈ R.
A language defined on A is denoted by a regular expression of R when it is exactly the set of words obtained by interpreting each symbol * , • or ∪ as the corresponding regular operation on sets of words. Let L(R) be the language denoted by R ∈ R. For convenience, we shall freely remove parenthesis symbols that are not needed in an element of R. It is also often useful to see regular expressions as trees, with this equivalent inductive definition:

                 ε ∈ R a ∈ R ∀a ∈ A * | R ∈ R ∀R ∈ R ∪ /\ R1 R2 ∈ R ∀R 1 , R 2 ∈ R • /\ R1 R2 ∈ R ∀R 1 , R 2 ∈ R (1)
The size of an element of R is the number of nodes in its tree representation:

|ε| = |a| = 1; * | R = |R| + 1; ∪ /\ R1 R2 = • /\ R1 R2 = |R 1 | + |R 2 | + 1
Note that one usually add to R the symbol ∅ that denotes the empty language. For technical reasons it is slightly more convenient in this paper to work on nonempty regular languages.

Glushkov's Automaton

Let m be the number of letter symbols in R, for R ∈ R. We consider the expression R obtained from R by distinguishing the letters with subscripts in {1, • • • , m}, marking them from left to right on its string representation, or equivalently using depth-first order on its tree representation. For instance

R = b * •(a∪b•b) * is changed into R = b * 1 •(a 2 ∪b 3 •b 4 ) * .
We denote by pos(R) the set of subscripted letters in R: pos(R) = {b 1 , a 2 , b 3 , b 4 } in the example. We also denote by ν the function from pos(R) to A that removes the subscripts, ν(a 2 ) = a for instance.

Let F irst(R) and Last(R) be the sets defined by And for any letter α in pos(R), the set f ollow(R, α) is defined by

F irst(R) = {α ∈ pos(R) | ∃u ∈ L( R),
f ollow(R, α) = {β ∈ pos(R) | ∃u ∈ L( R), αβ is a factor of u}
The Glushkov's automaton of R, also called the position automaton, is the automaton

A R = (A, Q, T, {i}, F ) with Q = pos(R) ∪ {i}, F = Last(R) ∪ {i} if ε ∈ L(R) and F = Last(R) otherwise, and T = {(i, ν(α), α) | α ∈ F irst(R)} ∪ {(α, ν(β), β) | β ∈ f ollow(R, α)}.
This classical construction provides an automaton that recognizes L(R).

Let Edges(R) be the set of pairs (α, β) ∈ pos(R) 2 such that β ∈ f ollow(α).

The number of transitions in

A R is thus |F irst(R)| + |Edges(R)|.
The set Edges(R) can also be defined inductively as follows.

                   Edges(ε) = 0 Edges(a) = 0 Edges * | R = Edges(R) ∪ Last(R) × F irst(R) Edges ∪ /\ R1 R2 = Edges(R 1 ) ∪ Edges(R 2 ) Edges • /\ R1 R2 = Edges(R 1 ) ∪ Edges(R 2 ) ∪ Last(R 1 ) × F irst(R 2 ) (2)

Generating Functions

A combinatorial class C is a set of objects with a size function | • | from C to N such that, for any n ∈ N, the number c n of objects of size n in C is finite. The generating function C(z) of a combinatorial class C is the formal power series

C(z) = C∈C z |C| = n≥0 c n z n We also denote by [z n ]C(z) = c n the coefficient of z n in C(z).
Let C be a combinatorial class of generating function C(z) and let f : C → R be a mapping from this class to R. The cost generating function

F (z) of C associated to f is F (z) = C∈C f (C)z |C| = n≥0 f n z n , with f n = C∈C |C|=n f (C)
For a given n, the average value of f for the uniform distribution on the elements of size n of C is therefore

µ n (C, f ) = [z n ]F (z) [z n ]C(z)
The following lemma, though trivial, will be useful throughout this article.

Lemma 1. Let A and B be two combinatorial classes. Let f : A → R and g : B → R be two mappings from A and B to R. The following property holds.

A∈A B∈B

(f (A) + g(B))z |A| z |B| = F (z)B(z) + A(z)G(z)
where A(z), B(z), F (z) and G(z) respectively denote the generating functions of A and B and the cost generating functions associated to f and g.

Symbolic Methods and Transfer Theorem

The symbolic methods were introduced in [START_REF] Flajolet | The average height of binary trees and other simple trees[END_REF]. When they can be applied, they directly and almost automatically build the generating functions associated to combinatorial classes. The idea is to avoid recurrence formulas on the number of objects by providing a dictionary that maps combinatorial constructions on classes into constructions on generating functions. This dictionary covers a lot of used constructions, and one can easily use it to describe combinatorial classes such as trees, permutations, set partitions, integer partitions, random mappings, etc. therefore obtaining directly their generating functions.

In this article we shall only use a small part of this dictionary, the most basic one. If A = B ∪ C are combinatorial classes such that B and C are disjoint, it is direct to prove that the associated generating functions A(z), B(z) and C(z) satisfy A(z) = B(z) + C(z). Moreover if A = B × C, one can see that A(z) = B(z)C(z). We shall only need this two constructions here, but in this framework, one can directly derive the generating functions of sequences of elements in A, sets of elements in A, and so on. We refer the reader to P. Flajolet and R. Sedgewick's book for more informations about this topic [START_REF] Flajolet | Analytic Combinatorics[END_REF].

Once the generating function is known, either in close or implicit form, several theorems exist to compute asymptotic estimations of its coefficients. This theorems mainly use the theory of complex analysis, seeing generating functions as analytic functions from C to C. The main idea is that the asymptotics of the coefficients of a generating function can be obtained by studying it around its dominant singularities (its singularities of smallest moduli). Informally, given a generating function A(z) of unique dominant singularity ρ, the transfer theorem states under some analytic conditions that if

A(z) ∼ B(z) as z → ρ, then [z n ]A(z) ∼ [z n ]B(z)
, for some useful functions B(z) whose coefficient asymptotics are well-known.

We use the notations of [START_REF] Flajolet | Analytic Combinatorics[END_REF] to give a formal description of the theorem. Let R > 1 and 0 < φ < π/2 be two real numbers, the domain ∆(φ, R) is

∆(φ, R) = {z ∈ C | |z| < R, z = 1 and |Arg(z -1)| > φ}
A domain is a ∆-domain at 1 if it is a ∆(φ, R) for some R and φ. For a given complex number ζ = 0, a ∆-domain at ζ is the image by the mapping z → ζz of a ∆-domain at 1. A function is ∆-analytic if it is analytic in some ∆-domain.

Theorem 1 (part of Transfer Theorem). Let α and β be real number and let f (z) be a function that is ∆-analytic that satisfies, on the intersection of a neighborhood of 1 and its ∆-domain, the condition

f (z) = o (1 -z) -α log 1 1 -z β then [z n ]f (z) = o(n α-1 (log n) β ).
Recall that Pringsheim's Theorem states that if f (z) representable at the origin by a series expansion with nonnegative coefficients, one of its dominant singularities, if any, is on R + . This theorem is useful as generating functions always have nonnegative coefficients.

Analytic Tools for This Paper

The generating functions we shall study in this paper always have a unique dominant singularity, which is therefore in R + by Pringsheim's theorem. For any fixed alphabet size k, the dominant singularity of each generating function will always be the same ρ k . Moreover, as they are all made of polynomials, quotients and square roots, their analysis have a lot of similarities. In particular, all generating functions satisfy one of the two conditions of the following proposition.

Proposition 1. Let f (z) be a function that is ∆-analytic at ρ ∈ R + .
1. If on the intersection of a neighborhood of ρ and its ∆-domain,

f (z) = a -b 1 -z/ρ + o( 1 -z/ρ), with a, b ∈ R, b = 0 then [z n ]f (z) ∼ b 2 √ π ρ -n n -3/2 .
2. If on the intersection of a neighborhood of ρ and its ∆-domain,

f (z) = a 1 -z/ρ + o 1 1 -z/ρ , with a ∈ R, a = 0 then [z n ]f (z) ∼ a √ π ρ -n n -1/2
. This proposition is a direct consequence of Theorem 1, using classical formulas for the asymptotic of the coefficients of z → √ 1 -z and z → (1 -z) -1/2 . If f (z) is a function which is ∆-analytic at ρ ∈ R + , we say that f satisfies the property Π 1 or Π 2 at ρ if it satisfies the first or second condition of Proposition 1 respectively.

The computations involved here can be technical, but can be done almost automatically (with the help of computer algebra software for the most complex ones). It is always straightforward to check that this functions satisfy the analytic conditions of Proposition 1. The value of a (and b) can also be computed, and will be some functions of the size of the alphabet. In the rest of the paper, due to the lack of space, most details of the computations will be omitted.

hal-00620388, version 1 30 Sep 2011 3 Generating Functions for Regular Expressions

In this section we apply the framework of analytic combinatorics to the classes of regular expressions we are studying. From now on, the alphabet considered is A = {a 1 , . . . , a k }, where k ≥ 1 is a positive integer.

General Regular Expressions

From Equation (1), one can use the symbolic method to obtain the following specification

R = ε + a 1 + • • • + a k + * | R + ∪ /\ R R + • /\ R R
And therefore, using the dictionary, one obtain the following equation for R(z), the generating function associated to R:

R(z) = (k + 1)z + zR(z) + 2zR 2 (z)
From which one can derive the following expression for R(z), using the fact that its Taylor coefficients are nonnegative:

R(z) = 1 -z -∆ k (z) 4z , with ∆ k (z) = 1 -2z -(7 + 8k)z 2
The unique dominant singularity of R(z)

is ρ k = 2 √ 2k+2-1 7+8k
, and around ρ k , one has the following expansion of R(z)

R(z) = 1 -ρ k 4ρ k - 1 4ρ k ∆ k (z) + o 1 - z ρ k 1 2 R(z) = √ 2k + 2 2 - 2(1 -ρ k ) 4ρ k 1 - z ρ k 1 2 + o 1 - z ρ k 1 2
therefore, using Proposition 1, one can obtain an asymptotic equivalent to the number of nonempty regular expressions.

Lemma 2. The number of elements of size n in R is asymptotically equivalent

to C k ρ -n k n -3/2 , with C k = √ 2(1-ρ k ) 8ρ k √
π . Note that if some generating function f (z) has a unique dominant singularity on ρ k where we can apply Proposition 1, and satisfies as z → ρ k :

f (z) = a - b 4ρ k ∆ k (z) + o( 1 -z/ρ k ) then [z n ]f (z) ∼ b [z n ]R(z)
. Therefore, for our computations, it is often more convenient to obtain developments in terms of

1 4ρ k ∆ k (z) instead of 1 -z/ρ k .
The techniques are of course the same, since they only differ by a multiplicative constant as z → ρ k .

Regular Expressions of Languages Containing ε

Denote by R ε and R ε the regular expressions whose associated languages respectively recognize and do not recognize the empty word. A specification of R ε is the following:

R ε = ε + * | R + ∪ /\ Rε R + ∪ /\ Rε Rε + • /\ Rε Rε (3)
From which one can obtain the following expression:

R ε (z) = z + zR(z) 1 -2zR(z)
The dominant singularity of R ε (z) is also ρ k and it satisfies Π 1 at ρ k :

R ε (z) = 2k + √ 2k + 2 4k + 2 - 1 -2k + 4k √ 2k + 2 (2k + 1) 2 ∆ k (z) 4ρ k + o 1 - z ρ k 1 2
Therefore, using Proposition 1 one can obtain an asymptotic equivalent to its coefficients:

[z n ]R ε (z) ∼ D k [z n ]R(z), with D k = 1 -2k + 4k √ 2k + 2 (2k + 1) 2 (4)
Note that, as a consequence, the ratio of regular expressions whose denoted language contains the empty word is asymptotically D k . For a two-letters alphabet, the value of D k is approximatively D 2 ≈ 0.664.

Main Result

This section is devoted to the proof of our main theorem:

Theorem 2. The average number of transitions of the Glushkov's automaton associated to a regular expression of size n, for the uniform distribution, is in Θ(n).

Lower Bound

First remark that if an expression R ∈ R contains m letters, then its Glushkov's automaton has m + 1 states. Moreover, since it is accessible by construction, it has at least m transitions. For R ∈ R, let (R) be the number of letters in R.

Let L(z) be the cost generating function of the number of letters in an element R of R:

L(z) = R∈R (R)z |R|
From Equation (1) and Lemma 1, we have

L(z) = kz + zL(z) + 2zL(z)R(z) + 2zL(z)R(z)
Hence, using the fact that 1 -z -4zR(z) = ∆ k (z):

L(z) = kz ∆ k (z)
Therefore, L(z) has a unique dominant singularity at ρ k and satisfy Π 2 at ρ k . By Proposition 1,

[z n ]L(z) ∼ kρ k 2π(1 -ρ k ) ρ -n k n -1/2
and the average number of letters in an element of size n of R is equivalent to

4kρ 2 k 1-ρ k n as n → ∞. For k = 2, an approximation of 4kρ 2 k
1-ρ k is 0.408. We conclude that in average, the number of transitions in the Glushkov's automaton of an element of size n of R is in Ω(n).

Outline of the Proof of the Upper Bound

In the following subsections we establish some results used to compute an upper bound for the average number of transitions in a Glushkov's automaton. As stated before, the size of the Glushkov's automaton associated to a nonempty regular expression R ∈ R is equal to the number of elements in F irst(R) plus the number of elements in Edges(R). In the next subsection we prove that in average, the size of F irst(R) tends towards a constant. For the remaining part, we actually compute an upper bound of the size of Edges(R), not its exact average cardinality. Define the function e : R -→ N by: Let E(z) and F (z) be the cost generating functions of e and |F irst(•)| respectively, and let P (z) be the following generating function

                   e(ε) = 0 e(a) = 0 ∀a ∈ A e * | R = e(R) + |Last(R)| • |F irst(R)| ∀R ∈ R e ∪ /\ R1 R2 = e(R 1 ) + e(R 2 ) ∀R 1 , R 2 ∈ R e • /\ R1 R2 = e(R 1 ) + e(R 2 ) + |Last(R 1 )| • |F irst(R 2 )| ∀R 1 , R 2 ∈ R (
P (z) = R∈R |F irst(R)| • |Last(R)|z |R|
Note that, by symmetry, F (z) is also the cost generating function of last, F (z) = R∈R last(R)z |R| . Using Equation [START_REF] Ilie | Constructing NFA s by optimal use of positions in regular expressions[END_REF] and Lemma 1, one has

E(z) = zE(z) + zP (z) + 2zR(z)E(z) + 2zR(z)E(z) + zF (z) 2

hal-00620388, version 1 -30 Sep 2011

As R(z) and R ε (z) are known, it is straightforward to obtain the expansion of F (z) near its dominant singularity ρ k and to check that it satisfies Π 1 at ρ k :

F (z) = E k -F k ∆ k (z) 4ρ k + o 1 - z ρ k 1 2 (8)
with

E k = 1 + √ 2k + 2 and F k = 12+6k+8 √ 2k+2 k
. Hence, using Proposition 1, one can prove the following proposition.

Proposition 2. For any fix integer k ≥ 1, the average size of first tends toward a constant

F k = 12+6k+8 √ 2k+2 k
, as n tends toward infinity:

[z n ]F (z) ∼ F k [z n ]R(z).
For k = 2, an approximation of F k is F 2 ≈ 21.8.

The Cost Generating Function F ε (z)

Similarly, one can use the specification of R ε of Equation ( 3) to compute F ε (z). We obtain

F ε (z) = zF (z) + 2zR ε (z)F (z) 1 -2zR(z) Once again, F ε (z) satisfies Π 1 at ρ k with F ε (z) = G k -H k ∆ k (z) 4ρ k + o( ∆ k (z)), with G k = 4k + 1 + √ 2k + 2 2k + 1
The expression of H k > 0 in terms of k can also be computed, but is not needed in the following.

The Cost Generating Function of the Product first × last

We analyze the average value of the product of first(R) and last(R), for a regular expression R ∈ R of size n. We consider the cost generating function P (z) of this product, and its restriction P ε (z) to R ε and P ε (z) = P (z) -P ε (z) to R ε :

P ε (z) = R∈Rε first(R) • last(R)z |R| ; P ε (z) = R∈Rε first(R) • last(R)z |R|
We use the following specification of R:

R = ε + a 1 + • • • + a k + * | R + ∪ /\ R R + • /\ Rε Rε + • /\ Rε Rε + • /\ Rε Rε + • /\ Rε Rε
The cost generating function associated to each term of the specification is computed separately. For instance, one has the following cost function for

• /\ Rε Rε : R1∈Rε R2∈Rε first • /\ R1 R2 last • /\ R1 R2 z 1+|R1|+|R2| = z R1∈Rε R2∈Rε (first(R 1 ) + first(R 2 )) last(R 2 )z |R1| z |R2| = z R1∈Rε R2∈Rε first(R 1 )last(R 2 )z |R1| z |R2| + zR ε (z)P ε (z) = zF ε (z)F ε (z) + zR ε (z)P ε (z)
Using the same techniques for the other parts of the expression, we obtain:

P (z) = kz + 3zF (z) 2 + zF ε (z) 2 1 -z -2zR(z) -2zR ε (z)
From which, using the previous results, we conclude that P (z) satisfies Π 1 at ρ k and that there exists some real numbers I k and J k such that, as z → ρ k ,

P (z) = I k -J k ∆ k (z) + o( ∆ k (z)) with I k = 38k 2 +77k+28+(14k 2 +45k+20) √ 2k+2 2k(k+1)
and J k > 0.

Concluding the Proof of Theorem 2

We can now analyze Equation [START_REF] Champarnaud | Computing the follow automaton of an expression[END_REF]. As both F (z) and P (z) satisfy Π 1 , so does zP (z) + zF (z) 2 , since the constant term of its development near ρ k is not zero. Hence E(z) satisfies Π 2 at ρ k and Proposition 1 can be applied:

[z n ]E(z) ∼ e k n [z n ]R(z)
The value of e k is not needed to prove the theorem, but is still an indication on a bound of the average number of transitions in a Glushkov's automaton: e k = 32k 4 + 204k 3 + 406k 2 + 306k + 72 + (80k 3 + 230k 2 + 193k + 52) √ 2k + 2 2k(k + 1)(2k + 1)(8k + 7) For k = 2, an approximation of e k is e 2 ≈ 6.77.

The quantity [z n ]E(z)/[z n ]R(z) is an upper bound of the average cardinality of Edges and the average cardinality of F irst is bounded by Proposition 2, therefore, by linearity of the average, the average number of transitions in a Glushkov's automaton is in O(n). This concludes the proof of Theorem 2.

hal-00620388, version 1 30 Sep 2011 5 Remarks

In this paper we used the specification of regular expressions that directly follows the inductive definition. One could try to use a more precise specification to prevent some useless patterns in regular expressions to appear, as was done for instance in [START_REF] Lee | Enumerating regular expressions and their languages[END_REF] for enumeration purposes. Depending on the chosen such rules, the analysis we conduct here could still be doable, but probably much more complicated. Especially if the specification is not context-free (see [START_REF] Fernández-Camacho | Algebraic simplification in computer algebra: An analysis of bottom-up algorithms[END_REF] for a related analysis). However, we believe that the result would be the same in much cases. Indeed, the proofs of Theorem 2 and Proposition 2 are based on the fact that for a non-negligible proportion of regular expressions, the denoted language does not recognize the empty word, and that the average number of concatenation operators is non-negligible. This must be true for most natural specifications.

Also note that we could have used bivariate generating functions instead of cost generating functions in this paper. The computations would have been the same here, but this approach should be useful if one want to go one step further, and try to obtain some informations not only about the average value, but also about the limit distribution.

The author is supported by the ANR (GAMMA -project BLAN07-2 195422).

2 .

 2 Transform the specification into a functional equation for the associated generating function.3. Analyze the dominant singularities of the generating function to obtain the needed asymptotics.

  u starts with the letter α} Last(R) = {α ∈ pos(R) | ∃u ∈ L( R), u ends with the letter α}

5 )

 5 Clearly e(R) is an upper bound of |Edges(R)|, since its definition is obtained from the one of Edges, Equation (2), and the inequality |X ∪ Y | ≤ |X| + |Y |.

hence

(1 -z -4zR(z))E(z) = zP (z) + zF (z) 2 and as 1 -z -4zR(z) = ∆ k (z), we finally obtain

At this point we need more informations about P (z) and

). They will be obtained in the next subsections.

The Cost Generating Function F (z)

For an element R ∈ R, let first(R) and last(R) denote respectively the cardinalities of the sets F irst(R) and Last(R). We analyze the average value of first(R), for a regular expression R ∈ R of size n. F (z) is the cost generating function of first, and we also consider its restrictions

For a given R ∈ R, the value of first(R) can be computed inductively as

We consider the following specification of R

This specification can be transformed into a functional equation on cost generating functions using Lemma 1 and Equation [START_REF] Flajolet | Analytic Combinatorics[END_REF]. For instance, the construction

All computations and simplifications done, we obtain:


D Corpet

J.-L Nicolas

Antagonistic Effect of Intestinal Bacteria from the Microflora of Holoxenic (Conventional) Piglets, Against Clostridium Perfringens in the Digestive Tract of Gnotoxenic Mice and Gnotoxenic Piglets

Antagonistic effect of piglet microflora against Clostridium perfringens was studied in germfree mice, to isolate bacterial strains responsible for this colonization resistance. The 1:100 dilution of the feces of a 2 day-old conventional piglet, given per os to germfree mice already harboring C. perfringens, led to the elimination of C. perfringens. From this piglet flora, 8 bacterial strains were selected, belonging to the genera Bacteroides, Clostridium, Eubacterium, Bifidobacterium, Lactobacillus and a strain belonging to the class of Mollicutes. When the 8 strains were given to germfree mice 3 days after C. perfringens inoculation, they led to rapid elimination of C. perfringens from feces. Sixteen other mixtures of 2 to 7 strains were similarly tested, but none was able to fully antagonize C. perfringens. When the 8 strains were given per os to germfree piglets after C. perfringens inoculation, they led to the rapid elimination of C. perfringens from pig feces, and to a quick recovery from diarrhea. This study led to the identification of a simplified fraction of gut microflora, able to exert a barrier effect against C. perfringens comparable to the entire flora of the piglet. This study suggests that gnotoxenic mice can be a suitable model for simplifying the flora responsible for a given effect in another host, animal or human.

Introduction

The barrier effect exerted by gastrointestinal microflora, is one of the basic mechanisms protecting the host against enteric infections. Bacterial strains responsible for a barrier effect against Shigella flexneri [START_REF] Ducluzeau | Antagonistic effect of extremely oxygen sensitive clostridia from the microflora of conventional mice, and of E. coli against Shigella flexneri in the digestive tract of gnotobiotic mice[END_REF] and Escherichia coli [START_REF] Syed | Efficiency of various intestinal bacteria in assuming normal functions of enteric flora after association with germ-free mice[END_REF] in the mouse, have already been isolated. But little work has been done on the antagonistic effect exerted by the microflora of animals other than rodents.

The purpose of this study was to determine whether there was an antagonistic effect of the microflora of the holoxenic piglet against Clostridium perfringens, and to isolate bacterial strains responsible for this effect, using gnotoxenic mice. C. perfringens bas been recognized as the cause of enteritis in young pigs [START_REF] Bergeland | Pathogenesis and immunity of C. perfringens type C enteritis in swine[END_REF], and a study on the number of C. perfringens in suckling piglets, has shown a great variability in this number [START_REF] Decuypre | Stuy of the gastrointestinal microflora of suckling piglets and early weaned piglets reared using different feeding systems[END_REF]. So, the barrier effect against C. perfringens in piglet must be quite variable.

Materials and Methods

Maintenance and Inoculation of Mice

Adult balb mice were fed a commercial diet (UAR) or a solid milk replacer for piglet, sterilized by irradiation (4 Mrad). For short term studies, the mice were maintained in glass jars as previously described (4). For long term studies, the mice were maintained in plastic Trexler type isolators. The mice were inoculated by injecting 2 ml of the appropriate bacterial culture, containing 10 8 viable cells, or 2 ml of a 1:100 dilution of feces directly into the individual drinking water tubes, after each animal had been deprived of water for one day.

Obtaining, Maintenance and Inoculation of Piglets

Axenic (germfree) newborn piglets were obtained by decontamination immediately after birth as previously described [START_REF] Ducluzeau | Immediate postnatal decontamination as a mean of obtaining axenic animals and human infants[END_REF], and maintained in plastic Trexler type isolators. Absence of bacteria in the piglet's digestive tract was controlled for 4 days after birth [START_REF] Ducluzeau | Immediate postnatal decontamination as a mean of obtaining axenic animals and human infants[END_REF]. The baby pigs were fed concentrated cow milk ("Gloria" milk), diluted with autoclaved water, and admixed with a vitamin mixture. The piglets were inoculated per os, by giving them 10 ml of bacterial culture, or 10 ml of a 1:100 dilution of feces.

Fecal Sampling

In the short term experiments on mice, freshly passed feces were collected from individual animal at the end of the experiments, 1 week after introduction of the last inoculum. In the case of mice housed in the same cage in an isolator for long term experiments, pooled, freshly passed feces were used for the enumeration of bacteria. Each pooled sample contained one fecal pellet from every animal in the group. In the case of piglets, freshly passed feces were collected from individual animals. All quantitative bacterial counts were made immediately after sample collection.

Bacterial Strains, Culture Media, and Enumerations

The strain of C. perfringens used to initiate these experiments was an asporogenous mutant of a strain previously described (3) and was cultured in the medium B' containing 0,2% agar [START_REF] Sacquet | Etude comparée de la microflore de l'estomac, de l'intestin grêle et du caecum du rat holoxénique et de ses modifications, á la suite de diverses interventions chirurgicales : anse aveugle jéjunale, déviations biliaires[END_REF]. A second strain of C. perfringens had originally been isolated from the digestive tract of a holoxenic piglet, and a third one (strain C.p. A. 78) had been obtained from the Institut Pasteur (Paris). C. perfringens was enumerated in GCN medium containing per liter : enzymatic casein hydrolysate (ATBC) : 35 g, agar (Touzart and Matignon) : 10 g. The pH of the medium was adjusted to 6.5, and 0.013% Neomycin (NBC) were extemporarily added.

The strains of Bacteroides, Clostridium, Eubacterium, Bifidobacterium, Lactobacillus, and a strain belonging to the class of Mollicutes, were originally isolated by us from the feces of a holoxenic (conventional) 48 hour-old piglet.

Enumeration of the two Bacteroides strains and the two Clostridium strains in the feces, was made in medium B', previously described [START_REF] Sacquet | Etude comparée de la microflore de l'estomac, de l'intestin grêle et du caecum du rat holoxénique et de ses modifications, á la suite de diverses interventions chirurgicales : anse aveugle jéjunale, déviations biliaires[END_REF]. For enumeration of the Mollicutes strain, the same medium was used after addition of 0.0075% Bacitracin (NBC). Eubacterium was counted after addition of 1 % of glucose and 0.09% of Streptomycin (Specia) to medium B'. For enumeration of Bifidobacterium and Lactobacillus, medium B' was used after addition of 1 % glucose, and after five minutes contact between the dilution and 0,2 ml of a 1,5% sodium azide solution, as previously described [START_REF] Raibaud | La microflore du tube digestif du rat. I. Techniques d'étude et milieux de culture proposés[END_REF]. For all the strains, serial 10-fold dilutions were poured into these selective media, placed in 8 by 400 mm tubes [START_REF] Raibaud | La microflore du tube digestif du rat. I. Techniques d'étude et milieux de culture proposés[END_REF], and incubated at 37 ° C for 18 hours in the case of C. perfringens, and for 7 days in the case of the other strains.

Results

Barrier Effect against C. perfringens Exerted in Mice by the Conventional Piglet Flora

C. perfringens inoculated into axenic mice, became rapidly established in the digestive tract of the animals, and stayed then at a high level (Fig. 1). The 1:100 dilution of the feces of a 48 hours-old holoxenic (conventional) piglet, inoculated into gnotoxenic mice, monoassociated with C. perfringens led to a drastic decrease in the number of C. perfringens. This number reached within 5 days the level below 100 viable cells by gram of wet feces.

Simplification of the Microflora Exerting the Barrier Effect

86 bacterial strains were isolated from the dominant microflora of the feces of these mice, on the different selective media.

Among these strains, 8 were selected, easily differentiated by their morphology, and their ability to grow on various selective media. These strains were belonging to the genera Bacteroides (strains B1 and B2), Clostridium (strains En and P1), Eubacterium (Eu), Bifidobacterium (Bf), Lactobacillus (La) and a strain belonging to the class of Mollicutes (Mo). This last strain, strictly anaerobic but not Extremely Oxygen Sensitive, showed a mycoplasm morphology and no wall in electron microscopy, typical incrusted colony on Petri dishes, but was cholesterol independent and did not pass through a Millipore membrane of 0,45 µm. These 8 strains, together associated with axenic (germfree) mice were found to decrease drastically the number of C. perfringens in the feces of animals when C. perfringens was given per os to the gnotoxenic mice.

The barrier effect was also achieved when the 8 strains were inoculated into monoxenic mice, already monoassociated with C. perfringens (Fig. 1). Two other strains of C. perfringens were eliminated in the same way by this simplified flora. When the mice were fed the milk replacer, the barrier effect exerted by the 8 strains still remained when C. perfringens was inoculated after the 8 strains.

Partial Barrier Effect exerted by less than 8 Strains

When only one of the 8 strains was associated with C. perfringens in axenic (germfree) mice no one was able alone to eliminate C. perfringens from the digestive tract of mice. But when the strains B2 and En were inoculated 6 days and 13 days, respectively, after C. perfringens, they led to a partial decrease in the number of C. perfringens (Fig. 2). The same result was obtained when the order of inoculation of strains B 2 and En was inversed. The mixtures of more than 2 and less than 8 strains tested in mice housed in jars, did not lead to a better elimination of C. perfringens (Table 1). Table 1: Number of C. perfringens in the feces of gnotoxenic mice housed in jars, inoculated with various mixtures of strains, chosen among the 8 strains. In the upper part of the table, the abbreviations designate the strains present in each mixture; figures on the last horizontal line are the log 10 of the number of C. perfringens.

Barrier Effect of the Simplified Flora in Gnotoxenic Piglets

C. perfringens inoculated into an axenic piglet became rapidly established in the digestive tract of the animal, at the level of 10 8 bacteria/g fresh feces and induced diarrhea in the pig. When an axenic piglet was inoculated with a 1:100 dilution of the feces of the octoxenic mice (harboring the 8 strains), and 24 hours later with C. perfringens, there was a rapid decrease in the number of C. perfringens (Fig. 3). Lactobacillus, inoculated into a piglet monoassociated since 3 days with C. perfringens, was unable to eliminate C. perfringens, or to decrease the pH of the feces. But when the 8 strains were added 3 days later, they led to a rapid decease in the number of C. perfringens, and to a quick recovery from diarrhea (data not shown).

Discussion

The experiment described above led to the identification of a simplified, defined fraction of holoxenic (conventional) microflora, able to exert a barrier effect with regard to C. perfringens comparable to the entire flora of the piglet. The ecological barrier effect is likely to be exerted by the association of a few different strains, and not by a single one, as pointed out by different authors [START_REF] Ducluzeau | Antagonistic effect of extremely oxygen sensitive clostridia from the microflora of conventional mice, and of E. coli against Shigella flexneri in the digestive tract of gnotobiotic mice[END_REF][START_REF] Syed | Efficiency of various intestinal bacteria in assuming normal functions of enteric flora after association with germ-free mice[END_REF]. It is unlikely that all the 8 bacterial strains used in this experiment are necessary for this effect, and it would be interesting to find out the minimum number of strains exerting the same effect. This would allow further studies on the mechanisms involved in such a barrier effect. From another point of view, it would be easier to detect the presence of the bacteria responsible for the barrier effect in all the holoxenic piglets, and on the basis of this to try to understand why the barrier effect is not present in each animal.

Generally speaking, it would be very interesting to maintain all the potential pathogenic bacteria at a low level in the digestive tract of man and animals. But such a control requires intensive further studies to determine which are the bacteria involved in the different barrier effects, and in which conditions they eliminate the pathogens. The data presented here pro-vide the necessary tools for such studies: they show that the bacteria involved in the control process can be isolated in pure culture, and can be reassociated with axenic once to test the barrier effect. When this effect is obtained with the minimal flora, the strains can be inoculated into axenic piglets and exert the same barrier effect. Thus, gnotoxenic mice seem to be a suitable model for simplifying the flora responsible for a given effect in another host (man or animal).

Fig. l :

 l Fig. l: Kinetics of the establishment of C. perfringens in axenic mice, and of the elimination of C. perfringens when the 8 strains are inoculated into the monoxenic mice. Symbols: (Black square) C. perfringens, (-----) level below which the bacterial strains are considered as absent; (Arrow) day of inoculation of (C) C. perfringens and (8S) the 8 strains.

Fig. 2 :

 2 Fig. 2: Kinetics of the decrease in number of C. perfringens in gnotoxenic mice when Bacteroides (B2) and Clostridium (En) are successively inoculated, and elimination of C. perfringens when the 8 strains are added. Symbols: See Fig. 1.

Fig. 3 :

 3 Fig. 3: Kinetics of the elimination of C. perfringens in a gnotoxenic piglet previously inoculated with the 8 strains. Symbols: See Fig. 1.