Laurent O Martinez
email: laurent.martinez@inserm.fr

Cécile Ingueneau

Annelise Genoux

Is it time to reconcile HDL with cardiovascular diseases and beyond? An update on a paradigm shift

According to numerous epidemiological studies, low plasma levels of high-density lipoprotein cholesterol (HDL-C) are independently associated with an increased risk of atherosclerotic cardiovascular disease (ASCVD). For instance, in patients with acute coronary syndrome (ACS), low HDL-C levels are associated with an increase in the number of recurrent cardiovascular events [START_REF] Nakazawa | Lower levels of high-density lipoprotein cholesterol are associated with increased cardiovascular events in patients with acute coronary syndrome[END_REF]. In addition, low plasma HDL-C levels also correlate with an increased risk of developing type 2 diabetes mellitus (T2DM), liver diseases, and dementia [2,3*,4]. However, although elevated HDL-C levels could be expected to be beneficial for health, randomized controlled trials of agents that increase HDL-C levels, such as cholesteryl ester transfer protein inhibitors (CETPi) and reconstituted HDL (rHDL), have failed to reveal a beneficial effect on cardiovascular disease outcomes [5,6*,7].

Moreover, Mendelian randomization analyses have reported that some genetic variants associated with elevated HDL-C levels are not associated with a lower risk of ASCVD, T2DM, or Alzheimer's disease [START_REF] Frikke-Schmidt | HDL cholesterol and apolipoprotein A-I concentrations and risk of atherosclerotic cardiovascular disease: Human genetics to unravel causality[END_REF][START_REF] Karjalainen | Apolipoprotein A-I concentrations and risk of coronary artery disease: A Mendelian randomization study[END_REF][START_REF] Haase | HDL cholesterol and risk of type 2 diabetes: A mendelian randomization study[END_REF][START_REF] Østergaard | Associations between Potentially Modifiable Risk Factors and Alzheimer Disease: A Mendelian Randomization Study[END_REF][START_REF] Proitsi | Genetic Predisposition to Increased Blood Cholesterol and Triglyceride Lipid Levels and Risk of Alzheimer Disease: A Mendelian Randomization Analysis[END_REF]. However, the conclusions of these studies regarding the absence of a causal link between HDL-C levels and disease risk are questionable because the analyses did not take into account i) changes in HDL composition and functions in disease, ii) the complexity of HDL metabolism, as they excluded important genes from their analyses that regulate the levels of lipoproteins other than HDL-C [START_REF] Geller | Genetic and secondary causes of severe HDL deficiency and cardiovascular disease[END_REF].

These discordant results have led to the notion that beneficial functions of HDL particles are not determined solely by the cholesterol moiety in HDL (i.e., HDL-C). This paradigm shift has led to renewed interest in HDL research, particularly in terms of the identification of biomarkers that reflect causal structure-function-disease relationships of HDL, with the ultimate goal of developing novel therapeutic approaches based on restoration/activation of HDL functions rather than increasing HDL-C levels.

HDL particles exert pleiotropic atheroprotective activities, including cholesterol efflux from peripheral tissues to the liver for excretion by reverse cholesterol transport (RCT), in addition to exerting anti-infectious, antioxidative, anti-inflammatory, antithrombotic, anti-apoptotic, vasodilatory, and antidiabetic properties [START_REF] Kajani | Unravelling hdl-looking beyond the cholesterol surface to the quality within[END_REF]. These pleiotropic beneficial activities rely on the fact that the plasma HDL fraction consists of heterogeneous and highly dynamic particles that contain hundreds of different quantitatively minor proteins and lipid species, most of which are thought to be biologically active [6*,15].

Recently, analyses of data from large epidemiological population studies have revealed that the relationship between HDL-C levels and disease risks is nonlinear, with both extremely low and extremely high HDL-C levels associated with increased risks of ASCVD and infectious diseases [6*,16,17,18]. This observation could account for the negative results of trials of entities that enhance HDL-C levels. Further studies of this parabolic relationship have revealed that extremely high HDL-C levels (> 100 mg/dL) are associated with endothelial dysfunction [19,20*], impaired glucose metabolism [START_REF] Nakajima | Impaired Glucose Metabolism in People with Extremely Elevated High-Density Lipoprotein Cholesterol and Low Alcohol Consumption: Results of the Kanagawa Investigation of Total Checkup Data from the National Database-3 (KITCHEN-3)[END_REF] and an impaired capacity of HDL to acquire free cholesterol from triglyceride-rich lipoprotein lipolysis [START_REF] Feng | Free cholesterol transfer to high-density lipoprotein (HDL) upon triglyceride lipolysis underlies the U-shape relationship between HDL-cholesterol and cardiovascular disease[END_REF]. Alternatively, extremely high HDL-C levels may be attributed to particular lifestyles such as excessive alcohol consumption, or genomic factors such as loss-of-function mutations in key HDL metabolism-regulating genes [START_REF] Zanoni | Rare variant in scavenger receptor BI raises HDL cholesterol and increases risk of coronary heart disease[END_REF]. Thus, the identification of reliable markers for HDL functions requires in-depth knowledge of HDL complexity.

Under pathological conditions, quantitative and qualitative changes in the composition of HDL particles can compromise their beneficial properties for health [24**]. Interestingly, the distinct profile in the changes in HDL structure and lipid and protein compositions between coronary heart disease (CHD) and T2DM patients has led to the identification of three independent functional HDL components, namely the polyunsaturated sphingomyelin SM 42:3 and glycosylphosphatidylinositolphospholipase D1 (GPLD1), which inhibit endothelial cell apoptosis, and apolipoprotein F (apoF), which promotes maximal respiration of brown adipocytes [24**]. In terms of hepatic and cognitive diseases, apoA-I levels are negatively associated with the risks of chronic liver failure and dementia [3*,4]. Moreover, HDL particles that contain apoE but not apoJ may predict cognitive decline, independently of the presence of the apoE ε4 allele [START_REF] Koch | Apolipoproteins and Alzheimer's pathophysiology[END_REF]. Among the other emerging HDL-related biomarkers, ATPase inhibitory factor 1 (IF1) has been proposed to reflect hepatic HDL uptake (one of the last steps of RCT). IF1 has been reported to be independently and negatively associated with the long-term prognosis in CHD patients [START_REF] Martinez | Serum inhibitory factor 1, high-density lipoprotein and cardiovascular diseases[END_REF][START_REF] Genoux | Serum levels of mitochondrial inhibitory factor 1 are independently associated with long-term prognosis in coronary artery disease: The GENES Study[END_REF]. Importantly, a rapid and inexpensive high-throughput spectrometry-based assay that is amenable to clinical practice and that allows multiplexing in the quantification of circulating apolipoproteins and IF1 was recently developed and could serve to further validate a panel of these emerging HDL-related biomarkers [28,29*].

Studies of HDL-related biomarkers often comprise assessment of the Cholesterol Efflux Capacity (CEC) [30**]. A meta-analysis recently concluded that the CEC is negatively associated with cardiovascular morbidity and mortality [START_REF] Soria-Florido | High density lipoprotein functionality and cardiovascular events and mortality: A systematic review and meta-analysis[END_REF]. However, as measuring CEC is time-consuming and it has not yet been standardized, there will need to be substantial technical progress before this biomarker will be used in routine clinical practice. A novel score was recently developed, called the HDL apolipoproteomic score (pCAD). This score, which correlates well with the CEC, is based on mass spectrometry quantification of specific HDL-associated apolipoproteins [32**]. Although the pCAD score warrants further clinical evaluation, it has been reported to be independently associated with cardiovascular mortality in CHD patients. Another clinically advanced HDL-related biomarker is based on measurement of the HDL particle number (HDL-P) by nuclear magnetic resonance spectroscopy.

HDL-P has been shown to have a greater prognostic value than HDL-C and apoA-I in coronary patients [START_REF] Duparc | Serum level of HDL particles are independently associated with long-term prognosis in patients with coronary artery disease: The GENES study[END_REF], and it may be a surrogate marker of HDL anti-oxidative activity [30**].

Although further studies are needed to validate these biomarkers as proxies of the many protective properties of HDL, their use, either alone or as part of a panel, should permit a biologicaland clinical-based reassessment of the optimal therapeutic strategy for targeting HDL. Thus, the use of HDL as therapeutics is contingent on further research, as indicated by the very limited number of current active clinical trials evaluating HDL-based therapies. For instance, of the three formulations of rHDL that have been developed for intravenous infusion, only a randomized controlled trial of the compound CSL-112 is still ongoing (expected completion in 2022), while the two other entities (MDCO-216 and CER-001) did not result in a reduction of atherosclerotic plaque in patients with acute coronary syndrome compared to placebo [30**]. rHDL formulations, which have exhibited disappointing outcomes to date, are mainly composed of poorly lipidated apoA-I and they are expected to exert a beneficial effect by increasing the CEC. However, it should be kept in mind that oxidative stress and inflammatory conditions, which occur in many chronic diseases, may convert HDL into dysfunctional particles. In particular, myeloperoxidase is enriched in atherosclerotic lesions and it promotes oxidative modification of apoA-I at residue Trp72, which is essential for the cholesterol efflux activity of apoA-I [START_REF] Huang | An abundant dysfunctional apolipoprotein A1 in human atheroma[END_REF]. The control of the oxidative stress and inflammation status of patients should thus be evaluated to ensure that injected rHDL remain sufficiently functional to exert their intended beneficial effects. Alternatively, myeloperoxidase inhibitors could be used simultaneously to prevent lipoprotein oxidation [START_REF] Premkumar | Synthetic Guaiacol Derivatives as Promising Myeloperoxidase Inhibitors Targeting Atherosclerotic Cardiovascular Disease[END_REF]. Additionally, a short apoA-I-derived peptide was recently shown to improve glucose metabolism, promote cholesterol efflux, and reduce atherosclerosis in pre-clinical models, thus positioning this peptide as a promising drug candidate to reduce the risk of CVD in individuals with insulin resistance [START_REF] Edmunds | ApoAI-derived peptide increases glucose tolerance and prevents formation of atherosclerosis in mice[END_REF].


Duality and equational theory of regular languages

Mai Gehrke * Serge Grigorieff † Jean-Éric Pin † ‡

To appear in ICALP 2008

This paper presents a new result in the equational theory of regular languages, which emerged from lively discussions between the authors about Stone and Priestley duality. Let us call lattice of languages a class of regular languages closed under finite intersection and finite union. The main results of this paper (Theorems 5.2 and 6.1) can be summarized in a nutshell as follows:

A set of regular languages is a lattice of languages if and only if it can be defined by a set of profinite equations.

The product on profinite words is the dual of the residuation operations on regular languages.

In their more general form, our equations are of the form u → v, where u and v are profinite words. The first result not only subsumes Eilenberg-Reiterman's theory of varieties and their subsequent extensions, but it shows for instance that any class of regular languages defined by a fragment of logic closed under conjunctions and disjunctions (first order, monadic second order, temporal, etc.) admits an equational description. In particular, the celebrated McNaughton-Schützenberger characterisation of first order definable languages by the aperiodicity condition x ω = x ω+1 , far from being an isolated statement, now appears as an elegant instance of a very general result.

How is this equational theory related to duality? The connection between profinite words and Stone spaces was already discovered by Almeida [START_REF] Almeida | Residually finite congruences and quasi-regular subsets in uniform algebras[END_REF], [START_REF] Almeida | Finite semigroups and universal algebra[END_REF]Theorem 3.6.1], but Pippenger [START_REF] Pippenger | Regular languages and Stone duality[END_REF] was the first to formulate it in terms of Stone duality. Almeida (implicitely) and Pippenger (explicitely) both observed that the Boolean algebra of regular languages over A * is dual to the Stone space A * , the set of profinite words. Pippenger actually came very close to our first result, since he mentioned that this duality extends to a one-to-one correspondence between Boolean algebras of regular languages and quotients of A * . Our first result is the full-fledged consequence of the similar one-to-one correspondence for all lattices of languages provided by Priestley duality.

However, this link to duality theory is in fact much stronger and encompasses not only the underlying lattices and spaces involved but also the algebraic operations including the product of profinite words. That is the content of our second result. It means that the profinite semigroup structure, in its entirety, is a dual structure and thus the entire theory is a special case of duality theory. In particular, the deep and highly evolved theory of duality and relational semantics from modal logic applies, and, in the other direction, the wealth of knowledge and examples from semigroup theory enriches our understanding of general duality theory. In this sense, the results described here are just the tip of an iceberg yet to be explored.

Due to the lack of space, most of the proofs are omitted.

Historical background

Our starting point was Eilenberg's variety theorem [START_REF] Eilenberg | Automata, languages, and machines[END_REF]. Recall that a variety of languages is a class of regular languages closed under Boolean operations, inverses of morphisms and left and right quotients by words. Eilenberg's theorem states that varieties of languages are in one-to-one correspondence with varieties of finite monoids, that is, classes of finite monoids closed under taking submonoids, quotient monoids and finite direct products. The notion of a variety of finite monoids is similar to that of variety of monoids introduced by Birkhoff: a variety of monoids is a class of monoids closed under taking submonoids, quotient monoids and direct products. Birkhoff proved in [START_REF] Birkhoff | On the structure of abstract algebras[END_REF] that his varieties can be characterized by sets of identities: for instance the identity xy = yx characterizes the variety of commutative monoids. Almost fifty years later, Reiterman [START_REF] Reiterman | The Birkhoff theorem for finite algebras[END_REF] extended Birkhoff's theorem to varieties of finite monoids: any variety of finite monoids can be characterized by a set of profinite identities. A profinite identity is an identity between two profinite words. The precise definition of profinite words will be given in Section 2, but they can be viewed as limits of sequences of words for a certain metric, the profinite metric. For instance, one can show that the sequence x n! converges to a profinite word denoted by x ω and the variety of finite aperiodic monoids can be defined by the identity x ω = x ω+1 .

Eilenberg's and Reiterman's theorems have been extended several times over the last twenty years by relaxing the definition of a variety of languages. In [START_REF] Pin | A variety theorem without complementation, Russian Mathematics[END_REF], the third author considered positive varieties, for which the closure under complement is not required and showed they correspond to varieties of finite ordered monoids. The counterpart of Reiterman's theorem, obtained by Pin-Weil [START_REF] Pin | A Reiterman theorem for pseudovarieties of finite first-order structures[END_REF], makes use of identities of the form u v, where u and v are profinite words.

Pippenger [START_REF] Pippenger | Regular languages and Stone duality[END_REF] proposed to relax another condition by introducing strains of languages, which share the same properties as varieties of languages except for the closure under quotients by words, which is not required. Finally, Straubing [START_REF] Straubing | On logical descriptions of regular languages[END_REF] and independently, Esik [START_REF] Ésik | Extended temporal logic on finite words and wreath products of monoids with distinguished generators[END_REF], relaxed the closure under inverses of morphisms. Esik just required the closure under inverses of length-preserving morphisms. Straubing considered a class C of morphisms between free monoids containing the length-preserving morphisms and closed under composition and called Cvariety a class of regular languages closed under Boolean operations, quotients and inverses of morphisms from the class C. The counterpart of Reiterman's theorem for this case was given by Kunc [START_REF] Kunc | Equational description of pseudovarieties of homomorphisms[END_REF] (see also [START_REF] Pin | Some results on C-varieties[END_REF]).

Profinite topology

In this paper, A denotes a finite alphabet. A morphism ϕ : A * → M separates two words u and v of A * if ϕ(u) = ϕ(v). By extension, we say that a monoid M separates two words if there is a morphism from A * onto M that separates them. One can show that two distinct words can always be separated by a finite monoid. Given two words u, v ∈ A * , we set

r(u, v) = min {|M | | M is a monoid that separates u and v} d(u, v) = 2 -r(u,v)
with the usual conventions min ∅ = +∞ and 2 -∞ = 0. One can show that d is an ultrametric, that is, satisfies the following properties, for all u, v, w ∈ A * , (1)

d(u, v) = 0 if and only if u = v, (2) d(u, v) = d(v, u), ( 3
) d(u, w) max{d(u, v), d(v, w)}. Moreover, the relations d(uv, u ′ v ′ ) max{d(u, u ′ ), d(v, v ′ )} hold for all u, u ′ , v, v ′ ∈ A * ,
so that the concatenation product on A * is uniformly continuous.

Thus (A * , d) is a metric space. Its completion, denoted by A * , is called the free profinite monoid on A and its elements are called profinite words.

We now briefly review the main properties of A * . The reader is referred to [START_REF] Weil | Profinite methods in semigroup theory[END_REF][START_REF] Almeida | Profinite semigroups and applications[END_REF] for more details. First, A * is compact. Second, the topology defined by d is the profinite topology, that is, the least topology which makes continuous every morphism from A * onto a finite monoid (considered as a discrete metric space). It follows that every morphism ϕ from A * onto a finite monoid F extends uniquely to a (uniformly) continuous morphism φ : A * → F . Thirdly, since the product on A * is uniformly continuous, it can be extended in a unique way to a uniformly continuous product on A * . This product makes A * a monoid.

Recall that a set is clopen if it is both open and closed. There is a strong connection between clopen sets of A * and regular languages of A * . Indeed, a language L is regular if and only if L is clopen in A * and L = L ∩ A * [START_REF] Almeida | Profinite semigroups and applications[END_REF]. The languages of the form L, where L is a regular language, actually form a basis for the topology and hence A * is zero-dimensional. It is also totally disconnected since its connected components are singletons.

What about sequences? First, every profinite word is the limit of some converging sequence of words. Next, a sequence of profinite words (u n ) n 0 is converging to a profinite word u if and only if, for every morphism ϕ from A * onto a finite monoid, φ(u n ) is ultimately equal to φ(u).

For instance, if u is a word (or even a profinite word), one can prove that the sequence u n! is converging. Its limit is denoted by u ω for the following reason: if ϕ is a morphism from A * onto a finite monoid M , the sequence φ(u) n! is ultimately equal to the unique idempotent power of φ(u), which is traditionally denoted by φ(u) ω in semigroup theory. Thus the notation u ω is justified by the formula φ(u ω ) = φ(u) ω .

The closure in A * of a regular language of A * can be characterized as follows.

Proposition 2.1 Let L be a regular language of A * and let u ∈ A * . The following conditions are equivalent:

(1) u ∈ L, (2)
φ(u) ∈ ϕ(L), for all morphisms ϕ from A * onto a finite monoid, (3) φ(u) ∈ ϕ(L), for some morphism ϕ from A * onto a finite monoid that recognizes L, (4) η(u) ∈ η(L), where η is the syntactic morphism of L.

Duality for distributive lattices

In Stone duality, the dual space of a bounded distributive lattice D is based on the set S D of prime filters of D. As identified already by Birkhoff, there is a lattice embedding e of D into P(S D ), defined by: e(d) is the set of prime filters containing d.

A description of the range of e, both for Boolean algebras and then for distributive lattices was first provided by Stone [START_REF] Stone | The theory of representations for Boolean algebras[END_REF][START_REF] Stone | Applications of the theory of Boolean rings to general topology[END_REF]. He showed that if one generates a topology on the space of prime filters with the sets in the image of the embedding e, then the resulting space is, in the Boolean case, a compact 0-dimensional space, and in the distributive lattice case a spectral space, i.e. a compact (not necessarily Hausdorff), sober space with a ring of compact-open sets as a basis. An answer in complete lattice theoretic terms is the result by Jónsson and Tarski on canonical extensions. This is the most advantageous point of view when considering additional structure on lattices and spaces such as the semigroup operation.

For distributive lattices, Priestley [START_REF] Priestley | Representation of distributive lattices by means of ordered Stone spaces[END_REF] gave a slightly different topological characterization of the range of e than Stone. If one generates a topology τ , not just with the sets in the range of e, but also with their complements, one obtains the dual space of the free Boolean extension of the lattice and, crucially, one may reconstruct the original lattice if one remembers, in addition to the dual space of the free Boolean extension of the lattice, also the inclusion order on the space of prime filters. Thus in Priestley duality the dual of a distributive lattice is the ordered topological space (S D , ⊆, τ ). It is characterized by the property that it is compact and totally order disconnected. An ordered topological space is totally order disconnected provided the points of the space are separated by the upwards saturated clopen subsets. This is the duality we will use here.

One of the most powerful facts about dualities is that we get a complete correspondence between subobjects on one side and quotients on the other. Here we are interested in sublattices of regular languages, and these will of course correspond, under Priestley duality, to Priestley space quotients or equivalently, certain compatible preorders on the dual space of the lattice of all regular languages. Working out this correspondence dates back to work by M. E. Adams [START_REF] Adams | The Frattini sublattice of a distributive lattice[END_REF]. If D is a subalgebra of B, we obtain a dual quotient S B ։ S D by mapping a prime filter p of B to p ∩ D. The topological condition that is needed is that the quotient is a continuous (and, in the DL case, order preserving) map. An equivalence relation (preorder for DL subalgebras) on the space S B corresponds to a subalgebra provided the clopen subsets that are saturated with respect to the equivalence relation (preorder for DL subalgebras) separate the equivalence classes (of the equivalence relation corresponding to the preorder in the DL case).

Duality applied to Reg(A * )

The proof that the dual space of Reg(A * ) is none other than the space A * of profinite words can be found in Pippenger's paper [START_REF] Pippenger | Regular languages and Stone duality[END_REF]. It relies on two facts. First, given a prime filter p of Reg(A * ), there is a unique profinite word u such that, for every morphism from A * onto a finite monoid, ϕ(u) is the unique element m of M such that ϕ -1 (m) ∈ p. In the opposite direction, if u is a profinite word, the set

p u = {L ∈ Reg(A * ) | ϕ -1 ( φ(u)) ⊆ L for some morphism ϕ from A * onto a finite monoid } (1)
is a prime filter of Reg(A * ).

Theorem 4.1 (See [START_REF] Pippenger | Regular languages and Stone duality[END_REF]) The topological space underlying the profinite completion A * is equal to the dual space of the Boolean algebra Reg(A * ). Furthermore, the canonical embedding is given by the topologial closure: e(L) = L.

Equational characterization of lattices

Formally, a profinite equation is a pair (u, v) of profinite words of A * . We also use the term explicit equation when both u and v are words of A * . We say that a regular language L of A * satisfies the profinite equation

u → v (or v ← u) if the condition u ∈ L implies v ∈ L. Proposition 2.
1 immediately gives some equivalent definitions:

Corollary 5.1 Let L be a regular language of A * , let η be its syntactic morphism and let ϕ be any morphism onto a finite monoid recognizing L. The following conditions are equivalent:

(1) L satisfies the equation u → v,

(u) ∈ η(L) implies η(v) ∈ η(L), (2) η
(u) ∈ ϕ(L) implies φ(v) ∈ ϕ(L). (3) φ
Given a set E of equations of the form u → v, the set of all regular languages of A * satisfying all the equations of E is called the set of languages defined by E.

It is not hard to see that the set of languages defined by a set E of equations is a lattice. Our first result states that the converse is true as well.

Theorem 5.2 A set of regular languages of A * is a lattice of languages if and only if it can be defined by a set of equations of the form u → v, where u, v ∈ A * .

Proof. The proof is an instantiation of the duality between sublattices of Reg(A * ) and preorders on its dual space A * . Given a lattice D of regular languages, we get dually a quotient map q D : A * ։ S D given by p u → p u ∩ D, where p u is defined by Formula (1). Equivalently, we may describe this quotient map by the preorder Q D on A * given by u Q D v if and only if q D (p u ) ⊆ q D (p v ). But this latter condition is equivalent to requiring that, for all L ∈ D, u ∈ L implies v ∈ L. That is, in our terminology, the preorder on A * determining the quotient dual to D is exactly the equational theory of D:

Q D = {(u, v) | for all L ∈ D (L satisfies u → v)}.
On the other hand, in the duality, given a preorder Q on A * giving rise to a Priestley quotient A * /Q, the corresponding lattice is the set of all L ∈ Reg(A * ) so that their representation L is saturated with respect to the preorder. That is,

u ∈ L implies v ∈ L for all (u, v) ∈ Q. But,

Duality for quotienting operations

As announced in the introduction, our second main result is that the product on A * itself is dual to operations on Reg(A * ). The pertinent operations are the residuals of the product of languages, \ and /, defined, for all L, M, N ∈ Reg(A * ), by the conditions

LM ⊆ N ⇐⇒ M ⊆ L\N ⇐⇒ L ⊆ N/M.
More explicitely, the right and left residuals of N by M are given by:

M \N = {u ∈ A * | M u ⊆ N } = {u ∈ A * | for all v ∈ M , vu ∈ N } N/M = {u ∈ A * | uM ⊆ N } = {u ∈ A * | for all v ∈ M , uv ∈ N }.
In extended Priestley duality [START_REF] Goldblatt | Varieties of complex algebras[END_REF], the additional operations are captured by additional relational structure on the dual space. A well-known case of this is the capture of a modality on the dual frame by its binary Kripke relation. More generally, n-ary relations on lattices are captured by (n + 1)-ary relations on their dual spaces. Remarkably, in the case of the algebra (Reg(A * ), \, /), the dual relation common to the two additional operations is functional and turns out to be the product on profinite words. Theorem 6.1 The dual space of the algebra (Reg(A * ), \, /) under extended duality is the topological monoid of profinite words ( A * , τ, •). The relational dual of the operations \ and / is the product of profinite words. The closure of Reg(A * ) under \ and / accounts for the right and left continuity of the product, respectively, and the equational property (H\K)/L = H\(K/L) of (Reg(A * ), \, /) corresponds to the associativity of the product.

The proof of Theorem 6.1 requires advanced machinery from duality theory and space does not allow us to give even a sketch of the proof here.

This theorem has far-reaching consequences. To mention just two, the syntactic ordered monoid of a regular language is none other than the dual space of the subalgebra of (Reg(A * ), \, /) generated by the singleton set {L} under the lattice operations and the residuation operations with arbitrary denominators, and closure of Reg(A * ) under product of languages corresponds to the fact that product for profinite words is an open mapping. In the next section we use Theorem 6.1 to give an important specialisation of Theorem 5.2.

The following observations will come in handy in the next section: for each a ∈ A the residuals with denominator {a} are central in language theory. We denote them by a -1 ( ) and ( )a -1 instead of {a}\( ) and ( )/{a}, respectively, and call them quotienting operations.

We call a lattice of languages a quotienting algebra of languages provided it is closed under the quotienting operations. For instance, the lattice Reg(A * ) is a quotienting algebra. It is easy to prove that, for sets of regular languages closed under finite intersections, closure under the residuals with arbitrary denominators amounts to the same as closure under the quotienting operators.

Lattices of languages closed under quotienting

In this section we characterise those lattices of languages for which the dual quotient is not only a topological quotient but also an ordered monoid quotient. Recall that an ordered monoid is a partially ordered monoid in which the monoid operation is order preserving in each coordinate. Note that the map A * ։ S D defined in the proof of Theorem 5.2 is an ordered monoid quotient if and only if the relation Q D is a congruence of ordered monoid.

Let u and v be two profinite words of A * . We say that L satisfies the semigroup equation u v if, for all x, y ∈ A * , it satisfies the equation xvy → xuy. Since A * is dense in A * , it is equivalent to state that L satisfies these equations only for all x, y ∈ A * . But there is a much more convenient characterization using the syntactic ordered monoid of L. Proposition 7.1 Let L be a regular language of A * , let (M, L ) be its syntactic ordered monoid and let η : A * → M be its syntactic morphism. Then L satisfies the equation u v if and only if η(u) L η(v).

Proof. Corollary 5.1 shows that L satisfies the equation u v if and only if, for every x, y ∈ A * , η(xvy) ∈ η(L) implies η(xuy) ∈ η(L). Since η(xvy) = η(x)η(v)η(y) = η(x)η(v)η(y) and since η is surjective, this is equivalent to saying that, for all s, t ∈ M , sη(v)t ∈ η(L) implies sη(u)t ∈ η(L), which exactly means that η(u) L η(v).

Using the fact that in the extended duality, preservation of operations on the algebraic side corresponds to bounded morphisms [START_REF] Goldblatt | Varieties of complex algebras[END_REF] on the other, one can now prove the following specialisation of Theorem 5.2. Theorem 7.2 Let D be a lattice of languages of A * . The following conditions are equivalent:

(1) D is a quotienting algebra of languages,

(2) D can be defined by a set of semigroup equations u v, where u, v ∈ A * ,

(3) the corresponding dual quotient A * ։ S D is an ordered quotient monoid.

Theorem 7.2 can be readily extended to Boolean algebras. Let u and v be two profinite words. We say that a regular language L satisfies the equation u = v if it satisfies the equations u v and v u. Proposition 7.1 now gives immediately: Proposition 7.3 Let L be a regular language of A * and let η be its syntactic morphism. Then L satisfies the equation u = v if and only if η(u) = η(v). This leads to the following equational description of the Boolean algebras of languages closed under quotients. Proposition 7.4 A set of regular languages of A * is a Boolean quotienting algebra if and only if it can be defined by a set of semigroup equations of the form u = v, where u, v ∈ A * .

Classes of languages closed under inverses of morphisms

The results of this section and the previous section permit in particular to recover the equational characterization of Eilenberg's varieties and Straubing's C-varieties.

Denote by C a class of morphisms between free monoids containing the length-preserving morphisms and closed under composition. These morphisms will be called C-morphisms. Examples include the classes of all length-preserving morphisms (morphisms for which the image of each letter is a letter), all lengthmultiplying morphisms (morphisms such that, for some integer k, the length of the image of a word is k times the length of the word), all non-erasing morphisms (morphisms for which the image of each letter is a nonempty word), all length-decreasing morphisms (morphisms for which the image of each letter is either a letter of the empty word) and all morphisms.

A class of language lattices L associates with every finite alphabet A a lattice of languages L(A * ). Theorem 5.2 gives an equational description for each of these lattices, but these equations depend on the alphabet A. We now show that if L is closed under inverses of C-morphisms, a single set of equations suffices to characterize the whole class L.

Indeed, if u → v is an equation of L(A * ) and ϕ : A * → B * is a C-morphism, then φ(u) → φ(v) is an equation of L(B *
). This leads naturally to the following definition. Let Σ be a countable alphabet. A regular language L of A * satisfies the C-identity u v, where u, v ∈ Σ * if, for each C-morphism ϕ : Σ * → A * , L satisfies the equation φ(v) → φ(u). Then one gets the following result: Theorem 8.1 A class of language lattices is closed under quotienting and under inverses of C-morphisms if and only if it can be defined by a set of C-identities of the form u v, where u, v ∈ Σ * .

In practice, one may consider a C-identity as an equation in which each letter represents a variable. If C is the class of length-preserving morphisms, these variables can be replaced by letters, if it is the class of length-multiplying morphisms, they can be replaced by words of the same fixed length, etc.

Of course, similar results hold for identities of the form u ↔ v, u v or u = v. Our main result thus offers multifarious aspects, which are summarized in the following table. Reiterman's theorem corresponds to the strongest assumptions.

Closed under

Equations Definition

∪, ∩ u → v η(u) ∈ η(L) ⇒ η(v) ∈ η(

Examples of equational definitions

In this section, we give a few examples of equational characterizations for classes of languages that are not closed under inverses of morphisms and hence do not form a variety of languages. The language A * is called the full language.

Languages with zero and nondense languages

A language with zero is a language whose syntactic monoid has a zero. The class of regular languages with zero is closed under Boolean operations and residuals. According to Proposition 7.4, it has an equational definition, but finding one explicitely requires a little bit of work.

Let us fix a total order on the alphabet A. Let u 0 , u 1 , . . . be the ordered sequence of all words of A + in the induced shortlex order. For instance, if A = {a, b} with a < b, the first elements of this sequence would be 1, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, . . . It is proved in [START_REF] Reilly | Decomposition of the lattice of pseudovarieties of finite semigroups induced by bands[END_REF][START_REF] Almeida | Profinite identities for finite semigroups whose subgroups belong to a given pseudovariety[END_REF] that the sequence of words (v n ) n 0 defined by v 0 = u 0 , v n+1 = (v n u n+1 v n ) (n+1)! converges to an idempotent ρ A of the minimal ideal of A * . We can now state: Proposition 9.1 A regular language has a zero if and only if it satisfies the equation xρ A = ρ A = ρ A x for all x ∈ A * .

Proof. Let L be a regular language and let η : A * → M be its syntactic monoid. Since ρ A belongs to the minimal ideal of A * , η(ρ A ) is an element of the minimal ideal of M . In particular, if M has a zero, η(ρ A ) = 0 and L satisfies the equations xρ A = ρ A = ρ A x for all x ∈ A * . Conversely, assume that L satisfies these equations. Let m ∈ M and let x ∈ A * be such that η(x) = m. Then the equations η(

xρ A ) = η(ρ A ) = η(ρ A x) give mη(ρ A ) = η(ρ A ) = η(ρ A )m, showing that η(ρ A ) is a zero of M . Thus L has a zero.
In the sequel, we shall use freely the symbol 0 in equations to mean that a monoid has a zero. For instance the equation x 0 of Theorem 9.2 below should be formally replaced by the three equations xρ A = ρ A = ρ A x and x ρ A .

A language L of A * is dense if, for every word u ∈ A * , L ∩ A * uA * = ∅. Note that dense languages are not closed under intersection: (A 2 ) * and (A 2 ) * A ∪ {1} are dense, but their intersection is not dense. However, one can show that regular nondense or full languages form a lattice of languages closed under quotients.

We now give an equational description of the form foretold by Theorem 7.2.

Theorem 9.2 A language of A * is nondense or full if and only if it satisfies the equations x 0 for all x ∈ A * .

Languages defined by density

The density of a language L ⊆ A * is the function which counts the number of words of length n in L. More formally, it is the function d

L : N → N defined by d L (n) = |L ∩ A n |. See [23] for a general reference. If d L (n) = O(1)
, then L is called a slender language. It is well known that a regular language is slender if and only if it is a finite union of languages of the form xu * y, where x, u, y ∈ A * . Regular slender languages form a lattice of languages closed under residuals and morphisms.

Note that if |A| 1, all regular languages are slender. For |A| 2, slender or full languages admit a simple equational characterization. Let us denote by i(u) the first letter (or initial ) of a word u. Theorem 9.3 Suppose that |A| 2. A regular language of A * is slender or full if and only if it satisfies the equations x 0 for all x ∈ A * and the equation x ω uy ω = 0 for each x, y ∈ A + , u ∈ A * such that i(uy) = i(x).

We now also consider the Boolean closure of slender languages. A language is called coslender if its complement is slender. Theorem 9.4 Suppose that |A| 2. A regular language of A * is slender or coslender if and only if its syntactic monoid has a zero and satisfies the equations x ω uy ω = 0 for each x, y ∈ A + , u ∈ A * such that i(uy) = i(x).

Note that if A = {a}, the language (a 2 ) * is slender but its syntactic monoid, the cyclic group of order 2, has no zero. Therefore the condition |A| 2 in Theorem 9.4 is mandatory.

A language is sparse if it has polynomial density, that is, if d L (n) = O(n k ) for some k > 0. It is well known that a regular language is sparse if and only if it is a finite union of languages of the form u 0 v * 1 u 1 • • • v * n u n , where u 0 , v 1 , . . . , v n , u n are words. Regular sparse languages from a lattice of languages and are closed under concatenation product, morphisms and residuals. Theorem 9.5 Suppose that |A| 2. A regular language of A * is sparse or full if and only if it satisfies the equations x 0 for all x ∈ A * and the equations (x ω y ω ) ω = 0 for each x, y ∈ A + such that i(x) = i(y).

Pursuing the analogy with slender languages, we consider now the Boolean closure of sparse languages. A language is cosparse if its complement is sparse. Theorem 9.6 Suppose that |A| 2. A regular language of A * is sparse or cosparse if and only if its syntactic monoid has a zero and satisfies the equations (x ω y ω ) ω = 0 for each x, y ∈ A + such that i(x) = i(y).

Conclusion

We proved that every lattice of regular languages is given by an equational theory, a result that subsumes Eilenberg's variety theorem and its extensions to positive varieties and C-varieties. One could further extend this result to classes of regular languages only closed under finite intersection by using the syntactic semiring introduced by Polák [START_REF] Polák | Syntactic semiring of a language[END_REF]. Our result could also be adapted to languages of infinite words, words over ordinals or linear orders, and even perhaps to tree languages.

Our second main result does not in itself give a new result in the theory of automata and semigroups, but it reveals a very strong link between two theories pertaining to the foundations of computer science: the theory of relational semantics for non-classical (modal, intuitionistic, many-valued, etc.) logics on the one side and the algebraic theory of automata on the other. We have indicated how the fundamental tools of semigroup theory fit into the duality perspective, obtaining an extensive repertoire of equational theories as a modular family of results so typical of modal correspondence theory. Further duality results will be presented in the full version of this paper.

  by our earlier definition, this is exactly what we call the set of languages defined by Q if we identify each pair (u, v) in Q with the corresponding equation u → v.Since, coming from D, going to the preorder Q D , and then going back to the set of languages defined by Q D under duality gives us back we see that D is the set of languages defined by Q D .Writing u ↔ v for (u → v and v → u), we get an equational description of the Boolean algebras of languages.Corollary 5.3 A set of regular languages of A * is a Boolean algebra of languages if and only if it can be defined by a set of equations of the form u ↔ v, where u, v ∈ A * .

The authors acknowledge support from the AutoMathA programme of the European Science Foundation.


When does partial commutative closure preserve regularity?

Antonio Cano Gómez * Giovanna Guaiana † Jean-Éric Pin ‡ §

To appear at ICALP 2008

The closure of a regular language under commutation or partial commutation has been extensively studied [START_REF] Achache | Opérateurs de fermeture semi-commutatifs[END_REF][START_REF] Ginsburg | Bounded regular sets[END_REF][START_REF] Ginsburg | Semigroups, Presburger formulas, and languages[END_REF][START_REF] Gohon | An algorithm to decide whether a rational subset of N k is recognizable[END_REF], notably in connection with regular model checking [START_REF] Bouajjani | Permutation Rewriting and Algorithmic Verification[END_REF][START_REF] Bouajjani | Permutation Rewriting and Algorithmic Verification[END_REF][START_REF] Cécé | Efficiency of Automata in Semi-Commutation Verification Techniques[END_REF] or in the study of Mazurkiewicz traces, one of the models of parallelism [START_REF] Guaiana | On the product of trace languages[END_REF][START_REF] Guaiana | On the trace product and some families of languages closed under partial commutations[END_REF][START_REF] Muscholl | A note on the commutative closure of star-free languages[END_REF][START_REF] Sakarovitch | The "last" decision problem for rational trace languages[END_REF]. We refer the reader to the survey [START_REF]The book of traces[END_REF][START_REF] Diekert | Partial commutation and traces[END_REF] or to the recent articles of Ochmański [START_REF] Ochmański | On closures of lexicographic starfree languages[END_REF][START_REF] Ochmański | Star-free star and trace languages[END_REF][START_REF] Ochmański | A Star Operation for Star-Free Trace Languages[END_REF] for further references.

In this paper, we present new advances on two problems of this area. The first problem is well-known and has a very precise statement. The second problem is more elusive, since it relies on the somewhat imprecise notion of robust class. By a robust class, we mean a class of regular languages closed under some of the usual operations on languages, such as Boolean operations, product, star, shuffle, morphisms, inverses of morphisms, residuals, etc. For instance, regular languages form a very robust class, commutative languages (languages whose syntactic monoid is commutative) also form a robust class. Finally, group languages (languages whose syntactic monoid is a finite group) form a semi-robust class: they are closed under Boolean operation, residuals and inverses of morphisms, but not under product, shuffle, morphisms or star.

Here are the two problems:

Problem 1. When is the closure of a regular language under [partial] commutation still regular?

Problem 2. Are there any robust classes of languages closed under [partial] commutation?

The classes considered in this paper are all closed under polynomial operations. Recall that, given a class L of regular languages, the polynomial languages of L are the finite unions of languages of the form L 0 a 1 L 1 • • • a k L k where a 1 , . . . , a k are letters and L 0 , . . . , L k are languages of L. Taking the polynomial closure usually increase robustness. For instance, the class Pol(G) of polynomials of group languages is closed under union, intersection, quotients, product, shuffle and inverses of morphisms. Let I be a partial commutation and let D be its complement in A × A. Our main results on Problems 1 and 2 can be summarized as follows:

1

(1) The class Pol(G) is closed under commutation. If D is transitive, it is also closed under I-commutation. (2) Under some simple conditions on the graph of I, the closure of a language of Pol(G) under I is regular. (3) There is a very robust class of languages W which is closed under commutation. This class, which contains Pol(G), is closed under intersection, union, shuffle, concatenation, residual, length preserving morphisms and inverses of morphisms. Further, it is decidable and can be defined as the largest positive variety of languages not containing. (4) If I is transitive, the closure of a language of W under I is regular. Result (3) is probably the most important of the four results. It is, in a sense, optimal since (ab) * is the canonical example of a regular language whose commutative closure is not regular.

The proofs are nontrivial and combine several advanced techniques, including combinatorial Ramsey type arguments, algebraic properties of the syntactic monoid [START_REF] Cano Gómez | On a conjecture of Schnoebelen[END_REF][START_REF] Cano Gómez | Shuffle on positive varieties of languages[END_REF], finiteness conditions on semigroups [START_REF] De Luca | Finiteness and regularity in semigroups and formal languages[END_REF] and properties of insertion systems [START_REF] Bucher | On total regulators generated by derivation relations[END_REF]. Some proofs are missing but are given in the Appendix.

Our paper is organised as follows. We first survey the known results in Section 1. Then we establish some combinatorial properties of group languages in Section 2. Our results on commutative closure are established in Section 3 and those on closure under partial commutation in Section 4.

Known results

Let

The first problem

For the commutative closure, the problem is solved [START_REF] Ginsburg | Bounded regular sets[END_REF][START_REF] Ginsburg | Semigroups, Presburger formulas, and languages[END_REF][START_REF] Gohon | An algorithm to decide whether a rational subset of N k is recognizable[END_REF]: the commutative closure of the language (ab) * is not regular, but one can effectively decide whether the commutative closure of a regular language is regular or not.

For partial commutations, the result of Sakarovitch [START_REF] Sakarovitch | The "last" decision problem for rational trace languages[END_REF] concluded a series of previous partial results.

Theorem 1.1 One can decide whether the closure [L] I of a regular language L is regular if and only if I is a transitive relation.

The second problem

Only a few results are known for the second problem. They concern the following classes of languages:

(1) the class Pol(I) of finite unions of languages of the form

A * a 1 A * • • • a k A * ,
with a 1 , . . . , a k ∈ A, (2) the class J of piecewise testable languages (the Boolean closure of Pol(I)), (3) the class Pol(J ), which consists of finite unions of languages of the form

A * 0 a 1 A * 1 • • • a k A * k with A i ⊆
A and a 1 , . . . , a k ∈ A. These languages are also called APC (Alphabetic Pattern Constraints) in [START_REF] Bouajjani | Permutation Rewriting and Algorithmic Verification[END_REF], (4) the class Pol(Com) of polynomials of commutative languages. The following theorem summarises the results of Guaiana, Restivo and Salemi [START_REF] Guaiana | On the product of trace languages[END_REF][START_REF] Guaiana | On the trace product and some families of languages closed under partial commutations[END_REF], Bouajjani, Muscholl and Touili [START_REF] Bouajjani | Permutation Rewriting and Algorithmic Verification[END_REF][START_REF] Bouajjani | Permutation Rewriting and Algorithmic Verification[END_REF] and Cécé, Héam and Mainier [START_REF] Cécé | Efficiency of Automata in Semi-Commutation Verification Techniques[END_REF].

Star-free languages

Two nice results on star-free languages were proved by Muscholl and Petersen [START_REF] Muscholl | A note on the commutative closure of star-free languages[END_REF]. The first one is the counterpart of Theorem 1.1 for star-free languages.

Theorem 1.3 One can decide whether the closure [L] I of a star-free language L is star-free if and only if I is a transitive relation.

The second result is related to our second problem.

Theorem 1.4 Let L be a star-free language. If D is transitive, then [L] I is either star-free or non regular. If D is not transitive, then there exist star-free languages such that [L] I is regular but not star-free.

Properties of group languages

Recall that a group language is a regular language whose syntactic monoid is a group, or, equivalently, is recognized by a finite deterministic automaton in which each letter defines a permutation of the set of states. We gather in this section the properties of these languages needed in this paper.

Let π be a morphism from A * onto a finite group G and let R = π -1 (1). The next lemma is a well-known consequence of Ramsey's theorem [START_REF] Pin | Varieties of formal languages[END_REF].

Lemma 2.1 For any n > 0, there exists N > 0 such that, for any u 0 , u 1 , . . . , u N ∈ A * there exists a sequence 0

i 0 < i 1 < . . . < i n N such that π(u i0 u i0+1 • • • u i1-1 ) = π(u i1 u i1+1 • • • u i2-1 ) = . . . = π(u in-1 • • • u in-1 ) = 1.
An insertion system is a special type of rewriting system whose rules are of the form 1 → r for all r in a given language R. We write

u → R v if u = u ′ u ′′ and v = u ′ ru ′′ for some r ∈ R. We denote by * → R the reflexive transitive closure of the relation → R . Given a language L of A * , its closure under * → R is the language [L] * →R = {v ∈ A * | there exists u ∈ L such that u * → R v.}
We are especially interested in the case R = π -1 (1), where π is a morphism from A * onto a finite group G. Let F be the set of words of R of length |G|. It is not difficult to see that the relations * → F and * → R coincide. The next result follows from the results of Bucher, Ehrenfeucht and Haussler [START_REF] Bucher | On total regulators generated by derivation relations[END_REF].

Proposition 2.2 (1)
The relation π is a well preorder on A * .

(2) For any language L, the language

[L] * → R is regular.
We prove a slightly more precise result.

Proposition 2.3 For any language L, the language

[L] * → R
is a polynomial of group languages.

Proof. Let R = π -1 (1). By construction, R is a group language. If u = a 1 • • • a n , the language [u] * →R is equal to Ra 1 R • • • Ra n R,

Commutative closure

This section contains three new results. The first one concerns group languages, the second one polynomials of group languages and the third one a robust class introduced in [START_REF] Cano Gómez | On a conjecture of Schnoebelen[END_REF][START_REF] Cano Gómez | Shuffle on positive varieties of languages[END_REF] and denoted by W.

Recall that if L is a language of A * , the syntactic preorder of L is the relation L defined on A * by u L v if and only if, for every x, y ∈ A * , xvy ∈ L implies xuy ∈ L. The syntactic congruence ∼ L is defined by u ∼ L v if and only if u L v and v L u.

Group languages

Theorem 3.1 The commutative closure of a group language is regular.

Proof. Let L ⊆ A * be a group language and let π : A * → G be its syntactic morphism. Let n = |G| and let N be the integer given by Lemma 2.1. We claim that for any letter a ∈ A, a

N ∼ [L] a N +n . Let g = π(a). Suppose that xa N y ∈ [L].
Then there exists a word w of L commutatively equivalent to xa N y. It follows that wa n is commutatively equivalent to xa N +n y. Further, since G is a finite group, one has g n = 1 by Lagrange's theorem, whence π(wa n ) = π(w)π(a n ) = π(w). Thus the words w and wa n have the same syntactic image by π and hence wa n ∈ L. Therefore xa N +n y ∈ [L].

Conversely, assume that xa N +n y ∈ [L]. Then xa N +n y is commutatively equivalent to some word of L, say w = u 0 au 1 a • • • u N -1 au N au N +1 . By applying Lemma 2.1 to the sequence of words u 0 a, u 1 a, . . . , u N a, we obtain a sequence

0 i 0 < i 1 < . . . < i n N such that π(u i0 a • • • au i1-1 a) = π(u i1 a • • • au i2-1 a) = . . . = π(u in-1 a • • • au in-1 a) = 1 (1)
This implies in particular

π(u i0 a • • • au i1-1 ) = π(u i1 a • • • au i2-1 ) = . . . = π(u in-1 a • • • au in-1 ) = g -1 (2)
Let r and s be the words defined by

w = r(u i0 a • • • au i1-1 a)(u i1 a • • • au i2-1 a)(u in-1 a • • • au in-1 a)s
Since w is commutatively equivalent to xa N +n y, the word

w ′ = r(u i0 a • • • au i1-1 )(u i1 a • • • au i2-1 ) • • • (u in-1 a • • • au in-1 )s
is commutatively equivalent to xa N y. Furthermore, Formulas (1) and ( 2) show that π(w) = π(r)π(s) and π(w ′ ) = π(r)(g -1 ) n π(s). Since (g -1 ) n = 1 by Lagrange's theorem, π(w) = π(w ′ ) and thus w ′ ∈ L. It follows that xa N y ∈ [L], which proves the claim. Now, the syntactic monoid of [L] is a commutative monoid in which each generator has a finite index. Since the alphabet is finite, this monoid is finite and thus [L] is regular. Theorem 3.1 indicates that the commutative closure of a group language is a commutative regular language. One may wonder whether, in turn, any commutative regular language is the commutative closure of a group language. The answer is no, but requires an improved version of Theorem 3.1.

Theorem 3.2

The commutative closure of a group language is a polynomial of group languages.

Proof. Let L be a group language and let π : A * → G be its syntactic morphism. We claim that [L] is a filter for π , which will give the result by Proposition 2.3. Let us show that if

a 1 • • • a n ∈ [L] and v 0 , v 1 , . . . , v n ∈ π -1 (1), then v 0 a 1 v 1 • • • a n v n ∈ [L]. Since a 1 • • • a n ∈ [L], there exists a word w ∈ L which is commutatively equivalent to a 1 • • • a n . Thus the word wv 0 v 1 • • • v n is commuta- tively equivalent to v 0 a 1 v 1 • • • a n v n . Now π(wv 0 v 1 • • • v n ) = π(w)π(v 0 ) • • • π(v n ) = π(w). Therefore wv 0 v 1 • • • v n ∈ L, proving the claim.
Note that the commutative closure of a group language is not necessarily a group language. Indeed, consider the set of all words of {a, b} * having an even number of (scattered) subwords equal to ab. Its commutative closure, A * aA * bA * ∪ A * bA * aA * is not a group language. However, Theorem 3.2 can be extended to polynomials of group languages.

Theorem 3.3

The commutative closure of a polynomial of group languages is also a polynomial of group languages.

Proof. It is shown in [START_REF] Pin | Polynomial closure of group languages and open sets of the Hall topology[END_REF] that for any polynomial of group languages L, there exists a morphism π : A * → G from A * onto a finite group G such that L is a finite union of languages of the form Ra

1 R • • • Ra n R, with R = π -1 (1). Thus it suffices to show that if K = Ra 1 R • • • Ra n R
for some letters a 1 , . . . , a n , then [K] is a polynomial of group languages.

We claim that [K] is a filter for π , which will give the result by Proposition

2.3. Let us show that if b 1 • • • b m ∈ [K] and v 0 , v 1 , . . . , v n ∈ R, then v 0 b 1 v 1 • • • b m v n ∈ [K]. Let w be a word of K commutatively equivalent to b 1 • • • b m .
As an element of K, w can be written as r 0 a 1 r 1 • • • a n r n for some words r 0 , . . . , r n ∈ R. Since the words v 0 , . . . , v m are in R, the word wv

0 v 1 • • • v n also belongs to K and is commutatively equivalent to v 0 b 1 v 1 • • • b m v m .
This proves the claim and concludes the proof.

Languages of W

We now define the class of regular languages W first introduced and studied in [START_REF] Cano Gómez | On a conjecture of Schnoebelen[END_REF][START_REF] Cano Gómez | Shuffle on positive varieties of languages[END_REF]. Recall that a positive variety of languages is a class of regular languages closed under union, intersection, residuals and inverses of morphisms.

The class W is the unique maximal positive variety of languages which does not contain the language (ab) * , for all letters a = b. It is also the unique maximal positive variety satisfying the two following conditions: it is proper, that is, strictly included in the variety of regular languages, and it is closed under the shuffle operation. It is also the largest proper positive variety closed under length preserving morphisms. Being closed under intersection, union, shuffle, concatenation, length preserving morphisms and inverses of morphisms, W is a quite robust class, which strictly contains the classes APC, Pol(Com) and Pol(G) introduced in Section 1.2.

The class W has an algebraic characterization [START_REF] Cano Gómez | On a conjecture of Schnoebelen[END_REF][START_REF] Cano Gómez | Shuffle on positive varieties of languages[END_REF]. Let a and b be two elements of a monoid. Recall that b is an inverse of a if aba = a and bab = b. Now, a regular language belongs to W if and only if its syntactic ordered monoid belongs to the variety of finite ordered monoids W defined as follows: an ordered monoid (M, ) belongs to W if and only if, for any pair (a, b) of mutually inverse elements of M , and any element z of the minimal ideal of the submonoid generated by a and b, (abzab) ω ab (see [6, p.435-436] for a precise definition of the semigroup notions used in this characterization). This description might appear quite involved, but has an important consequence: the variety W is decidable. That is, given a regular language L, one can decide whether or not L belongs to W. We also mention for the specialists that W contains the variety of finite monoids DS.

The main result of this section states that W is closed under commutative closure. In fact, we prove a stronger result, which relies on the notion of a period that we now introduce.

Let M be a finite monoid. The exponent of M is the least integer ω such that for all x ∈ M , x ω is idempotent. Its period is the least integer p such that for all x ∈ M , x ω+p = x ω . By extension, the period (respectively exponent ) of a regular language is the period (respectively exponent) of its syntactic monoid. Proposition 3.4 Let L be a commutative language of A * and let d be a positive integer. If, for each letter c of A, there exists N > 0 such that c N +d L c N , then L is regular and its period divides d.

Proof. It follows from [8, Theorem 6.6.2, page 215] that, under these conditions, L is a regular language. Let ω be the exponent of L. The relation

c N +d L c N gives c N (ω-1) c N +d L c N (ω-1) c N , whence c N ω+d L c N ω and since c ω ∼ L c 2ω ∼ L c N ω , one gets finally c ω+d L c ω . It follows that c ω ∼ L c ω+ωd L . . . L c ω+2d L c ω+d L c ω
and hence c ω ∼ L c ω+d . Since L is commutative, its syntactic monoid is commutative and therefore u ω ∼ L u ω+d for all u ∈ A * . It follows that the period of L divides d.

We can now state: Theorem 3.5 Let L be a language of W(A * ). Then [L] is regular and commutative (and hence in W) and its period divides that of L.

Proof. Let L be a language of W(A * ) and let [L] be its commutative closure.

Then there exist an ordered monoid (M, ) ∈ W, a surjective monoid morphism ϕ : A * → M and an order ideal P of (M, ) such that ϕ -1 (P ) = L. Let ω be the exponent of M and let p be its period. Let also d be any number such that, for all t ∈ M , t d is idempotent. In particular, d can be either ω or ω + p. We claim that, for every such d, there exists an integer N such that, for every letter c ∈ A, c N +d [L] c N . If the claim holds, then Proposition 3.4 shows that [L] is regular and that its period divides d. Taking d = ω and d = ω + p then proves that this period also divides p.

The rest of the proof consists in proving the claim. We need two combinatorial results. The first one is a slight variation of Lemma 2.1.

Lemma 3.6 Let c be a letter of A. For any n 0, there exists an integer N such that, for every word u of A * containing at least N + 1 occurrences of c, there exist an idempotent e of M and a factorization u

= v 0 v 1 cv 2 c • • • v n cv n+1 such that, for 1 i n, ϕ(v i c) = e.
= v 0 v 1 c • • • v n1 cv n1+1 such that, for 1 i n 1 , ϕ(v i c) = e.
Now, since n 1 = 3n 2 , one can also write u as u = v 0 (f 1 g 1 ) • • • (f n2 g n2 )v n1+1 where, for 1 i n 2 , f i = v 3i-2 cv 3i-1 and g i = cv 3i c. Lemma 3.8 For 1 i n 2 , the elements ϕ(f i ) and ϕ(g i ) are mutually inverse.

Proof. We omit this proof, but it is a straightforward verification.

Setting s = ϕ(c)e, one gets ϕ(g i ) = s for 1 i n 2 . Further, by the choice of n 2 and by the pigeonhole principle, one can find n 3 indices i 1 < . . . < i n3 and an element s ∈ M such that ϕ(f i1 ) = . . . = ϕ(f in 3 ) = s. Setting

w 0 = v 0 f 1 g 1 • • • f i1-1 g i1-1 x 1 = f i1 y 1 = g i1 w 1 = f i1+1 g i1+1 • • • f i2-1 g i2-1 x 2 = f i2 y 2 = g i2 . . . . . . w n3-1 = f in 3 -1 +1 g in 3 -1+1 • • • f in 3 -1 g in 3 -1 x n3 = f in 3 y n3 = g in 3 w n3 = f in 3 +1 g in 3 +1 • • • f n2 g n2 v n1+1
we obtain a factorization

u = w 0 x 1 y 1 w 1 x 2 y 2 w 2 • • • w n3-1 x n3 y n3 w n3 (3)
such that ϕ(w 1 ) = . . . = ϕ(w n3-1 ) = e, ϕ(x 1 ) = . . . = ϕ(x n3 ) = s and ϕ(y 1 ) = . . . = ϕ(y n3 ) = s. Recall that n 3 = d(1 + r) where r = |z| a = |z| b . We now define words z 1 , . . . , z d as follows: the word z j is obtained by replacing in z the first occurrence of a by x d+(j-1)r+1 , the second occurrence of a by x d+(j-1)r+2 , . . . , the r's occurrence of a by x d+jr and, similarly, the first occurrence of b by y d+(j-1)r+1 , the second occurrence of b by y d+(j-1)r+2 , . . . , the r's occurrence of b by y d+jr . Finally, set

u ′ = w 0 (v 3i1-2 ccv 3i1-1 cz 1 v 3i1 c)(v 3i2-2 ccv 3i2-1 cz 2 v 3i2 c) • • • (v 3i d -2 ccv 3i d -1 cz d v 3i d c)w 1 • • • w n3 (4)
We are now ready for the three final steps.

Lemma 3.9 The word u ′ is commutatively equivalent to xc N +d y.

Proof. It is clear that u ′ is commutatively equivalent to

c d w 0 (v 3i1-2 cv 3i1-1 cv 3i1 c) • • • (v 3i d -2 cv 3i d -1 cv 3i d c)(z 1 • • • z d )(w 1 • • • w n3 ) Now, v 3i1-2 cv 3i1-1 cv 3i1 c = f i1 g i1 = x 1 y 1 , . . . , v 3i d -2 cv 3i d -1 cz d v 3i d c = f i d g i d = x d y d . Further, by construction, z 1 • • • z d ∼ x d+1 y d+1 • • • x n3 y n3 . Therefore u ′ ∼ c d w 0 x 1 y 1 w 1 x 2 y 2 w 2 • • • w n3-1 x n3 y n3 w n3
and finally u ′ ∼ uc d ∼ xc N +d y.

Let T be the submonoid of M generated by s and s and let γ : {a, b} * → T be the morphism defined by γ(a) = s and γ(b) = s. By Proposition 3.7, γ(z) belongs to the minimal ideal of T and since e = ss, the definition of W shows that in M , (eγ(z)e) d e. Proof. Each of the words z j is obtained by replacing in z the occurrences of a by some x k and each occurrence of b by some y k . Since all the x k (resp. y k ) have the same image by ϕ, namely s (resp. s), ϕ(z j ) is equal to γ(z). Lemma 3.11 The word u ′ belongs to L.

Proof. It follows from (3) that ϕ(u) = ϕ(w 0 )eϕ(w n3 ), and hence, since P = ϕ(L), ϕ(w 0 )eϕ(w n3 ) ∈ P . Now, observe that

ϕ(v 3i1-2 ccv 3i1-1 cz 1 v 3i1 c) = ϕ(v 3i1-2 c)ϕ(c)ϕ(v 3i1 -1 c)ϕ(z 1 )ϕ(v 3i1 c)
= eϕ(c)eϕ(z 1 )e = esγ(z)e by Lemma 3.10 By a similar argument, one has

ϕ(v 3i1-2 ccv 3i1-1 cz 1 v 3i1 c) = . . . = ϕ(v 3i d -2 ccv 3i d -1 cz d v 3i d c) = esγ(z)e
Finally, since ϕ(w 1 ) = . . . = ϕ(w n3-1 ) = e, it follows from (4) that ϕ(u ′ ) = ϕ(w 0 )(esγ(z)e) d ϕ(w n3 ) Furthermore, since s ∈ T , sγ(z) belongs to the minimal ideal of T and since M is in W, one has (esγ(z)e) d e. Since ϕ(L) is an order ideal, the element ϕ(w 0 )(esγ(z)e) d ϕ(w n3 ) is also in ϕ(L) and hence u ′ ∈ L.

Putting Lemmas 3.9 and 3.11 together, we conclude that xc N +d y ∈ [L], which proves the claim and the theorem.

Closure under partial commutation

Some of the results of Section 3 can be extended to partial commutations, under some restrictions on the set I.

The case where D is transitive

The condition that D is transitive is equivalent to requiring that A * /∼ I is isomorphic to a direct product of free monoids A * 1 × • • • × A * k . Denote by π j the projection from A * onto A * j and let π I be the morphism from A * onto A * 1 ו • •×A * k defined by π I (u) = (π 1 (u), . . . , π k (u)). This morphism is intimately connected to our problem, since u ∼ I v if and only if π I (u) = π I (v). Let us denote by X the shuffle product. The (easy) proof of the next result is omitted. The second part of the statement relies on Mezei's theorem characterizing the recognizable subsets of a direct product of monoids. Proposition 4.1 Let L be a language of A * . If

π I (L) = 1 i n L i,1 × • • • × L i,k (5)
where for 1 j k, the languages L 1,j , . . . , L n,j are languages of A * j , then

[L] I = 1 i n L i,1 X • • • X L i,k . In particular, if π I (L) is a recognizable subset of A * 1 × • • • × A * k , then [L] I is regular.
Then one can prove that if each language [{u ∈ A * j | p• u q} Ij is regular, then [L] I is regular. Putting D j = {(a, b) ∈ A j × A j | (a, b) / ∈ I j } for 1 j k, one can show, thanks to Theorem 4.3, that R p,q is regular if L is a polynomial of group languages and each relation D j is transitive.

There is a simple graph theoretic interpretation of this latter condition. One can show that I satisfies it if and only if the restriction of the graph (A, I) to any four letter subalphabet is not one of the graphs P 4 and P aw represented below:

P 4 P aw
We can now state our last result.

  A be an alphabet and let I be a symmetric and irreflexive relation on A (often called the independence relation). We denote by ∼ I the congruence on A * generated by the set {ab = ba | (a, b) ∈ I}. If L is a language on A * , we also denote by [L] I the closure of L under ∼ I . When I is the relation {(a, b) ∈ A×A | a = b}, we simplify the notation to ∼ and [L], respectively. Thus ∼ is the commutation relation and [L] is the commutative closure of L. The dependence relation associated with I is the relation D = {(a, b) ∈ A × A | (a, b) / ∈ I}. The relations I and D define two graphs (A, I) and (A, D) with A as set of vertices. A class C of languages is closed under I-commutation if L ∈ C implies [L] I ∈ C.

Theorem 1 . 2

 12 Let I be any independence relation. Then (1) the class Pol(I) is closed under commutation, (2) the class J is closed under commutation, (3) the class Pol(J ) is closed under I-commutation, (4) the class Pol(Com) is closed under I-commutation.

  The second one requires an auxiliary definition. A word u of {a, b} * is said to be balanced if |u| a = |u| b . Proposition 3.7 Let B = {a, b}. There exists a balanced word z ∈ B * such that, for any morphism γ : B * → M , γ(z) belongs to the minimal ideal of the monoid γ(B * ). Proof. Let n = |M | and let z be a balanced word of B * containing all words of length n as a factor. Let γ : B * → M be a morphism and let m be an element of the minimal ideal J of γ(B * ). Then one can show there is a word u of length n such that γ(u) = m. Since |u| n, u is a factor of z and γ(z) belongs to M γ(u)M . Now since m ∈ J, M γ(u)M = M mM = J and hence γ(z) ∈ J. Let us continue the proof of Theorem 3.5. Let n = |M | and let z be the balanced word given by Proposition 3.7. Let r = |z| a = |z| b , n 3 = d(1 + r), n 2 = nn 3 and n 1 = 3n 2 . Finally let N = N (n 1 ) be the constant given by Lemma 3.6. Let x, y ∈ A * . If xc N y ∈ [L], there exists a word u of L commutatively equivalent to xc N y and hence containing at least N occurrences of c. By Lemma 3.6, there exist an idempotent e of M and a factorization u

Lemma 3 . 10

 310 One has ϕ(z 1 ) = . . . = ϕ(z d ) = γ(z).

Theorem 4 . 5

 45 Let L be a polynomial of group languages. If the graph (A, I) is (P 4 , P aw)-free, then [L] I is regular.

  a polynomial of group languages. Now since π is a well preorder, every language of the form [L] * →R is equal to a language of the form [F ] * →R with F finite and thus a finite union of languages of the form Ra 1 R • • • Ra n R. It is therefore a polynomial of group languages.

The authors acknowledge support from the AutoMathA programme of the European Science Foundation.

If L is a group language, one can adapt an argument from [START_REF] Cano Gómez | On a conjecture of Schnoebelen[END_REF]Proposition 9.6] to show that π I (L) can be decomposed as in [START_REF] Cano Gómez | On a conjecture of Schnoebelen[END_REF], where each L i,j belongs to Pol(G). Therefore, since Pol(G) is closed under shuffle, we get:

Still some work is needed to obtain the following result.

The case where I is transitive

We now consider the case where I is transitive. In this case, A * /∼ I is a free product of free commutative monoids. Proof. (Sketch) Let P = {A 1 , . . . , A k } be the partition of A such that A * /∼ I is isomorphic to the free product

Let A = (Q, A, • , q 0 , F ) be the minimal automaton of L. Recall that the states of Q are partially ordered by the relation defined by p q if and only if, for all u ∈ A * , q• u ∈ F implies p• u ∈ F .

We now construct a generalized automaton B, over the same set of states Q, in which transitions are labelled by regular languages. More precisely, for each pair of states (p, q), we create a transition from p to q labelled by

Each language {u ∈ A * i | p• u q} can be written as the intersection of A * i and of the language K p,q = {u ∈ A * | p• u q}. Since L ∈ W(A * ), one also has K p,q ∈ W(A * ) and since W is closed under commutation by Theorem 3.5, so does R p,q . The remainder of the proof (omitted for lack of space) consists in proving that B recognizes [L] I . It follows that [L] I is regular.

Note that we don't know whether [L] I also belongs to W(A * ). However, the proof of Theorem 4.4 can be adapted to prove another result.

Let I 1 , . . . , I k be the connected components of the graph (A, I). Then A * /∼ I is isomorphic to the free product A * /∼ I1 * • • • * A * /∼ I k . Let us modify the construction of the automaton B by taking


Julie Poline

Jean Gaschignard

Claire Leblanc

Fouad Madhi

Elsa Foucaud

Elodie Nattes

Albert Faye

Stéphane Bonacorsi

Patricia Mariani

Emmanuelle Varon

Mounira Smati-Lafarge

Marion Caseris

Romain Basmaci

Noémie Lachaume

Naïm Ouldali

Systematic Severe Acute Respiratory Syndrome Coronavirus 2 Screening at Hospital Admission in Children: A French Prospective Multicenter Study

Intercommunal de Créteil, Créteil, France, 10 National Reference Center for Pneumococci, Créteil, France, 11 Service de Pédiatrie-Urgences, Assistance Publique-Hôpitaux de Paris, Hôpital Louis-Mourier, Colombes, France, and 12 Association Clinique et Thérapeutique Infantile du Val-de-Marne, Créteil, France Correspondence: N. Ouldali, Department of General Pediatrics, Pediatric Infectious Disease and Internal Medicine, Robert Debré University Hospital, Assistance Publique-Hôpitaux de Paris, F-75019 Paris, France (naim.ouldali@aphp.fr). To[AU: Your article has been edited for spelling, grammar, clarity, consistency, and adherence to journal style and the American Medical Association Manual of Style (10th edition). Please read the article and author queries carefully to make sure your meaning has been retained. If changes are required, please enter the changes directly into the text. Please note that we may be unable to make changes that conflict with journal style, obscure meaning, or create grammatical or other problems.] assess the relevance of systematic severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) screening of all children admitted to hospital, we conducted a prospective multicenter study including 438 consecutive hospitalized children. A symptom-based SARS-CoV-2 testing strategy failed to identify 45% (95% confidence interval, 24%-68%) of hospitalized children infected by SARS-CoV-2. To limit intrahospital transmission, a systematic screening of children admitted to hospital should be considered.

Keywords.[AU:

Please provide up to 5 keywords.] xxx; xxx; xxx.

Since the first cases of pneumonia in Wuhan, China in December 2019, severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) has been responsible for a global pandemic, leading to >300 000 deaths [1][AU: Please consider updating the first 2 sentences of the main text and reference [1] to reflect the current numbers of deaths.].

France is among the main affected countries, with >27 000 deaths to date [1]. The reproduction number (R0), initially underestimated due to the large proportion of paucisymptomatic or asymptomatic individuals, has since been estimated between 3 and 6, explaining the rapid worldwide spread of the virus [START_REF] Sanche | High contagiousness and rapid spread of severe acute respiratory syndrome coronavirus 2[END_REF][START_REF] Pan | Association of public health interventions with the epidemiology of the COVID-19 outbreak in Wuhan, China[END_REF]. A recent analysis has highlighted that >40% of transmissions could occur before the onset of symptoms [START_REF] He | Temporal dynamics in viral shedding and transmissibility of COVID-19[END_REF], challenging the detection of contagious patients and the implementation of appropriate prevention measures [START_REF] He | Temporal dynamics in viral shedding and transmissibility of COVID-19[END_REF].

Healthcare workers have the potential for frequent contact with infected patients [START_REF] Lancet | COVID-19: protecting health-care workers[END_REF], and several intrahospital clusters have been reported [START_REF] Wang | Nosocomial outbreak of 2019 novel coronavirus pneumonia in Wuhan, China[END_REF][START_REF] Chang | Protecting health-care workers from subclinical coronavirus infection[END_REF], including in pediatric settings [START_REF] Schwierzeck | First reported nosocomial outbreak of severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) in a pediatric dialysis unit[END_REF], threatening both healthcare workers and vulnerable inpatients [START_REF] Wang | Nosocomial outbreak of 2019 novel coronavirus pneumonia in Wuhan, China[END_REF][START_REF] Schwierzeck | First reported nosocomial outbreak of severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) in a pediatric dialysis unit[END_REF][START_REF] Wang | Clinical characteristics of 138 hospitalized patients with 2019 novel coronavirus-infected pneumonia in Wuhan, China[END_REF]. In Italy, up to 20% of healthcare workers may have been infected by SARS-CoV-2 [START_REF] Remuzzi | COVID-19 and Italy: what next?[END_REF]. In the context of maximal pressure applied on healthcare systems in many countries, protecting healthcare workers and fighting against nosocomial coronavirus disease 2019 (COVID-19) are major issues [START_REF] Lancet | COVID-19: protecting health-care workers[END_REF][START_REF] Wang | Clinical characteristics of 138 hospitalized patients with 2019 novel coronavirus-infected pneumonia in Wuhan, China[END_REF]. To limit the risk of intrahospital transmission, optimal SARS-CoV-2 screening strategies and prevention measures are required [START_REF] Wang | Nosocomial outbreak of 2019 novel coronavirus pneumonia in Wuhan, China[END_REF][START_REF] Schwierzeck | First reported nosocomial outbreak of severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) in a pediatric dialysis unit[END_REF].

In pediatrics, given the low prevalence of severe COVID-19 forms described to date, the diagnostic strategy in hospital settings is often limited to performing a real-time reverse-transcription polymerase chain reaction (rRT-PCR) assay of nasopharyngeal swabs in patients presenting symptoms of suspected COVID-19 [START_REF] Schwierzeck | First reported nosocomial outbreak of severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) in a pediatric dialysis unit[END_REF]. However, given the broad spectrum of SARS-CoV-2 manifestations in children [START_REF] Castagnoli | Severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) infection in children and adolescents: a systematic review[END_REF], which are often similar to other highly prevalent viral infections in children, detecting all COVID-19 patients with this testing strategy may be highly challenging.

In this context, we hypothesized that a substantial proportion of children admitted to hospital could escape current SARS-CoV-2 screening strategies, potentially leading to avoidable intrahospital transmission. To test this hypothesis, we set up a systematic SARS-CoV-2 screening strategy in several tertiary pediatric hospitals, for all children admitted for surgical or medical reasons, whether scheduled or after a consultation in pediatric emergencies. Our aim was to assess, in children, the proportion of patients with confirmed SARS-CoV-2 infection that would not have been detected by screening strategy based on clinical presentation alone.

MATERIALS AND METHODS

We conducted a prospective multicenter study in 4 tertiary pediatric hospitals located in the region of Paris, one of the epicenters of the COVID-19 epidemic in France [START_REF]COVID 19 point epidemiologique[END_REF]. A national lockdown was implemented in France on 17 March 2020. We conducted our study between 15 April and 30 April 2020 (ie, 4 weeks after the lockdown), in a situation of reduced circulation of SARS-CoV-2 due to major social contact restrictions [START_REF]COVID 19 point epidemiologique[END_REF]. We assumed that over this short study period, the incidence of COVID-19 did not change substantially [START_REF]COVID 19 point epidemiologique[END_REF].

We included all pediatric patients hospitalized in one of the participating centers during the study period. Before admission, each patient had a nasopharyngeal-specific SARS-CoV-2 rRT-PCR test using the Xpert Xpress SARS-CoV-2 assay (Cepheid), according to local hospital guidelines. We recorded demographic data, symptoms, and clinical findings. The cycle threshold value, which is inversely proportional to the viral load, was used as an indicator of the copy number of SARS-CoV-2 RNA [START_REF] Wang | Detection of SARS-CoV-2 in different types of clinical specimens[END_REF].

The main outcome was the proportion of patients without any symptoms of suspected COVID-19 among children with confirmed SARS-CoV-2 infection confirmed by rRT-PCR. To define children suspected to have COVID-19, we conducted a review of the literature to identify any symptoms or clinical signs reported in children during SARS-CoV-2 infection (details are shown in Supplementary Appendix 1). The following characteristics were considered: fever; upper respiratory tract symptoms (cough, rhinitis, tonsillitis, odynophagia, otalgia, otitis, conjunctivitis); influenza-like illness (including asthenia, headache, and myalgia); anosmia; dysgeusia; dyspnea; chest pain; vomiting or diarrhea; abdominal pain; skin involvement; arthritis or arthralgia; mucosal hemorrhage; Kawasaki syndrome; and myocarditis. Patients were suspected to have COVID-19 if any of these symptoms or signs were identified.

We hypothesized that the rate of positive SARS-CoV-2 nasopharyngeal rRT-PCR would be 5%, and the proportion of positive patients without any symptom of suspected COVID-19 would be 35%. Under these assumptions, we calculated that to estimate the proportion of patients with SARS-CoV-2 infection without any symptom of suspected COVID-19 with a 95% confidence interval (CI) of ±20%, 400 patients would be required. We described patient characteristics as numbers and percentages for categorical variables, and median with interquartile range (IQR) for quantitative variables. We then assessed the association between these characteristics and results of SARS-CoV-2 PCR using the Fisher exact test for categorical variables and the Mann-Whitney U test for quantitative variables. The likelihood ratios (LRs), sensitivity, and specificity were calculated with their 95% CIs. A 2-sided P value < .05 was considered statistically significant. All statistical analyses were performed using R version 3.6.1 software (http://www.R-project.org).

This study received approval from the Robert Debré Hospital institutional review board.

RESULTS

Among the 446 consecutive pediatric patients admitted in the 4 hospitals during the study period, 438 (98.2%) with available clinical data were included. Median age was 6. However, none of these parameters had sensitivity above 41% (Table 1). Combining all symptoms or signs of suspected COVID-19, the sensitivity remained largely suboptimal (55% [95% CI, 32%-76%]). Hence, 10 of 22 patients (45% [95% CI, 24%-68%]) with positive SARS-CoV-2 PCR did not exhibit any symptom or sign of suspected COVID-19. Among these 10 children, 5 had a familial history of proven (n = 1) or suspected (n = 4) COVID-19. Of note, the median cycle threshold value was similar between patients with or without symptoms of COVID-19 (37 vs 32.3; P = 1.0).

DISCUSSION

To our knowledge, this is the first prospective multicenter study including all consecutive hospitalized children to assess the performance of a symptom-based testing strategy for COVID-19. We observed that this strategy failed to detect 45% (95% CI, 24%-68%) of infected children, despite an extensive definition of suspected symptoms and signs of COVID-19. These patients, however, exhibited a similar viral load to patients with classical symptoms of COVID-19, suggesting a comparable potential for contamination [START_REF] Schwierzeck | First reported nosocomial outbreak of severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) in a pediatric dialysis unit[END_REF]. This finding is in line with He et al, who reported that 44% of contaminations occurred before onset of symptoms [START_REF] He | Temporal dynamics in viral shedding and transmissibility of COVID-19[END_REF]. Altogether, these findings raise major concerns regarding a symptom-based COVID-19 screening strategy, which could lead to a substantial increased risk of intrahospital transmission.

In our study, respiratory and digestive symptoms were highly associated with an increased likelihood of positive PCR, in line with the literature [START_REF] Tagarro | Screening and severity of coronavirus disease 2019 (COVID-19) in children[END_REF]. However, the lockdown may have reduced the circulation of other common viruses associated with similar symptoms, leading to an overestimation of these LRs.

Interestingly, Kawasaki-like syndrome[AU: Please check "Kawasaki-like syndrome"; elsewhere in the text and table, this was described as "Kawasaki syndrome." Please ensure that this term is reported consistently throughout the manuscript.] and myocarditis were also highly associated with SARS-CoV-2 infection, confirming the specificity of these novel clinical forms to suspect COVID-19 [START_REF] Riphagen | Hyperinflammatory shock in children during COVID-19 pandemic[END_REF]. In contrast, immunosuppressive treatment, including corticosteroids, and underlying medical conditions were not associated with a higher risk of COVID-19. This suggests that these conditions may not be a major risk factor for COVID-19, an important consideration at the time of reopening schools. Further studies are required to confirm these findings.

Recent studies suggested that despite the magnitude of the outbreak, only a small proportion of the population may have been infected [START_REF] Salje | Estimating the burden of SARS-CoV-2 in France[END_REF]. Thus, with the end of lockdown in process, this rate of immunized population may not be sufficient to exclude the possibility of a second wave, as suggested by recent simulation studies [START_REF] Salje | Estimating the burden of SARS-CoV-2 in France[END_REF][START_REF] Dimeglio | The SARS-CoV-2 seroprevalence is the key factor for deconfinement in France[END_REF].

These observations make optimal screening strategies all the more important.

The strength of our study is the prospective inclusion of consecutive admitted patients over a short period (14 days) during which the incidence of SARS-CoV-2 was relatively stable [START_REF]COVID 19 point epidemiologique[END_REF]. Our study still has limitations. A potential infection with SARS-CoV-2 was assessed by PCR of nasopharyngeal swab alone, which may be associated with a substantial proportion of false negatives. However, this proportion seems lower during the contagious period, which begins before the onset of symptoms, and during which the PCR is currently considered the most sensitive [START_REF] Wang | Detection of SARS-CoV-2 in different types of clinical specimens[END_REF][START_REF] Sethuraman | Interpreting diagnostic tests for SARS-CoV-2[END_REF].

In summary, a symptom-based SARS-CoV-2 testing strategy would fail to identify up to 45% of hospitalized children infected by SARS-CoV-2. To limit further intrahospital transmission to both healthcare workers and vulnerable inpatients, a systematic screening of all children admitted to hospital should be considered, especially in the postlockdown era.

  5 years (IQR, 2.1-13.0 years). Two hundred nine (47.7%) patients presented an underlying condition, and 33 had an immunosuppressive treatment. Overall, 182 (41.6%) had suspected symptoms of COVID-19. Most frequent suspected symptoms were fever (126/182 [69.8%]), diarrhea or vomiting (83/182 [45.6%]), abdominal pain (60/182 [33.0%]), upper respiratory tract infection symptoms (52/182 [28.6%]), dyspnea (27/182 [14.8%]), and skin involvement (20/182 [11.0%]) (Supplementary Appendix 2). SARS-CoV-2 PCR was positive for 22 of 438 children (5.0%). Patients with underlying conditions were not more frequently infected by SARS-CoV-2 than other children (9/209 [4.3%] vs 13/229 [5.7%], respectively; P = .63), nor were patients with chronic immunosuppressive treatment (2/33 [6.1%] vs 20/405 [4.9%]; P = 1.0). Symptoms that most increased the likelihood to have a positive SARS-CoV-2 PCR were dyspnea (positive LR, 6.6 [95% CI, 3.1-14.0]), skin involvement (positive LR, 6.3 [95% CI, 2.5-15.7]), upper respiratory tract symptoms (positive LR, 2.9 [95% CI, 1.5-5.8]), and diarrhea or vomiting (positive LR, 2.3 [95% CI, 1.3-4.0]). Kawasaki syndrome and myocarditis were also strongly associated with COVID-19 (Supplementary Appendix 2).

Supplementary Data

Supplementary materials are available at Clinical Infectious Diseases online. Consisting of data provided by the authors to benefit the reader, the posted materials are not copyedited and are the sole responsibility of the authors, so questions or comments should be addressed to the corresponding author.

Note

Potential conflicts of interest.