Keywords: [2.2]paracyclophanes, formylation, regioselective reactions, para-disubstitution, planar chirality

Para-functionalization of N-substituted 4amino[2.2]paracyclophanes by regioselective formylation

Simon Felder, a Laurent Micouin, a, * and Erica Benedetti a, * Dedication ((optional)) [a] Simon Felder, Dr. Laurent Micouin, Dr. Erica Benedetti Laboratoire de Chimie et Biochimie Pharmacologiques et Toxicologiques -UMR8601 CNRS Université de Paris 45 rue des Saints Pères, 75006 Paris, France laurent.micouin@u-paris.fr; erica.benedetti@u-paris.fr Supporting information for this article is given via a link at the end of the document Abstract: Herein we report a simple and convenient procedure to prepare para-disubstituted [2.2]paracyclophanes in a straightforward manner. Our approach relies on a regioselective formylation of Nsubstituted 4-amino [2.2]paracyclophanes, which allows an easy access to a series of products incorporating a reactive aldehyde function para to the electron-donating group. These compounds can be engaged in a variety of orthogonal late-stage derivatization processes involving either the carbonyl group or the amine function, and can serve as precursors to rapidly access more complex paracyclophane derivatives. Control of planar chirality is also possible by performing a kinetic resolution of key racemic intermediates through asymmetric transfer hydrogenation. The formylation can be run on a synthetically useful scale, thus confirming the practical applicability of our method.

[2.2]Paracyclophane (pCp) 1 and its derivatives constitute a rather unique class of aromatic compounds characterized by an unusual three-dimensional framework. These substrates incorporate two benzene rings called decks, covalently fixed together by two ethylene bridges at their para positions. As evidenced by X-ray diffraction crystallography, the aromatic decks of pCps are stacked face-to-face and adopt a bent conformation. 2 Due to their geometrical constraints, steric effects and unique -interactions, [2.2]paracyclophanes display an uncommon reactivity. These molecules can in fact undergo Diels-Alder cycloadditions, hydrogenations, and ionic additions. 3 Functionalized pCps also often show remarkable substituent effects in electrophilic aromatic substitutions: the functional groups on one deck can induce the incoming electrophile to preferentially attack the other deck at specific positions. 4 Such transannular directive effects are, for example, frequently exploited to selectively access pseudo-gem di-substituted paracyclophanes. 5 While various methods can be followed to functionalize both pCp rings, the selective decoration of only one deck is more of a synthetic challenge. Indeed, only few examples of regioselective ortho-or para-functionalization of pCps have been reported to date. Usually, in these cases, carbon-heteroatoms bonds are formed starting form monosubstituted derivatives through bromination, 6 acetoxylation 7 or amination reactions. 8 In our ongoing work on the chemistry of [2.2]paracyclophanes, 9 we became interested in exploring new synthetic routes to access para-disubstituted pCps in a straightforward manner through selective carbon-carbon bond formation. Such compounds could potentially be used to develop original chromophores. [START_REF] Zafra | For selected examples of pCp-based chromophores[END_REF] In addition, since substituted [2.2]paracyclophanes can display planar chirality due to the hindered rotation of their aryl moieties, 11 para-disubstituted pCps may be employed as precursors of new chiral ligands and catalysts. 12 Very recently, a palladium-catalyzed para-selective C-H activation/aryl-aryl coupling of 4-phenylamino[2.2]paracyclophane has been reported (Scheme 1a). 13 To the best of our knowledge, this constitute the sole example of a reaction allowing the functionalization of paracyclophanes with the creation of aryl-aryl bonds para to an electron-donating amino group. Herein we present a practical method to perform a regioselective para-formylation of N-substituted 4-amino [2.2]paracyclophanes (Scheme 1b). Our approach is complementary to the Pdcatalyzed aryl-aryl couplings since it provides reactive aldehyde derivatives that can serve as intermediates to create aryl-alkyl or aryl-alkenyl bonds. We began our investigations with the synthesis of racemic 4dimethylamino [2.2]paracyclophane. Compound (±)-2 was prepared first, starting from commercially available [2.2]paracyclophane, and following a two-step nitration/reduction procedure previously reported in the literature (Scheme 2). 14 Reductive methylation of derivative (±)-2 then afforded product (±)-3a in 90% yield (Scheme 2). Having pCp (±)-3a in hand, we considered the possibility of performing selective formylation reactions. By taking inspiration from a protocol frequently employed to decorate pCps with aldehyde groups, 15 Rieche's conditions were tested in a first assay (Scheme 3a). The introduction of an aldehyde group at the para position of 4-methoxy [2.2]paracyclophane has indeed been described to occur in a chemical yield of 90% after only 4 hours of reaction. 16 However, N-substituted analog 3a was regioselectively formylated in only 15% chemical yield after 3 days using similar conditions. Amines are known to interact with TiCl 4 to form metal-nitrogen bonds. 17 Such reactivity may hamper the activation of dichloromethyl methyl ether and explain the low conversion observed when performing Rieche's formylation. Different conditions were therefore screened to optimize this transformation, and we were pleased to find that the Vilsmeier-Haack protocol could afford aldehyde (±)-4a in a short reaction time and 90% yield (Scheme 3b). The reaction could be run on a synthetically useful scale (750 mg) without any appreciable loss of efficiency, thus confirming the practical applicability of our method. The relative position of the substituents in compound (±)-4a (formyl group para to the amino group) was deduced from NMR studies, and subsequently confirmed by chemical correlation. Indeed, 4-amino[2.2]paracyclophane (±)-2 was converted into para-iodinated compound (±)-5 using a previously described synthetic protocol. 18 N,N-Dimethylation of amine (±)-5, followed by iodine-lithium exchange and formylation with DMF afforded product (±)-4a in 35% overall yield (Scheme 4). The proton and carbon NMR spectra of this aldehyde and the one obtained through the direct formylation pathway showed identical signal patterns. N,N-Diallyl substituted 4-amino [2.2]paracyclophane(±)-3d reacted as well to form product (±)-4d in 50% yield (Scheme 5). Interestingly, when Fmoc-protected amine (±)-3e was subjected to formylation under the same conditions, product (±)-4d could be isolated in 42% yield (Scheme 5). This last example clearly shows that the reaction also tolerates substrates incorporating mild electron-withdrawing groups on the nitrogen atom. All transformations are supposed to proceed through the mechanism proposed to explain the Vilsmeier-Haack formylation of more common benzene derivatives. 20 The formylated products (±)-4a-d incorporate both an electrondonating and an electron-withdrawing group, and exhibit interesting UV-Vis absorption and fluorescence emission properties. 19 In addition, due to the presence of the reactive aldehyde group, these compounds can undergo a variety of derivatization reactions. To exemplify different possibilities, compound (±)-4a was reduced to the corresponding benzylic alcohol (±)-7, engaged in a reductive amination reaction, and submitted to Grignard addition (Scheme 6). Wittig reactions were also successfully conducted starting from compound (±)-4a (Scheme 6). [START_REF](±)-4a. For more details, see the Supporting information[END_REF] Derivatization reactions involving reactive substituents at the nitrogen atom can also be performed. For instance, compound (±)-4d, showing a N,N-diallyl moiety, was successfully submitted to ring-closing metathesis (RCM) in the presence of a nd generation Hoveyda-Grubbs catalyst (HG cat, Scheme 7) to generate cyclized product (±)-4f in 72% yield (Scheme 7). The Fmoc-protected derivative (±)-4e, on its side, was easily converted to the corresponding primary amine (±)-4g upon treatment with piperidine in DMF (Scheme 7), thus opening up a plethora of possibilities for further functionalization at the nitrogen atom. All the transformations described above have been conducted on racemic material. It is however possible to prepare enantiopure 4-amino [2.2]paracyclophane (S p )-2 taking advantage of a method previously optimized in our laboratory. 9a In a first step, the kinetic resolution of racemic 4formyl [2.2]paracyclophane (±)-11 was performed by asymmetric transfer hydrogenation using RuCl(p-cymene)[(S,S)-Ts-DPEN] as the catalyst, and t-BuOK as the base, in a 1:1 i-PrOH/MeCN mixture (Scheme 8). The resulting enantiopure aldehyde (S p )-11 was converted into the corresponding oxime (S p )-12 through a classical condensation reaction. Treatment of compound (S p )-12 with Koser's reagent [START_REF] Ae | [END_REF] and NaOH finally leaded to the formation of the desired enantiopure amine (S p )-2, which was isolated in 58% yield (Scheme 8). Starting from this precursor, it will clearly be easy to prepare a variety of para-disubstituted pCps in their enantiopure form simply by using our regioselective formylation protocol as a key synthetic step.

NR 1 R 2 NR 1 R 2 O 1) POCl 3 , DMF 0 to 100 °C, 3h
In conclusion, we reported a practical method to regioselectively synthesize para-disubstituted [2.2]paracyclophanes in few steps, and good overall yields. Our approach is based on the Vilsmeier-Haack formylation of differently substituted 4amino [2.2]paracyclophanes, which allows the introduction of a reactive aldehyde function para to the electron-donating groups.

The formylated products exhibit interesting spectroscopic properties, and can be engaged in a variety of late-stage functionalization processes leading to more complex paracyclophane derivatives. All synthesized compound can be easily obtained in their enantiopure form. We are convinced that our convenient formylation reaction will reveal particularly useful as a key step to access planar chiral paracyclophanes showing interesting photophysical or catalytic properties. The possibility to use this approach for preparing new circularly polarized light emitters is currently under investigation in our laboratory.

  Scheme 1. Access to para-disubstituted pCps through selective carboncarbon bond formation.

Scheme 2 .

 2 Scheme 2. Synthesis of racemic compound (±)-3a.

  Scheme 3. Selective formylation of compound (±)-3a.

Scheme 4 .

 4 Scheme 4. Chemical correlation studies.

Scheme 6 .

 6 Scheme 6. Late-stage derivatization of compound (±)-4a.

Scheme 7 .

 7 Scheme 7.Transformations involving reactive substituents at the nitrogen atom.

8 .

 8 Scheme 8. Access to enantiopure 4-amino[2.2]paracyclophane (Sp)-2.

Acknowledgements

We gratefully thank the Agence Nationale de la Recherche (ANR PhotoChiraPhane), CNRS, Université de Paris and the Ministère de l'Enseignement Supérieur et de la Recherche for financial support. Patrice Gerardo is kindly acknowledged for his help with mass analysis.

Entry for the Table of Contents

Regioselective C-C bond formation Access to versatile key intermediates Simple route to para-disubstituted pCps

A regioselective formylation of N-substituted 4-amino [2.2]paracyclophanes is described, which allows an easy access to key synthetic intermediates useful to prepare a large variety of para di-substituted paracyclophanes in a straightforward manner.

Institute and/or researcher Twitter usernames: ((optional))


MD Hélène Affres
email: helene.affres@aphp.fr

MD, PhD Marie-Victoire Senat
email: marie-victoire.senat@aphp.fr

MD Alexandra Letourneau
email: letourneau.alexandra@aphp.fr

MD, PhD Philippe Deruelle
email: philippe.deruelle@chru-strasbourg.fr

MD Magali Coustols-Valat

MD Hanane Bouchghoul
email: hanane.bouchghoul@aphp.fr

PhD Jean Bouyer
email: jean.bouyer@inserm.fr

Magali Coustols
email: valatmagali.coustols@wanadoo.fr

Glyburide therapy for gestational diabetes: glycemic control, maternal hypoglycemia, and treatment failure

Keywords: gestation diabetes mellitus, glyburide, hypoglycemia, blood glucose control

Aims

The recommended first-line treatment for women with gestational diabetes mellitus (GDM) in the case of failure of diet is insulin. Recent results suggest that there is a potential role for glyburide therapy and highlight the need for better knowledge of glycemic control with glyburide. The objective of this study was to describe and quantify in women with GDM the quality of glycemic control, including the risk of maternal hypoglycemia and of therapy failure.

Methods

This is a secondary analysis of the French INDAO non-inferiority trial from 2012 to 2016, in which 890 women with GDM randomized to receive glyburide or insulin treatment were compared for perinatal outcomes. Blood glucose concentrations were assessed prospectively during pregnancy. Optimal glycemic control was defined as less than 20% of blood glucose values exceeding the targets.

Results

More than 50% of the women had optimal glycemic control with glyburide, similar to that with insulin. Around 40% of the women had at least one episode of hypoglycemia, more than with insulin. However, those hypoglycemic episodes were mostly moderate and the rate of severe hypoglycemia decreased significantly during the course of the trial.

Failure of glyburide treatment (switch to insulin therapy) occurred in 18% of women and had few predictors. However, when failure occurred, glycemic control was improved after switching to insulin.

Conclusions

Glyburide is an effective treatment for reaching glycemic goals during pregnancy in women with GDM. The risk of maternal hypoglycemia may be minimized by clinical practice experience. These findings could be taken into account in the management of GDM.

Introduction

The rate of gestational diabetes mellitus (GDM) ranges from 9% to 25%, depending on the characteristics of the mother, and has been increasing over time, because of the rising prevalence of obesity and increasing maternal age [START_REF] Durnwald | Gestational diabetes: Linking epidemiology, excessive gestational weight gain, adverse pregnancy outcomes, and future metabolic syndrome[END_REF][START_REF] Mack | Gestational Diabetes: Diagnosis, Classification, and Clinical Care[END_REF]. Two large randomized controlled studies [START_REF] Crowther | Effect of treatment of gestational diabetes mellitus on pregnancy outcomes[END_REF][START_REF] Landon | A multicenter, randomized trial of treatment for mild gestational diabetes[END_REF] have shown that treatment of women with mild GDM in order to reach strict glycemic goals can reduce the frequency of some adverse perinatal outcomes, especially macrosomia. Therefore, the aim of treatment of GDM is to normalize maternal fasting and postprandial glucose levels in order to limit perinatal complications. The recommended first-line treatment for women with GDM in the case of failure of diet is insulin [START_REF]American Diabetes Association. 14. Management of Diabetes in Pregnancy: Standards of Medical Care in Diabetes-2019[END_REF]. However, oral agents may have advantages over insulin due to their lower cost, easier administration, easier storage, and better acceptance, and may be required in some situations.

Since the first randomized trial by Langer et al [START_REF] Langer | A comparison of glyburide and insulin in women with gestational diabetes mellitus[END_REF], meta-analyses based on randomized trials have shown that maternal glycemic control is similar with insulin and glyburide [START_REF] Balsells | Glibenclamide, metformin, and insulin for the treatment of gestational diabetes: a systematic review and meta-analysis[END_REF][START_REF] Dhulkotia | Oral hypoglycemic agents vs insulin in management of gestational diabetes: a systematic review and metaanalysis[END_REF][START_REF] Jiang | Comparative efficacy and safety of OADs in management of GDM: network meta-analysis of randomized controlled trials[END_REF][START_REF] Song | Comparison of glyburide and insulin in the management of gestational diabetes: A meta-analysis[END_REF][START_REF] Poolsup | Efficacy and safety of oral antidiabetic drugs in comparison to insulin in treating gestational diabetes mellitus: a meta-analysis[END_REF][START_REF] Zeng | The use of glyburide in the management of gestational diabetes mellitus: a meta-analysis[END_REF]. Recently, the INDAO randomized non-inferiority trial (NCT01731431) [START_REF] Senat | Effect of Glyburide vs Subcutaneous Insulin on Perinatal Complications Among Women With Gestational Diabetes: A Randomized Clinical Trial[END_REF] compared glyburide to insulin whose primary outcome was a composite criterion of perinatal complications associated with GDM, including macrosomia, neonatal hypoglycemia, and hyperbilirubinemia,. Although it did not show the non-inferiority of glyburide, this trial showed that the increase in neonatal complications was no more than 10.5% and concerned mainly neonatal transient hypoglycemia. This leaves a potential role for glyburide therapy and highlights the need for better knowledge of glycemic control with glyburide and of which patients could benefit from it without failure. The INDAO trial offers this opportunity since it gathered a large sample of women who had been followed up until the end of pregnancy.

The objectives of this ancillary analysis of INDAO data were to describe and quantify in women with GDM the quality of glycemic control and the risk of maternal hypoglycemia with glyburide compared to insulin, and to study glyburide therapy failure in women who switched to insulin.

The INDAO trial protocol, including ancillary studies like the present one, was approved by the ethics committee of the Poissy St-Germain Hospital, France (2011-004221-28) and registered in clinicaltrials.gov (NCT01731431).

Material and methods

This study is an ancillary analysis of the INDAO non-inferiority trial conducted from May 2012 to November 2016 in 13 tertiary care university hospitals in France, comparing glyburide versus insulin for the prevention of perinatal complications of GDM. Detailed information regarding the design of the trial has been reported elsewhere [START_REF] Senat | Effect of Glyburide vs Subcutaneous Insulin on Perinatal Complications Among Women With Gestational Diabetes: A Randomized Clinical Trial[END_REF]. In summary, women with a singleton pregnancy and diagnosed with GDM with the 75 g oral glucose tolerance test using International Association of the Diabetes and Pregnancy Study Groups (IADPSG) criteria [START_REF] Panel | International association of diabetes and pregnancy study groups recommendations on the diagnosis and classification of hyperglycemia in pregnancy[END_REF] between 24 and 34 weeks of gestation were given individual nutrition education by a dietitian and were taught to self-monitor capillary blood glucose four times daily (fasting and 2 hours after each meal). Goals were considered not achieved after 10 days of well-managed diet if at least 2 blood glucose values above the targets were observed over a week: fasting ≥ 0.95 g/L; 2-hour postprandial ≥ 1.20 g/L, with no variations in the diet. In that case, the woman was eligible for randomization between the two therapeutic strategies: insulin or glyburide.

Treatments

Insulin: The starting dose for rapid analogs was 4 IU subcutaneously before meals, one to three times daily, and this was increased by 2 IU every 2 days according to the postprandial blood glucose value. When necessary, the starting dose for basal or intermediate insulin was 4 to 8 IU subcutaneously at bedtime, and increased by 2 IU every two days according to the morning fasting blood glucose value. Women were taught to self-adjust their insulin doses in order to reach and maintain glycemic goals throughout pregnancy.

Glyburide: The starting dose for therapy was 2.5 mg orally once a day before breakfast and could be increased if necessary 4 days later by 2.5 mg and thereafter by 5 mg every four days in two doses morning and evening before meals up to a maximum of 20 mg per day. In cases of symptomatic hypoglycemia or blood glucose < 60 mg/dL, glyburide dose could be decreased or returned to the previous dose. If the maximum tolerated dose was reached without achieving the desired glucose values of less than 95 mg/dL for fasting and 120 mg/dL for 2 hours postprandial, women were switched to insulin. We have considered here that all switches were glyburide therapy failures.

Monitoring of glycemic control

At each visit, all the woman's blood glucose measurements and treatment intakes since the previous visit were recorded. Glycemic control was quantified by the clinician by the percentage of her blood glucose values since the previous visit greater than 95 mg/dL for fasting and 120 mg/dL for 2 hours postprandial, which are the targets currently recommended [START_REF] Crowther | Effect of treatment of gestational diabetes mellitus on pregnancy outcomes[END_REF][START_REF] Landon | A multicenter, randomized trial of treatment for mild gestational diabetes[END_REF][START_REF]American Diabetes Association. 14. Management of Diabetes in Pregnancy: Standards of Medical Care in Diabetes-2019[END_REF][START_REF] Vayssiere | Expert consensus on gestational diabetes mellitus. Methods and organization[END_REF]. Overall glycemic control per woman during treatment was quantified by computing the percentage of blood glucose values exceeding targets in all her blood glucose assays, from randomization to delivery. Two categories of glycemic control were defined (and estimated separately for fasting and postprandial blood glucose): "optimal glycemic control" (≤ 20% of blood glucose values exceeding targets) and "sub-optimal glycemic control" (percentage > 20%).

Maternal hypoglycemia was defined as blood glucose below 60 mg/dL, and severe hypoglycemia as blood glucose below 40 mg/dL and/or clinical symptoms of severity: confusion, poor coordination, double vision, convulsion, or inability to self-treat symptoms.

Statistical analysis

To study glycemic control and maternal hypoglycemia, women randomized to the insulin group were compared to women randomized to the glyburide group. In the glyburide group, women who were switched to insulin (glyburide treatment failure) were compared to women who remained in the glyburide group.

Comparisons of continuous variables were done with Student's t-test and comparisons of categorical variables were done with chi-square tests. The evolution of glycemic control during pregnancy was studied by modeling the relationship between fasting or postprandial blood glucose results and time elapsed since the start of treatment. Modeling was performed with fractional polynomials [START_REF] Royston | Multivariable model-building. A pragmatic approach to regression analysis based on fractional polynomials for modelling continuous variables[END_REF] with generalized linear models [START_REF] Raudenbush | Hierarchical Linear Models: Applications and Data Analysis Methods[END_REF] to take into account the successive blood glucose assays for a woman during pregnancy. The rate of hypoglycemia during the course of the trial was modeled by fractional polynomials and logistic regression. Statistical analyses were performed using Stata software, release 15 [START_REF] Statacorp | Stata Statistical Software: Release 15[END_REF].

Results

Characteristics of the women

From May 2012 through September 2016, 914 women with GDM were randomized: 460 to the glyburide group and 454 to the insulin group. After randomization, 18

(2.0%) patients were excluded because they did not meet the inclusion criteria and six had no primary outcome or refused the treatment. The 890 remaining women were of mean age 32.7 years, had a mean pre-pregnancy body mass index (BMI) of 27.6 kg/m 2 , 63.5% were multiparous and 20.3% had had previous GDM. Among the Data on glycemic control during pregnancy were available for 845 women (95%): 418 in the insulin group and 427 in the glyburide group. We verified that the loss of 5% of women did not alter the balance between the 2 groups.

Glycemic control and hypoglycemia during treatment

On average, with glyburide, 80% of the fasting blood glucose measurements and 78% of the postprandial blood glucose measurements of a woman were within the targets. More than 60% of the women with glyburide had optimal fasting glycemic control and almost 50% optimal postprandial glycemic control. Glycemic control (fasting or postprandial) was similar with glyburide and insulin (Table 1). Glycemic control during pregnancy improved with both treatments to the same extent according to the time elapsed since the start of the treatment (Figure 1). Among women treated with glyburide, 41.1% had at least one hypoglycemic event during treatment (Table 1). Among the 16 women (3.6%) with severe hypoglycemia, two reported an inability to self-treat their symptoms. No women had symptoms of neuroglucopenia. The proportion of hypoglycemic episodes was lower (9.1%) in women treated with insulin, but it is noteworthy that the proportion of severe hypoglycemic episodes with glyburide decreased dramatically during the course of the trial and was close to that associated with insulin (i.e., almost zero) after two years of prescribing experience (Figure 2). We found no factors associated with severe hypoglycemia, likely due to this strong learning-curve phenomenon. More precisely, there were no factors significantly associated with severe hypoglycemia episodes in the insulin group. In the glyburide group, there were only slight differences in postprandial or fasting blood glucose at randomization between women with or without a hypoglycemia episode (supplementary Tables A1 andA2).

The mean dose received by the women randomized to the glyburide group was 5.7 mg/day and 69.8% of the women had a dosage less than 10 mg/day. There was no significant trend in the mean dose of glyburide with time (p=0.79). The mean dose of insulin received by women randomized to the insulin group was 19.6 IU/day, and 84.5% of the women were treated with a dosage of insulin less than 40 IU/day.

Glyburide therapy failure

Compared to women who remained on glyburide treatment, women switched to insulin were significantly older and were slightly more often multiparous (mainly because they are older). There was no significant difference between the two groups in pre-pregnancy BMI or previous GDM. They had significantly poorer glycemic control at randomization before medical treatment (Table 2) either fasting or postprandial. When fasting and post-prandial glycemic control were considered together, the proportion or glyburide therapy failure was 15.8 % when only fasting glycemic control was sub-optimal, 18.8 % when only post-prandial glycemic control was suboptimal and 26.8 % when both glycemic control were sub-optimal.

Half of the 81 women who were switched did so in the 3 rd week of glyburide treatment or before. A large majority had sub-optimal glycemic control before the switch, either fasting (61.5%) or postprandial (82.7%). However 8 women were switched despite optimal glycemic control, both fasting and post-prandial, so it is possible that in some cases hypoglycemia may lead to stop glyburide treatment. The proportions of hypoglycemia and severe hypoglycemia cases before the switch were 33.3% and 3.7%, respectively and were of the same magnitude than those in women treated with glyburide until the end of pregnancy.

After the switch, glycemic control with insulin improved: 42.3% of women had suboptimal fasting glycemic control and 61.5% had sub-optimal postprandial glycemic control. The proportions of hypoglycemia and severe hypoglycemia cases decreased to 7.4% and 0%, respectively, which were of the same magnitude as for women treated with insulin since randomization.

Discussion

Statement of principal findings

This ancillary analysis of the INDAO trial [START_REF] Senat | Effect of Glyburide vs Subcutaneous Insulin on Perinatal Complications Among Women With Gestational Diabetes: A Randomized Clinical Trial[END_REF] provides new information on women with GDM treated with glyburide. More than 50% of the women have optimal glycemic control with glyburide (i.e. less than 20% of their blood glucose values exceeded the targets) and an average of 0.80 of blood glucose values are within the targets. These results were similar to those with insulin. Around 40% of the women have had at least one episode of hypoglycemia, which is more than with insulin, though those hypoglycemic episodes were mostly moderate, and the rate of severe hypoglycemia with glyburide decreased during the course of the trial. Finally, glyburide treatment failed in 18% of the women who were switched to insulin, helping to improve their glycemic control.

Strengths and weaknesses in relation to other studies, discussing important differences in results

These results are in line with previous publications of randomized controlled trials and meta-analyses concluding that glyburide and insulin are equally effective in normalizing maternal glucose levels in GDM [START_REF] Balsells | Glibenclamide, metformin, and insulin for the treatment of gestational diabetes: a systematic review and meta-analysis[END_REF][START_REF] Dhulkotia | Oral hypoglycemic agents vs insulin in management of gestational diabetes: a systematic review and metaanalysis[END_REF][START_REF] Jiang | Comparative efficacy and safety of OADs in management of GDM: network meta-analysis of randomized controlled trials[END_REF][START_REF] Song | Comparison of glyburide and insulin in the management of gestational diabetes: A meta-analysis[END_REF][START_REF] Poolsup | Efficacy and safety of oral antidiabetic drugs in comparison to insulin in treating gestational diabetes mellitus: a meta-analysis[END_REF][START_REF] Zeng | The use of glyburide in the management of gestational diabetes mellitus: a meta-analysis[END_REF]. However, the way that glycemic control was quantified in many of these studies (mean of fasting or preprandial and postprandial blood glucose) did not always take into account glycemic profile and the frequency of glucose excursions. In our study, we used a pragmatic indicator to assess glycemic control for each woman individually (percentage of fasting and 2hour postprandial blood glucose values exceeding the targets currently recommended [START_REF] Crowther | Effect of treatment of gestational diabetes mellitus on pregnancy outcomes[END_REF][START_REF] Landon | A multicenter, randomized trial of treatment for mild gestational diabetes[END_REF][START_REF]American Diabetes Association. 14. Management of Diabetes in Pregnancy: Standards of Medical Care in Diabetes-2019[END_REF]). This indicator is an approximation of the "time in range" derived from continuous glucose monitoring, a method that allows total glucose exposure and variability to be quantified. However, continuous glucose monitoring is not used routinely in GDM since it has been evaluated during pregnancy mainly in women with pre-existing diabetes [START_REF] Feig | Continuous glucose monitoring in pregnant women with type 1 diabetes (CONCEPTT): a multicentre international randomised controlled trial[END_REF][START_REF] Kristensen | Continuous glucose monitoring in pregnant women with type 1 diabetes: an observational cohort study of 186 pregnancies[END_REF][START_REF] Secher | The effect of realtime continuous glucose monitoring in pregnant women with diabetes: a randomized controlled trial[END_REF][START_REF] Voormolen | Continuous glucose monitoring during diabetic pregnancy (GlucoMOMS): A multicentre randomized controlled trial[END_REF] and only one trial in women with type 1 diabetes has shown some advantages of its use in terms of glycemic control or neonatal outcomes [START_REF] Feig | Continuous glucose monitoring in pregnant women with type 1 diabetes (CONCEPTT): a multicentre international randomised controlled trial[END_REF].

Maternal hypoglycemia, both moderate and severe, was more frequent in the glyburide group compared to the insulin group. Glyburide as an insulin secretagogue may cause greater risk than additional insulin because stimulated endogenous insulin secretion cannot be reduced during hypoglycemia. The rate of severe maternal hypoglycemia (blood glucose < 40 mg/dL) during glyburide treatment was close to that reported in the main trial using the same glyburide regiment [START_REF] Langer | A comparison of glyburide and insulin in women with gestational diabetes mellitus[END_REF].

However, the rate of severe hypoglycemia we observed in the insulin group was much lower than that reported by Langer et al in the first large randomized trial [START_REF] Langer | A comparison of glyburide and insulin in women with gestational diabetes mellitus[END_REF].

This could be due to our precautionary modalities of insulin titration in women with significant residual insulin secretion, in order to avoid maternal hypoglycemia.

Interestingly, the rate of severe maternal hypoglycemia with glyburide treatment decreased significantly over time, which corresponded to the learning curve needed to use glyburide cautiously in order to prevent hypoglycemia: time of administration of glyburide and distribution of carbohydrates between meals and snacks could be adapted according to individual glycemic profile.

The doses of glyburide used in our study were relatively low: 5.7 mg/day on average and almost 70% of the women received less than 10 mg/day. Other studies have also found that women treated with glyburide achieve the desired level of glycemic control during pregnancy with low glyburide dosages (10 mg/day or less):

observational studies [START_REF] Jacobson | Comparison of glyburide and insulin for the management of gestational diabetes in a large managed care organization[END_REF][START_REF] Rochon | Glyburide for the management of gestational diabetes: risk factors predictive of failure and associated pregnancy outcomes[END_REF][START_REF] Yogev | Glyburide in gestational diabetes--prediction of treatment failure[END_REF] and a secondary analysis of a large randomized trial which found that only 6% of patients in the well-controlled group required high doses of glyburide (>10 mg/day) [START_REF] Langer | Insulin and glyburide therapy: dosage, severity level of gestational diabetes, and pregnancy outcome[END_REF]. Therefore, it can be argued that women responding to glyburide need only small doses to achieve glycemic control.

Like most studies, we have defined "glyburide treatment failure" as the fact that a woman treated with glyburide was switched to insulin by her supervising clinician due to sub-optimal glucose control. This is a proxy since sub-optimal glycemic control may also be observed in some women who were not switched to insulin, although it could be considered as another form of glyburide failure. It is also noteworthy that, similarly, some women not optimally controlled with insulin could be considered as "insulin treatment failure". Our finding of 18% women with glyburide failure is consistent with reports of cohort studies [START_REF] Rochon | Glyburide for the management of gestational diabetes: risk factors predictive of failure and associated pregnancy outcomes[END_REF][START_REF] Yogev | Glyburide in gestational diabetes--prediction of treatment failure[END_REF][START_REF] Harper | Predicting failure of glyburide therapy in gestational diabetes[END_REF][START_REF] Kahn | Predictors of glyburide failure in the treatment of gestational diabetes[END_REF] and a meta-analysis [START_REF] Balsells | Glibenclamide, metformin, and insulin for the treatment of gestational diabetes: a systematic review and meta-analysis[END_REF].

We found few predictors of glyburide treatment failure (maternal age and sub-optimal glycemic control before treatment) and their predictive ability is limited. This is consistent with previous studies suggesting that pretreatment glycemic values [START_REF] Rochon | Glyburide for the management of gestational diabetes: risk factors predictive of failure and associated pregnancy outcomes[END_REF][START_REF] Yogev | Glyburide in gestational diabetes--prediction of treatment failure[END_REF][START_REF] Harper | Predicting failure of glyburide therapy in gestational diabetes[END_REF][START_REF] Kahn | Predictors of glyburide failure in the treatment of gestational diabetes[END_REF], maternal age and parity [START_REF] Kahn | Predictors of glyburide failure in the treatment of gestational diabetes[END_REF], and early diagnosis of GDM [START_REF] Harper | Predicting failure of glyburide therapy in gestational diabetes[END_REF][START_REF] Kahn | Predictors of glyburide failure in the treatment of gestational diabetes[END_REF] may be associated with treatment failure. Therefore, in clinical practice, it is difficult to predict the failure and thus to select women who are likely to respond well to glyburide. However, since glyburide is usually effective at low dosages in patients who respond to it [START_REF] Rochon | Glyburide for the management of gestational diabetes: risk factors predictive of failure and associated pregnancy outcomes[END_REF][START_REF] Yogev | Glyburide in gestational diabetes--prediction of treatment failure[END_REF][START_REF] Langer | Insulin and glyburide therapy: dosage, severity level of gestational diabetes, and pregnancy outcome[END_REF], and because sub-optimal glycemic control the week following treatment initiation is predictive of treatment failure [START_REF] Harper | Predicting failure of glyburide therapy in gestational diabetes[END_REF], women in whom glyburide treatment will fail can be detected early in clinical practice. Moreover, since glycemic control can be markedly improved after a switch to insulin, there is no chance lost for a woman initially treated with glyburide of reaching the glycemic targets recommended during pregnancy.

Based on these results and its greater ease of use, after informing patients of the balance of risks and benefits, glyburide could be considered as an alternative treatment in women with GDM for whom the constraints of insulin therapy are too great and could lead to poor observance.

Strengths and weaknesses of the study

The main strength of our study is its large size and that it is part of a randomized controlled trial, which involves rigorous monitoring of women and their treatment. Therefore, most potential glucose measurement biases limited. Glycemic control was assessed prospectively at each visit, allowing us to quantify it accurately throughout pregnancy.

The main limitation of our study is the substantial percentage of women who were switched from glyburide to insulin. This situation was foreseen in the protocol and the percentage was expected, but it does not allow for an unbiased description of the women treated with glyburide. Our choice to maintain these women in their initial treatment group is similar to an intention-to-treat analysis. It avoids excluding women whose glycemic control is more difficult to achieve and therefore avoids overestimating glyburide results. Symmetrically, it tends to underestimate treatment results with glyburide and possible differences from insulin in glycemic control.

Conclusion

Glyburide is an effective treatment for reaching glycemic goals during pregnancy in women with GDM. However, the use of glyburide requires a clear understanding of its mechanism of action and a learning period may be necessary to reduce the rate of maternal hypoglycemia. Glyburide failure is difficult to predict, but can be detected early during the first weeks of treatment, in which case the switch to insulin rapidly improves glycemic control. These findings could be taken into account in the management of GDM.

French and European regulations. Requests should be addressed to the Delegation for Clinical Research and Innovation (DRCI) at secretariat-direction.drc@aphp.fr. For each woman, we computed the number of blood glucose values exceeding targets in all her blood glucose assays during the diet phase, between diagnosis and randomization. The mean of these proportions was calculated.

  This study was funded by a research grant from the French Ministry of Health and was sponsored by Paris Public Hospitals (AP-HP, Assistance Publique des Hôpitaux de Paris), via its Clinical Research Department. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

Figure 1 :Figure 2 :

 12 Figure 1: Glycemic control during pregnancy according to the treatment group (insulin or glyburide): curves and 95% confidence intervals

Table 1 :

 1 Glycemic control and hypoglycemia during treatment For each woman, we computed the number of blood glucose values within the targets in all her blood glucose assays, from randomization to delivery, divided by the total number of her blood glucose values. The mean of these proportions was calculated.† at least one fasting or postprandial blood glucose measurement < 60 mg/dL during treatment ‡ at least one fasting or postprandial blood glucose measurement < 40 mg/dL during treatment

	Glyburide n = 448	Insulin n = 442	p

*

Table 2 :

 2 Failure of glyburide therapy For each woman, we computed the number of blood glucose values exceeding targets in all her blood glucose assays during the diet phase, between diagnosis and randomization divided by the total number of her blood glucose values.. The mean of these proportions was calculated.

	Failure of glyburide
	No	Yes	p
	n = 367	n = 81

*

Table A1 .

 A1 Characteristics of the women with an episode of hypoglycemia defined as blood glucose below 60 mg/dL. Glyburide therapy group. +5 (25 +3 to 28 +0 ) 26 +3 (25 +1 to 28 +0 ) 0.58 For each woman, we computed the number of blood glucose values exceeding targets in all her blood glucose assays during the diet phase, between diagnosis and randomization. The mean of these proportions was calculated.

	At least one hypoglycemia episode
		No	Yes	p
		(n = 264)	(n = 184)
	Age, mean (SD), years	32.4 (5.1)	33.4 (5.2)	0.04
	Multiparity, No (%)	158 (59.9)	114 (62.9)	0.65
	Pre-pregnancy BMI, mean (SD), kg/m 2	27.8 (5.7)	26,9 (5.3)	0.10
	BMI at diagnosis, mean (SD), kg/m 2	31.1 (5.2)	30.2 (5.1)	0.08
	Geographical origin, No (%)			0.14
	Europe	114 (44.9)	64 (35.6)
	North Africa	86 (33.9)	62 (34.4)
	Sub-Saharan Africa	22 (8.7)	26 (14.4)
	Asia	14 (5.5)	9 (5.0)
	Other	18 (7.1)	19 (10.6)
	Previous gestational diabetes, No (%)	49 (18.6)	43 (23.4)	0.24
	GA a at OGTT screening b , median (IQR), weeks +days 26 Type of abnormal blood glucose at			0.02
	randomization, No. (%)
	only fasting	10 (3.8)	2 (1.1)
	only 2 h postprandial	33 (12.5)	39 (21.2)
	both fasting and 2 h postprandial	221 (83.7)	143 (77.7)
	Mean of the proportions per woman c
	of blood glucose values within the
	targets at randomization
	Fasting blood glucose ≤ 95 mg/dL	0.57	0.64	0.04
	Postprandial blood glucose ≤ 120	0.78	0.75	0.10
	mg/dL

a GA: gestational age b OGTT: oral glucose tolerance test c

Table A2 .

 A2 Characteristics of the women with an episode of hypoglycemia defined as blood glucose below 40 mg/dL. Glyburide therapy group. at OGTT screening b , median (IQR), weeks +days 26 +4 (25 +2 to 28 +0 ) 26 +2 (25 +0 to 27 +5 ) 0.63

		At least one hypoglycemia episode
		No	Yes	p
		(n = 432)	(n = 16)
	Age, mean (SD), years	32.8 (5.1)	32.8 (6.9)	0.99
	Multiparity, No (%)	262 (60.7)	10 (62.5)	0.82
	Pre-pregnancy BMI, mean (SD), kg/m 2	27.5 (5.6)	27.5 (6.1)	0.98
	BMI at diagnosis, mean (SD), kg/m 2	30.8 (5.2)	30.4 (5.6)	0.77
	Geographical origin, No (%)			0.71
	Europe	173 (41.3)	5 (33.3)
	North Africa	140 (33.4)	8 (53.3)
	Sub-Saharan Africa	47 (11.2)	1 (6.7)
	Asia	23 (5.5)	0 (0.0)
	Other	36 (8.6)	1 (6.7)
	Previous gestational diabetes, No (%)	86 (20.0)	6 (7.5)	0.10
	GA Type of abnormal blood glucose at			1.00
	randomization, No. (%)
	only fasting	12 (2.8)	0 (0.0)
	only 2 h postprandial	70 (16.2)	2 (12.5)
	both fasting and 2 h postprandial	350 (81.0)	14 (67.5)
	Mean of the proportions per woman c
	of blood glucose values within the
	targets at randomization
	Fasting blood glucose ≤ 95 mg/dL	0.60	0.54	0.47
	Postprandial blood glucose ≤ 120	0.77	0.69	0.06
	mg/dL

a a GA: gestational age b OGTT: oral glucose tolerance test c

Diabetes & Metabolism -accepted version

Acknowledgements

We thank David Marsh, BSc (Biophysics, First Class Honours, University of Leeds, UK) PhD (Biophysics, King's College London, UK), freelance translator and copyeditor/proofreader for language editing. He received compensation for this work.

Funding

This study was supported by a research grant from the French Ministry of Health and was sponsored by Paris Public Hospitals (AP-HP, Assistance Publique des Hôpitaux de Paris), via its Clinical Research Department. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

Data availability

Data of the INDAO trial cannot be shared publicly as it contains sensitive patient information and is the property of AP-HP (Paris Public Hospitals). Consultation of the data by other interested researchers may be considered by AP-HP, subject to prior determination of the terms and conditions of such consultation and in respect of compliance with the applicable

Author Contributions

HA, MVS, JB conceived the study, analyzed and interpreted the data, drafted the first version of this article, and reviewed/edited the manuscript. HB, MC, PD critically revised the manuscript and reviewed/edited it.

MVS and JB had full access to all the data in the study and take responsibility for the integrity of the data and the accuracy of the data analysis.

Conflict of Interest Disclosure

The authors do not report any potential conflicts of interest.


Pierre Fraigniaud
email: pierre.fraigniaud@liafa.jussieu.fr

David Ilcinkas
email: david.ilcinkas@labri.fr

Andrzej Pelc
email: pelc@uqo.ca

Impact of memory size on graph exploration capability

Keywords: Graph exploration, finite automaton, memory size, mobile agent, robot

A mobile agent (robot), modeled as a finite automaton, has to visit all nodes of a regular graph. How does the memory size of the agent (the number of states of the automaton) influence its exploration capability? In particular, does every increase of the memory size enable an agent to explore more graphs? We give a partial answer to this problem by showing that a strict gain of the exploration power can be obtained by a polynomial increase of the number of states. We also show that, for automata with few states, the increase of memory by even one state results in the capability of exploring more graphs.

1 Introduction

The problem

A mobile agent (robot), has to explore an undirected graph by visiting all its nodes, without any a priori knowledge of the topology of the graph or of its size. This task is fundamental, e.g., in searching for data stored at unknown nodes of a network. More precisely, we consider the task of "perpetual" exploration in which the robot has to visit all nodes of the graph but is not required to stop. That is, the robot moves from node to node, traversing edges, so that eventually all nodes have been visited.

If nodes and edges have unique labels, exploration can be easily achieved, e.g., by depth-first search. However, if the robot operates in an unknown environment, such unique labeling may not be available. Hence it is important to be able to program the robot to explore anonymous graphs, i.e., graphs without unique labeling of nodes or edges. Clearly, the robot has to be able to locally distinguish ports at a node: otherwise it is impossible to explore even the star with 3 leaves (after visiting the second leaf, the robot cannot distinguish the port leading to the first visited leaf from that leading to the unvisited one). Hence we make a natural assumption that all ports at a node are locally labeled 0, . . . , d -1, where d is the degree of the node. No consistency between those local labelings is assumed.

In many applications the memory size of the robot has to be kept small, due to cost and size constraints. Hence it is important to determine the exploration capabilities of a robot with restricted memory size. We model a robot as a finite automaton and measure its memory by the number of states. A given robot is capable of exploring a graph G if it can visit all its nodes regardless of the port labeling and of the starting node. (Note that if the port labeling can be chosen, even a memoryless robot, i.e., an automaton with one state, can visit all nodes by always exiting by port i + 1 after entering by port i: the labeling simply has to guide the robot along an Eulerian tour of the respective bidirectional oriented graph.)

In this paper we restrict attention to exploration of regular graphs. These graphs are usually harder to explore by an automaton with small memory because decisions where to go next cannot be made on the basis of the degrees of visited nodes, and must be based only on entry port numbers. For example, it is easy to see that every graph can be augmented by adding a few high-degree nodes on some edges, so that the resulting (non-regular) graph can be explored by a memoryless robot (i.e., an automaton with one state). These high degree nodes are used as flags guiding the robot in DFS traversal of a spanning tree. The non-tree edges are marked by inserting middle nodes of high degree. By contrast we show that the only regular graphs that can be explored by a memoryless robot are cycles and 1-and 2-node graphs.

The central question of this paper is:

How does the memory size of the robot (the number of states of the automaton) influence its exploration capability? In particular, does every increase of the memory size enable the robot to explore more graphs?

We conjecture that the answer to the latter question is yes and our results give a partial support to this claim. In order to state the conjecture and our results precisely, we need to introduce appropriate terminology and fix the model.

Terminology and model

We consider only undirected regular connected graphs without multiple edges and self-loops. An anonymous graph with locally labeled ports is a regular graph of degree d whose nodes are unlabeled and where the edges incident to a node v have distinct labels 0, . . . , d -1. Thus every undirected edge {u, v} has two labels which are called its port numbers at u and at v. Port numbering is local, i.e., there is no relation between port numbers at u and at v. All arithmetic operations on port numbers are done modulo d.

We are given a mobile entity (robot) traveling in a regular anonymous graph of degree d with locally labeled ports. The graph and its size are a priori unknown to the robot, which only knows the degree d. Since the graph is regular and anonymous, the only input obtained by the robot at every stage of the exploration is the port number by which it enters a node. More precisely, a k-state robot is a finite Mealy automaton R = (X, Y, S, δ, λ, S 0 ) where X = Y = {0, . . . , d -1} (X and Y are the input and the output alphabets, respectively), S is a set of k states among which there is a specified state S 0 called the initial state, δ : S × X → S is the state transition function, and λ : S × X → Y is the output function. Initially the robot comes to some node u 0 by a port i 0 in the initial state S 0 ∈ S. The pair (S 0 , i 0 ) determines a local port number i 1 = λ(S 0 , i 0 ) ∈ Y , by which the robot leaves u 0 , and a new state S 1 = δ(S 0 , i 0 ). When incoming to a node v in some state S, the behavior of the robot is as follows. It reads the number i ∈ X of the port through which it entered v. The pair (S, i) causes the transition from state S to the state S ′ = δ(S, i) and yields a local port number j = λ(S, i), by which the robot leaves v. The robot continues moving in this way, possibly infinitely.

Further in the paper we will use the following observation.

Observation 1.1 If there exist a state S and port number i such that δ(S, i) = S and λ(S, i) = i then a robot entering an edge whose both port numbers are i, in state S, must move along this edge back and forth forever.

As mentioned before, we consider the task of "perpetual" exploration in which the robot has to visit all nodes of the graph but is not required to stop. That is, it is not required that a final state be in S. A robot is said to perform an exploration of a graph G with fixed port labeling starting at (u 0 , i 0 ) if, when entering an initial node u 0 of G by the initial port i 0 in the initial state S 0 , it visits all nodes of G in finitely many steps.

A regular graph G of degree d is edge-colored if every edge of G is given a color, every two incident edges have different colors, and there are d colors used in total. There is a clear correspondence between edge-colored graphs and regular graphs in which the labels at the two extremities of each edge are identical. Notice that in an edge-colored graph the automaton does not learn any new information when coming to a new node because the port number by which it enters is the same as the port number by which it left the previous node. Hence in edge-colored graphs both the trajectory of the robot and its sequence of states depend exclusively on the pair (S 0 , i 0 ).

Since we are interested in exploring graphs regardless of their port labeling and starting node and port number, we introduce the following notion. Definition 1.1 Given any positive integer k, the class of k-explorable graphs is the set G k of regular graphs G such that there exists a k-state automaton A(G) which visits all nodes of G for any port labeling of G, any starting node u 0 , and any initial port number i 0 .

Clearly, the sequence of sets G k is non-decreasing, i.e., G k ⊆ G k+1 for every k > 0.

The conjecture and our results

Using the notion of classes G k of k-explorable graphs, our conjecture that every increase of the memory size enables the robot to explore more graphs can be concisely and formally stated as follows.

Conjecture. For every k > 0, G k is strictly included in G k+1 .

Our results give a partial support to this conjecture. We prove that a polynomial increase of the number of states increases exploration capabilities of a robot. More precisely, we show that there is a polynomial function f :

N → N, such that G k is strictly included in G f (k) , for any k > 0.
The previous knowledge on this subject was the following. It follows from [START_REF] Rollik | Automaten in planaren Graphen[END_REF] that the hierarchy G k is unbounded, in the sense that there are graphs outside of any G k . On the other hand, any graph can be explored by a sufficiently large automaton, hence [START_REF] Rollik | Automaten in planaren Graphen[END_REF] implies that there exists a function g : N → N, such that G k is strictly included in G g(k) . However, this function g obtained from [START_REF] Rollik | Automaten in planaren Graphen[END_REF] is exponential. Hence the result from [START_REF] Rollik | Automaten in planaren Graphen[END_REF] guarantees only that an exponential increase of the number of states allows a robot to explore more graphs, while we show that a polynomial increase is sufficient.

On the other hand, we show that for a small number of states the increase of memory by even one state results in the capability of exploring new graphs, i.e., that the beginning of the hierarchy G k is indeed strictly increasing. More precisely, we show that G k is strictly included in G k+1 , for k = 1, 2. Moreover we provide an exact characterization of classes G 1 and G 2 . The class G 1 of regular graphs that can be explored by a memoryless automaton (i.e., an automaton with 1 state) consists of cycles and of the 1-and 2-node cliques, while the class G 2 of regular graphs that can be explored by a 2-state automaton consists of all cycles and all cliques.

Related work

Exploration and navigation problems for robots in an unknown environment have been extensively studied in the literature (cf. [START_REF] Hemmerling | Labyrinth Problems: Labyrinth-Searching Abilities of Automata[END_REF][START_REF] Rao | Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms[END_REF]). There are two groups of models for these problems. In one of them a particular geometric setting is assumed. Another approach is to model the environment as a graph, assuming that the robot may only move along its edges. The graph setting can be further specified in two different ways. In [START_REF] Albers | Exploring unknown environments[END_REF][START_REF] Bender | The power of a pebble: Exploring and mapping directed graphs[END_REF][START_REF] Bender | The power of team exploration: Two robots can learn unlabeled directed graphs[END_REF][START_REF] Deng | Exploring an unknown graph[END_REF][START_REF] Fraigniaud | Directed Graphs Exploration with Little Memory[END_REF] the robot explores strongly connected directed graphs and it can move only in the head-to-tail direction of an edge, not vice-versa. In [START_REF] Awerbuch | Piecemeal graph learning by a mobile robot[END_REF][START_REF] Betke | Piecemeal learning of an unknown environment[END_REF][START_REF] Budach | Automata and labyrinths[END_REF][START_REF] Diks | Tree Exploration with Little Memory[END_REF][START_REF] Dudek | Robotic Exploration as Graph Construction[END_REF][START_REF] Duncan | Optimal constrained graph exploration[END_REF][START_REF] Panaite | Exploring unknown undirected graphs[END_REF][START_REF] Rollik | Automaten in planaren Graphen[END_REF] the explored graph is undirected and the robot can traverse edges in both directions. Graph exploration scenarios considered in the literature differ in an important way: it is either assumed that nodes of the graph have unique labels which the robot can recognize (as in, e.g., [START_REF] Deng | Exploring an unknown graph[END_REF][START_REF] Duncan | Optimal constrained graph exploration[END_REF][START_REF] Panaite | Exploring unknown undirected graphs[END_REF]), or it is assumed that nodes are anonymous (as in, e.g., [START_REF] Bender | The power of a pebble: Exploring and mapping directed graphs[END_REF][START_REF] Bender | The power of team exploration: Two robots can learn unlabeled directed graphs[END_REF][START_REF] Budach | Automata and labyrinths[END_REF][START_REF] Rollik | Automaten in planaren Graphen[END_REF]). We are concerned with the latter context. The efficiency measure adopted in papers dealing with graph exploration is either the completion time of this task, measured by the number of edge traversals, (cf., e.g., [START_REF] Panaite | Exploring unknown undirected graphs[END_REF]), or the memory size of the robot, measured either in bits or by the number of states of the finite automaton modeling the robot (cf., e.g., [START_REF] Diks | Tree Exploration with Little Memory[END_REF][START_REF] Fraigniaud | Graph exploration by a finite automaton[END_REF][START_REF] Fraigniaud | Directed Graphs Exploration with Little Memory[END_REF]). Time is not an issue in our approach, and we address the latter efficiency measure, i.e., memory space. Three versions of the exploration problem have been addressed in the literature: exploration with return (in which the robot has to perform exploration and return to its starting position), exploration with stop (in which the robot has to complete exploration and eventually stop), and perpetual exploration (the type of exploration considered in this paper). For instance, it is shown in [START_REF] Diks | Tree Exploration with Little Memory[END_REF] that exploration with stop of n-node trees requires a robot with memory size Ω(log log log n) bits, and that exploration with return of n-node trees can be achieved by a robot with O(log 2 n) memory bits.

The capability of a robot to explore anonymous undirected graphs has been addressed in, e.g., [START_REF] Blum | On the power of the compass (or, why mazes are easier to search than graphs)[END_REF][START_REF] Budach | Automata and labyrinths[END_REF][START_REF] Diks | Tree Exploration with Little Memory[END_REF][START_REF] Fraigniaud | Graph exploration by a finite automaton[END_REF][START_REF] Kozen | Automata and planar graphs[END_REF][START_REF] Rollik | Automaten in planaren Graphen[END_REF]. In particular, it was shown in [START_REF] Rollik | Automaten in planaren Graphen[END_REF] that no finite automaton can explore all cubic planar graphs (in fact no finite set of finite automata can cooperatively perform this task). The size of port-labeled graphs which cannot be explored by a given robot was investigated in [START_REF] Fraigniaud | Graph exploration by a finite automaton[END_REF].

Our work has connections with derandomized random walks. There, the objective is to produce an explicit universal traversal sequence (UTS), i.e., a sequence of port labels, such that the path guided by this sequence visits all edges of any graph. It has been proved in [START_REF] Kahn | On the cover time of random walks on graphs[END_REF] that, with high probability, a sequence of length O(n 3 d 2 log n), chosen uniformly at random, guides a walk in any d-regular (connected) graph of n nodes. Explicit UTS constructions are known for 2-regular graphs (cf. [START_REF] Bar-Noy | Bounds on universal sequences[END_REF][START_REF] Bridgland | Universal traversal sequences for paths and cycles[END_REF][START_REF] Buss | Lower bounds on universal traversal sequences based on chains of length five[END_REF][START_REF] Istrail | Polynomial universal traversing sequences for cycles are constructible[END_REF][START_REF] Kouckỳ | Log-space constructible universal traversal sequences for cycles of length O(n 4.03 )[END_REF]), for 3-regular graphs (cf. [START_REF] Babai | Multiparty protocols and logspace-hard pseudorandom sequences[END_REF][START_REF] Impagliazzo | Pseudorandomness for network algorithms[END_REF][START_REF] Nisan | Pseudorandom generators for space-bounded computation[END_REF]), for cliques (cf. [START_REF] Alon | Universal sequences for complete graphs[END_REF][START_REF] Karloff | Universal traversal sequences of length n log n for cliques[END_REF]), and for expanders (cf. [START_REF] Hoory | Universal traversal sequences for expander graphs[END_REF]). Some of these sequences can be constructed in log-space, and hence can produce perpetual exploration with compact memory. However, even if bounds on the length of these sequences have been derived, they provide little knowledge on the minimum number of states for graph exploration by a robot. For instance, sequences of length Ω(n 1.43 ) are required to traverse all cycles with n nodes [START_REF] Buss | Lower bounds on universal traversal sequences based on chains of length five[END_REF], although a 1-state robot can accomplish this task.

Polynomial memory increase

In this section we prove that a polynomial increase of the number of states of a robot results in augmenting the capability to explore graphs. More precisely, the main result of this section is the following.

Theorem 2.1 There exists a polynomial function f : N → N, such that G k is strictly included in G f (k) , for any k > 0.

We will use the notion of pseudo-palindrome, which was defined in [START_REF] Fraigniaud | Graph exploration by a finite automaton[END_REF]. We recall here the main definitions and properties.

A sequence L of labels is a pseudo-palindrome if any of the following two conditions is satisfied:

(1) L = ∅, or (2) L = L ′ • (ℓ, ℓ) • L ′′ , where L ′ • L ′′ is a pseudo-palindrome,
ℓ is a label, and • denotes concatenation. In particular, a palindrome is a pseudo-palindrome precisely if its length is even.

A sequence

L ′ is a reduction of L if L ′ = A • B and L = A • L ′′ • B
where L ′′ is a nonempty pseudo-palindrome, and A and B are two arbitrary sequences (possibly empty). A sequence is said pp-free if it has no reduction. A sequence L ′ is the pp-reduction of a sequence L if L ′ is ppfree and obtained from L by successive reductions. One can easily check that the pp-reduction of a finite sequence is unique (cf., e.g., Section 1.7 in [START_REF] Budach | Automata and labyrinths[END_REF]). For instance the pp-reduction of 1122121121322331131332311221 is 1231. Given any regular edge-colored graph G = (V, E) and any node u ∈ V , each sequence L of edge labels defines a path P from u in G. By induction of the length of L, the following observation holds. Observation 2.1 If L is a pseudo-palindrome then P starts and ends at u.

An infinite sequence L is called periodic if L = A • B * , where A and B are finite, B non-empty. The length of the shortest B for which L can be represented in this way is called the period of L. By induction of the period of L we have the following observation. Observation 2.2 If L is an infinite sequence with period p, then the pp-reduction L ′ of L is either finite or is also periodic with period p ′ ≤ p.

The main tool to prove Theorem 2.1 is the following lemma, which may be of independent interest. Lemma 2.1 For any k > 0 there exists a regular planar graph G of degree 3, with O(k 3 ) nodes, such that G ∈ G k .

Proof. For k = 1 the lemma follows from Propositions 3.1 and 3.2 in the next section. Fix an integer k > 1. We first define a graph T that is used as a subgraph of G (cf. Figure 1). The graph T has 6k + 6 nodes x 1 , x 2 , y, y ′ , y 1 , y 2 , u 1 , . . . , u 3k , u ′ 1 , . . . , u ′ 3k and 9k + 7 edges {x 1 , x 2 }, {x 2 , u 1 }, {x 2 , u ′ 1 }, {y 1 , y 2 }, {y, y 1 }, {y, y 2 }, {y ′ , y 1 }, {y ′ , y 2 }, {y ′ , u 3k }, {y ′ , u ′ 3k }, {u 3k , u ′ 3k } and {u i , u ′ i }, {u i , u i+1 }, {u ′ i , u ′ i+1 } for all 1 ≤ i < 3k. Thus all nodes have degree 3 except x 1 that has degree 1. The subgraph of T induced by the nodes y, y ′ , y 1 , y 2 is called the tail of the graph T .

3k x 1 x 2 y 1 y 2 y y' u 1 u 2 u 3k u' 1 u' 2 u' 3k
Let G be a chain of disjoint cycles of all lengths from 3 to 3k. More precisely, let v n and v ′ n be two different nodes of the cycle of length n, for 3 ≤ n ≤ 3k. Connect the cycles by the edges {v ′ n , v n+1 }, for 3 ≤ n < 3k. Now attach a graph T to each node w of G of degree 2 by identifying w of G and x 1 of T . Let G denote the resulting graph. It is regular of degree 3. Since T has O(k) nodes, the graph G has O(k 3 ) nodes.

It remains to prove that G ∈ G k . Fix an automaton A with k > 1 states. Our goal is to find a port-labeling of G, and a starting node and port number, such that the automaton A does not visit all nodes of G.

If an automaton traverses only colored edges in a regular graph (even if ports of non traversed edges are different at both extremities of the edge), then both the trajectory of the automaton (the sequence of port numbers) and its sequence of states depend exclusively on the pair (S 0 , i 0 ), where S 0 is the initial state and i 0 the initial port number. In particular, after at most 3k + 1 steps, the automaton will enter a node in a state S by a port i, such that the pair (S, i) already occurred at some previous node. Thus, after this step, both the sequence of states and the sequence of edge colors L = {a n } n≥0 are periodic. There exist q and p, with q + p ≤ 3k, such that for all i ≥ q, a i = a i+p . Let L ′ = b 1 , b 2 , . . . be the pp-reduction of the sequence L. We have i 1 < i 2 < . . . such that b r = a i r . We use a specific port-labeling which is partially an edge-coloring. The given automaton will only traverse colored edges, even though the graph is not completely edge-colored.

By Observation 2.2, we consider two cases. First assume that the sequence L ′ is finite. Then the pp-reduction of the sequence a q+1 , . . . , a q+p is a palindrome and hence the sequence a q+1 , . . . , a q+2p is a pseudo-palindrome. Choose some node w in the cycle of size 3 of G. Choose an arbitrary proper 3-coloring of the three edges of the cycle. Extend the proper 3-coloring to the rest of the graph except for the tail of each T . (This can be easily done, while proper edge 3-coloring of the entire graph, even of the subgraph T , is impossible). Label arbitrarily the remaining ports of the graph (those in the tails of copies of T ) by integers 0,1,2 at each node. It remains to compute the starting node of the automaton. From node w, traverse edges colored a q , a q-1 , . . . , a 1 . This traversal leads to a node u 0 . We claim that the automaton, starting at u 0 with the initial port i 0 never visits any tail of a copy of T and thus fails to explore G. During the first q steps, the automaton is at distance at most 3k from w because q ≤ 3k. At step q + 2rp, for r ≥ 0, the automaton is always at w by Observation 2.1, because a q , a q+1 , . . . , a q+2p is a pseudo-palindrome. Since p ≤ 3k, the automaton is again at distance at most 3k from w. Since w is on one of the 3k -2 cycles, the automaton never visits any tail of a copy of T , thus it never traverses non-colored edges. Hence A fails to explore G.

Assume from now on that L ′ is infinite. By Observation 2.2 L ′ inherits the property of periodicity: there exist q ′ ≤ q and p ′ ≤ 3k such that b r = b r+p ′ for all r ≥ q ′ . If the period is 2, we choose p ′ = 4 to avoid double edges (a cycle of length 2). Starting at a node u, label the edges of the cycle of size p ′ in G with colors b q ′ +1 , b q ′ +2 , . . . , b q ′ +p ′ . Extend the coloring to the rest of the graph except for the tail of each copy of T . Label arbitrarily the remaining ports of the graph by integers 0,1,2 at each node. It remains to compute the starting node of the automaton. From node u, traverse edges colored b q ′ , b q ′ -1 , . . . , b 1 . This traversal leads to a node u 0 . We claim that the automaton, starting in u 0 with the initial port i 0 never visits any tail of a copy of T and thus fails to explore G. During the first q steps, the automaton is at distance at most 3k from u because q ≤ 3k. At step i q ′ the automaton is in u and then it comes back to u every 2p steps because u is on the cycle of length p ′ , which is labeled to trap the automaton. Since p ≤ 3k, the automaton is again at distance at most 3k from u. Since u is on one of the 3k -2 cycles, the automaton never explores any tail of a copy T , thus it fails to explore G.

For every automaton with k states we showed a port labeling of G, an initial node u 0 and a port i 0 such that this automaton fails to explore G. Hence G ∈ G k .

Proof of Theorem 2.1. Now the proof of the theorem can be concluded as follows. For any k take the graph G with n ∈ O(k 3 ) nodes whose existence is guaranteed by Lemma 2.1. Hence G ∈ G k . Take a Universal Traversal Sequence of length O(n 3 log n) for all regular graphs of degree 3 and of size n. This sequence can be coded by an automaton with O(n 3 log n) states. Hence there exists a polynomial f (k), such that an automaton with f (k) states explores graph G regardless of the port labeling and of the starting node and port. This implies G ∈ G f (k) .

Exploration power of small automata

In this section we show that our conjecture concerning the hierarchy G k holds for k = 1, 2, i.e., G 1 is strictly included in G 2 , which is strictly included in G 3 . To this end we determine exactly elements of G 1 and of G 2 . Proposition 3.1 The class G 1 of regular graphs that can be explored by a memoryless automaton (an automaton with one state) consists of the single-node graph, the two-node clique, and all cycles.

Proof. The fact that the one-and two-node cliques and all cycles can be explored by a 1-state automaton is straightforward (for cycles the output function is λ(S 0 , i) = i + 1). Suppose that some other regular graph G belongs to G 1 . Since the only regular trees are the single-node graph and the two-node clique, the graph G must contain a simple cycle C. Since G itself is not a cycle, there are two cases: either there are nodes of G not in C or G contains a chord of C. In the latter case G contains a shorter cycle C ′ containing this chord. It follows that in the second case there are nodes of G not in C ′ . Hence, in any case, G contains a cycle C * and a node v not belonging to it. Let λ : {S 0 } × X → Y be the output function of an automaton with a single state S 0 exploring G. If λ(S 0 , i) = i, for all i, then, by Observation 1.1, it does not explore G. Otherwise, let i be such that λ(S 0 , i) = i. Label all ports on the cycle C * such that every edge of the cycle C * is labeled i at one of its extremity and λ(S 0 , i) at the other extremity. For this labeling, the automaton entering any node of the cycle by the initial port i perpetually explores only C * without ever visiting v. Hence it does not explore G. This contradiction implies that G cannot belong to G 1 .

In order to characterize the class G 2 we will need some graph theoretical facts. By a simple cycle we mean a cycle with non-repeating nodes. The following result is well known. Lemma 3.1 Every regular graph of degree larger than 2 contains a simple cycle of even length. Lemma 3.2 Every regular graph of degree larger than 2 and different from the 4-node clique contains a non-hamiltonian simple cycle of even length.

Proof. Take the simple cycle C of even length whose existence is guaranteed by Lemma 3.1. If it is not hamiltonian, we are done, so suppose that C is a hamiltonian cycle. First suppose that the graph is of degree at least 4. Take any node v of C. There must exist at least two chords of C with endpoint v, say {v, x} and {v, y}. Consider the cycle C ′ composed of the chord {v, y} and the part of C containing x (cf. Fig. 2 (a)). If the length of C ′ is even, this is a non-hamiltonian cycle of even length. Otherwise, one of the following cycles must have this property: either the cycle composed of {v, x} and of the part of C not containing y, or the cycle containing {v, x} and {v, y} and the part of C between x and y not containing v (the sum of lengths of these cycles is of the same parity as the length of C ′ ).

It remains to consider the case when the degree of G is 3. Consider two adjacent nodes v and w on C (cf. Fig. 2 (b) and(c)). Each of these nodes is an endpoint of a chord, {v, x} and {w, y}, respectively, with x = y. If these chords are not intersecting (when the cycle C is represented as a circle in the plane, cf. Fig. 2 (b)), there are two cases. If part a or part c of the cycle is of even size then the cycle (a, v, x) (resp. (c, y, w)) is as required. If both a and c are of odd size then part b must be of even size (because C is of even length) and the cycle (v, w, y, b, x) is as required. Hence suppose that the chords {v, x} and {v, y} intersect (cf. Fig. 2 (c Proof. Consider an n-node regular graph of degree larger than 2 and different from the 4-node clique. By Lemma 3.2 it contains a simple non-hamiltonian cycle C of even length. If there are at least two nodes outside of C, we are done. Hence assume that there exists exactly one node v outside of C. If C has a chord in G then both shorter cycles containing this chord have the required property. Hence we assume that C does not have chords. Since the degree of G is at least 3, all nodes of C must be adjacent to v. Hence v is of degree n -1. Since G is regular, it must be a clique. Since it is not the 4-node clique, it must be a clique with at least 5 nodes. Hence it contains a cycle of length at most n -2.

Our next result characterizes the class G 2 .

Proposition 3.2

The class G 2 of regular graphs that can be explored by a 2-state automaton consists of all cliques and of all cycles.

Proof. Since all cycles belong to class G 1 , they also belong to class G 2 . Consider any clique and the 2-state automaton with states S 0 and S 1 and the following transition and output functions: for all i, δ(S

0 , i) = S 1 δ(S 1 , i) = S 0 λ(S 0 , i) = i + 1 λ(S 1 , i) = i
It is easy to verify that the above automaton, starting at state S 0 at any node v of a clique, with any initial port, traverses the star centered at v and hence explores the clique.

It remains to prove that no regular graphs other than cycles and cliques belong to class G 2 . Suppose that such a graph G exists and let A be a 2-state automaton that explores G. Let S 0 and S 1 be the states of A, where S 0 is the initial state. Define, for every i,

δ 0 (i) = δ(S 0 , i) δ 1 (i) = δ(S 1 , i) λ 0 (i) = λ(S 0 , i) λ 1 (i) = λ(S 1 , i)
where δ and λ are the transition and output functions of A.

First suppose that δ 0 (i) = S 0 for some port number i. If λ 0 (i) = i then, by Observation 1.1, the automaton does not explore G. If λ 0 (i) = i then let C be a non-hamiltonian cycle in G (cf. Lemma 3.1). Label all ports on the cycle C by the sequence (i, λ 0 (i), i, λ 0 (i), . . .). For this labeling, the automaton entering any node of the cycle by the initial port i in state S 0 perpetually explores only C and thus fails to explore G.

Hence from now on we assume that δ 0 (i) = S 1 for all i.

Next suppose that λ 0 (i) = i, for all i.

If δ 1 (j) = S 0 , for all port numbers j, then let u be an arbitrary node in G. Let v 0 , v 1 , . . . , v d-1 be the d neighbors of u. If the automaton enters a node v k by port i in state S 0 , then it backtracks to u in state S 1 . If the automaton enters node u in state S 1 , then it leaves u in state S 0 moving to some v s . Thus, for this labeling, the automaton entering node v 0 by the initial port i leading to u explores only u and its neighbors. Since G is not a clique, the automaton fails to explore G.

Otherwise, let j be the port number for which δ 1 (j) = S 1 . If λ 1 (j) = j then, by Observation 1.1, the automaton does not explore G. If λ 1 (j) = j then let C be a non-hamiltonian cycle in G. Label all ports on the cycle C by the sequence (j, λ 1 (j), j, λ 1 (j), . . .). For this labeling, the automaton entering any node of the cycle by the initial port λ 1 (j) in state S 0 perpetually explores only C and thus fails to explore G.

Hence in the rest of the proof we assume that δ 0 (i) = S 1 for all i, and that λ 0 is not the identity function. We consider three cases.

Case 1: δ 1 (j) = S 0 and λ 1 (j) = j for some port number j. Let u be an arbitrary node in G. Let v 0 , v 1 , . . . , v d-1 be the d neighbors of u. At every v k , give the port number j to the edge leading to u. If the automaton enters a node v k by port j in state S 1 , then it backtracks to u in state S 0 . If the automaton enters node u in state S 0 , then it leaves u in state S 1 moving to some v s . Thus, for this labeling, the automaton entering node u by any initial port explores only u and its neighbors. Since G is not a clique, the automaton fails to explore G.

Case 2: δ 1 (j) = S 0 and λ 1 (j) = j for some port number j. Let i be a port number such that λ 0 (i) = i. Let C be a non-hamiltonian cycle of even length in G, existing in view of Lemma 3.2. Label all ports on the cycle C by the sequence (i, λ 0 (i), j, λ 1 (j), i, λ 0 (i), j, λ 1 (j), . . .). More precisely, if the cycle C is v 1 , v 2 , . . . , v 2k , v 1 , then an edge {v 2l , v 2l+1 } is labeled λ 0 (j) at v 2l and i at v 2l+1 . The edge {v 2l+1 , v 2l+2 } is labeled λ 0 (i) at v 2l+1 and j at v 2l+2 . For this labeling, the automaton entering node v 1 in state S 0 by the initial port i perpetually explores only C and thus fails to explore G.

Case 3: δ 1 (j) = S 1 for all port numbers j. There are two subcases.

Case 3.a: λ 0 ({0, . . . , d -1}) ∩ λ 1 ({0, . . . , d -1}) = ∅ Hence λ 1 is not bijective and therefore not injective. Thus there are two different port numbers j and j ′ such that λ 1 (j) = λ 1 (j ′ ) = k. At least one of j and j ′ is different from k. Without loss of generality assume j ′ = k. If j = k, let C be a cycle of size at most n -2 in G, existing in view of Lemma 3.3. Label all ports on the cycle C by the sequence (j, k, j, k, . . .). If j = k, let C be an edge of G. Label both port numbers of this edge by k. Let v be a node of C adjacent to a node u outside C. Such a node exists since G is connected. Label ports of edge e = {u, v} by j ′ at v and by λ 0 (i) at u, for some port number i. For this labeling, the automaton entering node u by the initial port i in state S 0 moves to v and perpetually explores C. Hence the automaton visits u and all nodes of C. Since the size of C is at most n -2, the automaton fails to explore G. Case 3.b: λ 0 ({0, . . . , d -1}) ∩ λ 1 ({0, . . . , d -1}) = ∅ Hence there exist some port numbers i and j such that λ 0 (i) = λ 1 (j) = k. If k = j then consider an edge e = {u, v} with both ports numbered j. By Observation 1.1, the automaton entering u by the initial port i in state S 0 visits only u and v. If k = j then let C be a non-hamiltonian cycle in G. Label all ports in the cycle C by the sequence (j, k, j, k, . . .). For this labeling, the automaton entering any node of the cycle by the initial port i perpetually explores only C and thus fails to explore G.

Hence for every regular graph G which is not a cycle or a clique and for any 2-state automaton A we showed a port labeling of G for which A does not visit all nodes of G. Thus G ∈ G 2 .

Propositions 3.1 and 3.2 imply that the class G 1 is strictly included in G 2 . In order to prove the strict inclusion of G 2 in G 3 , it is enough to describe a graph in G 3 which is neither a cycle nor a clique. Proof. Consider the 6-node graph G consisting of two disjoint cycles of length 3 whose nodes are connected by edges forming a perfect matching (cf. Fig. 3). We will show that G can be explored by a 3-state automaton. More precisely we show that this can be done by the following automaton A:

• Set of states {U, D, B}, where D is the initial state;

• Transition function δ(D, i) = B, δ(B, i) = U , δ(U, i) = D, for any i;

• Output function λ(D, i) = i + 1, λ(B, i) = i, λ(U, i) = i + 1, for any i. First notice that if A enters a node u in state D during exploration (excluding the first step), then the automaton visits node u, and each of its three neighbors, at least once, for any port assignment. One of u's neighbor is visited just before entering u in state D, and the two other neighbors are visited during the three next steps.

Let us consider the behavior of A in G. At step 4, A enters some node u in state D. After three more steps, A enters another node v in state D. After again three more steps, A enters a node w in state D. Node w is different from v. It is also different from u because edges {u, v} and {v, w} are different, and there are no multiple edges in G. Therefore, three different nodes of G are entered by A in state D during exploration. These three nodes and all of their neighbors are thus visited at least once by the automaton. Since any set of three nodes of G is a dominating set, all nodes of G are visited by A, for any port labeling and for any starting position.

Conclusion

We showed that a polynomial increase of the number of states of a robot results in augmenting the capability to explore graphs. The main open problem is to prove or disprove our conjecture which says that any increase of the number of states of a robot enables to explore more graphs, i.e., that the hierarchy G k is strict. Another interesting question is to show how complex it is to decide whether a given graph G can be explored by a k-state automaton. More precisely, can the decision problem "G ∈ G k ?", for a given input (G, k), be decided in polynomial time?

Figure 1 :

 1 Figure 1: The subgraph T

Figure 2 :

 2 Figure 2: (a) degree at least 4, (b) and (c) Chords in the cycle C

Proposition 3 . 3

 33 The class G 3 contains a graph which is neither a cycle nor a clique.

Figure 3 :

 3 Figure 3: A graph in G 3 \ G 2

Corollary 3 . 1

 31 Propositions 3.1, 3.2 and 3.3 imply the following corollary. Both inclusions G 1 ⊂ G 2 ⊂ G 3 are strict.

* This work was done while the authors were with University Paris-Sud (LRI). Additional support by the project "PairAPair" of the ACI Masses de Données, and by the project "Grand Large" of INRIA.

† Supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais.