Sabine Trellu

Sabrina Dadoun

Francis Berenbaum

Bruno Fautrel

Laure Gossec
email: laure.gossec@psl.aphp.fr

S Trellu¹

S Dadoun¹

F Berenbaum²

B Fautrel¹

L Gossec¹

Pr Laure Gossec

Intra-articular injections in thumb osteoarthritis: a systematic review and meta-analysis of randomized controlled trials

Keywords: Thumb osteoarthritis, intra-articular injection, corticosteroids, hyaluronic acid, pain, functional capacity

published or not. The documents may come

Introduction

Osteoarthritis (OA) of the carpo-metacarpal joint of the thumb is a common condition, affecting at least 30% of women over the age of 65 [START_REF] Cushnagan | Study of 500 patients with limb joint osteoarthritis. Analysis by age, sex and distribution of joint symptomatic sites[END_REF]. The life impact and disability associated to hand OA are significant. Hand disability is frequent in patients suffering from thumb OA, with a reduction of grip strength and difficulty writing or fingering small objects [START_REF] Dahaghin | Prevalence and determinants of one month hand pain and hand related disability in the elderly[END_REF][START_REF] Zhang | Prevalence of symptomatic hand osteoarthritis and its impact on functional status among the elderly: the Framingham Study[END_REF]. Few treatments have been assessed in thumb OA. According to the European League Against Rheumatism (EULAR) and the American College of Rheumatology (ACR) recommendations, the optimal management of thumb OA requires a combination of non-pharmacological measures such as local application of heat or splints, and pharmacological treatment modalities [START_REF] Hochberg | American College of Rheumatology 2012 recommendations for the use of nonpharmacologic and pharmacologic therapies in osteoarthritis of the hand, hip, and knee[END_REF][START_REF] Zhang | EULAR evidence based recommandations for the management of hand osteoarthritis: report of a Task Force of the EULAR Standing Commitee for International Clinical Studies Including Therapeutics (ESCISIT)[END_REF]. Local treatments are preferred to systemic treatments. For intra-articular injections, experts' opinion differs in thumb OA [START_REF] Hochberg | American College of Rheumatology 2012 recommendations for the use of nonpharmacologic and pharmacologic therapies in osteoarthritis of the hand, hip, and knee[END_REF][START_REF] Zhang | EULAR evidence based recommandations for the management of hand osteoarthritis: report of a Task Force of the EULAR Standing Commitee for International Clinical Studies Including Therapeutics (ESCISIT)[END_REF]. Evidence of efficacy of intra-articular hyaluronic acid or corticosteroid injections in thumb OA is scarce, while largely investigated in hip and knee (6 -10). For example in knee OA, intra-articular corticosteroids are reported to decrease pain [START_REF] Bellamy | Intraarticular corticosteroid for treatment of osteoarthritis of the knee[END_REF] whereas hyaluronic acid injection seems to relieve pain and to improve functional capacity [START_REF] Lo | Intra-articular hyaluronic acid in treatment of knee osteoarthritis: a meta-analysis[END_REF][START_REF] Wang | Therapeutic effects of hyaluronic acid on osteoarthritis of the knee. A meta-analysis of randomized controlled trials[END_REF][START_REF] Bellamy | Viscosupplementation for the treatment of osteoarthritis of the knee[END_REF]. Both of these modalities are recommended by international associations for the treatment of lower-limb OA [START_REF] Hochberg | American College of Rheumatology 2012 recommendations for the use of nonpharmacologic and pharmacologic therapies in osteoarthritis of the hand, hip, and knee[END_REF][START_REF] Zhang | OARSI recommendations for the management of hip and knee osteoarthritis, Part III: Changes in evidence follwing systematic cumulative update of research published through January 2009[END_REF][START_REF] Jordan | EULAR Recommendations 2003: an evidence based approach to the management of knee osteoarthritis: Report of a Task Force of the Standing Committee for International Clinical Studies Including Therapeutic Trials (ESCISIT)[END_REF]. In thumb OA, corticosteroid injections are recommended, and hyaluronic acid injections may be useful, according to the EULAR experts [START_REF] Zhang | EULAR evidence based recommandations for the management of hand osteoarthritis: report of a Task Force of the EULAR Standing Commitee for International Clinical Studies Including Therapeutics (ESCISIT)[END_REF]. However both of these injection modalities are not recommended by the ACR experts [START_REF] Hochberg | American College of Rheumatology 2012 recommendations for the use of nonpharmacologic and pharmacologic therapies in osteoarthritis of the hand, hip, and knee[END_REF]. The objective of the present study was to assess short-term and medium-term efficacy on pain, functional capacity and pulp pinch force of intra-articular injections of corticosteroids or hyaluronic acid in patients with thumb OA in controlled trials, by performing a meta-analysis of published articles.

Methods

A systematic search was performed in PubMed Medline and EMBASE databases up to August 2013 with an update up to August 2014, without limitation of year of publication or journal, using the following keywords: (((("thumb" [MeSH Terms] OR "thumb"[All Fields]) OR ("trapeziometacarpal joint"[MeSH Terms] OR "trapeziometacarpal"[All Fields]) OR "first metacarpal-carpal"[All Fields] OR "carpometacarpal"[All Fields]) "osteoarthritis") OR "rhizarthrosis"[All Fields]) AND ("injection"[MeSH Terms] OR "injection"[All Fields] OR "injections"[All Fields]). The limits were English, French, German or Spanish language and controlled trials. In addition, the Cochrane database, reference lists of the papers initially detected to identify additional relevant reports were manually searched, as were EULAR, OARSI and ACR abstracts of the last 5 years. Studies were initially selected on their title and abstract by one author (ST), then on their full text. All controlled trials reporting the efficacy on pain and/or functional capacity and/or pulp pinch force of intra-articular injections of corticosteroids and/or hyaluronic acid in thumb OA, were selected. For studies with incomplete data, the corresponding authors were contacted by email.

Data collection:

Using a predetermined form, the following features were collected: blinding, intention-to-treat analysis and number of participants who completed the follow-up. The Jadad scale (13) was applied to assess the methodological quality: 5 points can be awarded, with higher scores indicating higher quality. The Cochrane risk of bias tools was also applied. For each trial, demographic characteristics (sex, mean age), thumb OA features, type of corticosteroids and/or hyaluronic acid (with doses and number of injections), type of placebo if needed and duration of follow-up were collected. Pain was extracted from the studies by a 100mm visual analogue scale; functional capacity was extracted as available by the following scores: Disabilities of the Arm, Shoulder and Hand [START_REF] Hudak | Development of an upper extremity outcome measure: the DASH (Disabilities of the Arm, Shoulder and Hand). The Upper Extremity Collaborative Group (UECG)[END_REF], the Dreiser functional index [START_REF] Dreiser | Validation of an algofunctional index for osteoarthritis of the hand[END_REF], the Purdue Pegboard Test [START_REF] Desrosiers | The Purdue Pegboard Test: normative data for people aged 60 and over[END_REF] and/or the Duruöz Hand Index [START_REF] Duruöz | Development and validation of a rheumatoid hand functional disability scale that assesses functional handicap[END_REF]; because functional capacity was assessed by different scores, each score was transformed linearly to fit the range 0-100, in which 0 was the best situation and 100 the worst. Pulp pinch force was extracted by pulp to pulp pinch force in pounds [START_REF] Mathiowetz | Reliability and validity of grip and pinch strength evaluations[END_REF].

Studies were classified according to the injection type (hyaluronic acid versus placebo, corticosteroids versus placebo and hyaluronic acid versus corticosteroids). Efficacy was assessed by the change in pain and/or functional capacity and/or pulp pinch force status between baseline and week 4, week 12 and week 24 to 26 (as available according to the studies, called week 24 in the text) in corticosteroids, hyaluronic acid and placebo groups.

Statistical analysis

In each study, the standardized response mean (SRM) was determined to assess the magnitude of treatment effect. The SRM is calculated as the mean change divided by the standard deviation of the change. Improvement was considered as a positive change. Pooled SRMs were calculated by meta-analysis, using the Mantel-Haenszel method with RevMan version 5.2 statistical software (Review Manager, Copenhagen, Denmark). Statistical heterogeneity was measured by I². All meta-analyses were carried out with use of random effects model in case of significant heterogeneity.

Results

Literature search results and trial characteristics

Initially, 84 potentially relevant articles were screened; 76 were excluded (Figure 1). For 3 studies, the results described in the articles did not allow meta-analysis, but the studies are reported descriptively here (Table 1) [START_REF] Figen Ayhan | The evaluation of efficacy and tolerability of hylan G-F 20 in bilateral tjumb base osteoarthritis: 6 months follow-up[END_REF][START_REF] Fuchs | Intra-articular hyaluronic acid compared with corticoid injections for the treatment of rhizarthrosis[END_REF][START_REF] Heyworth | Hylan versus corticosteroid versus placebo for the treatment of basal joint arthritis: a prospective, randomized, double-blinded clinical trial[END_REF]. After adding 1 report from congress abstracts, 9 reports were included (Table 1) [START_REF] Figen Ayhan | The evaluation of efficacy and tolerability of hylan G-F 20 in bilateral tjumb base osteoarthritis: 6 months follow-up[END_REF][START_REF] Fuchs | Intra-articular hyaluronic acid compared with corticoid injections for the treatment of rhizarthrosis[END_REF][START_REF] Heyworth | Hylan versus corticosteroid versus placebo for the treatment of basal joint arthritis: a prospective, randomized, double-blinded clinical trial[END_REF][START_REF] Bahadir | Comparison of therapeutic effects of sodium hyaluronate and corticosteroid injections on trapeziometacarpal joint osteoarthritis[END_REF][START_REF] Mandl | A Randomized Controlled Trial of Hylan G-F 20 for the Treatment of Carpometacarpal Osteoarthritis[END_REF][START_REF] Meenagh | A randomised controlled trial of intra-artcular corticosteroid injection of the carpometacarpal joint of the thumb osteoarthritis[END_REF][START_REF] Monfort | Comparative efficacy of intra-articular hyaluronic acid and corticoid injections in osteoarthritis of the first carpometacarpal joint: Results of a 6-month single-masked randomized study[END_REF][START_REF] Roux | Injection of intra-articular sodium hyaluronate (Sinovial®) into the carpometacarpal joint of the thumb (CMC1) in osteoarthitis. A prospective evaluation of efficacy[END_REF][START_REF] Stahl | Comparison of intraarticular injection of depot corticosteroid and hyaluronic acid for treatment of degenerative trapeziometacarpal joints[END_REF]. Thus this meta-analysis included 428 patients; 168 (39.2%) treated by hyaluronic acid injections, 166 (38.8%) by corticosteroids injections and 94 (22.0%) by placebo. Mean (standard deviation, SD) age was 63 (2.3) years and 368 patients (86%) were females (Table 1). The methodological quality was moderate: the mean Jadad score was 2.2 (SD 2.8) (range 1-5); 4 (67%) trials performed intention-to-treat analyses. Of the 6 trials, 3 described precisely the patient selection or outcome, 2 used a concealed random allocation, 5 presented difference in changes with standard error of the mean and 1 with interquartile range. The Cochrane risk of bias tool also indicated moderate quality (online figure S2). The injection was guided by X-ray in 2 studies, by ultrasound in 1 study and not guided in 3 studies. The number of injections varied across studies and sometimes across study groups (Table 1). Heterogeneity was substantial, varying between 0 and 97 for I 2 across the analyses.

Efficacy of corticosteroids injections versus placebo

Mandl's study [START_REF] Mandl | A Randomized Controlled Trial of Hylan G-F 20 for the Treatment of Carpometacarpal Osteoarthritis[END_REF] indicated no difference on pain at week 24 between two groups of 62 patients with 2 injections (Table 2). Meenagh's study [START_REF] Meenagh | A randomised controlled trial of intra-artcular corticosteroid injection of the carpometacarpal joint of the thumb osteoarthritis[END_REF] compared 2 groups of 20 patients with one injection, and showed efficacy for corticosteroids on pain at week 24 with a large effect size (Table 2). Heyworth's study [START_REF] Heyworth | Hylan versus corticosteroid versus placebo for the treatment of basal joint arthritis: a prospective, randomized, double-blinded clinical trial[END_REF] indicated no difference on pain at week 24 after 2 injections between corticosteroids (22 patients) and placebo (18 patients), but the data could not be included in the meta-analysis (Table 3). The pooled analysis (82 patients in each arm) showed no difference between the two treatments for pain (SRM = -1.20 [-3.69; 1.29]) (online figure S1 and Table 3).

Efficacy of hyaluronic acid injections versus placebo

Roux's study [START_REF] Roux | Injection of intra-articular sodium hyaluronate (Sinovial®) into the carpometacarpal joint of the thumb (CMC1) in osteoarthitis. A prospective evaluation of efficacy[END_REF] compared one versus three injection of hyaluronic acid with 14 patients in each group at week 12. Patients who received one injection of hyaluronic acid were considered as placebo (Table 1). It showed efficacy on pain and functional capacity at week 12 for 3 injections with a large effect size (Table 2). Mandl's study [START_REF] Mandl | A Randomized Controlled Trial of Hylan G-F 20 for the Treatment of Carpometacarpal Osteoarthritis[END_REF] showed efficacy of hyaluronic acid (62 patients) on functional capacity and of placebo (62 patients) on pain at week 24 (Table 2). Figen Ayhan's study [START_REF] Figen Ayhan | The evaluation of efficacy and tolerability of hylan G-F 20 in bilateral tjumb base osteoarthritis: 6 months follow-up[END_REF](not included in the meta-analysis) compared with baseline but not together 2 groups of 29 patients. It indicated lower pain and improvement of functional capacity at week 24 after one injection of hyaluronic acid. Heyworth's study [START_REF] Heyworth | Hylan versus corticosteroid versus placebo for the treatment of basal joint arthritis: a prospective, randomized, double-blinded clinical trial[END_REF](not included in the meta-analysis) showed no difference on pain and functional capacity at week 12 between hyaluronic acid (20 patients) and placebo (18 patients). The pooled analyses of the studies (74 patients in each arm) showed superiority of hyaluronic acid on functional capacity (SRM= -1.14 [-1.69; -0.60]) but not on pain (SRM= -0.95 [-3.87; 1.97]) (online figure S1 and Table 3).

Efficacy of hyaluronic acid versus corticosteroids injections

Mandl's study [START_REF] Mandl | A Randomized Controlled Trial of Hylan G-F 20 for the Treatment of Carpometacarpal Osteoarthritis[END_REF] showed no difference between corticosteroids (62 patients) and hyaluronic acid (62 patients) on functional capacity and pain at week 24 after 2 injections (Table 2). Monfort's study [START_REF] Monfort | Comparative efficacy of intra-articular hyaluronic acid and corticoid injections in osteoarthritis of the first carpometacarpal joint: Results of a 6-month single-masked randomized study[END_REF] compared two groups (48 patients for hyaluronic acid group, 40 for corticosteroids group) who received three injections. It showed efficacy of corticosteroids on functional capacity at week 12 and 24, with no difference on pain (Table 2). Bahadir's study [START_REF] Bahadir | Comparison of therapeutic effects of sodium hyaluronate and corticosteroid injections on trapeziometacarpal joint osteoarthritis[END_REF] compared two groups (20 patients in each) with one injection of corticosteroids or 3 of hyaluronic acid. It showed efficacy of hyaluronic acid on pain and functional capacity at all time points and on pulp pinch force at week 12 and 24 with large effect sizes (Table 2). Stahl's study [START_REF] Stahl | Comparison of intraarticular injection of depot corticosteroid and hyaluronic acid for treatment of degenerative trapeziometacarpal joints[END_REF] showed efficacy of corticosteroids (25 patients) on pain at week 4 and of hyaluronic acid (27 patients) on pulp pinch force at week 24 after one injection (Table 2). Fuchs' study [START_REF] Fuchs | Intra-articular hyaluronic acid compared with corticoid injections for the treatment of rhizarthrosis[END_REF](non included in the meta-analysis) compared 2 groups of 28 patients receiving 3 injections and indicated superiority of corticosteroids until week 12 and of hyaluronic acid on week 24 on pain. For pulp pinch force no difference was evidenced. Heyworth's study [START_REF] Heyworth | Hylan versus corticosteroid versus placebo for the treatment of basal joint arthritis: a prospective, randomized, double-blinded clinical trial[END_REF](not included in the meta-analysis) indicated no difference on each outcome at all time points. Finally, 157 participants with hyaluronic acid and 147 with corticosteroids were available for the comparison of pain and functional capacity and 92 for the comparison on pulp pinch force (Table 3). The pooled analyses (Table 3) indicated no difference between hyaluronic acid and corticosteroids at short term follow-up but hyaluronic acid seemed superior on pulp pinch force status, and corticosteroids on pain at week 24 (online figure S1 and Table 3). For hyaluronic acid vs corticosteroids and pain at week 24, the results are almost entirely driven by a strongly positive study (N=40) while 3 other studies (N=274) found no effect.

Heterogeneity

The heterogeneity was significant for all outcomes: range of I² over the time points was respectively 85% to 97%, 34% to 95% and 0% to 82% for pain, functional capacity and pulp pinch force status (online Figure S1).

Discussion

This meta-analysis found great heterogeneity in the results. Against placebo, only hyaluronic acid appeared useful. However studies comparing hyaluronic acid and corticosteroids indicated hyaluronic acid may be useful in thumb OA in particular to increase functional capacity, and corticosteroid to decrease pain. These results should be further confirmed.

This study has some weaknesses. Despite the high prevalence of hand OA, there were few controlled trials in the literature, with a limited number of patients included in each. Many sources of heterogeneity were present among these studies. For example, the outcomes were heterogeneous. Pain, sometimes functional capacity and pulp pinch force were assessed, whereas the Outcome Measures in Rheumatology (OMERACT) consensus advises to evaluate joint activity and patient global assessment too [START_REF] Kloppenburg | Report from the OMERACT Hand Osteoarthritis Special Interst Group: advances and future research priorities[END_REF]. For functional capacity, each study used a different score with some tests evaluating not only the hand but the arm in its globality. Only 2 studies used a score (Dreiser functional index [START_REF] Dreiser | Validation of an algofunctional index for osteoarthritis of the hand[END_REF]) validated in hand OA, according to the OMERACT Hand Osteoarthritis Group [START_REF] Kloppenburg | Report from the OMERACT Hand Osteoarthritis Special Interst Group: advances and future research priorities[END_REF]. Length of folIow up was heterogeneous too, varying from 4 to 52 weeks, making difficult the comparison between the studies, which is why 3 different endpoints were used to better model the results. The number of injections was variable as was the technique of intra-articular injection making reproductibility and pooling difficult. In one study [START_REF] Roux | Injection of intra-articular sodium hyaluronate (Sinovial®) into the carpometacarpal joint of the thumb (CMC1) in osteoarthitis. A prospective evaluation of efficacy[END_REF], one injection of hyaluronic acid was considered as a placebo. This is based on a study realised in 1995 in knee OA which demonstrated that one injection of hyaluronic acid was no more effective than placebo. However, in the first carpo-metacarpal which is a small joint, only one injection may be sufficient. Finally, the majority of the studies used for this meta-analysis didn't have a high methodological quality highlighting the difficulties inherent to study design for injections trials. However this study also has strengths. This review and meta-analysis is important because of the frequency of thumb OA and its impact on everyday life [START_REF] Cushnagan | Study of 500 patients with limb joint osteoarthritis. Analysis by age, sex and distribution of joint symptomatic sites[END_REF][START_REF] Dahaghin | Prevalence and determinants of one month hand pain and hand related disability in the elderly[END_REF][START_REF] Zhang | Prevalence of symptomatic hand osteoarthritis and its impact on functional status among the elderly: the Framingham Study[END_REF]. In this meta-analysis, the literature search was exhaustive, with searches in several databases and was updated over one year. The data extracted from the studies were analysed descriptively but also meta-analysed after having pooled the outcome measures in order to increase the strength of the analysis where possible. As the studies were heterogeneous in term of results and methodology, random effect models were used.

EULAR recommends intra-articular injections of corticosteroids in thumb OA but this recommendation was based on one small randomised controlled trial and one uncontrolled trial [START_REF] Zhang | EULAR evidence based recommandations for the management of hand osteoarthritis: report of a Task Force of the EULAR Standing Commitee for International Clinical Studies Including Therapeutics (ESCISIT)[END_REF]. Hyaluronic acid was also endorsed by the EULAR recommendations [START_REF] Zhang | EULAR evidence based recommandations for the management of hand osteoarthritis: report of a Task Force of the EULAR Standing Commitee for International Clinical Studies Including Therapeutics (ESCISIT)[END_REF]. The results of this meta-analysis may comfort the EULAR recommendations for hyaluronic acid and -less so -for corticosteroids. Furthermore, in knee OA, one study explored an associated injection of hyaluronic acid and corticosteroids: results were in favour of the association for the reduction of pain [START_REF] Grecomoro | Therapeutic synergism between hyaluronic acid and dexamethasone in the intra-articular treatment of the osteoarthritis of the knee: a preliminary open study[END_REF]. Synergy between these 2 drugs should be more explored. To conclude, our data suggest some benefit for hyaluronic acid and corticosteroids injections in thumb OA but the assessment of efficacy is limited by the heterogeneity of the results observed. Other controlled trials with a higher number of patients would be useful.

AUTHORSHIP AND CONTRIBUTORSHIP

All of the authors fulfil the following 4 criteria:  Substantial contributions to the conception or design of the work; or the acquisition, analysis, or interpretation of data for the work; AND  Drafting the work or revising it critically for important intellectual content; AND  Final approval of the version to be published; AND  Agreement to be accountable for all aspects of the work in ensuring that questions related to the accuracy or integrity of any part of the work are appropriately investigated and resolved.

The guarantors who accept full responsibility for the work and/or the conduct of the study, had access to the data, and controlled the decision to publish are for this paper, Sabine Trellu and Laure Gossec.

Grants: none

Competing interests:

Figure 1 Flow chart Table 1 Baseline characteristics of patients in randomised controlled trials of intra-articular injections in thumb osteoarthritis.

Table 2 Standardised response means in controlled trials comparing intra-articular injections on pain, functional capacity and/or pulp pinch force status in patients with thumb osteoarthritis.

Table 3 Pooled standardised response mean for intra-articular injections in thumb osteoarthritis

Online supplement only Figure S1

A: Comparison placebo versus corticosteroids; B: comparison placebo versus hyaluronic acid, C: comparison corticosteroids versus hyaluronic acid.

Online supplement only Figure S2

Cochrane risk of bias tool NA: not available. DASH: Disability of the Arm, Shoulder and Hand [START_REF] Hudak | Development of an upper extremity outcome measure: the DASH (Disabilities of the Arm, Shoulder and Hand). The Upper Extremity Collaborative Group (UECG)[END_REF]. Dreiser: Dreiser functional index [START_REF] Dreiser | Validation of an algofunctional index for osteoarthritis of the hand[END_REF]. PPT: Purdue Pegboard Test [START_REF] Desrosiers | The Purdue Pegboard Test: normative data for people aged 60 and over[END_REF]. DHI: Durüoz Hand Index [START_REF] Duruöz | Development and validation of a rheumatoid hand functional disability scale that assesses functional handicap[END_REF]. Significant results are in bold type.

Figure 1 :

 1 Figure 1: Flow chart

  Comparison of hyaluronic acid versus corticosteroids. Outcome: Functional capacity at week 12 Comparison of hyaluronic acid versus corticosteroids. Outcome: Functional capacity at week 24 Comparison of hyaluronic acid versus corticosteroids. Outcome: Pulp pinch force at week 4 Comparison of hyaluronic acid versus corticosteroids. Outcome: Pulp pinch force at week 12 [1.56, 3.22] -0.66 [-1.02, -0.30] -0.47 [-0.90, -0.05] -0.19 [-0.74, 0.35]

/exp OR injection) 65 records identified through Pubmed (((thumb or trapeziometacarpal or first metacarpal-carpal or carpometacarpal) osteoarthritis) or rhizarthrosis )AND injection 84 records non-duplicated 2 records identified through manual search in congress abstracts 6 records included in the meta-analysisTable 1

 1 Baseline characteristics of patients in randomised controlled trials of intra-articular injections in thumb osteoarthritis.

	64 records identified through Embase thumb/exp OR thumb OR trapeziometacarpal OR metacarpalcarpal OR carpometacarpal AND ('osteoarthritis'/exp OR osteoarthritis) AND Study Duration (weeks) Number of patients Women (%) (100) ('injection'Study, publication year Intervention Number of injections 2009 -SH (5mg/0.5ml) -3 weekly for SH Bahadir et al (22), -TA (20mg/0.5ml) -1 for TA 52 40 40	Mean age ± SD or (min-max) (years) 61.8±8.2	Guidance of the injection None	Jadad score 1
	Mandl et al (23),	-TA (40mg/1ml) puis	2	26	188		127		66.5	None	1
	2012	1ml 0.5% bupivacaine					(67.7)		(45-89)
		-Hylan G-F 20 1ml
		-Bupivacaine 1ml 0.5%
	(24), 2004 Meenagh et al	-Saline 0.25ml -TA (5mg/0.25ml)	1	24	40		(90) 36	abstracts (41-71) Records excluded by reading the 59.9 X-ray 5
									-20 not hand osteoarthritis
	Monfort et al (25), 2014 2007 Roux et al (26),	-Bethametasone (1.5mg/0.5ml) -Suplasyn (5mg/0.5ml) -SH 1ml	3 -1 for -3 for SH 9 records included of 24 88 which 6 included in 12 42		77 (87.5) (90.5) 38	-23 not hyaluronic 62.8±8.7 ultrasound acid/corticosteroids -19 not controlled -13 not clinical 64.8±8.0 X-ray	3 2
				placebo	meta-analysis
	Stahl et al (27),	-SH(15mg/ml)	1	24	52		46		62	None	2
	2005	-Methylprednisolone					(88)		(37-91)
		acetate (40mg/ml)
	Figen Ayhan et al	-Hylan G-F 20 1ml in	1	24	33	with	33		62.6 +/-6.4	None	3
	(19), 2009	one hand				bilateral	(100)
	Not included in	-Saline 1ml in the other			hand OA
	meta-analysis	hand
	Fuchs et al (20),	-Sodium	hyaluronate,	3	26	56		45		60.25	None	1
	2006	1ml						(75)
	Not included in	-TA, 1ml
	meta-analysis
	Heyworth et al	-Hylan G-F 20, 1ml	2	26	60		52		63 +/-1	None	5
	(21), 2008	-Saline, 1ml then					(87)
	Not included in	Sodium betamethasone,
	meta-analysis	1ml
		-Saline, 1ml

SD: standard deviation. TA: triamcinolone acetonide. SH: sodium hyaluronate

Table 2

 2 Standardised response mean of controlled trials comparing injections for pain, functional capacity and/or pulp pinch force status in patients with hand osteoarthritis.

	Reference	Type of injection	Comparator Outcome measure	Week 4	Week 12	Week 24
				Pain			1.19 [0.51; 1.87]	1.38 [0.68; 2.07]	9.31 [7.07; 11.55]
	Bahadir et al (2009) (22)	Triamcinolone acetonide	Sodium Hyaluronate	Functional capacity (DHI)	3.64 [2.60; 4.69]	1.95 [1.18; 2.71]	2.39 [1.56; 3.22]
				Pulp	pinch	force	0.38	1.03	2.16
				status			[-0.24; 1.01]	[0.37; 1.69]	[1.37; 2.96]
		Triamcinolone	Hylan	Pain			NA	NA	0.15 [-0.21; 0.50]
		acetonide	G-F 20	Functional capacity (DASH)	NA	NA	-0.66 [-1.02; 0.30]
	Mandl et al (2012) (23)	Triamcinolone acetonide	Bupivacaine	Pain				NA	0.04 [-0.31; 0.39]
				Pain			NA	NA	0.49 [0.13; 0.85]
		Hylan G-F 20	Bupivacaine
				Functional capacity (DASH)	NA	NA	-0.98 [-1.35; -0.60]
	Meenagh et al (2004) (24)	Triamcinolone acetonide	Saline	Pain			NA	NA	-2.50 [-3.35; -1.65]
	Montfort et al 2014 (25)	Betamethasone acetate	Suplasyn®	Pain Functional	capacity	0,23 [-0.20; 0.65] 0.00	-0.03 [-0.44; 0.39] -0.75	-0.21 [-0.63; 0.21] -0.47
				(Dreiser)		[-0.42; 0.42]	[-1.19;-0.32]	[-0.90; -0.05]
	Roux	Sodium	Sodium	Pain			NA	-2.
	et	hyaluronate	Hyaluronate
	al (2007) (26)	(3 injections)	(1 injection)

49 [-3.60;-1.38] NA

	Functional capacity (Dreiser)	NA	-1.

61 [-2.56;-0.67] NA

				Pain	-0.90 [-1.47;-0.33]	-0.13 [-0.68; 0.41]	0.00 [-0.54; 0.54]
	Stahl et al (2005) (27)	Methylprednisolo ne acetate	Sodium Hyaluronate	Functional capacity (PPT)	0.00 [-0.54; 0.54]	0.00 [-0.54; 0.54]	-0.19 [-0.77; 0.35]
				Pulp pinch	0.00	0.00	1.23
				force status	[-0.54; 0.54]	[-0.54; 0.54]	[0.63; 1.83]

Table 3

 3 Pooled SRMs for intra-articular injections in thumb osteoarthritis

Type of injection Outcome measure Week 4 Week 12 Week 24

	Online supplement only figure S1 A: Comparison placebo versus corticosteroids; B: comparison
	placebo versus hyaluronic acid, C: comparison corticosteroids versus hyaluronic acid.
	A. Comparison corticosteroids versus placebo. Outcome Pain at week 24
							Std. Mean Difference
	Corticosteroids vs placebo Mandl 2012 Study	Pain 62 N		62 N	NE	NE IV, Random, 95% CI 0.04 [-0.31, 0.39]	-1.20 [-3.69; 1.29] IV, Random, 95% CI
	Meenagh 2004		20	20	-2.50 [-3.35, -1.65]
	Hyaluronic acid vs Total (95% CI) placebo I² = 97%	Pain 82 Functional capacity NE NE 82 -1.20 [-3.69, 1.29]	-0.95 [-3.97; 1.97] NE -1.14 [-1.69; -0.60] NE -4 -2 0 2 4
			Pain			0.16 [-0.89; 1.21] Favours [Corticosteroids] Favours [Placebo] 0.37 [-0.45; 1.18] 1.44 [0.14; 2.74]
	B. Comparison hyaluronic acid versus placebo. Outcome Functional capacity at week 12 Hyaluronic acid vs Study IV, Random, 95% CI IV, Random, 95% CI N N corticosteroids Functional capacity 1.13 [-0.49; 2.73] 0.36 [-1.02; 1.75] 0.20 [-0.77; Std.
	Mandl 2012	62	Pulp pinch force 62	0.17 [-0.25; 0.58] -0.98 [-1.35, -0.60]	0.50 [-0.51; 1.50]	-1.66 [-0.75; -2.57]
	Significant results are in bold type Roux 2007 12 12	-1.61 [-2.56, -0.67]
	NE: not estimable Total (95% CI) 74		74	-1.14 [-1.69, -0.60]
	I² = 34%						-4	-2	0	2	4
						Favours [hyaluronic acid] Favours [Placebo]
	Comparison hyaluronic acid versus placebo. Outcome: Pain at week 12
	Study	N		N		IV, Random, 95% CI	IV, Random, 95% CI
	Mandl 2012	62	62		0.49 [0.13, 0.85]
	Roux 2007	62	12		-2.49 [-3.60, -1.38]
	Total (95% CI)	74	74		-0.95 [-3.87, 1.97]
	I² = 96%						-4	-2	0	2	4
						Favours [hyaluronic acid] Favours [Placebo]

Mean Difference Std. Mean Difference Std. Mean Difference Corticosteroids Placebo Hyaluronic acid Std. Mean Difference Placebo Std. Mean Difference Hyaluronic acid Placebo C

  . Comparison of hyaluronic acid versus corticosteroids. Outcome: Pain at week 4 Comparison of hyaluronic acid versus corticosteroids. Outcome: Pain at week 12 Comparison of hyaluronic acid versus corticosteroids. Outcome: Pain at week 24 Comparison of hyaluronic acid versus corticosteroids. Outcome: Functional capacity at week 4

				Std. Mean Difference
	Study	N	N	IV, Random, 95% CI		IV, Random, 95% CI
	Bahadir 2009 Stahl 2005 Monfort	20 27 48	20 25 40	1.19 [0.51, 1.87] -0.90 [-1.47, -0.33] 0.23 [-0.20, 0.65]
	Total (95% CI)	95	85	0.16 [-0.89, 1.21]
	I² = 91%			-4	-2		0	2	4
				Favours [hyaluronic acid] Favours [corticosteroids] 74
	Study	N	N	IV, Random, 95% CI		IV, Random, 95% CI
	Stahl 2005 Monfort Bahadir 2009	27 48 20	25 40 20	-0.13 [-0.68, 0.41] -0.03 [-0.44, 0.39] 1.38 [0.68, 2.07]
	Total (95% CI)	95	85	0.37 [-0.45, 1.18]
	I² = 85%			-4	-2		0	2	4
				Favours [hyaluronic acid] Favours [corticosteroids]
				Std. Mean Difference	Std. Mean Difference
	Study	N	N	IV, Random, 95% CI		IV, Random, 95% CI
	Monfort Mandl 2012 Bahadir 2009	48 62 20	40 62 20	-0.21 [-0.63, 0.21] 0.15 [-0.21, 0.50] 9.31 [7.07, 11.55]
	Stahl 2005	27	25	0.00 [-0.54, 0.54]
	Total (95% CI)	157	147	1.44 [0.14, 2.74]
	I² = 96%			-10	-5	0	5	10
				Favours [hyaluronic acid] Favours [corticosteroids]
							Std. Mean Difference
	Study			IV, Random, 95% CI	IV, Random, 95% CI
	Bahadir 2009			3.64 [2.60, 4.69]
	Monfort Stahl 2005			0.00 [-0.42, 0.42] 0.00 [-0.54, 0.54]
	Total (95% CI)			1.13 [-0.49, 2.75]
	I² = 95%				-4	-2	0	2	4
				Favours [hyaluronic acid] Favours [corticosteroids]

S.T., B.F. and S.D. do not have any conflicts of interest to declare. F.B. has received fees for speaking and/or consulting from AbbVie, Pfizer, Sanofi, Expanscience, Pierre Fabre, IBSA, Genevrier, TRB Chemedica, Rottapharm, BioIberica . L.G. has received fees for speaking and/or consulting from AbbVie, Pfizer, Janssen, MSD, Novartis, Roche-Chugai and UCB.


Olivier Finkel
email: finkel@math.univ-paris-diderot.fr

Locally Finite ω-Languages and Effective Analytic Sets Have the Same Topological Complexity

Keywords: Local sentences, logic in computer science, formal languages, locally finite languages, infinite words, ω-languages, topological complexity, Borel hierarchy, Wadge hierarchy, models of set theory, decision problems

. We prove that locally finite ω-languages and effective analytic sets have the same topological complexity: the Borel and Wadge hierarchies of the class of locally finite ω-languages are equal to the Borel and Wadge hierarchies of the class of effective analytic sets. In particular, for each non-null recursive ordinal α < ω CK 1 there exist some Σ 0 α -complete and some Π 0 αcomplete locally finite ω-languages, and the supremum of the set of Borel ranks of locally finite ω-languages is the ordinal γ 1 2 , which is strictly greater than the first non-recursive ordinal ω CK 1 . This gives an answer to the question of the topological complexity of locally finite ωlanguages, which was asked by Simonnet [Sim92] and also by Duparc, Finkel, and Ressayre in [DFR01]. Moreover we show that the topological complexity of a locally finite ω-language defined by a local sentence ϕ may depend on the models of the Zermelo-Fraenkel axiomatic system ZFC. Using similar constructions as in the proof of the above results we also show that the equivalence, the inclusion, and the universality problems for locally finite ω-languages are Π 1 2 -complete, hence highly undecidable.

Introduction

Local sentences were introduced by Ressayre who proved in [START_REF] Ressayre | Formal languages defined by the underlying structure of their words[END_REF] some remarkable stretching theorems which established some links between the finite and the infinite model theory of these sentences. These theorems show that the existence of some well ordered models of a local sentence ϕ (a binary relation symbol is here assumed to belong to the signature of ϕ and to be interpreted by a linear order in every model of ϕ) is equivalent to the existence of some finite model of ϕ, generated by some particular kind of indiscernibles, like special, remarkable or monotonic ones. In particular, a local sentence ϕ has a model of order type ω if and only if it has a finite model generated by N ϕ special indiscernibles (where N ϕ is a positive integer depending on ϕ), and a similar result establishes a connection between the existence of a model of order type α (where α is an ordinal < ω ω ) and the existence of a finite model (of another local sentence ϕ α ) generated by semi-monotonic indiscernibles [START_REF] Finkel | Stretchings[END_REF].

These theorems provide some decision algorithms which show the decidability of the following problem: "For a given local sentence ϕ and an ordinal α < ω ω , has ϕ a model of order type α ?"

These results look like Büchi's one about the decidability of the monadic second order theory of one successor over the integers [START_REF] Büchi | On a decision method in restricted second order arithmetic[END_REF], and even more like its extension: the decidability of the monadic second order theory of the structure (α, <) for a countable ordinal α. In order to prove this result, Büchi studied in the sixties the class of ω-languages accepted by finite automata with what is now called Büchi acceptance condition. He showed that an ω-language, i.e. a set of words of length ω over a finite alphabet, is accepted by a finite automaton with the Büchi acceptance condition if and only if it is defined by a monadic second order sentence [START_REF] Büchi | On a decision method in restricted second order arithmetic[END_REF][START_REF] Thomas | Automata on infinite objects[END_REF]. The equivalence between definability by monadic second order sentences and acceptance by finite automata, which is also true for languages of finite words, has then been extended to α-languages, i.e. languages of words of length α, where α is a countable ordinal ≥ ω [START_REF] Büchi | Axiomatization of the monadic second order theory of ω 1[END_REF]. This led to decision algorithms showing that the monadic second order theory of the structure (α, <) is decidable.

A way to compare the power of the above decidability results concerning local or monadic sentences is to compare the expressive power of monadic sentences and of local sentences, and then to consider languages defined by these sentences. Ressayre introduced locally finite languages which are defined by local sentences. Local sentences are first order, but they define locally finite languages via existential quantifications over relations and functions which appear in the local sentence. These second order quantifications are more general than the monadic ones. When finite words are considered, each regular language is locally finite, [START_REF] Ressayre | Formal languages defined by the underlying structure of their words[END_REF], and many context-free as well as non-context-free languages are locally finite [START_REF] Finkel | Locally finite languages[END_REF]. Moreover it was proved in [START_REF] Finkel | Langages de Büchi et ω-langages locaux[END_REF][START_REF] Finkel | Locally finite languages[END_REF] that the class LOC α of locally finite α-languages, for ω ≤ α < ω ω , is a strict extension of the class REG α of regular α-languages (defined by monadic second order sentences). Then the following question naturally arises: "How large is the extension of REG α by LOC α ?"

We have begun to attack this problem by comparing the topological complexity of ω-languages in each of these classes, and firstly to locate them with regard to the Borel and projective hierarchies. On one side it is well known that all ω-regular languages are boolean combinations of Σ 0 2 -sets hence ∆ 0 3 -sets, [START_REF] Thomas | Automata on infinite objects[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF]. On the other side we proved in [START_REF] Finkel | Topological complexity of locally finite ω-languages[END_REF] that locally finite ω-languages extend far beyond regular ω-languages: the class LOC ω meets all finite levels of the Borel hierarchy, contains some Borel sets of infinite rank and even some analytic but non-Borel sets.

Notice that the question of the topological complexity of locally finite ω-languages is also motivated by the general project of studying the logical definability of classes of formal languages of (finite or) infinite words, (or of relational structures like graphs); see [START_REF] Pin | Logic, semigroups and automata on words[END_REF][START_REF] Thomas | Languages, automata, and logic[END_REF] for a survey about this field of research called "descriptive complexity".

In [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF] we proved that the Borel and Wadge hierarchies of the class of ω-languages accepted by real-time 1-counter Büchi automata are equal to the Borel and Wadge hierarchies of the class of effective analytic sets accepted by Büchi Turing machines.

Using this previous result, we prove in this paper that locally finite ω-languages and effective analytic sets have the same topological complexity: the Borel and Wadge hierarchies of the class of locally finite ωlanguages are equal to the Borel and Wadge hierarchies of the class of effective analytic sets. In particular, for each non-null recursive ordinal α < ω CK 1 there exist some Σ 0 α -complete and some Π 0 α -complete locally finite ω-languages, and the supremum of the set of Borel ranks of locally finite ω-languages is the ordinal γ 1 2 , (see [START_REF] Kechris | Π 1 1 Borel sets[END_REF] for more precision), which is strictly greater than the first non-recursive ordinal ω CK 1 . This gives an answer to the question of the topological complexity of locally finite ω-languages, which was asked by Simonnet [START_REF] Simonnet | Automates et théorie descriptive[END_REF] and also by Duparc, Finkel, and Ressayre in [START_REF] Duparc | Computer science and the fine structure of Borel sets[END_REF].

Moreover we show that the topological complexity of a locally finite ω-language defined by a local sentence ϕ may depend on the models of the Zermelo-Fraenkel axiomatic system ZFC.

Using similar constructions as in the proof of the above results, we also show that the equivalence, the inclusion, and the universality problems for locally finite ω-languages are Π 1 2 -complete, hence highly undecidable.

The paper is organized as follows. In section 2 we review the definitions and some properties of local sentences and locally finite (omega) languages. Then we give some examples of locally finite ω-languages.

In section 3 we recall notions of topology, and in particular the Borel and Wadge hierarchies on a Cantor space. In section 4 we study topological properties of locally finite ω-languages.

Review of local sentences and languages

Definitions and properties of local sentences

In this paper the (first order) signatures are finite, always contain one binary predicate symbol = for equality, and can contain both functional and relational symbols. The terms, open formulas and formulas are built in the usual way.

When M is a structure in a signature Λ and X ⊆ |M |, we define:

cl 1 (X, M ) = X ∪ {f n-ary function of Λ } f M (X n ) ∪ {a constant of Λ } a M cl n+1 (X, M ) = cl 1 (cl n (X, M ), M ) for an integer n ≥ 1 and cl(X, M ) = n≥1 cl n (X, M ) is the closure of X in M .
Let us now define local sentences. We shall denote S(ϕ) the signature of a first order sentence ϕ, i.e. the set of non-logical symbols appearing in ϕ.

Definition 2.1 A first order sentence ϕ is local if and only if:

a) M |= ϕ and X ⊆ |M | imply cl(X, M ) |= ϕ b) ∃n ∈ N such that ∀M , if M |= ϕ and X ⊆ |M |, then cl(X, M ) = cl n (X, M ), (closure in models
of ϕ takes at most n steps).

Notation. For a local sentence ϕ, let n ϕ be the smallest integer n ≥ 1 verifying b) of the above definition.

Remark 2.2 Because of a) of Definition 2.1, a local sentence ϕ is always equivalent to a universal sentence, so we may assume that ϕ is universal.

Let us now state first properties of local sentences.

Theorem 2.3 (Ressayre, see [START_REF] Finkel | Locally finite languages[END_REF])

(a)
The set of local sentences is recursively enumerable.

(b) It is undecidable whether an arbitrary sentence ϕ is a local one.

Per contra to these negative results, there exists a "recursive presentation" up to logical equivalence of all local sentences.

Theorem 2.4 (Ressayre, see [START_REF] Finkel | Locally finite languages[END_REF]) There exist a recursive set L of local sentences and a recursive function F such that:

1) ψ local ←→ ∃ψ ∈ L such that ψ ≡ ψ . 2) ψ ∈ L -→ n ψ = F(ψ ).
The elements of L are the ψ ∧ C n , where ψ run over the universal formulas and C n run over the universal formulas in the signature S(ψ) which express that closure in a model takes at most n steps. ψ ∧ C n is local and n ψ∧Cn ≤ n. Then we can compute n ψ∧Cn , considering only finite models of cardinal ≤ m, where m is an integer depending on n. And each local sentence ψ is equivalent to a universal formula θ, hence ψ ≡ θ ∧ C n ψ .

We shall restrict in the sequel our attention to local sentences with a binary predicate < in their signature which is interpreted by a linear ordering in all of their models.

A fundamental result about local sentences is the stretching theorem, see [START_REF] Finkel | Stretchings[END_REF] which shows the existence of remarkable connections between the finite and the infinite model theory of local sentences. The stretching theorem implies the existence of decision procedures for several problems. Notice that the set of local sentences is not recursive but we can consider that the algorithms given by the following theorem are applied to local sentences in the recursive set L given by Proposition 2.4. In particular ϕ is given with the integer n ϕ .

Theorem 2.5 ( [START_REF] Finkel | Stretchings[END_REF]) It is decidable, for a given local sentence ϕ, whether (1) ϕ has arbitrarily large finite models.

(2) ϕ has an infinite model.

(3) ϕ has an infinite well ordered model.

(4) ϕ has a model of order type ω.

(5) ϕ has well ordered models of unbounded order types in the ordinals.

On the other side Büchi showed that one can decide whether a monadic second order formula of S1S is true in the structure (ω, <). But for a formula of size n his procedure might run in time

2 2 . . 2 n O(n)
see [START_REF] Büchi | On a decision method in restricted second order arithmetic[END_REF] for more details. Moreover it has been proved by Meyer that one cannot essentially improve this result: the monadic second order theory of the structure (ω, <) is not elementary recursive, [START_REF] Meyer | Weak monadic second order theory of succesor is not elementary-recursive[END_REF]. Notice that the complexity of Büchi's algorithm for monadic sentences is in terms of the length of the formula and the complexity of the algorithms for local sentences is in terms of the length of a local sentence ϕ and the corresponding integer N ϕ . But, as explained in [START_REF] Finkel | Topological complexity of locally finite ω-languages[END_REF], the algorithms for local sentences given by Theorem 2.5 are of much lower complexity than the algorithm for decidability of S1S. This is remarkable because the expressive power of local sentences is also greater than the expressive power of monadic second order sentences, as shown in [START_REF] Finkel | Topological complexity of locally finite ω-languages[END_REF] and in this paper.

Definitions and first properties of local languages

Let us now introduce notations for words. Let Σ be a finite alphabet whose elements are called letters. A finite non-empty word over Σ is a finite sequence of letters: x = a 1 a 2 • • • a n where ∀i ∈ [1; n] a i ∈ Σ. We shall denote x(i) = a i the i th letter of x and x[i] = x(1) • • • x(i) for i ≤ n. The length of x is |x| = n. The empty word will be denoted by λ and has 0 letters. Its length is 0. The set of finite words over Σ is denoted Σ . Σ + = Σ -{λ} is the set of non-empty words over Σ. A (finitary) language L over Σ is a subset of Σ . Its complement (in Σ ) is L -= Σ -L. The usual concatenation product of u and v will be denoted by u • v or just uv. For V ⊆ Σ , we denote

V = {v 1 • • • v n | n ∈ N and ∀i ∈ [1; n] v i ∈ V }. The first infinite ordinal is ω. An ω-word over Σ is an ω -sequence a 1 a 2 • • • a n • • •, where ∀i ≥ 1 a i ∈ Σ. When σ is an ω-word over Σ, we write σ = σ(1)σ(2) • • • σ(n) • • • and σ[n] = σ(1)σ(2) • • • σ(n)
the finite word of length n, prefix of σ. The set of ω-words over the alphabet Σ is denoted by Σ ω . An ωlanguage over an alphabet Σ is a subset of

Σ ω . For V ⊆ Σ , V ω = {σ = u 1 • • • u n • • • ∈ Σ ω | ∀i ≥ 1 u i ∈ V } is the ω-power of V . For a subset A ⊆ Σ ω , the complement of A (in Σ ω ) is Σ ω -A denoted A -.
The concatenation product is extended to the product of a finite word u and an ω-word v: the infinite word u • v is then the ω-word such that:

(u • v)(k) = u(k) if k ≤ |u| , and (u • v)(k) = v(k -|u|) if k > |u|.
The prefix relation is denoted : the finite word u is a prefix of the finite word v (respectively, the infinite word v), denoted u v, if and only if there exists a finite word w (respectively, an infinite word w), such that v = u • w.

A word over Σ may be considered as a structure in the following usual manner: Let Σ be a finite alphabet. We denote P a a unary predicate for each letter a ∈ Σ and Λ Σ the signature {<, (P a ) a∈Σ }. Let σ be a finite word over the alphabet Σ, |σ| is the length of the word σ. We may write that |σ| = {1, 2, . . . , |σ|}. σ is identified with the structure (|σ|, < σ , (P σ a ) a∈Σ ) of signature Λ Σ where P σ a = {1 ≤ i ≤ |σ| | the i th letter of σ is an a}. In a similar manner if σ is an ω-word over the alphabet Σ, then ω is the length of the word σ and we may write |σ| = {1, 2, 3, . . .}. σ is identified to the structure (|σ|, < σ , (P σ a ) a∈Σ ) of signature Λ Σ where P σ a = {1 ≤ i < ω | the i th letter of σ is an a}.

Definition 2.6 Let Σ be a finite alphabet and L ⊆ Σ be a language of finite words (respectively, L ⊆ Σ ω be a language of infinite words) over the alphabet Σ. Then L is a locally finite language (respectively, ω-language) ←→ there exists a local sentence ϕ in a signature Λ ⊇ Λ Σ such that σ ∈ L iff ∃ finite M , (respectively, ∃M of order type ω) M |= ϕ and M |Λ Σ = σ (where M |Λ Σ is the reduction of M to the signature Λ Σ ).

We then denote L = L Σ (ϕ) (respectively, L = L Σ ω (ϕ)), and to simplify, when there is no ambiguity, L = L(ϕ) (respectively, L = L ω (ϕ)) the locally finite language (respectively, ω-language) defined by ϕ. The class of locally finite languages will be denoted LOC. The class of locally finite ω-languages will be denoted LOC ω .

The empty word λ has 0 letters. It is represented by the empty structure. Recall that if L(ϕ) is a locally finite language then L(ϕ) -{λ} and L(ϕ) ∪ {λ} are also locally finite [START_REF] Finkel | Locally finite languages[END_REF].

Remark 2.7 The notion of locally finite language is very different from the usual notion of local language which represents a subclass of the class of rational languages. But from now on, as in [START_REF] Finkel | Locally finite languages[END_REF], things being well defined and made precise, we shall call simply local languages the locally finite languages.

Let us state the following decidability results.

Theorem 2.8 It is decidable, for a local sentence ϕ, given with the integer n ϕ , and an alphabet Σ, whether

(1) The local language L Σ (ϕ) is empty.

(2) The local language L Σ (ϕ) is infinite.

(3) The local ω-language L Σ ω (ϕ) is empty.

Remark 2.9 Item (3) states that the emptiness problem for local ω-languages is decidable. It relies on a remarkable analogue to the property: "a regular ω-language is non-empty iff it contains an ultimately periodic word, i.e. an ω-word in the form u • v ω where u and v are finite words". When local ω-languages are considered, this property becomes: "a local ω-language is non-empty iff it contains an ω-word which is the reduction, to the signature of words, of an ω-model generated by special indiscernibles", see [START_REF] Ressayre | Formal languages defined by the underlying structure of their words[END_REF][START_REF] Finkel | Stretchings[END_REF].

Examples of local languages

We first recall the following result which shows that the class of local (finitary) languages extends the class of regular ones.

Theorem 2.10 (Ressayre, see [START_REF] Ressayre | Formal languages defined by the underlying structure of their words[END_REF]) The class of local (finitary) languages is closed under finite union, concatenation product, and star operation. This implies that each regular (finitary) language is local.

We now give some examples of local ω-languages.

Example 2.11 ([Fin04])

The ω-language which contains only the word σ = abab 2 ab 3 ab 4 . . . is a local ω-language over the alphabet {a, b}. Notice that this ω-language is not regular since its single ω-word is not ultimately periodic.

Recall that for any family L of finitary languages, the ω-Kleene closure of L, is:

ω-KC(L) = { 1≤i≤n U i • V ω i | ∀i ∈ [1, n] U i , V i ∈ L}
It is well known that the class REG ω of regular ω-languages (respectively, the class CF ω of context free ω-languages) is the ω-Kleene closure of the family REG of regular finitary languages (respectively, of the family CF of context free finitary languages), [START_REF] Thomas | Automata on infinite objects[END_REF][START_REF] Staiger | ω-languages[END_REF].

We showed that a similar characterization does not hold for local languages. Then we easily derive the following example because every regular finitary language is local [START_REF] Ressayre | Formal languages defined by the underlying structure of their words[END_REF].

Example 2.13 ([Fin01]) Every regular ω-language is a local ω-language, i.e. REG ω ⊆ LOC ω .

Since numerous context free languages are local [START_REF] Finkel | Locally finite languages[END_REF], CF ω = ω-KC(CF ) implies that many context free ω-languages are local. The problem whether every context free ω-language is local is still open but by Theorem 2.12, CF ⊆ LOC would imply that CF ω ⊆ LOC ω .

Example 2.14 The ω-languages U ω and U.a ω , where Recall that a substitution f is defined by a mapping Σ → P (Γ ), where Σ = {a 1 , ..., a n } and Γ are two finite alphabets, f : a i → L i where ∀i ∈ [1; n], L i is a finitary language over the alphabet Γ. The substitution is said to be λ-free if ∀i ∈ [1; n], L i does not contain the empty word λ. It is a (λ-free) morphism when every language L i contains only one (non-empty) word. Now this mapping is extended in the usual manner to finite words and to finitary languages: for some letters

U = {a n 2 b n 2 c n 2 | n ≥ 1} is a
x(1), x(2), . . . , x(n) in Σ, f (x(1)x(2) • • • x(n)) = {u 1 u 2 • • • u n | ∀i ∈ [0; n] u i ∈ f (x(i))}, and for L ⊆ Σ , f (L) = ∪ x∈L f (x).
If the substitution f is λ-free, we can extend this to ω-words and ω-languages:

f (x(1)x(2) • • • x(n) • • •) = {u 1 u 2 • • • u n • • • | ∀i ≥ 0 u i ∈ f (x(i))} and for L ⊆ Σ ω , f (L) = ∪ x∈L f (x).
We now recall some closure properties of the class LOC ω which allow us to generate many other local ω-languages from the known ones.

Theorem 2.15 ([Fin04])

The class LOC ω is closed under union, left concatenation with local (finitary) languages, λ-free substitution of local (finitary) languages, λ-free morphism.

Topology

Borel hierarchy and analytic sets

We assume the reader to be familiar with basic notions of topology which may be found in [Mos80, LT94, Sta97, PP04]. There is a natural metric on the set Σ ω of infinite words over a finite alphabet Σ containing at least two letters which is called the prefix metric and is defined as follows. For u, v ∈ Σ ω and u = v let δ(u, v) = 2 -l pref(u,v) where l pref(u,v) is the first integer n such that the (n + 1) st letter of u is different from the (n + 1) st letter of v. This metric induces on Σ ω the usual Cantor topology in which the open subsets of Σ ω are of the form

W • Σ ω , for W ⊆ Σ . A set L ⊆ Σ ω is a closed set iff its complement Σ ω -L is an open set.
Define now the Borel Hierarchy of subsets of Σ ω : Definition 3.1 For a non-null countable ordinal α, the classes Σ 0 α and Π 0 α of the Borel Hierarchy on the topological space Σ ω are defined as follows: Σ 0 1 is the class of open subsets of Σ ω , Π 0 1 is the class of closed subsets of Σ ω , and for any countable ordinal α ≥ 2:

Σ 0 α is the class of countable unions of subsets of Σ ω in γ<α Π 0 γ . Π 0 α is the class of countable intersections of subsets of Σ ω in γ<α Σ 0 γ . The class of Borel sets is ∆ 1 1 := ξ<ω1 Σ 0 ξ = ξ<ω1 Π 0 ξ ,
where ω 1 is the first uncountable ordinal. There are also some subsets of Σ ω which are not Borel. In particular the class of Borel subsets of Σ ω is strictly included into the class Σ 1 1 of analytic sets which are obtained by projection of Borel sets.

Definition 3.2 A subset A of Σ ω is in the class Σ 1 1 of analytic sets iff there exists another finite set Y and a Borel subset B of (Σ × Y ) ω such that x ∈ A ↔ ∃y ∈ Y ω such that (x, y) ∈ B, where (x, y) is the infinite word over the alphabet Σ × Y such that (x, y)(i) = (x(i), y(i)) for each integer i ≥ 1.

We now define completeness with regard to reduction by continuous functions. For a countable ordinal

α ≥ 1, a set F ⊆ Σ ω is said to be a Σ 0 α (respectively, Π 0 α , Σ 1 1 )-complete set iff for any set E ⊆ Y ω (with Y a finite alphabet): E ∈ Σ 0 α (respectively, E ∈ Π 0 α , E ∈ Σ 1 1 ) iff there exists a continuous function f : Y ω → Σ ω such that E = f -1 (F ).
Let us now recall the definition of the arithmetical hierarchy of ω-languages, see for example [START_REF] Staiger | ω-languages[END_REF][START_REF] Moschovakis | Descriptive set theory[END_REF]. Let Σ be a finite alphabet. An ω-language L ⊆ Σ ω belongs to the class Σ n if and only if there exists a recursive relation

R L ⊆ (N) n-1 × Σ such that L = {σ ∈ Σ ω | ∃a 1 . . . Q n a n (a 1 , . . . , a n-1 , σ[a n + 1]) ∈ R L }
where Q i is one of the quantifiers ∀ or ∃ (not necessarily in an alternating order). An ω-language L ⊆ Σ ω belongs to the class Π n if and only if its complement Σ ω -L belongs to the class Σ n . The inclusion relations that hold between the classes Σ n and Π n are the same as for the corresponding classes of the Borel hierarchy and the classes Σ n and Π n are strictly included in the respective classes Σ 0 n and Π 0 n of the Borel hierarchy.

As in the case of the Borel hierarchy, projections of arithmetical sets (of the second Π-class) lead beyond the arithmetical hierarchy, to the analytical hierarchy of ω-languages. The first class of the analytical hierarchy of ω-languages is the (lightface) class Σ 1 1 of effective analytic sets. An ω-language L ⊆ Σ ω belongs to the class Σ 1 1 if and only if there exists a recursive relation R L ⊆ (N) × {0, 1} × Σ such that:

L = {σ ∈ Σ ω | ∃τ (τ ∈ {0, 1} ω ∧ ∀n∃m((n, τ [m], σ[m]) ∈ R L ))}
Thus an ω-language L ⊆ Σ ω is in the class Σ 1 1 iff it is the projection of an ω-language over the alphabet {0, 1} × Σ which is in the class Π 2 of the arithmetical hierarchy.

We recall the following result which gives a first upper bound on the complexity of local ω-languages.

Theorem 3.3 ([Fin08])

The class LOC ω is strictly included in the class Σ 1 1 .

By Suslin's Theorem [Kec95, page 226], an analytic subset of Σ ω is either countable or has the continuum power. Then we can infer the following:

Corollary 3.4 Let Σ be a finite alphabet. Every local ω-language L Σ ω (ϕ) over the alphabet Σ is either countable or has the continuum power.

Kechris, Marker and Sami proved in [START_REF] Kechris | Π 1 1 Borel sets[END_REF] that the supremum of the set of Borel ranks of (lightface) Π 1 1 , so also of (lightface) Σ 1 1 , sets is the ordinal γ 1 2 . This ordinal is precisely defined in [START_REF] Kechris | Π 1 1 Borel sets[END_REF]. Kechris, Marker and Sami proved that the ordinal γ 1 2 is strictly greater than the ordinal δ 1 2 which is the first non ∆ 1 2 ordinal. Thus in particular it holds that ω CK 1 < γ 1 2 , where ω CK 1 is the first non-recursive ordinal, usually called the Chruch-Kleene ordinal. The exact value of the ordinal γ 1 2 may depend on axioms of set theory [START_REF] Kechris | Π 1 1 Borel sets[END_REF]. It is consistent with the axiomatic system ZFC that γ 1 2 is equal to the ordinal δ 1 3 which is the first non ∆ 1 3 ordinal (because γ 1 2 = δ 1 3 in ZFC + (V=L)). On the other hand the axiom of Π 1 1 -determinacy implies that γ 1 2 < δ 1 3 . For more details, the reader is referred to [START_REF] Kechris | Π 1 1 Borel sets[END_REF] and to a textbook of set theory like [START_REF] Jech | Set theory[END_REF].

Notice however that it seems still unknown whether every non null ordinal γ < γ 1 2 is the Borel rank of a (lightface) Π 1 1 (or Σ 1 1 ) set. On the other hand it is known that every ordinal γ < ω CK 1 is the Borel rank of a (lightface) ∆ 1 1 -set, since for every ordinal γ < ω CK 1 there exist some Σ 0 γ -complete and Π 0 γ -complete sets in the class ∆ 1 1 .

Wadge hierarchy

We now introduce the Wadge hierarchy, which is a great refinement of the Borel hierarchy defined via reductions by continuous functions, [START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF][START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF].

Definition 3.5 (Wadge [START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF]) Let X, Y be two finite alphabets. For L ⊆ X ω and L ⊆ Y ω , L is said to be Wadge reducible to L (L ≤ W L ) iff there exists a continuous function f :

X ω → Y ω , such that L = f -1 (L ).
L and L are Wadge equivalent iff L ≤ W L and L ≤ W L. This will be denoted by L ≡ W L . And we shall say that

L < W L iff L ≤ W L but not L ≤ W L. A set L ⊆ X ω is said to be self dual iff L ≡ W L -,
. For L ⊆ X ω and L ⊆ Y ω , if L ≤ W L and L = f -1 (L )
where f is a continuous function from X ω into Y ω , then f is called a continuous reduction of L to L . Intuitively it means that L is less complicated than L because to check whether x ∈ L it suffices to check f (x) ∈ L where f is a continuous function. Hence the Wadge degree of an ω-language is a measure of its topological complexity.

Notice that in the above definition, we consider that a subset L ⊆ X ω is given together with the alphabet X.

We can now define the Wadge class of a set L:

Definition 3.6 Let L be a subset of X ω . The Wadge class of L is :

[L] = {L | L ⊆ Y ω for a finite alphabet Y and L ≤ W L}. Recall that each Borel class Σ 0 α and Π 0 α is a Wadge class. A set L ⊆ X ω is a Σ 0 α (respectively Π 0 α )- complete set iff for any set L ⊆ Y ω , L is in Σ 0 α (respectively Π 0 α ) iff L ≤ W L .
There is a close relationship between Wadge reducibility and games which we now introduce.

Definition 3.7 Let L ⊆ X ω and L ⊆ Y ω . The Wadge game W (L, L ) is a game with perfect information between two players, player 1 who is in charge of L and player 2 who is in charge of L . Player 1 first writes a letter a 1 ∈ X, then player 2 writes a letter b 1 ∈ Y , then player 1 writes a letter a 2 ∈ X, and so on. The two players alternatively write letters a n of X for player 1 and b n of Y for player 2.

After ω steps, the player 1 has written an ω-word a ∈ X ω and the player 2 has written an ω-word b ∈ Y ω . The player 2 is allowed to skip, even infinitely often, provided he really writes an ω-word in ω steps. The player 2 wins the play iff [a ∈ L ↔ b ∈ L ], i.e. iff :

[(a ∈ L and b ∈ L ) or (a / ∈ L and b / ∈ L and b is infinite)].
Recall that a strategy for player 1 is a function σ : (Y ∪ {s}) → X. And a strategy for player 2 is a function f :

X + → Y ∪ {s}.
σ is a winning stategy for player 1 iff he always wins a play when he uses the strategy σ, i.e. when the n th letter he writes is given by

a n = σ(b 1 • • • b n-1 )
, where b i is the letter written by player 2 at step i and b i = s if player 2 skips at step i.

A winning strategy for player 2 is defined in a similar manner.

Martin's Theorem states that every Gale-Stewart Game G(X) (see [START_REF] Kechris | Classical descriptive set theory[END_REF]), with X a Borel set, is determined and this implies the following : Theorem 3.8 (Wadge) Let L ⊆ X ω and L ⊆ Y ω be two Borel sets, where X and Y are finite alphabets. Then the Wadge game W (L, L ) is determined : one of the two players has a winning strategy. And L ≤ W L iff the player 2 has a winning strategy in the game W (L, L ). Theorem 3.9 (Wadge) Up to the complement and ≡ W , the class of Borel subsets of X ω , for a finite alphabet X having at least two letters, is a well ordered hierarchy. There is an ordinal |W H|, called the length of the hierarchy, and a map d 0 W from W H onto |W H| -{0}, such that for all L, L ⊆ X ω :

d 0 W L < d 0 W L ↔ L < W L and d 0 W L = d 0 W L ↔ [L ≡ W L or L ≡ W L -].
The Wadge hierarchy of Borel sets of finite rank has length 1 ε 0 where 1 ε 0 is the limit of the ordinals α n defined by α 1 = ω 1 and α n+1 = ω αn 1 for n a non negative integer, ω 1 being the first non countable ordinal. Then 1 ε 0 is the first fixed point the ordinal exponentiation of base ω 1 . The length of the Wadge hierarchy of Borel sets in ∆ 0 ω = Σ 0 ω ∩ Π 0 ω is the ω th 1 fixed point of the ordinal exponentiation of base ω 1 , which is a much larger ordinal. The length of the whole Wadge hierarchy of Borel sets is a huge ordinal, with regard to the ω th 1 fixed point of the ordinal exponentiation of base ω 1 . It is described in [START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF][START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF] by the use of the Veblen functions.

Topological complexity of local ω-languages

We now firstly recall the notion of real-time 1-counter Büchi automaton which will be useful in the sequel.

A 1-counter machine has one counter containing a non-negative integer. The machine can test whether the content of the counter is zero or not. And transitions depend on the letter read by the machine, the current state of the finite control, and the tests about the values of the counter. Notice that in this model some λ-transitions are allowed.

Formally a 1-counter machine is a 4-tuple M=(K, Σ, ∆, q 0 ), where K is a finite set of states, Σ is a finite input alphabet, q 0 ∈ K is the initial state, and

∆ ⊆ K × (Σ ∪ {λ}) × {0, 1} × K × {0, 1, -1} is the transition relation. The 1-counter machine M is said to be real time iff: ∆ ⊆ K × Σ × {0, 1} × K × {0, 1, -1}, i.e. iff there are no λ-transitions.
If the machine M is in state q and c ∈ N is the content of the counter then the configuration (or global state) of M is the pair (q, c).

For a ∈ Σ ∪ {λ}, q, q ∈ K and c ∈ N, if (q, a, i, q , j) ∈ ∆ where i = 0 if c = 0 and i = 1 if c > 0, then we write: a : (q, c) → M (q , c + j). Thus the transition relation must obviously satisfy: if (q, a, i, q , j) ∈ ∆ and i = 0 then j = 0 or j = 1 (but j may not be equal to -1).

Let σ = a 1 a 2 • • • a n • • • be an ω-word over Σ. An ω-sequence of configurations r = (q i , c i ) i≥1 is called a run of M on σ, iff:

(1) (q 1 , c 1 ) = (q 0 , 0) (2) for each i ≥ 1, there exists b i ∈ Σ ∪ {λ} such that b i : (q i , c i ) → M (q i+1 , c i+1 ) and such that

a 1 a 2 • • • a n • • • = b 1 b 2 • • • b n • • •
For every such run r, In(r) is the set of all states entered infinitely often during r.

Definition 4.1 A Büchi 1-counter automaton is a 5-tuple M=(K, Σ, ∆, q 0 , F ), where M =(K, Σ, ∆, q 0 ) is a 1-counter machine and F ⊆ K is the set of accepting states. The ω-language accepted by M is:

L(M)= {σ ∈ Σ ω | there exists a run r of M on σ such that In(r) ∩ F = ∅}
The class of ω-languages accepted by Büchi 1-counter automata is denoted BCL(1) ω . The class of ω-languages accepted by real time Büchi 1-counter automata will be denoted r-BCL(1) ω .

The class BCL(1) ω is a strict subclass of the class CF ω of context free ω-languages accepted by Büchi pushdown automata.

If we omit the counter of a real-time Büchi 1-counter automaton, then we simply get the notion of Büchi automaton. The class of ω-languages accepted by Büchi automata is the class of regular ω-languages, denoted REG ω .

Recall that a Büchi Turing machine is just a Turing machine working on infinite inputs with a Büchilike acceptance condition, and that the class of ω-languages accepted by Büchi Turing machines is the class Σ 1 1 of effective analytic sets [START_REF] Cohen | ω-computations on Turing machines[END_REF][START_REF] Staiger | ω-languages[END_REF]. Using this essential property and the fact that Turing machines can be simulated by (non real-time) 2-counter automata, we proved the following result. We are going to use this result from [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF] to prove our main result about local ω-languages.

We first define a coding of ω-words over a finite alphabet Σ by ω-words over the alphabet Σ∪{A, B, 0} where A, B and 0 are new letters not in Σ.

We shall code an ω-word x ∈ Σ ω by the ω-word h(x) defined by

h(x) = A0x(1)B0 2 A0 2 x(2)B0 3 A0 3 x(3)B • • • B0 n A0 n x(n)B • • •
This coding defines a mapping h : Σ ω → (Σ ∪ {A, B, 0}) ω . The function h is continuous because for all ω-words x, y ∈ Σ ω and each positive integer n, it holds that δ(x, y) < 2 -n → δ(h(x), h(y)) < 2 -n .

Recall that we denote h(Σ ω ) -= (Σ∪{A, B, 0}) ω -h(Σ ω ). We are going to prove that if L(A)⊆ Σ ω is accepted by a real time 1-counter automaton A with a Büchi acceptance condition then h(L(A))∪h(Σ ω ) - is a local ω-language. Moreover this ω-language will have the same Wadge degree as the initial language L(A), except for some very simple cases.

We firstly prove the following lemma.

Lemma 4.3 Let Σ be a finite alphabet and h be the coding of ω-words over Σ defined as above. Then h(Σ ω ) -is a local ω-language.

Proof. We can easily see that h(Σ ω ) -is the set of ω-words in (Σ ∪ {A, B, 0}) ω which belong to one of the following ω-languages.

• D 1 is the set of ω-words over the alphabet Σ ∪ {A, B, 0} which have not any initial segment in

A • 0 • Σ • B.
It is easy to see that D 1 is in fact a regular ω-language, hence also a local ω-language.

• D 2 is the complement of (A•0

+ •Σ•B•0 + ) ω in (Σ∪{A, B, 0}) ω . The ω-language (A•0 + •Σ•B•0 + ) ω
is regular thus its complement D 2 is also a regular ω-language, and thus a local ω-language.

• D 3 is the set of ω-words over the alphabet Σ ∪ {A, B, 0} which contain a segment of the form

B • 0 n • A • 0 m • Σ for some positive integers n = m.
It is easy to see (using only a unary function symbol, see for instance methods used in [START_REF] Finkel | Locally finite languages[END_REF]) that the finitary language containing words of the form B.0 n .A.0 m .Σ for some positive integers n = m is a local finitary language. Thus the ω-language D 3 is a local ω-language.

• D 4 is the set of ω-words over the alphabet Σ∪{A, B, 0} which contain a segment in

A•0 n •Σ•B•0 m •A
for some positive integers n and m with m = n + 1. Again the finitary language containing words of the form

A • 0 n • Σ • B • 0 m • A with m = n + 1 is easily seen to be local. Thus the ω-language D 4 is a local ω-language.
The class LOC ω is closed under finite union. On the other hand it holds that h(Σ ω ) -= 1≤i≤4 D i thus h(Σ ω ) -is a local ω-language.

We would like now to prove that if L(A)⊆ Σ ω is accepted by a real time 1-counter automaton A with a Büchi acceptance condition then h(L(A)) is a local ω-language. We have not been able to show this, so we are firstly going to define another ω-language L(A) which will be a local ω-language (and will be also accepted by another 1-counter Büchi automaton) and we shall prove that h(L(A))∪h(Σ ω ) -= L(A)∪h(Σ ω ) -.

Let then A= (K, Σ, ∆, q 0 , F ) be a real-time 1-counter Büchi automaton accepting the ω-language L(A)⊆ Σ ω . The ω-language L(A) is the set of ω-words over the alphabet Σ ∪ {A, B, 0} of the form

Au 1 v 1 x 1 Bw 1 z 1 Au 2 v 2 x 2 Bw 2 z 2 A • • • Au n v n x n Bw n z n A • • • where, for all integers i ≥ 1, v i , w i , u i , z i ∈ 0 , x i ∈ Σ, |u 1 | = 1, |u i+1 | = |z i |
and there is a sequence (q i ) i≥0 of states of K and integers j i ∈ {-1; 0; 1}, for i ≥ 1, such that for all integers i ≥ 1:

x i : (q i-1 , |v i |) → A (q i , |v i | + j i ) and |w i | = |v i | + j i
Moreover some state q f ∈ F occurs infinitely often in the sequence (q i ) i≥0 .

Notice that the state q 0 of the sequence (q i ) i≥0 is also the initial state of A.

Lemma 4.4 Let A be a real time 1-counter Büchi automaton accepting ω-words over the alphabet Σ and L(A)⊆ (Σ ∪ {A, B, 0}) ω be defined as above. Then L(A) is a local ω-language.

Proof. Let A be a real time 1-counter Büchi automaton accepting ω-words over the alphabet Σ and L(A)⊆ (Σ ∪ {A, B, 0}) ω be defined as above.

We first define the following finitary languages, for q, q ∈ K.

T (q,q ) = {vxBw | v, w ∈ 0 and x ∈ Σ and x : (q, |v|) → A (q , |w|)} It holds that T (q,q ) = T 0 (q,q ) ∪ T 1 (q,q )

where T 0 (q,q ) = {xBw | w ∈ 0 and x ∈ Σ and x : (q, 0) → A (q , |w|)} and T 1 (q,q ) = {vxBw | v ∈ 0 + , w ∈ 0 , and x ∈ Σ and x : (q, 1) → A (q , 1 + ε) and |w| = |v| + ε}

We firstly notice that the finitary language T 0 (q,q ) is finite since if xBw ∈ T 0 (q,q ) for some x ∈ Σ and w ∈ 0 then |w| = 0 or |w| = 1. Thus the languages T 0 (q,q ) are local because every finite language is rational and local.

On the other hand we now recall that a linear context free language L(G), over a finite alphabet Σ, is generated by a linear grammar G whose production rules are of the form: A i → u i B i v i for 1 ≤ i ≤ n, and C i → w i for 1 ≤ i ≤ k, where ∀i u i , v i , w i ∈ Σ . The variables A i , B i , C i not necessarily are distinct, but are variables taken in a finite set given by G. It was proved in [START_REF] Finkel | Locally finite languages[END_REF] that every linear context free language is a local language.

It is now easy to see that each language T 1 (q,q ) is a finite union of linear languages and thus is a local language since the class LOC is closed under finite union. Moreover this implies also that the languages T (q,q ) , for q, q ∈ K, are also local.

Let now X be the finite alphabet containing letters t (q,q ) , for q, q ∈ K, and also the letters 0 and A and a letter A 0 . And let L ⊆ X ω be the ω-language over X containing the ω-words of the form:

A 0 • 0 • t (q0,q 0 ) • A • t (q1,q 1 ) • A • t (q2,q 2 ) • A • t (q3,q 3 ) • • •
where q 0 is the initial state of the automaton A, and for each integer i ≥ 0, q i , q i ∈ K and q i = q i+1 and for which there is an accepting state q f ∈ F and infinitely many integers i ≥ 0 such that q i = q f . It is easy to see that the ω-language L ⊆ X ω is regular and thus local.

Consider now the following substitution f : X → P((Σ ∪ {A, B, 0}) ) given by t (q,q ) → T (q,q ) for every q, q ∈ K, and A → {zAu | z, u ∈ 0 and |z| = |u|}, and A 0 → A.

By the definition of the ω-language L(A), it is straightforward to check that f (L) = L(A). But by Theorem 2.15 the class of local ω-languages is closed under λ-free substitution by local finitary languages. Thus the ω-language L(A) is local.

We can now infer the following proposition from Lemmas 4.3 and 4.4 and from the closure of the class of local ω-languages under finite union. Proposition 4.5 Let L(A)⊆ Σ ω be an ω-language accepted by a real time 1-counter automaton A with a Büchi acceptance condition, and let h and L(A) be defined as above. Then L(A)∪h(Σ ω ) -is a local ω-language.

We now state the following lemma which will imply that h(L(A))∪h(Σ ω ) -= L(A)∪h(Σ ω ) -. Lemma 4.6 Let A be a real time 1-counter Büchi automaton accepting ω-words over the alphabet Σ and L(A)⊆ (Σ∪{A, B, 0}) ω be defined as above. Then

L(A) = h -1 (L(A)), i.e. ∀x ∈ Σ ω h(x) ∈ L(A)←→ x ∈ L(A).
Proof. Let A be a real time 1-counter Büchi automaton accepting ω-words over the alphabet Σ and L(A)⊆ (Σ ∪ {A, B, 0}) ω be defined as above. Let x ∈ Σ ω be an ω-word such that h(x) ∈ L(A). So h(x) may be written

h(x) = A0x(1)B0 2 A0 2 x(2)B0 3 A0 3 x(3)B • • • B0 n A0 n x(n)B • • • and also h(x) = Au 1 v 1 x 1 Bw 1 z 1 Au 2 v 2 x 2 Bw 2 z 2 A • • • Au n v n x n Bw n z n A • • • where, for all integers i ≥ 1, v i , w i , u i , z i ∈ 0 , x i = x(i) ∈ Σ, |u 1 | = 1, |u i+1 | = |z i |
and there is a sequence (q i ) i≥0 of states of K and integers j i ∈ {-1; 0; 1}, for i ≥ 1, such that for all integers i ≥ 1:

x i : (q i-1 , |v i |) → A (q i , |v i | + j i )
and

|w i | = |v i | + j i
some state q f ∈ F occurring infinitely often in the sequence (q i ) i≥0 .

In particular, u 1 = 0 and u 1 • v 1 = 0 thus |v 1 | = 0. We are going to prove by induction on the integer i ≥ 1 that, for all integers i ≥ 1, |w i | = |v i+1 |. Moreover, setting c i = |v i |, we are going to prove that for each integer i ≥ 1 it holds that

x i : (q i-1 , c i ) → A (q i , c i+1 )
We have already seen that |v 1 | = 0. By hypothesis there is a state q 1 ∈ K and an integer j 1 ∈ {-1; 0; 1} such that x 1 : (q 0 , |v 1 |) → A (q 1 , |v 1 | + j 1 ), i.e. x 1 : (q 0 , 0) → A (q 1 , j 1 ).

Then |w 1 | = |v 1 | + j 1 = j 1 . We have now |w 1 • z 1 | = |u 2 • v 2 | = 0 2 and |u 2 | = |z 1 | thus |v 2 | = |w 1 | = j 1 . Setting c 1 = 0 and c 2 = j 1 = |v 2 |, it holds that x 1 : (q 0 , c 1 ) → A (q 1 , c 2 ). Assume now that, for all integers i, 1 ≤ i ≤ n -1, it holds that |w i | = |v i+1 | and x i : (q i-1 , c i ) → A (q i , c i+1 ) where c i = |v i |.
We know that there is a state q n ∈ K and an integer j n ∈ {-1; 0; 1} such that

x n : (q n-1 , |v n |) → A (q n , |v n | + j n ), i.e. x n : (q n-1 , c n ) → A (q n , c n + j n ) and |w n | = |v n | + j n . On the other hand |w n • z n | = |u n+1 • v n+1 | = 0 n+1 and |u n+1 | = |z n | thus |v n+1 | = |w n | = c n + j n . By setting c n+1 = |v n+1 | we have x n : (q n-1 , c n ) → A (q n , c n+1 ).
Finally we have proved by induction the announced claim. If for all integers i ≥ 1, we set

c i = |v i | then it holds that x i : (q i-1 , c i ) → A (q i , c i+1 )
But there is some state q f ∈ K which occurs infinitely often in the sequence (q i ) i≥1 . This implies that

(q i-1 , c i ) i≥1 is a successful run of A on x thus x ∈ L(A).
Conversely it is easy to see that if x ∈ L(A) then h(x) ∈ L(A). This ends the proof of Lemma 4.6.

Remark 4.7 Let A be a real time 1-counter Büchi automaton accepting ω-words over the alphabet Σ and L(A)⊆ (Σ∪{A, B, 0}) ω be defined as above. Then L(A) is accepted by another real-time 1-counter Büchi automaton .

We are now going to prove the following result.

Theorem 4.8 The Wadge hierarchy of the class r-BCL(1) ω is equal to the Wadge hierarchy of the class LOC ω .

To prove this result we firstly consider non self dual Borel sets. We recall the definition of Wadge degrees introduced by Duparc in [START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF] and which is a slight modification of the previous one. Wadge and Duparc used the operation of sum of sets of infinite words which has as counterpart the ordinal addition over Wadge degrees.

Definition 4.10 (Wadge, see [START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF][START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF]) Assume that X ⊆ Y are two finite alphabets, Y -X containing at least two elements, and that {X + , X -} is a partition of Y -X in two non empty sets. Let L ⊆ X ω and L ⊆ Y ω , then

L + L = df L ∪ {u • a • β | u ∈ X , (a ∈ X + and β ∈ L ) or (a ∈ X -and β ∈ L -)}
This operation is closely related to the ordinal sum as it is stated in the following: A player in charge of a set L + L in a Wadge game is like a player in charge of the set L but who can, at any step of the play, erase his previous play and choose to be this time in charge of L or of L -. Notice that he can do this only one time during a play.

The following lemma was proved in [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF]. Notice that below the emptyset is considered as an ωlanguage over an alphabet Γ such that Γ -Σ contains at least two elements. Lemma 4.12 Let L ⊆ Σ ω be a non self dual Borel set such that d w (L) ≥ ω. Then it holds that L ≡ W ∅+L.

We can now prove the following lemma. Lemma 4.13 Let L ⊆ Σ ω be a non self dual Borel set acccepted by a real time 1-counter Büchi automaton A. Then there is a local ω-language L such that L ≡ W L .

Proof. Recall first that there are regular ω-languages of every finite Wadge degree, [START_REF] Staiger | ω-languages[END_REF][START_REF] Selivanov | Fine hierarchy of regular ω-languages[END_REF]. These regular ω-languages are Boolean combinations of open sets, and they are local since every regular ωlanguage is local.

So we have only to consider the case of non self dual Borel sets of Wadge degrees greater than or equal to ω.

Let then L = L(A) ⊆ Σ ω be a non self dual Borel set, acccepted by a real time 1-counter Büchi automaton A, such that d w (L) ≥ ω. We have seen that h(L(A))∪h(Σ ω ) -= L(A)∪h(Σ ω ) -is a local ω-language, where the mapping h : Σ ω → (Σ ∪ {A, B, 0}) ω is defined, for x ∈ Σ ω , by:

h(x) = A0x(1)B0 2 A0 2 x(2)B0 3 A0 3 x(3)B • • • B0 n A0 n x(n)B • • •
We set L = h(L(A)) ∪ h(Σ ω ) -and we now prove that L ≡ W L.

Firstly, it is easy to see that L ≤ W L . In order to prove this we can consider the Wadge game W (L, L ). It is easy to see that Player 2 has a winning strategy in this game which consists in essentially copying the play of Player 1, except that Player 2 actually writes a beginning of the code given by h of what has been written by Player 1. This is achieved in such a way that Player 2 has written the initial word A0x(1)B0 2 A0 2 x(2)B0 3 A0 3 x(3)B • • • B0 n A0 n x(n) while Player 1 has written the initial word x(1)x(2)x(3)x(4) • • • x(n). Notice that one can admit that a player writes a finite word at each step of the play instead of a single letter. This does not change the winner of a Wadge game. At the end of a play if Player 1 has written the ω-word x then Player 2 has written h(x) and thus x ∈ L(A) ⇐⇒ h(x) ∈ L and Player 2 wins the play.

To prove that L ≤ W L, it suffices to prove that L ≤ W ∅ + L because Lemma 4.12 states that ∅ + L ≡ W L. Consider the Wadge game W (L , ∅ + L). Player 2 has a winning strategy in this play which we now describes.

As long as Player 1 remains in the closed set h(Σ ω ) (this means that the word written by Player 1 is a prefix of some infinite word in h(Σ ω )) Player 2 essentially copies the play of player 1 except that Player 2 skips when player 1 writes a letter not in Σ. He continues forever with this strategy if the word written by player 1 is always a prefix of some ω-word of h(Σ ω ). Then after ω steps Player 1 has written an ω-word h(x) for some x ∈ Σ ω , and Player 2 has written x. So in that case h(x)

∈ L iff x ∈ L(A) iff x ∈ ∅ + L.
But if at some step of the play, Player 1 "goes out of" the closed set h(Σ ω ) because the word he has now written is not a prefix of any ω-word of h(Σ ω ), then its final word will be surely outside h(Σ ω ) hence also inside L = h(L(A)) ∪ h(Σ ω ) -. Player 2 can now writes a letter of Γ -Σ in such a way that he is now like a player in charge of the wholeset and he can now writes an ω-word u so that his final ω-word will be inside ∅ + L. Thus Player 2 wins this play too.

Finally we have proved that L ≤ W L ≤ W L thus it holds that L ≡ W L. This ends the proof.

End of Proof of Theorem 4.8. Let L ⊆ Σ ω be a Borel set acccepted by a real time 1-counter Büchi automaton A. If the Wadge degree of L is finite, it is well known that it is Wadge equivalent to a regular ω-language, hence also to a local ω-language. If L is non self dual and its Wadge degree is greater than or equal to ω, then we know from Lemma 4.13 that there is a local ω-language L such that L ≡ W L .

It remains to consider the case of self dual Borel sets. The alphabet Σ being finite, a self dual Borel set L is always Wadge equivalent to a Borel set in the form

Σ 1 • L 1 ∪ Σ 2 • L 2 , where (Σ 1 , Σ 2 ) form a partition of Σ, and L 1 , L 2 ⊆ Σ ω are non self dual Borel sets such that L 1 ≡ W L - 2 . Moreover L 1 and L 2 can be taken in the form L (u1) = u 1 • Σ ω ∩ L and L (u2) = u 2 • Σ ω ∩ L for some u 1 , u 2 ∈ Σ , see [Dup03]. So if L ⊆ Σ ω is a self dual Borel set accepted by a real time 1-counter Büchi automaton then L ≡ W Σ 1 • L 1 ∪ Σ 2 • L 2 ,
where (Σ 1 , Σ 2 ) form a partition of Σ, and L 1 , L 2 ⊆ Σ ω are non self dual Borel sets accepted by real time 1-counter Büchi automata. We have already proved that there is a local ω-language L 1 such that L

1 ≡ W L 1 and a local ω-language L 2 such that L - 2 ≡ W L 2 . Thus L ≡ W Σ 1 • L 1 ∪ Σ 2 • L 2 ≡ W Σ 1 • L 1 ∪ Σ 2 • L 2 and Σ 1 • L 1 ∪ Σ 2 • L 2 is a local ω-language.
We have only considered above the Wadge hierarchy of Borel sets. If we assume the axiom of Σ 1 1determinacy, then Theorem 4.8 can be extended by considering the class of analytic sets instead of the class of Borel sets. In that case any set which is analytic but not Borel is Σ 1 1 -complete, see [START_REF] Kechris | Classical descriptive set theory[END_REF], and thus there is only one more Wadge degree containing Σ 1 1 -complete sets. It was proved in [START_REF] Finkel | Borel hierarchy and omega context free languages[END_REF] that there is a Σ 1 1 -complete set accepted by a real-time 1-counter Büchi automaton, and it was proved in [START_REF] Finkel | Topological complexity of locally finite ω-languages[END_REF] that there is a local ω-language which is Σ 1 1 -complete. If we do not assume the axiom of Σ 1 1 -determinacy, we can still prove that for every Σ 1 1 -set L accepted by a real-time 1-counter Büchi automaton there exists a local ω-language L such that L ≡ W L . Indeed By Lemma 4.7 of [START_REF] Finkel | The determinacy of context-free games[END_REF] the conclusion of the above Lemma 4.12 is also true if L is assumed to be an analytic but non-Borel set, and thus the proof of Lemma 4.13 can be adapted if L is an analytic but non-Borel set. Notice also that in the same way the proofs of [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF] can be adapted to this case, using [Fin13, Lemma 4.7] instead of the above Lemma 4.12. This way we easily see that for every effective analytic but non-Borel set L ⊆ Σ ω , where Σ is a finite alphabet, there exists an ω-language L in r-BCL(1) ω such that L ≡ W L.

We can finally summarize our results by the following theorem.

Theorem 4.14 The Wadge hierarchy of the class LOC ω is the Wadge hierarchy of the class r-BCL(1) ω and also of the class Σ 1 1 of effective analytic sets.

From this result, from the fact that for each non-null countable ordinal α the Σ 0 α -complete sets (respectively, the Π 0 α -complete sets) form a single Wadge degree, and from the results of [KMS89], we can infer the following result.

Corollary 4.15 For each non-null recursive ordinal α < ω CK 1 there exist some Σ 0 α -complete and some Π 0 α -complete local ω-languages. And the supremum of the set of Borel ranks of local ω-languages is the ordinal γ 1 2 , which is precisely defined in [START_REF] Kechris | Π 1 1 Borel sets[END_REF].

We can now also show that the topological complexity of a local ω-language may depend on the models of set theory. We first recall the following result, proved in [START_REF] Finkel | The complexity of infinite computations in models of set theory[END_REF]. We refer the reader to [START_REF] Finkel | The complexity of infinite computations in models of set theory[END_REF] and to a book on set theory like [START_REF] Jech | Set theory[END_REF] for more details about the notions appearing here.

Theorem 4.16 ([Fin09a]

) There is a real-time 1-counter Büchi automaton A which can be effectively constructed and for which the topological complexity of the ω-language L(A) is not determined by the axiomatic system ZFC. Indeed it holds that :

(ZFC + V=L).

The ω-language L(A) is an analytic but non-Borel set.

(ZFC + ω

L 1 < ω 1 ). The ω-language L(A) is a Π 0 2 -set.
Notice that, from a real time 1-counter Büchi automaton A reading words over the alphabet Σ, one can effectively construct a local sentence ϕ such that L Σ ω (ϕ) = h(L(A)) ∪ h(Σ ω ) -, where h is the mapping defined above. Moreover it follows from the previous proofs that if L(A) is a Π 0 2 -set then the local ωlanguage L Σ ω (ϕ) is also a Π 0 2 -set and that if L(A) is an analytic but non-Borel set then the local ω-language L Σ ω (ϕ) is also an analytic but non-Borel set. Thus we can now state the following result.

Theorem 4.17 There is a local sentence ϕ which can be effectively constructed and a finite alphabet Σ, such that the topological complexity of the ω-language L Σ ω (ϕ) is not determined by the axiomatic system ZFC. Indeed it holds that :

(ZFC + V=L).

The ω-language L Σ ω (ϕ) is an analytic but non-Borel set. 2. (ZFC + ω L 1 < ω 1 ). The ω-language L Σ ω (ϕ) is a Π 0 2 -set.

As a complement we now add some high undecidability results which can be obtained from the previous constructions and from results of [START_REF] Finkel | Highly undecidable problems for infinite computations[END_REF] which we now recall. As in [START_REF] Finkel | Highly undecidable problems for infinite computations[END_REF], we denote below A z the real time 1-counter Büchi automaton of index z reading words over a fixed finite alphabet Σ having at least two letters. We refer the reader to a textbook like [START_REF] Odifreddi | Classical Recursion Theory[END_REF][START_REF] Odifreddi | Classical Recursion Theory[END_REF] for more background about the analytical hierarchy of subsets of the set N of natural numbers.

Theorem 4.18 [START_REF] Finkel | Highly undecidable problems for infinite computations[END_REF]) The universality, the equivalence and the inclusion problems for ω-languages accepted by real time 1-counter Büchi automata are Π 1 2 -complete, i.e.:

1. {z ∈ N | L(A z ) = Σ ω } is Π 1 2 -complete 2. {(z, z ) ∈ N | L(A z ) = L(A z )} is Π 1 2 -complete 3. {(z, z ) ∈ N | L(A z ) ⊆ L(A z )} is Π 1 2 -complete
Notice that we can associate in a recursive manner an index z to each local sentence in the recursive set L of local sentences given by Theorem 2.4. Then we can denote ϕ z the local sentence of index z in the set L. Using the previous constructions we can now easily show the following results.

Theorem 4.19 The universality, the equivalence and the inclusion problems for local ω-languages are

Π 1 2 -complete. 1. {z ∈ N | L ω (ϕ z ) = Γ ω } is Π 1 2 -complete 2. {(z, z ) ∈ N | L ω (ϕ z ) = L ω (ϕ z )} is Π 1 2 -complete 3. {(z, z ) ∈ N | L ω (ϕ z ) ⊆ L ω (ϕ z )} is Π 1 2 -complete
Proof. Firstly, it is easy to see that each of these decision problems is in the class Π 1 2 , using the fact that, for a local sentence ϕ and an ω-word x ∈ Σ ω , the sentence "x ∈ L Σ ω (ϕ)" can be expressed by a Σ 1 1 -sentence, see [START_REF] Finkel | Topological complexity of locally finite ω-languages[END_REF]Theorem 3.6].

Secondly, we have seen that, from a real time 1-counter Büchi automaton A z reading words over the alphabet Σ, one can effectively construct a local sentence ϕ such that L ω (ϕ) = h(L(A)) ∪ h(Σ ω ) -, where h is the mapping defined above. Thus there is a recursive mapping g : N → N such that the local sentence ϕ g(z) is associated to A z , i.e. such that L ω (ϕ g(z) ) = h(L(A z )) ∪ h(Σ ω ) -. In order to prove the completeness part of the theorem it suffices now to remark that the universality probem (respectively, the equivalence problem, the inclusion problem) for ω-languages accepted by real time 1-counter Büchi automata is reduced to the universality probem (respectively, the equivalence problem, the inclusion problem) for local ω-languages. This follows from the following equivalences, where Γ = Σ ∪ {A, B, 0} (notice that, using a standard coding, it is straighforward to prove the result for any alphabet having at least two letters):

1. L(A z ) = Σ ω ⇐⇒ L Γ ω (ϕ g(z) ) = Γ ω 2. L(A z ) = L(A z ) ⇐⇒ L Γ ω (ϕ g(z) ) = L Γ ω (ϕ g(z ) ) 3. L(A z ) ⊆ L(A z ) ⇐⇒ L Γ ω (ϕ g(z) ) ⊆ L Γ ω (ϕ g(z ) )

Concluding remarks

We have given a solution to the problem of the topological complexity of local ω-languages, by considering the Wadge hierarchy which is a great refinement of the Borel hierarchy. Local ω-languages have the same topological complexity as effective analytic sets; but they are "more effective" in the sense that the emptiness problem for local ω-languages is decidable while it is Σ 1 1 -complete for ω-languages of Turing machines, see [START_REF] Castro | Nondeterministic ω-computations and the analytical hierarchy[END_REF].

We have also shown that the topological complexity of a local ω-language may depend on the models of set theory. Moreover we have given the high complexity of natural decision problems for local ω-languages, like the universality, the equivalence and the inclusion problems. Notice that other problems can be shown to be Π 1 2 -complete, like the cofiniteness problem, using again the previous constructions and results from [START_REF] Finkel | Highly undecidable problems for infinite computations[END_REF].

Theorem 2 .

 2 12 ([Fin04]) The ω-Kleene closure of the class LOC of finitary local languages is strictly included in the class LOC ω of local ω-languages.

  local finitary language over the alphabet {a, b, c}, are examples of local but non context free ω-languages, [Fin01].

  Theorem 4.2 ([Fin06]) The Wadge hierarchy of the class r-BCL(1) ω is the Wadge hierarchy of the class Σ 1 1 of ω-languages accepted by Turing machines with a Büchi acceptance condition.

  d w (∅) = d w (∅ -) = 1 (b) d w (L) = sup{d w (L ) + 1 | L non self dual and L < W L}(for either L self dual or not, L > W ∅).

Theorem 4 .

 4 11 (Wadge, see[START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF][START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF]) Let X ⊆ Y , Y -X containing at least two elements, L ⊆ X ω and L ⊆ Y ω be non self dual Borel sets. Then (L + L ) is a non self dual Borel set and d w (L + L) = d w (L ) + d w (L).

  and otherwise it is said to be non self dual.The relation ≤ W is reflexive and transitive, and ≡ W is an equivalence relation. The equivalence classes of ≡ W are called Wadge degrees. The Wadge hierarchy W H is the class of Borel subsets of a set X ω , where X is a finite set, equipped with ≤ W and with ≡ W

Acknowledgements. We thank the anonymous referee for useful comments on a preliminary version of this paper.