domain: sdv info

text:
Enrico Zanetti

Dr Massimo De Marchi
email: massimo.demarchi@unipd.it

Chiara Dalvit

Caroline Molette

Hervé Rémignon

Martino Cassandro

H Remignon

Cassandro

Carcass characteristics and qualitative meat traits of three Italian local chicken breeds

Keywords: Meat quality, Carcass characteristics, Local chicken breeds

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

INTRODUCTION 48

Consumer interest is growing in specialty poultry products, particularly in Europe. Examples 49 exist in France, with 'Label Rouge' [START_REF] Westgren | Delivering food safety, food quality, and sustainable production 317 practices: The Label Rouge Poultry System in France[END_REF] and Poulet de Bresse, and in Italy with 50 Padovana chicken [START_REF] De Marchi | 258 Carcass characteristics and qualitative meat traits of the Padovana breed of chicken[END_REF]. Production systems require extensive rearing 51 conditions with outdoor access. Despite a higher retail price than conventional poultry 52 products, these types of chicken have aroused lively interest in national markets (Westgren, 53 1999;[START_REF] Fanatico | The state of the world's animal genetic resources for food and agriculture. 275 Commission on genetic resources for food and agriculture[END_REF]. In Italy, among those slow-growing genotypes there are 54 several local chicken breeds that showed interesting meat quality traits (e.g. colour and 55 flavour) (De Marchi et al., 2006a). Fast-growing meat strains of chicken are characterised by 56 a very low degree of adaptation and resistance to natural environment (Reiter and Bessei, 57 1996); in contrast, the slow-growing strains can fully benefit from organic system (pasture 58 availability, older age). Several studies have investigated differences in the sensory quality of 59 meat from fast-and slow-growing birds, but there was a wide variation in breed (purebred, 60 broiler or layer), slaughter age and production system (standard, extensive or organic) 61 [START_REF] Touraille | Chicken meat quality. 1. 309 Influence of age and growth rate on physicochemical and sensory characteristics of the meat[END_REF][START_REF] Brown | Aspects 234 of meat and eating quality of broiler chickens reared under standard, maize-fed, free-range or 235 organic systems[END_REF][START_REF] Jaturasitha | Differences in 289 Carcass and Meat Characteristics Between Chicken Indigenous to Northern Thailand (Black-290 Boned and Thai Native) and Imported Extensive Breeds (Bresse and Rhode Island Red)[END_REF][START_REF] Sandercock | Quantifying the effects of 302 genetic selection and genetic variation for body size, carcass composition, and meat quality in 303 the domestic fowl (Gallus domesticus)[END_REF]. 62

This has produced contrasting results regarding consumer preference and acceptance, but 63 reports have generally been more favorable for slower-growing birds than conventional 64 products. 65 In the Veneto region of Italy, the increasing interest in the conservation of bovine, ovine 66 and poultry local breeds (De Marchi et al., 2006a,b;Dalvit et al., 2008[START_REF] Dalvit | Genetic variation 255 and population structure of Italian native sheep breeds undergoing in situ conservation[END_REF]Zanetti et al., 67 2010) is due to historical, social and economical reasons. A few breeds of chicken, Padovana 68 (PA), Ermellinata (EA), and Pépoi (PI), which are typically reared in extensive systems, provide 69 interesting alternatives to commercial broilers. The recent development of organic animal 70 production and consumer requests for food safety and sustainable systems of production might 71 encourage the use of local chicken breeds for several niche markets. Previous research has been 72

focused on the carcase characteristics and quality meat traits of the Padovana breed of chicken 73 [START_REF] De Marchi | 258 Carcass characteristics and qualitative meat traits of the Padovana breed of chicken[END_REF] because it has been in great demand. 74

The interest in local genotypes has increased noticeably in the last decade, mostly 75 because biodiversity conservation and management has become an important issue for the 76 international scientific community (Fao, 2007). Productive performance analysis and 77 phenotypic traits, together with genetic diversity, reproductive and adaptative performances, 78 and historical interest, are therefore highly relevant to the inclusion of local breeds in 79 conservation programmes [START_REF] Ruane | Genebanks and the conservation of farm animal genetic resources[END_REF]. 80

The objective of this research was to describe carcase characteristics and qualitative 81 meat traits of three local Italian chicken breeds at maturity, as well as at a light, medium or 82 heavy body weight. 83

MATERIALS AND METHODS 84

Animals, diets and experimental procedures 85

A trial was conducted at the Duca degli Abruzzi Agricultural High School in Padova. Three 86 slow-growing genotypes were compared, Pépoi (PI), Padovana (PA) and Ermellinata (EA), 87 and categorised according to the weight they reached at 190 d (market weight): PI had a live 88 weight of 1400 -1600 g, PA a live weight of 2000 -2200 g and EA a live weight of 2800 -89 3000 g (De Marchi et al., 2006a). Twenty 30-d male birds were obtained from each breed and 90 housed together in an indoor pen (5 birds/m 2 ) which had access to a grass paddock (4 91 m 2 /bird). All birds were provided with a grower diet (210 g CP/kg, 50 g/kg lipids, 40 g/kg 92 fibre, 70 g/kg ash, and 13.39 MJ ME/kg) from 2 d before the trial commenced until slaughter 93 at 190 d. Ingredients for the grower diet were maize flour, toasted soybean meal, maize gluten 94 meal, maize gluten, soybean oil, dicalcium phosphate, calcium carbonate, sodium chloride 95 and DL-methionine. Feed and water were supplied ad libitum. The diets were crumbled 96 vegetable diet without animal products, antibiotics or coccidiostats. A total of 60 birds (20 97 males for each breed) were slaughtered at 190 d of age. Feed was withdrawn 18 h prior to 98 slaughter, and the birds weighed, electronically stunned, plucked and eviscerated. 99 The carcases were cooled in a tunnel, refrigerated at 4° C for 24 h and weighed. The breast 100 and thigh meat from all chickens were then harvested and processed for meat quality 101 parameters determination. Other breast meat samples were also collected and stored at -20°C 102 for further analyses. 103

Analytical determinations 104

Breast (Pectoralis superficialis) and thigh (Peroneus longus) muscle pH were measured 24 h 105 post-mortem using a Delta Ohm HI-8314 pH-meter (Delta Ohm, Padova Italy). Colour, 106 tenderness and cooking loss were also determined 24 h post-mortem. Colour parameters were 107 measured using a Minolta CM-508c (illuminate: D65, observer: 10°) on thigh and breast skin 108 and on breast meat. Breast meat colour was taken immediately after skin removal. Readings 109 were performed at the same anatomical positions for all breast and thigh samples. For each 110 sample, three measurements were performed and the final value for each chicken was the 111 average of those readings. Skin colour of breast and thigh and meat colour of breast were 112 expressed in the CIELab colour space by reporting L*, a* and b* values [START_REF] Cie | International Commission on Illumination, recommendations on uniform color 246 spaces, color, difference equations, psychometric color terms[END_REF]. 113

Cooking loss percentage (CL%), expressed as the ratio of the weight before and after 114 cooking, was measured on the left part of the breast muscle without the skin using 2-cm thick 115 samples sealed in a polyethylene bag and heated in a water bath to an internal temperature of 116 70°C for 40 min [START_REF] Aspa | Associazione Scientifica di Produzione Animale, Metodiche per la 232 determinazione delle caratteristiche qualitative della carne[END_REF]. Shear force (SF) on breast muscle was measured on 5 117 cylindrical cores, 1.13 cm in diameter and taken parallel to muscle fibres, using a TA-HDi 118 Texture Analyser (Stable Macro System, London, Great Britain) with a Warner-Bratzler shear 119 attachment (10 N load cell, crosshead speed of 2 mm/s) and interpreted using texture expert 120 software [START_REF] Aspa | Associazione Scientifica di Produzione Animale, Metodiche per la 232 determinazione delle caratteristiche qualitative della carne[END_REF]. 121

All chemical analyses were performed on the right breast, without skin, and were in 122 accordance with [START_REF] Aoac | Official Methods of Analysis[END_REF] standards. Moisture was determined after drying at 102°C for 123 16 h, ash was determined after mineralisation at 525°C for 6 h and total lipids analysed by 124 extraction with petroleum ether (Soxhlet method). Protein content was estimated by 125 difference. For the determination of total fatty acids composition, lipids were extracted 126 according to the method of [START_REF] Folch | A simple method for the isolation 278 and purification of total lipids from animal tissue[END_REF]. A 5-g homogenised meat sample was blended 127 twice with extraction solvent chloroform/methanol (1:2, v/v), filtered, placed in separator 128 funnels and mixed with saline solution (0.88% KCl). After separation in two phases, the 129 methanol aqueous fraction was discarded and the lipid chloroform fraction washed with 130 distilled water/methanol (1:1, v/v). Following a further filtration and evaporation in a rotary 131 evaporator, lipid extracts were prepared for trans-esterification in n-Heptane according by 132 [START_REF] Christie | A simple procedure for rapid transmethylation of glycerolipids and 244 cholesterol ester[END_REF] 1). The pH values 152 measured in the breast muscle were significantly higher for PA than the other two breeds, 153 while, the thigh pH of PI birds had the highest values. The PA breed showed the highest 154 tenderness followed by EA and PI, while cooking loss values were higher for PI breed relative 155 to PA and EA birds. 156 Breast and thigh colour values are shown in Table 2. PA breed showed a significantly 157 higher L* value of breast skin than PI or EA, while the PI showed significantly lower a* and 158 b* values than PA or EA. The L* value of thigh skin for PI was significantly higher than 159 either PA or EA, a* indices were not significantly different for the three breeds, while the b* 160 index was significantly higher for EA than either PI or PA. The breast meat colour for PA had 161 a significantly lower L* value than for EA or PI, while EA b* values were significantly lower 162 than PA or PI. 163

Raw breast meat (without the skin) fatty acid compositions are shown in Table 3. 164 Ermellinata breed had a significantly higher content of saturated (SFA) but lower amount of 165 monounsaturated (MUFA) fatty acids than either PA or PI. There were no significant 166 differences between breeds for n-3 and n-6 polyunsaturated fatty acids. Ermellinata differed 167 from the other breeds because of a higher C 16:0 content and a lower production of C 18:1cis n-9 and 168 C 18:2cis n-6 fatty acids (Table 4). There were no significant differences in DPA nor CLA fatty 169 acids among breeds but PI breast meat had a significantly higher content of DHA than PA. 170 DISCUSSION 171

The EA, PA and PI chickens exhibited medium, light and very light carcase weights 172 respectively. The dressing and breast percentages of PA were slightly lower than those 173 reported for the same breed by De [START_REF] De Marchi | 258 Carcass characteristics and qualitative meat traits of the Padovana breed of chicken[END_REF]. Dressing percentages for PA, EA and 174 PI breeds were also slightly lower than those reported for local Thai chicken genotypes 175 (Jasurasitha et al., 2008) and markedly lower than that reported for commercial broilers 176 [START_REF] Havenstein | Carcass composition and 281 yield of 1957 versus 2001 broilers when fed representative 1957 and 2001 broiler diets[END_REF]Cortinas et al., 2004). These results indicate that the Italian local 177 chicken breeds have relatively low carcase weights, and inferior dressing and breast 178 percentages to other meat-type genotypes. 179 Contrastingly, the pH values were higher than expected; possible reasons are slaughter 180 stress and a higher content of oxidative muscle fibre in other common slow-growing genotypes 181 [START_REF] Dransfield | Relationship Between Muscle Growth and 271 Poultry Meat Quality[END_REF]. Regarding the first hypothesis, it is likely that the old 182 unselected breeds have a more aggressive and alert behaviour than the modern broilers 183 (Jaturasitha et al., 2004;Debut et al., 2005); this higher sensibility to the stressful conditions 184 before slaughter can lead to poor glycogen content in muscle at the time of death. However, no 185 other information is available concerning muscle fibre analysis for these breeds. breeds were similar to those reported for other organic chickens [START_REF] Castellini | Impiego della razza Ancona per 242 l'impiego di un pollastro di qualità[END_REF]192 Castellini et al., 2002). In contrast, protein, lipids and ash contents were higher for the Italian 193 local breeds than for Thai indigenous chickens or normal commercial broilers (Wattanachant 194 et al., 2004). As expected, local chicken muscle contains a high proportion of protein and low 195 fat and ash contents, which agrees with previously reported findings from Wattanachant et al. 196 (2005). The PA and EA breeds showed a greater cooking loss compared with the values 197 reported by De [START_REF] De Marchi | 258 Carcass characteristics and qualitative meat traits of the Padovana breed of chicken[END_REF] and Rizzi et al. (2007). 198 Low L* values are associated to a higher ultimate pH value because of the weak light 199 scattering in high-pH chicken meat [START_REF] Swatland | How pH causes paleness or darkness in chicken breast meat[END_REF]. The darker breast muscle of the PA 200 breed can thus reflect differences in the muscle fibre composition and in the glycogen content 201 of the muscle. For this reason, the analysis of breast meat L* values were also conducted 202 using the fixed effect of breed and the effect of pH as co-variate. In the preliminary analysis, 203 the interaction between breed and pH was not significant. Furthermore, the PA had the lowest 204 L* value of breast meat. 205

The fatty acid composition of the breast meat in this study was similar to that reported 206 by De [START_REF] De Marchi | 258 Carcass characteristics and qualitative meat traits of the Padovana breed of chicken[END_REF] and [START_REF] Castellini | Comparison 237 of two chicken genotypes organically reared: oxidative stability and other qualitative traits of 238 the meat[END_REF] for Ross 205 and Kabir chickens reared 207 in an organic rearing system. The observed differences in SFA and MUFA among the three 208 breeds in this study can be attributed only to their genetic make-up, because diets and rearing 209 system were identical for all breeds throughout the experimental period. Even the highest 210 saturated fatty acid contents of the EA breed were still lower than those reported for organic 211 (38%) and Thai local chickens (62%) [START_REF] Wattanachant | Composition, Color, 315 and Texture of Thai Indigenous and Broiler Chicken Muscles[END_REF]. Among SFA, palmitic 212 (C16:0) and stearic (C18:0) acids were the most abundant, as generally observed in chicken 213 breast meat. 214

In conclusion, the study demonstrated significant differences in meat quality traits 215 among the three breeds studied, for example in carcase yield, colour, tenderness and fatty acid 216 composition. From a consumer point of view, each breed offers unique features. Besides a 217 greater traditional interest and a high historical and cultural value, the tenderness of the PA meat 218 and its distinctively darker colour differentiated it from the other breeds. In contrast, none of the 219 meat quality traits of EA and PI showed the meat of these breeds to be significantly distinctive 220 from other meat-type genotypes. Additionally, adaptability features, traits of scientific and 221 economic interests, cultural\historical value, strong links to local traditions and its ability to 222 generate incomes from tourism justify the efforts for their conservation and characterisation 223 [START_REF] Ruane | Genebanks and the conservation of farm animal genetic resources[END_REF]. The commercialisation and capitalisation of local markets represent an 224 opportunity for future added value and development of these local genetic resources. 225

Alternative strategies, such as the use of crosses of these breeds with more productive 226 commercial breeds, are currently under evaluation to enhance their use for niche and regional 227 markets. 228

  Nevertheless, 186 the breast pH values of the PA breed were lower than those reported previously by De Marchi et 187 al. (2005) for the PA breed. 188 Dry matter, protein and lipid contents of the breast muscles differed slightly among 189 breeds. The chemical composition of the PA breed breast was consistent with values reported 190 by De Marchi et al. (2005). The dry matter and protein contents of these three local Italian 191

  and transferred to test tubes for subsequent gas chromatographic analysis, 133 The least square means of carcase composition, pH values, breast chemical composition, 142 shear force and cooking loss values are shown in Table 1. Final live weights of the three 143 breeds at 190 d of age (just before slaughter) were significantly different. Ermellinata had 144 heavier live, carcase and thigh weights than PA and PI, while PI had lighter breast weight 145 than PA and EA. Breast weight and total dressing did not differ statistically for PA and EA, 146 while the incidence of breast on carcase weight was similar for PA and PI. Dressing 147 percentage was greater for PA and EA than PI, while PA and PI had greater breast percentage 148 than EA. 149 Dry matter, protein and lipid contents of the breast muscle differed only slightly 150 among breeds (Table 1). Maximum shear force values for PA birds, as measured on cooked 151 breast muscle, were significantly different from the other breeds (Table

	134	which was conducted on a Thermo Quest (model 8000 Series Top, Milan, Italy) instrument
	135	equipped with a Omegawax 250 capillary column (length 30 m, internal diameter 0.25 mm,
	136	Supelco, Bellafonte, PA, USA).
	137	Statistical analysis
	138	Data were subjected to ANOVA by the GLM procedure considering breed as a fixed effect
	139	using SAS ® software (1997, SAS Institute, Cary, NC). For breed effect, a multiple
	140	comparison of means was performed using the Bonferroni's test (P < 0.05).
	141	r o F	RESULTS
		P
		e
		e r
			R
			e
			v i e
			w
			O n l
			y

Table 1

 1

	near here
	Tables 2 & 3 near here

Table 1 .

 1 Least square means of carcase composition, pH values, breast chemical 324 composition, shear force and cooking loss values of Ermellinata, Padovana and Pépoi slow-325

	326	growing chicken at 190 d of age
			Padovana	Breed Ermellinata	Pèpoi	r²	Res MS
		-Live weight (LW), g	2144 b	2718 a	1434 c	0.89	187
		-Carcase weight (CW), g	1346 b	1726 a	879 c	0.88	125
		-Breast weight (BW), g	225 a	243 a	140 b	0.72	29
		-Thigh weight (TW), g	478 b	667 a	322 c	0.89	50
		Dressing (CW/LW), %	63 a	64 a	61 b	0.27	1.59
		Breast (BW/CW), %	17 a	14 b	16 a	0.27	1.88
		Thigh (TW/CW), %	35 c	38 a	36 b	0.39	1.60
		Breast meat pH	6.18 a	5.97 b	5.99 b	0.21	0.18
		Thigh meat pH	6.19 b	6.15 b	6.30 a	0.16	0.15
		Breast muscle chemical composition
		-Dry matter (%)	24.85 b	26.18 a	25.45 ab	0.26	0.95
		-Total proteins (%)	23.23 b	24.65 a	23.89 b	0.11	0.79
		-Total lipids (%)	0.61 a	0.29 b	0.48 ab	0.37	0.28
		-Ash (%)	1.08	1.12	1.10	0.20	0.05
		Shear Force (N)	12.51 a	16.76 b	15.84 b	0.19	3.82
		Cooking loss (%)	18.20 b	19.31 b	22.34 a	0.29	2.81
	327	a,b,c Within a row, means not sharing a common superscript are significantly different at P
	328		<0.05.

Table 2 .

 2 Breast and thigh colour values of Ermellinata, Padovana and Pépoi slow-growing

	329
	330			chicken at190 d of age.
		Item	Breed Padovana Ermellinata Pepoì	r²	Res MS
		Skin colour
		Breast
		-L*	62.41 a	56.96 b	59.20 b	0.32	3.27
		-a*	-2.15 a	-2.42 a	-3.07 b	0.25	0.69
		-b*	1.91 a	1.06 a	-1.47 b	0.21	2.84
		Thigh
		-L*	62.08 b	62.35 b	63.81 a	0.15	1.89
		-a*	-2.19	-1.99	-2.47	0.08	0.69
		-b*	-1.97 c	3.94 a	0.01 b	0.62	1.94
		Meat colour
		Breast
		-L*	46.00 a	48.41 b	49.84 b	0.35	2.38
		-a*	-1.42	-1.72	-1.39	0.11	0.42
		-b*	-0.45 a	-1.64 b	0.04 a	0.14	1.75
	331	a,b Within a row, means not sharing a common superscript are significantly different at
	332	P <0.05.

Table 3 .

 3 Least square means of raw breast (without skin) fatty acid composition of

	333
	334	Ermellinata, Padovana and Pépoi slow-growing chicken at 190 d of age
			Breed Padovana Ermellinata	Pépoi	r²	Res MS
		Breast muscle	% of total analysed fatty acid
		Total SFA	33.88 b	35.59 a	32.82 b	0.46	1.29
		Total MUFA	23.45 a	20.21 b	24.92 a	0.39	2.55
		Total PUFA	40.24	41.38	40.09	0.05	2.71
		Total n-6 FA	36.63	37.74	36.23	0.08	2.27
		Total n-3 FA	3.60	3.64	3.85	0.02	0.73
		n-6/n-3	10.51	10.93	9.66	0.06	2.19
	335	a,b Within a row, means not sharing a common superscript are significantly different at
	336	P <0.05.
	337	SFA: saturated fatty acid; MUFA: monounsaturated fatty acid; PUFA: polyunsaturated
	338	fatty acid; FA: fatty acid.

Table 4 .

 4 Least square means of raw breast (without skin) detailed fatty acid 339 composition of Ermellinata, Padovana and Pépoi slow-growing chicken at 190 d of age

	340
	341
	342
		Fatty acid	Breed Padovana Ermellinata	Pépoi	r²	Res MS
		Breast muscle	% of total analysed fatty acid
		C6:0	0.02	0.02	0.01	0.18	0.02
		C8:0	0.06 b	0.10 a	0.11 a	0.40	0.03
		C10:0	0.06	0.08	0.07	0.08	0.02
		C12:0	0.03	0.02	0.02	0.08	0.02
		C14:0	0.44 a	0.29 b	0.28 b	0.28	0.12
		C15:0	0.09	0.08	0.07	0.08	0.02
		C16:0	20.65 a	21.40 a	19.50 b	0.34	1.13
		C17:0	0.28 a	0.25 ab	0.24 b	0.16	0.04
		C18:0	11.51 b	12.64 a	11.86 b	0.27	0.81
		C20:0	0.08 ab	0.06 b	0.09 a	0.15	0.04
		C21:0	0.01	0.01	0.01	0.10	0.01
		C22:0	0.01 b	0.01 b	0.02 a	0.21	0.02
		C10:1 n-1	0.05	0.04	0.04	0.05	0.02
		C14:1 n-1	0.01	0.01	0.01	0.01	0.01
		C16:1 n-9	0.20	0.16	0.18	0.09	0.05
		C16:1 n-7	0.39	0.34	0.46	0.08	0.17
		C17:1 n-9	0.03	0.07	0.11	0.09	0.10
		C17:1 n-7	0.01 b	0.01 ab	0.02 a	0.38	0.01
		C18:1 n-7 trans	0.04	0.03	0.02	0.13	0.02
		C18:1 n-9 trans	0.01 b	0.02 ab	0.02 a	0.17	0.01
		C18:1 n-9 cis	20.69 a	17.79 b	21.53 a	0.33	2.38
		C18:1 n-7 cis	1.73 b	1.46 c	2.18 a	0.68	0.21
		C20:1 n-9	0.19 a	0.13 b	0.22 a	0.34	0.05
		C18:2 n-6 trans	0.01	0.01	0.01	0.04	0.01
		C18:2 n-6 cis	25.25 a	21.79 b	21.84 b	0.18	3.52
		C18:3 n-6	0.08 a	0.04 b	0.05 b	0.32	0.03
		C18:3 n-3	0.93 a	0.56 b	0.61 b	0.26	0.28
		CLA	0.01	0.01	0.01	0.06	0.01
		C20:2 n-6	0.45 a	0.39 b	0.43 ab	0.15	0.05
		C20:3 n-6 cis	0.41 b	0.73 a	0.54 b	0.43	0.16
		C20:4 n-6	9.06 b	13.11 a	11.78 ab	0.19	3.64
		C22:1 n-9 cis	0.01	0.01	0.01	0.03	0.01
		C20:5 n-3 cis	0.06	0.05	0.08	0.03	0.06
		C22:2 n-6	0.17	0.29	0.22	0.10	0.16
		C22:4 n-6	0.01	0.03	0.01	0.14	0.04
		C22:5 n-6	1.19	1.33	1.36	0.04	0.34
		C24:1 n-9 cis	0.30	0.29	0.34	0.02	0.13
		C22:5 n-3 DPA	1.19	1.37	1.26	0.04	0.41
		C22:6 n-3 DHA	1.42 b	1.66 ab	1.90 a	0.13	0.53
	343	a,b Within a row, means not sharing a common superscript are significantly different at P
	344	<0.05.
	345
	346

E-mail: br.poultsci@bbsrc.ac.uk URL: http://mc.manuscriptcentral.com/cbps British Poultry Science


Olivier Finkel
email: finkel@logique.jussieu.fr

Stevo Todor

A HIERARCHY OF TREE-AUTOMATIC STRUCTURES

Keywords: Automata reading ordinal words, ω n -automatic structures, ω-treeautomatic structures, boolean algebras, partial orders, rings, groups, isomorphism relation, models of set theory, independence results

.

§1. Introduction. An automatic structure is a relational structure whose domain and relations are recognizable by finite automata reading finite words. Automatic structures have very nice decidability and definability properties and have been much studied in the last few years, see [START_REF] Blumensath | Automatic structures[END_REF][START_REF]Finite presentations of infinite structures: Automata and interpretations[END_REF][START_REF] Khoussainov | Automatic structures: Richness and limitations[END_REF][START_REF] Nies | Describing groups[END_REF][START_REF] Rubin | Automatic structures[END_REF][START_REF]Automata presenting structures: A survey of the finite string case[END_REF]. They form a subclass of the class of (countable) recursive structures where "recursive" is replaced by "recognizable by finite automata". Blumensath considered in [START_REF] Blumensath | Automatic structures[END_REF] more powerful kinds of automata. If we replace automata by tree automata (respectively, Büchi automata reading infinite words, Muller or Rabin tree automata reading infinite labelled trees) then we get the notion of tree-automatic (respectively, ω-automatic, ω-tree-automatic) structures. Notice that an ω-automatic or ω-tree-automatic structure may have uncountable cardinality. All these kinds of automatic structures have the two following fundamental properties. [START_REF] Büchi | The monadic second order theory of all countable ordinals[END_REF] The class of automatic (respectively, tree-automatic, ω-automatic, ω-tree-automatic) structures is closed under first-order interpretations. [START_REF] Bedon | Finite automata and ordinals[END_REF] The first-order theory of an automatic (respectively, tree-automatic, ω-automatic, ω-tree-automatic) structure is decidable.

On the other hand, automata reading words of ordinal length had been firstly considered by Büchi in his investigation of the decidability of the monadic second some related notions. We investigate in Section 6 the isomorphism relation for ω n -automatic structures and for ω-tree-automatic structures. Some concluding remarks are given in Section 7. §2. Automata.

2.1. ω n -Automata. When Σ is a finite alphabet, a non-empty finite word over Σ is any sequence x = a 0 .a 1 . . . a k , where a i ∈ Σ for i = 1, . . . , k , and k is an integer ≥ 0. The length of x is k + 1. The empty word has no letter and is denoted by ε; its length is 0. For x = a 0 .a 1 . . . a k , we write x(i) = a i . Σ ⋆ is the set of finite words (including the empty word) over Σ.

We assume the reader to be familiar with the elementary theory of countable ordinals. Let Σ be a finite alphabet, and α be an ordinal; a word of length α (or α-word) over the alphabet Σ is an α-sequence (x(β)) β<α (or sequence of length α) of letters in Σ. The set of α-words over the alphabet Σ is denoted by Σ α . The concatenation of an α-word x = (x(β)) β<α and of a γ-word y = (y(β)) β<γ is the (α + γ)-word z = (z(β)) β<α+γ such that z(β) = x(β) for β < α and z(β) = y(β ′ ) for α ≤ β = α + β ′ < α + γ; it is denoted z = x • y or simply z = xy.

We assume that the reader is familiar with the notion of Büchi automaton reading infinite words over a finite alphabet which can be found for instance in [START_REF] Thomas | Automata on infinite objects[END_REF][START_REF] Staiger | ω-languages[END_REF]. Informally speaking an ω-word x over Σ is accepted by a Büchi automaton A iff there is an infinite run of A on x enterring infinitely often in some final state of A. The ω-language L(A) ⊆ Σ ω accepted by the Büchi automaton A is the set of ω-words x accepted by A. A Muller automaton is a finite automaton equipped with a set F of accepting sets of states. An ω-word x over Σ is accepted by a Muller automaton A iff there is an infinite run of A on x such that the set of states appearing infinitely often during this run is an accepting set of states, i.e. belongs to F . It is well known that an ω-language is accepted by a Büchi automaton iff it is accepted by a Muller automaton.

We shall define ω n -automatic structures as relational structures presentable by automata reading words of length ω n , for some integer n ≥ 1. In order to read some words of transfinite length greater than ω, an automaton must have a transition relation for successor steps defined as usual but also a transition relation for limit steps. After the reading of a word whose length is a limit ordinal, the state of the automaton will depend on the set of states which cofinally appeared during the run of the automaton. These automata have been firstly considered by Büchi, see [START_REF] Büchi | The monadic second order theory of all countable ordinals[END_REF][START_REF] Hemmer | Automates sur mots de longueur supérieure à ω[END_REF]. We recall now their definition and behaviour. Definition 2.1 ([45, 46, 2]). An ordinal Büchi automaton is a sextuple (Σ, Q, q 0 , ∆, γ, F ), where Σ is a finite alphabet, Q is a finite set of states, q 0 ∈ Q is the initial state, ∆ ⊆ Q × Σ × Q is the transition relation for successor steps, and γ ⊆ P (Q) × Q is the transition relation for limit steps.

A run of the ordinal Büchi automaton A = (Σ, Q, q 0 , ∆, γ, F ) reading a word σ of length α, is an (α + 1)-sequence of states x defined by: x(0) = q 0 and, for i < α, (x(i), σ(i), x(i + 1)) ∈ ∆ and, for i a limit ordinal, (Inf (x, i), x(i)) ∈ γ, where Inf (x, i) is the set of states which cofinally appear during the reading of the i first letters of σ, i.e.

Inf (x, i) = {q ∈ Q | ∀µ < i, ∃ν < i such that µ < ν and x(ν) = q}
A run x of the automaton A over the word σ of length α is called successful if x(α) ∈ F . A word σ of length α is accepted by A if there exists a successful run of A over σ. We denote L α (A) the set of words of length α which are accepted by A. An α-language L is a regular α-language if there exists an ordinal Büchi automaton A such that L = L α (A).

An ordinal Büchi automaton (Σ, Q, q 0 , ∆, γ, F ) is said to be deterministic iff ∆ ⊆ Q × Σ × Q is in fact the graph of a function from Q × Σ into Q and γ ⊆ P (Q) × Q is the graph of a function from P (Q) into Q.
In that case there is at most one run of the automaton over a given word σ.

Remark 2.2. When we consider only finite words, the language accepted by an ordinal Büchi automaton is a rational language. If we consider only ω-words, the ω-languages acceped by ordinal Büchi automata are the ω-languages accepted by Muller automata and then also by Büchi automata. Definition 2.3. An ω n -automaton is an ordinal Büchi automaton reading only words of length ω n for some integer n ≥ 1.

We can obtain regular ω n -languages from regular ω-languages and regular ω n-1 -languages by the use of the notion of substitution. The following result appeared in [START_REF] Hemmer | Automates sur mots de longueur supérieure à ω[END_REF] and has been also proved in [START_REF] Finkel | Locally finite languages[END_REF].

Proposition 2.4. Let n ≥ 2 be an integer. An ω n -language L ⊆ Σ ω n is regular iff it is obtained from a regular ω-language R ⊆ Γ ω by substituting in every ω-word σ ∈ R a regular ω n-1 -language L a ⊆ Σ ω to each letter a ∈ Γ.

We now recall some fundamental properties of regular ω n -languages.

Theorem 2.5 (Büchi-Siefkes, see [START_REF] Büchi | The monadic second order theory of all countable ordinals[END_REF][START_REF] Hemmer | Automates sur mots de longueur supérieure à ω[END_REF][START_REF] Bedon | Finite automata and ordinals[END_REF]). Let n ≥ 1 be an integer. One can effectively decide whether the ω n -language L(A) accepted by a given ω nautomaton A is empty or not.

Theorem 2.6. [see [START_REF] Bedon | Finite automata and ordinals[END_REF]] Let n ≥ 1 be an integer. The class of regular ω nlanguages is effectively closed under finite union, finite intersection, and complementation, i.e. we can effectively construct, from two ω n -automata A and B, some

ω n -automata C 1 , C 2 , and C 3 , such that L(C 1 ) = L(A) ∪ L(B), L(C 2 ) = L(A) ∩ L(B), and L(C 3 ) is the complement of L(A).
We assume the reader to be familiar with basic notions of topology that may be found in [START_REF] Moschovakis | Descriptive set theory[END_REF][START_REF] Kechris | Classical descriptive set theory[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF]. The usual Cantor topology on Σ ω is the product topology obtained from the discrete topology on the finite set Σ, for which open subsets of Σ ω are in the form W • Σ ω , where W ⊆ Σ ⋆ .

Let n ≥ 1 be an integer. Let B : ω → ω n be a recursive bijection. Then we have a bijection φ from Σ ω n onto Σ ω defined by φ(x)(n) = x(B(n)) for each integer n ≥ 0. Then for each ω n -language L ⊆ Σ ω n we have the associated ωlanguage φ(L) = {φ(x) | x ∈ L}. Consider now a regular ω n -language L ⊆ Σ ω n . It is stated in [START_REF] Duparc | Computer science and the fine structure of Borel sets[END_REF] that φ(L) is Borel (in the class Σ 0 2n+1 ). 2.2. Tree automata. We introduce now languages of infinite binary trees whose nodes are labelled in a finite alphabet Σ.

A node of an infinite binary tree is represented by a finite word over the alphabet {l, r} where r means "right" and l means "left". Then an infinite binary tree whose nodes are labelled in Σ is identified with a function t : {l, r} ⋆ → Σ. The set of infinite binary trees labelled in Σ will be denoted T ω Σ . A tree language is a subset of T ω Σ , for some alphabet Σ. (Notice that we shall only consider in the sequel infinite trees so we shall often use the term tree instead of infinite tree).

Let t be a tree. A branch B of t is a subset of the set of nodes of t which is linearly ordered by the prefix relation ⊑ and which is closed under this prefix relation, i.e. if x and y are nodes of t such that y ∈ B and x ⊑ y then x ∈ B. A branch B of a tree is said to be maximal iff there is not any other branch of t which strictly contains B.

Let t be an infinite binary tree in T ω Σ . If B is a maximal branch of t, then this branch is infinite. Let (u i ) i≥0 be the enumeration of the nodes in B which is strictly increasing for the prefix order. The infinite sequence of labels of the nodes of such a maximal branch B, i.e. t(u 0 )t(u 1 ) . . . t(u n ) . . . is called a path. It is an ω-word over the alphabet Σ.

For a tree t ∈ T ω Σ and u ∈ {l, r} ⋆ , we shall denote t u : {l, r} ⋆ → Σ the subtree defined by t u (v) = t(uv) for all v ∈ {l, r} ⋆ . It is in fact the subtree of t which is rooted in u.

We are now going to define tree automata and regular languages of infinite trees.

Definition 2.7. A (nondeterministic) tree automaton is a quadruple A = (Q, Σ, ∆, q 0 ), where Q is a finite set of states, Σ is a finite input alphabet, q 0 ∈ Q is the initial state and ∆ ⊆ Q × Σ × Q × Q is the transition relation. A run of the tree automaton A on an infinite binary tree t ∈ T ω Σ is an infinite binary tree ρ ∈ T ω Q such that: (a) ρ(ε) = q 0 and (b) for each u ∈ {l, r} ⋆ , (ρ(u), t(u), ρ(ul), ρ(ur)) ∈ ∆.

A Muller (nondeterministic) tree automaton is a 5-tuple A = (Q, Σ, ∆, q 0 , F ), where (Q, Σ, ∆, q 0 ) is a tree automaton and F ⊆ 2 Q is the collection of designated state sets. A run ρ of the Muller tree automaton A on an infinite binary tree t ∈ T ω Σ is said to be accepting if for each path p of ρ, the set of states appearing infinitely often on this path is in F . The tree language L(A) accepted by the Muller tree automaton A is the set of infinite binary trees t ∈ T ω Σ such that there is (at least) one accepting run of A on t. A tree language L ⊆ T ω Σ is regular iff there exists a Muller automaton A such that L = L(A).

We now recall some fundamental closure properties of regular tree languages.

Theorem 2.8 (Rabin, see [START_REF] Rabin | Decidability of second-order theories and automata on infinite trees[END_REF][START_REF] Thomas | Automata on infinite objects[END_REF][START_REF]Automata, logics, and infinite games: A guide to current research [outcome of a dagstuhl seminar[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF]). The class of regular tree languages is effectively closed under finite union, finite intersection, and complementation, i.e. we can effectively construct, from two Muller tree automata A and B, some Muller tree automata C 1 , C 2 , and C 3 , such that L(C 1 ) = L(A) ∪ L(B), L(C 2 ) = L(A) ∩ L(B), and L(C 3 ) is the complement of L(A). §3. Automatic structures. Notice that one can consider a relation R ⊆

Σ ω n 1 × Σ ω n 2 × . . . × Σ ω n k
, where Σ 1 , Σ 2 , . . . Σ k , are finite alphabets, as an ω nlanguage over the product alphabet Σ 1 × Σ 2 × . . . × Σ k . In a similar way, we can consider a relation R ⊆ T ω Σ1 × T ω Σ2 × . . . × T ω Σ k , as a tree language over the product alphabet Σ 1 × Σ 2 × . . . × Σ k .

Let now M = (M, (R M i ) 1≤i≤k ) be a relational structure, where M is the domain, and for each i

∈ [1, k] R M
i is a relation of finite arity n i on the domain M . The structure is said to be ω n -automatic (respectively, ω-tree-automatic) if there is a presentation of the structure where the domain and the relations on the domain are accepted by ω n -automata (respectively, by Muller tree automata), in the following sense. Definition 3.1 (see [START_REF] Blumensath | Automatic structures[END_REF]). Let M = (M, (R M i ) 1≤i≤k ) be a relational structure, where k ≥ 1 is an integer, and each relation R i is of finite arity n i . An ω-tree-automatic presentation of the structure M is formed by a tuple of Muller tree automata (A, A = , (A i ) 1≤i≤k ), and a mapping h from L(A) onto M , such that:

1. The automaton A = accepts an equivalence relation E ≡ on L(A), and 2.

For each i ∈ [1, k], the automaton A i accepts an n i -ary relation R ′ i on L(A) such that E ≡ is compatible with R ′
i , and 3. The mapping h is an isomorphism from the quotient structure (L(A), (R ′ i ) 1≤i≤k )/E ≡ onto M. The ω-tree-automatic presentation is said to be injective if the equivalence relation E ≡ is just the equality relation on L(A). In this case A = and E ≡ can be omitted and h is simply an isomorphism from (L(A), (R ′ i ) 1≤i≤k ) onto M. A relational structure is said to be (injectively) ω-tree-automatic if it has an (injective) ω-tree-automatic presentation.

Notice that sometimes an ω-tree-automatic presentation is only given by a tuple of Muller tree automata (A, A = , (A i ) 1≤i≤k ), i.e. without the mapping h. In that case we still get the ω-tree-automatic structure (L(A), (R ′ i ) 1≤i≤k )/E ≡ which is in fact equal to M up to isomorphism.

We get the definition of ω n -automatic (injective) presentation of a structure and of ω n -automatic structure by simply replacing Muller tree automata by ω nautomata in the above definition.

Notice that, due to the good decidability properties of Muller tree automata and of ω n -automata, we can decide whether a given automaton A = accepts an equivalence relation E ≡ on L(A) and whether, for each i ∈ [1, k], the automaton

A i accepts an n i -ary relation R ′ i on L(A) such that E ≡ is compatible with R ′ i .
We denote ω n -AUT the class of ω n -automatic structures and ω-tree-AUT the class of ω-tree-automatic structures.

We state now two important properties of automatic structures. Theorem 3.2 (see [START_REF] Blumensath | Automatic structures[END_REF]). The class of ω-tree-automatic (respectively, ω n -automa -tic) structures is closed under first-order interpretations. In other words if M is an ω-tree-automatic (respectively, ω n -automatic) structure and M ′ is a relational structure which is first-order interpretable in the structure M, then the structure M ′ is also ω-tree-automatic (respectively, ω n -automatic).

Theorem 3.3 (see [START_REF] Hodgson | Décidabilité par automate fini[END_REF][START_REF] Blumensath | Automatic structures[END_REF]). The first-order theory of an ω-tree-automatic (respectively, ω n -automatic) structure is decidable.

Notice that ω-tree-automatic (respectively, ω n -automatic) structures are always relational structures. However we can also consider structures equipped with functional operations like groups, by replacing as usually a p-ary function by its graph which is a (p + 1)-ary relation. This will always be the case in the sequel where all structures are viewed as relational structures.

Some examples of ω-automatic structures can be found in [START_REF] Rubin | Automatic structures[END_REF][START_REF] Nies | Describing groups[END_REF][START_REF] Khoussainov | Automatic structures: Richness and limitations[END_REF][START_REF] Khoussainov | Automatic structures: Overview and future directions[END_REF][START_REF]Finite presentations of infinite structures: Automata and interpretations[END_REF][START_REF] Kuske | First-order and counting theories of omega-automatic structures[END_REF][START_REF] Hjorth | From automatic structures to Borel structures[END_REF][START_REF] Kuske | The isomorphism problem for omega-automatic trees[END_REF].

A first one is the boolean algebra P(ω) of subsets of ω.

The additive group (R, +) is ω-automatic, as is the product (R, +) × (R, +). Assume that a finite alphabet Σ is linearly ordered. Then the set (Σ ω n , ≤ lex ) of ω n -words over the alphabet Σ, equipped with the lexicographic ordering, is ω n -automatic.

Is is easy to see that every (injectively) ω-automatic structure is also (injectively) ω-tree-automatic. Indeed a Muller tree automaton can easily simulate a Büchi automaton on the leftmost branch of an infinite tree.

The inclusions ω n -AUT ⊆ ω n+1 -AUT, n ≥ 1, are straightforward to prove.

Proposition 3.4. For each integer n ≥ 1, ω n -AUT ⊆ ω-tree-AUT.

Proof. We are first going to associate a tree t x to each ω n -word x in such a way that if L ⊆ Σ ω n is a regular ω n -language then the tree language {t x ∈ T ω Σ | x ∈ L} will be also regular. We make this by induction on the integer n. Let then Σ be a finite alphabet and a ∈ Σ be a distinguished letter in Σ. We begin with the case n = 1. If x ∈ Σ ω is an ω-word over the alphabet Σ then t x is the tree in T ω Σ such that t x (l k ) = x(k) for every integer k ≥ 0 and t x (u) = a for every word u ∈ {l, r} ⋆ such that u / ∈ {l k | k ≥ 0}. It is clear that if L ⊆ Σ ω is a regular ω-language then the tree language {t x ∈ T ω Σ | x ∈ L} is a regular set of trees. Assume now that we have associated, for a given integer n ≥ 1, a tree t x to each ω n -word x ∈ Σ ω n in such a way that if L ⊆ Σ ω n is a regular ω n -language then the tree language {t x ∈ T ω Σ | x ∈ L} is also regular. Consider now an ω n+1 -word x over Σ. It can be divided into ω subwords x j , 0 ≤ j < ω, of length ω n . By induction hypothesis to each ω n -word x j is associated a tree t xj ∈ T ω Σ . Recall that we denote by t u the subtree of t which is rooted in u. We can now associate to the ω n+1 -word x the tree t x which is defined by: t x l k •r = t x k for every integer k ≥ 0, and t x (l k ) = a for every integer k ≥ 0. Let then now L ⊆ Σ ω n+1 be a regular ω n+1 -language. By Proposition 2.4 the language L is obtained from a regular ω-language R ⊆ Γ ω by substituting in every ω-word σ ∈ R a regular ω n -language L b ⊆ Σ ω to each letter b ∈ Γ. By induction hypothesis for each letter b ∈ Γ there is a tree automaton

A b such that L(A b ) = {t x ∈ T ω Σ | x ∈ L b }.
This implies easily that one can construct, from a Büchi automaton accepting the regular ω-language R and from the tree automata A b , b ∈ Γ, another tree automaton A such that L(A) = {t x ∈ T ω Σ | x ∈ L}. The inclusion ω n -AUT ⊆ ω-tree-AUT holds because any element of the domain of an ω n -automatic structure, represented by an ω n -word x, can also be represented by a tree t x . The relations of the structure are then also presentable by tree automata. ⊣

Notice that the strictness of the inclusion n≥1 ω n -AUT ω-tree-AUT follows easily from the existence of an ω-tree-automatic structrure without Borel presentation, proved in [START_REF] Hjorth | From automatic structures to Borel structures[END_REF], and the fact that every ω n -automatic structrure has a Borel presentation (see the end of Section 2.1).

On the other hand we can easily see that the inclusion ω-AUT ω 2 -AUT is strict by considering ordinals. Firstly, Kuske recently proved in [START_REF] Kuske | Is Ramsey's Theorem omega-automatic?[END_REF] that the ω-automatic ordinals are the ordinals smaller than ω ω . Secondly, it is easy to see that the ordinal ω ω is ω 2 -automatic. The ordinal ω ω is the order-type of finite sequences of integers ordered by (1) increasing length of sequences and (2) lexicographical order for sequences of integers of the same length n. A finite sequence of integers x = (n 1 , n 2 , . . . , n p ) can be represented by the following ω 2 -word α x over the alphabet {a, b}:

α x = (a n1+1 • b ω ) • (a n2+1 • b ω ) • • • (a np+1 • b ω ) • (b ω ) • (b ω ) • • •
it is then easy to see that there is an ω 2 -automaton accepting exactly the ω 2words of the form α x for a finite sequence of integers x. Moreover there is an ω 2 -automaton recognizing the pairs (α x , α x ′ ) such that x < x ′ . §4. Some ω n -automatic boolean algebras. We have seen that the boolean algebra P(ω) of subsets of ω is ω-automatic. Another known example of ωautomatic boolean algebra is the boolean algebra P(ω)/Fin of subsets of ω modulo finite sets. The set Fin of finite subsets of ω is an ideal of P(ω), i.e. a subset of the powerset of ω such that:

1. ∅ ∈ Fin and ω / ∈ Fin. 2. For all B, B ′ ∈ Fin, it holds that B ∪ B ′ ∈ Fin. 3. For all B, B ′ ∈ P(ω), if B ⊆ B ′ and B ′ ∈ Fin then B ∈ Fin.
For any two subsets A and B of ω we denote A∆B their symmetric difference. Then the relation ≈ defined by: "A ≈ B iff the symmetric difference A∆B is finite" is an equivalence relation on P(ω). The quotient P(ω)/ ≈ denoted P(ω)/Fin is a boolean algebra. It is easy to see that this boolean algebra is ω-automatic, see for example [START_REF] Kuske | First-order and counting theories of omega-automatic structures[END_REF][START_REF] Hjorth | From automatic structures to Borel structures[END_REF][START_REF] Finkel | The isomorphism relation between tree-automatic structures[END_REF].

More generally we now consider the boolean algebras P(ω n )/I ω n for integers n ≥ 1. We first give the definition of the sets I ω n ⊆ P(ω n ). For P ⊆ ω n we denote o.t.(P ) the order type of (P, <) as a suborder of the order (ω n , <). The set I ω n is defined by:

I ω n = {P ⊆ ω n | o.t.(P ) < ω n }.
For each integer n ≥ 1 the set I ω n is an ideal of P(ω n ). For any two subsets A and B of ω n we denote A∆B their symmetric difference. Then the relation ≈ n defined by: "A ≈ n B iff the symmetric difference A∆B is in I ω n " is an equivalence relation on P(ω n ). The quotient P(ω n )/ ≈ n , also denoted P(ω n )/I ω n , is a boolean algebra.

We are going to show that this boolean algebra P(ω n )/I ω n is ω n -automatic. We first notice that each set P ⊆ ω n can be represented by an ω n -word x P over the alphabet {0, 1} by setting x P (α) = 1 if and only if α ∈ P for every ordinal α < ω n . Let then

L n = {x P ∈ {0, 1} ω n | P ∈ I ω n }. Theorem 4.1. Let n ≥ 1 be an integer. Then the set L n ⊆ {0, 1} ω n is a regular ω n -language.
Proof. We reason by induction on the integer n. Firstly it is easy to see that L 1 is the set of ω-words over the alphabet {0, 1} having only finitely many letters 1. It is a well known example of a regular ω-language, see [START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF][START_REF] Thomas | Automata on infinite objects[END_REF]. Notice that its complement L - 1 = {0, 1} ω \ L 1 is then also regular since the class of regular ω-languages is closed under complementation.

We now assume that we have proved that for each integer k ≤ n the set L k ⊆ {0, 1} ω k is a regular ω k -language. In particular the language L n is a regular ω n -language. Moreover its complement L - n = {0, 1} ω n \ L n is then also regular since the class of regular ω n -languages is closed under complementation.

Consider now a set P ⊆ ω n+1 . It is easy to see that P belongs to I ω n+1 if and only if there are only finitely many integers k ≥ 0 such that P ∩ [ω n .k; ω n .(k + 1)[ has order type ω n .

Thus the ω n+1 -language L n+1 is obtained from the regular ω-language L 1 = {0, 1} ⋆ • 0 ω by substituting the ω n -language L - n to the letter 1 and the ω nlanguage L n to the letter 0. We can conclude, using Proposition 2.4, that the ω n+1 -language L n+1 is regular. ⊣

We can now state the following result.

Theorem 4.2. For every integer n ≥ 1 the boolean algebra P(ω n )/I ω n is ω nautomatic.

Proof. Let n ≥ 1 be an integer. We denote [A] I ω n , or simply [A] when there is no confusion from the context, the equivalence class of a set A ⊆ ω n for the equivalence relation ≈ n . Let Σ = {0, 1} and L(A) = Σ ω n and for any

x ∈ Σ ω n , h(x) = [{α < ω n | x(α) = 1}]. Then it follows easily from the preceding Theorem 4.1 that {(u, v) ∈ (Σ ω n ) 2 | h(u) = h(v)} is accepted by an ω n -automaton.
The operations ∩, ∪, ¬, of intersection, union, and complementation, on

P(ω n )/I ω n are defined by: [B] ∩ [B ′ ] = [B ∩ B ′ ], [B] ∪ [B ′ ] = [B ∪ B ′ ], and ¬[B] = [¬B]
, see [START_REF] Jech | Set theory[END_REF].

Thus the operations of intersection, union, (respectively, complementation), considered as ternary relations (respectively, binary relation) are also given by regular ω n -languages. On the other hand, 0 = [∅] is the equivalence class of the empty set and 1 = [ω n ] is the class of ω n . This proves that the structure (P(ω n )/I ω n , ∩, ∪, ¬, 0, 1) is ω n -automatic. ⊣

Notice that, as in the above proof, we can see that the relation

{(u, v) ∈ (Σ ω n ) 2 | h(u) ⊆ n h(v)} is a regular ω n -language because the "almost inclusion" relation ⊆ n is defined by: h(u) ⊆ n h(v) iff {α < ω n | u(α) > v(α)} ∈ I ω n .
Thus we can also state the following result.

P(ω n )/I ω n , ⊆ n ) is ω n - automatic.
From now on we shall denote B n = (P(ω n )/I ω n , ∩, ∪, ¬, 0, 1). The boolean algebra B n is ω n -automatic hence also ω-tree-automatic.

Recall now the definition of an atomless boolean algebra. Definition 4.4. Let B = (B, ∩, ∪, ¬, 0, 1) be a boolean algebra and ⊆ be the inclusion relation on B defined by x ⊆ y iff x ∩ y = x for all x, y ∈ B. Then the boolean algebra B is said to be an atomless boolean algebra iff for every x ∈ B such that x = 0 there exists an element z ∈ B such that 0 ⊂ z ⊂ x.

We can now recall the following known result. Proposition 4.5. For each integer n ≥ 1 the boolean algebra B n is an atomless boolean algebra.

Proof. Let n ≥ 1 be an integer. Consider the boolean algebra B n = (P(ω n )/I ω n , ∩, ∪, ¬, 0, 1). Let A ⊆ ω n be such that the equivalence class [A] is different from the element 0 in B n . Then the set A has order type ω n and it can be splitted in two sets A 1 and A 2 such that A = A 1 ∪ A 2 and both A 1 and A 2 have still order type ω n . The element [A 1 ] is different from the element 0 in B n because A 1 has order type ω n , and [A 1 ] ⊂ [A] because A -A 1 = A 2 has order type ω n . Thus the following strict inclusions hold in

B n : 0 ⊂ [A 1 ] ⊂ [A]
. This proves that the boolean algebra B n is atomless.

⊣ The following result is also well known but we give a proof for completeness. Proposition 4.6. For each integer n ≥ 1 the boolean algebra B n has the cardinality 2 ℵ0 of the continuum.

Proof. By recursion on n ≥ 1 we define a partition of ω n into a sequence F n k (k < ω) of nonempty finite sets such that for every infinite X ⊆ ω, the union Φ n (X) = k∈X F n k does not belong to the ideal

I ω n . For n = 1, let F 1 k = {k}. For n > 1, set F n k = ℓ<k F n-1 k (ℓ)
, where for each ℓ < ω we have fixed a decomposition F n-1 k (ℓ) (k < ω) of the interval [ℓω n-1 , (ℓ + 1)ω n-1 ) of ordinals into a sequence of finite nonempty pairwise disjoint sets with the property that k∈X F n-1 k (ℓ) has order type ω n-1 for every infinite X ⊆ ω. Clearly Φ n : P(ω) → P(ω n ) is a complete Boolean algebra embedding which induces also an embedding of P(ω)/Fin into P(ω n )/I ω n . Since P(ω)/Fin has cardinality continuum the conclusion follows. ⊣ In the sequel we shall often identify the powerset P(A) of a countable set A with the Cantor space 2 ω = {0, 1} ω . Then P(A) can be equipped with the standard metric topology obained from this identification, and the topological notions like open, closed, Σ 0 2 , Borel, analytic, can be applied to families of subsets of A.

Remark 4.7. In fact a similar result holds for an arbitrary Σ 1 1 -ideal of subsets of ω. More precisely, by a well-known result of Talagrand ( [41] ; Théorème 21), for every proper Σ 1 1 -ideal I of subsets of ω there is a partition of ω into a sequence F n (n < ω) of nonempty finite sets such that for every infinite X ⊆ ω, the union n∈X F n does not belong to the ideal I. Therefore, as above, there is an embedding of P(ω)/Fin into P(ω n )/I. Remark 4.8. Recall that two subsets X and Y are said to be almost disjoint if their intersection is finite. Recall that while a countable index set does not admit an uncountable family of pairwise disjoint subsets it does admit an uncountable family of subsets that are pairwise almost disjoint. So fix an uncountable family F of pairwise almost disjoint infinite subsets of ω. For n ≥ 1 fix a sequence F n k (k < ω) of nonempty finite subsets of ω n such that for every infinite X ⊂ ω, the union Φ n (X) = k∈X F n k does not belong to the ideal I ω n (see the proof of Proposition 4.6). For X ∈ F let A X = k∈X F n k . Then A X (X ∈ F ) is an uncountable family of infinite subsets of ω n which is also almost disjoint (i.e., A X ∩A Y ∈ Fin for X = Y in F ) but it has the additional property that A X ∈ I ω n for all X ∈ F . §5. Axioms of set theory. We now recall some basic notions of set theory which will be useful in the sequel, and which are exposed in any textbook on set theory, like [START_REF] Jech | Set theory[END_REF].

The usual axiomatic system ZFC is Zermelo-Fraenkel system ZF plus the axiom of choice AC. A model (V, ∈) of the axiomatic system ZFC is a collection V of sets, equipped with the membership relation ∈, where "x ∈ y" means that the set x is an element of the set y, which satisfies the axioms of ZFC. We shall often say " the model V" instead of "the model (V, ∈)".

The axioms of ZFC express some natural facts that we consider to hold in the universe of sets.

The infinite cardinals are usually denoted by ℵ 0 , ℵ 1 , ℵ 2 , . . . , ℵ α , . . . We recall that Cantor's Continuum Hypothesis CH states that the cardinality of the continuum 2 ℵ0 is equal to the first uncountable cardinal ℵ 1 . Gödel and Cohen have proved that the continuum hypothesis CH is independent from the axiomatic system ZFC. This means that, assuming ZFC is consistent, there are some models of ZFC + CH and also some models of ZFC + ¬ CH, where ¬ CH denotes the negation of the continuum hypothesis, [START_REF] Jech | Set theory[END_REF].

If V is a model of ZF and L is the class of constructible sets of V, then the class L forms a model of ZFC + CH.

Recall also that OCA denotes the Open Coloring Axiom (or Todorcevic's axiom as it is called in the more recent literature; see, for example, [START_REF] Farah | All automorphism of the Calkin algebras are inner[END_REF]), a natural alternative to CH that has been first considered by the second author in [START_REF] Todorčević | Partition problems in topology[END_REF]. It is known that if the theory ZFC is consistent, then so are the theories (ZFC + CH) and (ZFC + OCA), see [20, pages 176 and 577]. In particular, if V is a model of (ZFC + OCA) and if L is the class of constructible sets of V, then the class L forms a model of (ZFC + CH).

The axiom OCA was used in our previous paper [START_REF] Finkel | The isomorphism relation between tree-automatic structures[END_REF] on tree-automatic structures but here we shall use another related axiom first considered by Just [START_REF] Just | A modification of Shelah's oracle-c.c. with applications[END_REF].

To introduce this axiom we need some definitions.

Let A and B be two infinite countable sets, a function H : P(A) → P(B) and an ideal I of P(B) containing all finite subsets of B but not the whole set B. Then the function H is said to preserve intersections modulo I whenever

(i) H(X) △ H(Y ) ∈ I for every X, Y ⊆ A such that X △ Y ∈ Fin, and (ii) H(X ∩ Y ) △ (H(X) ∩ H(Y )) ∈ I for every X, Y ⊆ A
Recall that one can identify the powerset P(B), where B is a countable set, with the set 2 B equipped with the Cantor topology which is the product topology of the discrete topology on B. Thus one can also use notions like open, closed, Borel, analytic, for ideals of P(B), where n ≥ 1 is an integer. Then Just's axiom AT (where the shorthand stands for 'Almost Trivial') states that for every Σ 11 -ideal I of subsets of ω, for every H : P(ω) → P(ω) which preserves intersections modulo I, and for every uncountable family A of pairwise almost disjoint infinite subsets of ω there exist A ∈ A and a finite decomposition A = i<n A i such that for every i < n there is a continuous function 1 F i :

P(A i ) → P(ω) such that F i (X) △ H(X) ∈ I for every X ⊆ A i .
The axiom AT implies also the following form which will be used in the sequel: For every Σ 1 1 -ideal I of subsets of ω n , for every H : P(ω m ) → P(ω n ) which preserves intersections modulo I, and for every uncountable family A of pairwise almost disjoint infinite subsets of ω m there exist A ∈ A and a finite decomposition A = i<k A i such that for every i < k there is a continuous function

F i : P(A i ) → P(ω n ) such that F i (X) △ H(X) ∈ I for every X ⊆ A i .
In [START_REF] Just | A modification of Shelah's oracle-c.c. with applications[END_REF], Just showed that every model V of ZFC admits a forcing extension satisfying ZFC + AT. In another paper ( [START_REF]A weak version of AT from OCA, Set theory of the continuum[END_REF]) he showed that OCA implies many instances of AT. In particular, it is shown in [START_REF]A weak version of AT from OCA, Set theory of the continuum[END_REF] that OCA implies AT restricted to the class of all Σ 0 2 -ideals of subsets of ω. This was later extended by Farah [START_REF]Luzin gaps[END_REF] to a larger class of Σ 1 1 -ideals of subsets of ω, however it is still not known if OCA implies the full AT. The motivation behind the axiom AT came from the theory of quotient Boolean algebras of the form P(ω)/I where I is a proper (i.e., ω ∈ I) ideal on ω which we always assume to include the ideal Fin of all finite subsets of ω. Let π I : P(ω) → P(ω)/I denotes the natural quotient map, i.e. π I (X) = π I (Y ) whenever X △ Y ∈ I. A homomorphism Φ : P(ω)/I → P(ω)/J between two such quotient Boolean algebras is usually given by its lifting H : P(ω) → P(ω) i.e., a map for which the following diagram

P(ω) H -→ P(ω) ↓ π I ↓ π J P(ω)/ I Φ -→ P(ω)/J
commutes. Note that any such lifting H preserves intersections modulo the range ideal J. Note also that in general H : P(ω) → P(ω) does not need to be a Boolean algebra homomorphism. It is therefore quite natural to ask for conditions on the given ideals I and J on ω and the homomorphism Φ : P(ω)/I → P(ω)/J that would guarantee the existence of liftings H : P(ω) → P(ω) that preserve the Boolean algebra operations of the algebra P(ω), even the infinitary ones. Such liftings H : P(ω) → P(ω) are called completely additive liftings. Note that such completely additive liftings are always given by maps h : ω → ω in such a way that

H({n}) = h -1 (n) for all n < ω.
It follows that H(X) = h -1 (X) for all X ⊆ ω and so from this we can conclude that every completely additive lifting H : P(ω) → P(ω) is a continuous map when we make the natural identification of P(ω) with the Cantor set 2 ω . Thus AT asserts the seemingly weak form of this, the local continuity of liftings between quotient algebras over Σ 1 1 -ideals I of subsets of ω. While local continuity of liftings is a matter of additional axioms of set theory, the second author (see, for example, [START_REF]Gaps in analytic quotients[END_REF], Problem 1) has posed a problem about the natural mathematical counterpart of this asking under which conditions continuous liftings can be turned into completely additive ones. In subsequent work of Farah [START_REF]Analytic quotients: theory of liftings for quotients over analytic ideals on the integers[END_REF] and Kanovei-Reeken [START_REF] Kanovei | New Radon-Nikodym ideals[END_REF] this conjecture has been verified for a very wide class of ideals I of subsets of ω. We shall use the following particular result from this work, which is a reformulation of [23, Theorem 2], using the fact that a continuous homomorphism H : P(ω) → P(ω ξ ) is actually completely additive. Notice that below the boolean algebras P(ω ξ )/I ω ξ are a direct generalization of the boolean algebras P(ω n )/I ω n and that we shall in fact only use in the sequel the case where the ordinal ξ ≥ 1 is an integer. Theorem 5.1. (see [START_REF] Kanovei | New Radon-Nikodym ideals[END_REF]Theorem 2]) For every countable ordinal ξ ≥ 1, if a homomorphism Φ : P(ω) → P(ω ξ )/I ω ξ has a continuous lifting H : P(ω) → P(ω ξ ) then it also has a completely additive lifting, or in other words, there is a map h :

ω ξ → ω such that Φ(X) = [h -1 (X)] I ω ξ for all X ⊆ ω. §6.
The isomorphism relation. We had proved in [START_REF] Finkel | The isomorphism relation between tree-automatic structures[END_REF] that there exist two ω-tree automatic boolean algebras B and B ′ such that: (1) (ZFC + CH) B and B ′ are isomorphic. (2) (ZFC + OCA) B and B ′ are not isomorphic. We are going to prove a similar result for the class of ω n -automatic structures, for any integer n ≥ 2 using AT in place of OCA.

We first recall the following folklore result (see, for example, [START_REF]Analytic quotients: theory of liftings for quotients over analytic ideals on the integers[END_REF]).

Theorem 6.1. (ZFC + CH) The boolean algebras B n , n ≥ 1, are pairwise isomorphic.

Notice that this result is an immediate consequence of the simple fact that each of the Boolean algebras B n , n ≥ 1, is ℵ 1 -saturated. Therefore assuming CH, as the boolean algebras B n , n ≥ 1, are all of cardinality ℵ 1 , a well-known Cantor's back and forth argument will give us the isomorphisms. (The reader may find these notions in a textbook on Model Theory, like [START_REF] Poizat | A course in model theory[END_REF]).

Note that if 1 ≤ m ≤ n the equality ω p ω m = ω n for p = nm transfers easily to the existence of a map f : ω n → ω m with the property that for every subset X ⊆ ω m , X ∈ I ω m if and only if f -1 (X) ∈ I ω n . It follows that the corresponding map X → f -1 (X) is a lifting of an isomorphic embedding Φ : P(ω m )/I ω m → P(ω n )/I ω n and therefore we have the following fact. Proposition 6.2. (ZFC) The algebra B m is isomorphic to a subalgebra of B n whenever m and n are positive integers such that m ≤ n.

We shall see that such an isomorphic embedding is not always possible if we have the inequality m > n. We shall use the following consequence of a wellknown result of Rotman [START_REF] Rotman | A mapping theorem for countable well-ordered sets[END_REF] which one can prove by an easy induction on n ≥ 1. Lemma 6.3. Suppose that n is an integer ≥ 1 and that β is some ordinal. Then for every mapping f : ω n → β there is Y ⊆ ω n of order type ω n such that the image f (Y ) is a subset of β of order type at most ω n .

Proof. Consider firstly a mapping f : ω → β where β is some ordinal. If the order-type of f (ω) is strictly greater than ω then there is a subset Z of f (ω) which has order-type ω. But then Y = f -1 (Z) is a subset of ω which has also order-type ω and f (Y ) = Z has order-type ω. Assume now that the result is proved for every integer 1 ≤ p < n and let f : ω n → β be a mapping where β is some ordinal. The ordinal ω n can be decomposed into ω successive intervals (I k ) k≥1 of length ω n-1 . We can now consider the restriction f k of f to the interval I k . By induction hypothesis, for each integer k ≥ 1 there is a subset Y k of I k which has order-type ω n-1 and such that f k (Y k ) has order type at most ω n-1 . The set Y = 1≤k Y k ⊆ ω n has order type ω n and its image f (Y ) is a subset of β of order type at most ω n . ⊣

We are now ready to state the following result.

Theorem 6.4. (ZFC + AT) The ω n -automatic boolean algebras B n , n ≥ 1, are pairwise non isomorphic and in fact B m is not isomorphic to a subalgebra of B n whenever m > n ≥ 1.

Proof. Suppose that for some m > n ≥ 1 there is an isomorphic embedding Φ : P(ω m )/I ω m → P(ω n )/I ω n .

Choose a lifting H : P(ω m ) → P(ω n ) for the isomorphic embedding, i.e., a map for which the following diagram commutes

P(ω m ) H -→ P(ω n ) ↓ π I ω m ↓ π I ω n P(ω m )/ I ω m Φ -→ P(ω n )/I ω n It follows that for every X, Y ⊆ ω m , (1) X △ Y ∈ I ω m if and only if H(X) △ H(Y ) ∈ I ω n , (2) H(X) ∈ Φ([X] I ω m ).
So, in particular, H preserves intersections modulo I ω n . Using the argument appearing in Remark 4.8 above, there is an uncountable family A of pairwise almost disjoint (i.e., A∩B ∈ Fin for all A = B from A) infinite subsets of ω m such that A ∈ I ω m for all A ∈ A. By AT there is A ∈ A and a finite decomposition A = i<k A i and for every i < k a continuous function2 F i : P(A i ) → P(ω n ) forming a lifting of Φ when restricted to P(A i )/I ω m , or in other words a function for which the restricted diagram

P(A i ) Fi -→ P(ω n ) ↓ π I ω m ↓ π I ω n P(A i )/ I ω m Φ -→ P(ω n )/I ω n commutes.
In particular, for X ⊆ A i , we have that F i (X) ∈ I ω n if and only if X ∈ I ω m . Since A ∈ I ω m and the decomposition A = i<k A i is finite there is some i < k such that A i ∈ I ω m . Fix i < k such that A i ∈ I ω m . Let B = H(A i ). By Theorem 5.1, there is a function f i : B → A i which induces the completely additive lifting X → f -1 i (X) of the restriction of Φ to P(A i )/ I ω m . Since F i is also a lifting of this isomorphic embedding, we have that

F i (X) △ f -1
i (X) ∈ I ω n for every X ⊆ A i . It follows in particular that for X ⊆ A i , X ∈ I ω m if and only if f -1 i (X) ∈ I ω n . By Lemma 6.3, we can find a set Y ⊆ B of order type ω n whose image X = f i (Y ) is a subset of A i of order type at most ω n < ω m . But then, we have a subset X of A i of order type < ω m whose preimage f -1 i (X) has order type ω n as it contains the set Y, i.e. X ∈ I ω m and f -1 i (X) / ∈ I ω n , a contradiction. This completes the proof.

⊣

We can now state the following consequence of the above theorems.

Corollary 6.5. The isomorphism relation for ω 2 -automatic (respectively, ω n -automatic for n > 2) boolean algebras (respectively, partial orders) is not determined by the axiomatic system ZFC.

Proof. The result for ω n -automatic boolean algebras, n ≥ 2, follows directly from Theorems 6.1 and 6.4 and the fact that the boolean algebras B 1 and B 2 are ω 2 -automatic, hence also ω n -automatic for n > 2. For partial orders, we consider the ω 2 -automatic structures (P(ω)/Fin, ⊆ 1 ) and (P(ω 2 )/I ω 2 , ⊆ 2 ). These two structures are isomorphic if and only if the two boolean algebras B 1 and B 2 are isomorphic, see [20, page 79]. Then the result for partial orders follows from the case of boolean algebras. ⊣

Reasoning as in [START_REF] Finkel | The isomorphism relation between tree-automatic structures[END_REF] for ω-tree-automatic structures, we can now get similar results for other classes of ω n -automatic structures.

First a boolean algebra (B, ∩, ∪, ¬, 0, 1) can be seen as a commutative ring with unit element (B, ∆, ∩, 1), where ∆ is the symmetric difference operation. The operations of union and complementation can be defined from the symmetric difference and intersection operations. Moreover two boolean algebras (B, ∩, ∪, ¬, 0, 1) and (B ′ , ∩, ∪, ¬, 0, 1) are isomorphic if and only if the rings (B, ∆, ∩, 1) and (B ′ , ∆, ∩, 1) are isomorphic. For each integer n ≥ 1, we denote R n = (P(ω n )/I ω n , ∆, ∩, 1) the commutative ring associated with the boolean algebra B n . Theorem 6.6.

(ZFC + CH)

The ω n -automatic commutative rings R n , n ≥ 1, are pairwise isomorphic.

(ZFC + AT)

The ω n -automatic commutative rings R n , n ≥ 1, are pairwise non isomorphic.

Recall that M k (R) is the set of square matrices with k columns and k rows and coefficients in a given ring R. If k ≥ 2 then the set M k (R), equipped with addition and multiplication of matrices, is a non commutative ring. The ring M k (R) is first-order interpretable in the ring R; each matrix M being represented by a unique k 2 -tuple of elements of R, the addition and multiplication of matrices are first order definable in R.

On the other hand, for each integer n ≥ 1, the class of ω n -automatic structures is closed under first order interpretations. Thus if R is an ω n -automatic ring then the ring of matrices M k (R) is also ω n -automatic. It is well known that two rings R and R ′ are isomorphic if and only if the rings M k (R) and M k (R ′ ) are isomorphic, (this is proved for instance in [START_REF] Finkel | The isomorphism relation between tree-automatic structures[END_REF]). We now denote, for each integer

n ≥ 1, M n = M k (R n ),
where k ≥ 2 is a fixed integer. So we can state the following result. Theorem 6.7.

(ZFC + CH)

The ω n -automatic non commutative rings M n , n ≥ 1, are pairwise isomorphic.

(ZFC + AT)

The ω n -automatic non commutative rings M n , n ≥ 1, are pairwise non isomorphic.

Consider now the unitriangular group U T k (R) for some integer k ≥ 3 and R a unitary ring. A matrix M ∈ M k (R) is in the group U T k (R) if and only if it is an upper triangular matrix which has only coefficients 1 on the diagonal, where 1 is the multiplicative unit of R. The group U T k (R) is also first order interpretable in the ring R. (It is actually a classical example of nilpotent group of class k -1, for more details, see [START_REF] Belegradek | The model theory of unitriangular groups[END_REF][START_REF] Finkel | The isomorphism relation between tree-automatic structures[END_REF]).

We denote U n,k = U T k (R n ) for each n ≥ 1. The groups U n,k are first order interpretable in the ring R n . Thus the groups U n,k are ω n -automatic. We can now state the following result. Theorem 6.8. Let k ≥ 3 be an integer.

(ZFC + CH)

The ω n -automatic groups U n,k , n ≥ 1, are pairwise isomorphic.

(ZFC + AT)

The ω n -automatic groups U n,k , n ≥ 1, are pairwise non isomorphic.

Proof. The result follows from Theorem 6.6, from the fact that if R and S are two isomorphic commutative rings then U T k (R) and U T k (S) are also isomorphic, and from a result of Belegradek who proved in [START_REF] Belegradek | The model theory of unitriangular groups[END_REF] that if U T k (R) and U T k (S) are isomorphic, for some integer k ≥ 3 and some commutative rings R and S, then the rings R and S are also isomorphic. ⊣

Then we can now state the following result.

Corollary 6.9. The isomorphism relation for ω 2 -automatic (respectively, ω n -automatic for n > 2) commutative rings (respectively, non-commutative rings, groups, nilpotent groups of class p ≥ 2) is not determined by the axiomatic system ZFC.

An ω n -automatic presentation of a structure is given by a tuple of ω n -automata (A, A = , (A i ) 1≤i≤k ). The tuple of ω n -automata can be coded by a finite sequence of symbols, hence by a unique integer N . If N is the code of the tuple of ω nautomata (A, A = , (A i ) 1≤i≤k ) we shall denote S N the ω n -automatic structure (L(A), (R i ) 1≤i≤k ))/E ≡ .

The isomorphism problem for ω n -automatic structures is:

{(p, m) ∈ ω 2 | S p is isomorphic to S m }.
We can now infer from above independence results the following one. Theorem 6.10. The isomorphism problem for ω 2 -automatic (respectively, ω nautomatic for n > 2) boolean algebras (respectively, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class p ≥ 2) is neither a Σ 1 2 -set nor a Π 1 2 -set. Proof. We prove first the result for ω n -automatic boolean algebras. By Theorem 6.4 we know that if ZFC is consistent then there is a model V of (ZFC + AT) in which the two ω 2 -automatic boolean algebras B 1 and B 2 are not isomorphic. But the inner model L of constructible sets in V is a model of (ZFC + CH) so in this model the two boolean algebras B 1 and B 2 are isomorphic by Theorem 6.1.

On the other hand, Schoenfield's Absoluteness Theorem implies that every Σ 1 2set (respectively, Π 1 2 -set) is absolute for all inner models of ZFC, see [20, page 490].

In particular, if the isomorphism problem for ω n -automatic boolean algebras, n ≥ 2, was a Σ 1 2 -set (respectively, a Π 1 2 -set), then it could not be a different subset of ω 2 in the models V and L considered above. Thus the isomorphism problem for ω 2 -automatic (respectively, ω n -automatic for n > 2) boolean algebras is neither a Σ 1 2 -set nor a Π 1 2 -set. The other cases of rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class p ≥ 2, follow in the same way from Theorems 6.6, 6.7, and 6.8. ⊣ Remark 6.11. We had proved in [START_REF] Finkel | The isomorphism relation between tree-automatic structures[END_REF] that there exist two ω-tree-automatic atomless boolean algebras which are isomorphic under OCA but not under CH. But all the ω n -automatic atomless boolean algebras B n , n ≥ 1, we have considered in this paper are also ω-tree-automatic. Thus we have also in some sense improved our previous result by showing the following one. Theorem 6.12. There exist infinitely many ω-tree-automatic atomless boolean algebras B n , n ≥ 1, which are pairwise isomorphic under CH and pairwise non isomorphic under AT.

Notice that we have also a similar result for partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class p ≥ 2. §7. Concluding remarks. Khoussainov, Nies, Rubin, and Stephan proved in [START_REF] Khoussainov | Automatic structures: Richness and limitations[END_REF] that the automatic infinite boolean algebras are the finite products B n f in-cof of the boolean algebra B f in-cof of finite or cofinite subsets of the set of positive integers ω. An open problem is to characterize completely the ω n -automatic (respectively, ω-tree-automatic) boolean algebras. A similar problem naturally arises for other classes of ω n -automatic (respectively, ω-tree-automatic) structures, like groups, rings, linear orders, and so on.

Theorem 4 . 3 .

 43 For each integer n ≥ 1 the structure (

Continuity here is interpreted when we make the standard identification of P(A i ) and P(ω) with the Cantor cubes

A i and 2 ω , respectively.

Recall the identifications P(A i ) = 2 A i and P(ω n ) = 2 ω n which are giving us the topologies to which the continuity refers to.

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


Y Magnin

H T Diep
email: diep@u-cergy.fr

Monte Carlo Study of Magnetic Resistivity in Semiconducting MnTe

Keywords: numbers: 75, 76, +j ; 05, 60, Cd

We investigate in this paper properties of the spin resistivity in the magnetic semiconducting MnTe of NiAs structure. MnTe is a crossroad semiconductor with a large band gap. It is an antiferromagnet with the Néel temperature around 310K. Due to this high Néel temperature, there are many applications using its magnetic properties. The method we use here is the Monte Carlo simulation in which we take into account the interaction between itinerant spins and lattice Mn spins. Our results show a very good agreement with experiments on the shape of the spin resistivity near the Néel temperature.

I. INTRODUCTION

Spin resistivity in materials has been a subject of intensive studies both experimentally and theoretically for more than five decades. Experiments have been performed to determine the spin resistivity ρ in many magnetic materials from metals to semiconductors. The rapid development of the field is due mainly to many applications in particular in spintronics. One interesting aspect of magnetic materials is the existence of a magnetic phase transition from a magnetically ordered phase to the paramagnetic (disordered) state. Depending on the material, ρ can show a sharp peak at the magnetic transition temperature T C , 1 or just only a change of its slope, or an inflexion point. The latter case gives rise to a peak of the differential resistivity dρ/dT . 2,3 Very recent experiments such as those performed on ferromagnetic SrRuO 3 thin films 4 , Ru-doped induced ferromagnetic La 0.4 Ca 0.6 MnO 3 5 , antiferromagnetic ǫ-(Mn 1-x Fe x ) 3.25 Ge 6 , semiconducting Pr 0.7 Ca 0.3 MnO 3 thin films 7 , superconducting BaFe 2 As 2 single crystals 8 , and La 1-x Sr x MnO 3 9 compounds show different forms of anomaly of the magnetic resistivity at the magnetic phase transition temperature.

The properties of the total resistivity stem from different kinds of diffusion processes : the scattering of the itinerant spins by phonons, by lattice magnons, by impurities and defects etc. Each contribution has in general a different temperature dependence. Let us summarize the most important contributions at low temperature (T ) in the following expression

ρ(T ) = ρ 0 + AT 2 + BT 5 + C ln µ T (1)
where A, B and C are constants. The first term is Tindependent, the second term proportional to T 2 represents the scattering of itinerant spins at low T by lattice spin-waves. Note that the resistivity caused by a Fermi liquid is also proportional to T 2 . The T 5 term corresponds to low-T resistivity in metals. This is due to the scattering of itinerant electrons by phonons. Note that at high T , metals show a linear-T dependence. The ln term is the resistivity due to the quantum Kondo effect at very low T . For the magnetic contribution to the total resistivity, the T 2 term has been obtained from the magnon scattering by Kasuya 10 . However, at high T in particular in the region of the phase transition, much less has been known. The general idea that the magnetic resistivity is a function of the spin-spin correlation was introduced by de Gennes and Friedel. 11 According to this idea, the magnetic resistivity should behave as the magnetic susceptibility, thus it should diverge at T . Fisher and Langer 12 , and Kataoka 13 have suggested that the range of spin-spin correlation changes the shape of ρ near the phase transition. The resistivity due to magnetic impurities has been calculated by Zarand et al. 14 as a function of the Anderson's localization length. This parameter expresses in fact a kind the correlation sphere induced around each impurity. Their result that the resistivity peak depends on this parameter is in agreement with the spin-spin correlation idea. In our previous works [15][16][17] we have studied the spin current in ferromagnetic thin films by Monte Carlo (MC) simulations. The behavior of the spin resistivity as a function of T has been shown to be in agreement with main experimental features and theoretical investigations mentioned above. We have introduced in these works the picture of scattering of itinerant spins by magnetic defect clusters which are known to be formed in the transition temperature region. The size of each defect cluster expresses a kind of correlation between spins.

In antiferromagnets much less is known because there have been very few theoretical investigations which have been carried out. Haas 18 has shown that while in ferromagnets the resistivity ρ shows a sharp peak at the magnetic transition of the lattice spins, in antiferromagnets there is no such a peak. The alternate change of sign of the spin-spin correlation with distance may have something to do with the absence of a sharp peak.

In this paper, we are interested in the antiferromagnetic MnTe, a well-studied semiconductor with numerous applications due to its high Néel temperature. The pure MnTe has either the zinc-blend structure 19 or the hexagonal NiAs one 20 . We confine ourselves in the case of hexagonal structure. For this case, the Néel temperature is T N = 310 K 20 . Hexagonal MnTe is a crossroad semiconductor with a big gap (1.27 eV) and a room-temperature carrier concentration of n = 4.3×10 17 cm -3 . [START_REF] Mobasser | Proceed[END_REF][START_REF] Allen | [END_REF] Without doping, MnTe is non degenerate. In doped cases [23][24][25][26] , band tails created by doped impurities can cover more or less the gap. But these systems, which are disordered by doping, are not a purpose of our present study. So, in the following we study only the pure MnTe. The behavior of the spin resistivity ρ in MnTe as a function of T has been experimentally shown [27][28][29][30][31] . In our previous paper, 32 we have theoretically studied with the Boltzmann's equation using numerical data for cluster distribution obtained by MC simulations. We could only compare our result with old experimental data available at that time below the transition temperature. 27 After the publication of our paper, new experimental results become available for the whole range of temperature for pure MnTe performed by He et al. 31 This motivates the present work.

In this paper, we use the same model as in our previous work 32 for MnTe. But unlike that previous paper which used an approximate Boltzmann's equation, we shall use here direct MC simulations without recourse to approximations. In addition, we take into account the lattice magnetic relaxation time in the calculation of the spin resistivity. The tuning of the relaxation time allows an excellent agreement with experimental resistivity of MnTe as will be seen below.

In section II, we show our model and describe our MC method. Results are shown and compared with experimental resistivity of MnTe in section III. Concluding remarks are given in section IV.

II. MODEL

The hexagonal NiAs-type structure of MnTe is shown in Fig. 1. 20 It is composed of ferromagnetic xy hexagonal planes antiferromagnetically stacked in the c direction. The nearest-neighbor (NN) distance in the c direction is c/2 ≃ 3.36 Å shorter than the in-plane NN distance which is a = 4.158 Å. Neutron scattering experiments show that the main exchange interactions between Mn spins in MnTe are i) interaction between NN along the c axis with the value J 1 /k B = -21.5 ± 0.3 K, ii) ferromagnetic exchange J 2 /k B ≈ 0.67 ± 0.05 between in-plane neighboring Mn (they are next NN by distance), iii) third NN antiferromagnetic interaction J 3 /k B ≃ -2.87 ± 0.04 K.

The interactions J 1 , J 2 and J 3 are indicated in Fig. 1. In addition, the spins are lying in the xy planes perpendicular to the c direction with a small in-plane easy-axis anisotropy D. 20 We note that the values of the exchange integrals given above have been deduced from experimental data by fitting with a formula obtained from a free spin-wave theory 20 . Other fittings with mean-field theories give slightly different values. [START_REF] Mobasser | Proceed[END_REF] Therefore, care should be taken while using values deduced from experimental data, keeping in mind that they depend on models used and approximations involved in the fitting.

The lattice Hamiltonian is given by

H = -J 1 (i,j) S i .S j -J 2 (i,m) S i .S m -J 3 (i,k) S i .S k -D i (S x i ) 2 (2)
where S i is the Heisenberg spin at the lattice site i, (i,j) is made over the NN spin pairs S i and S j with interaction J 1 , while (i,m) and (i,k) are made over the NNN and third NN neighbor pairs with interactions J 2 and J 3 , respectively. D > 0 is an anisotropy constant which favors the in-plane x easy-axis spin configuration. The Mn spin is experimentally known to be of the Heisenberg model with magnitude S = 5/2. 20 The interaction between an itinerant spin and surrounding Mn spins in semiconducting MnTe is written as

H i = - n J( r -R n )s • S n (3)
where J( r -R n ) > 0 is a ferromagnetic exchange interaction between the itinerant spin s at r and the Mn spin S n at the lattice site R n . The sum on lattice spins S n is limited at some cut-off distance as will be discussed later. We suppose that J( r -R n ) is weak enough to be considered as a perturbation to the lattice Hamiltonian :

J( r -R n ) = I 0 exp[-α( r -R n )] ( 4
)
where I 0 and α are constants. We choose α = 1 for convenience. The choice of I 0 should be made so that the interaction H i yields an energy much smaller than the lattice energy due to H (see discussion on the choice of variables in Refs. 33,34 ).

Since in MnTe the carrier concentration is n = 4.3 × 10 17 cm -3 , low with respect to the concentration of its surrounding lattice spins ≃ 10 22 cm -3 , we do not take into account the interaction between itinerant spins. The contribution of that interaction to the energy of an itinerant spin is negligible.

We perform MC simulations on a thin film of dimension L × L × L where L is the number of MnTe cells in x, y and z directions. Note that each cell contains two Mn atoms and two Te atoms (see Fig. 1). Periodic boundary conditions are applied in all directions. The itinerant electrons move in the system under an electric field ǫ applied along the x direction

H E = -e ǫ. ℓ (5)
where -e is the charge of electron and ℓ the displacement vector of the electron. Each electron spin s of magnitude 1/2 interacts with neighboring lattice Mn spins within a sphere of radius D 1 according to Eq. ( 3). We take in the following the Ising model for the electron spin. In doing so, we neglect the quantum effects which are of course important at very low temperature but not in the transition region at room temperature where we focus our attention.

The MC technique we use for the transport is a multistep averaging which has shown to reduce efficiently statistical fluctuations 33,34 . The reader is referred to our early works for a detailed description of our method as well as the effects of changing physical parameters such as D 1 in antiferromagnets. In a word, this technique consists in changing the lattice spin configuration as often as the temperature-dependent relaxation time allows. The relaxation time of the lattice spin system is expressed as

35 τ L = A |1 -T /T N | zν (6)
where A is a constant, ν the correlation critical exponent, and z the dynamic exponent. From this expression, we see that as T tends to T N , τ L diverges. This phenomenon is known as the critical slowing-down. For the Heisenberg model, zν = 1.38 (ν = 0.704 and z = 1.97). 36 We have previously shown that τ L strongly affects the shape of ρ. 37

III. RESULTS

We have calculated the spin resistivity of the hexagonal MnTe using the exchange integrals taken from Ref. 20 . These values are given above. As said before, the values of the exchange interactions deduced from experimental data depend on the model Hamiltonian, in particular the spin model, as well as the approximations. Furthermore, in semiconductors, the carrier concentration is a function of T . In our model, there is however no interaction between itinerant spins. Therefore, the number of itinerant spins used in the simulation is important only for statistical average : the larger the number of itinerant spins the better the statistical average. The current obtained is proportional to the number of itinerant spins but there are no extra physical effects.

The result of the spin resistivity is shown in Fig. 2. Using the value of ρ, we obtain the relaxation time of itinerant spin equal to τ ≃ 0.1 ps, and the mean free path equal to l ≃ 20 Å, at the critical temperature. Several remarks are in order : i) With J 3 slightly larger in magnitude than the value deduced from experiments, we find T N = 310 K ii) ρ shows a pronounced peak in excellent agreement with experiments iii) Note that the shape of the peak depends on A. The value we used to obtain that agreement is A = 1 iv) In the temperature regions below T < 140 K and above T N the MC result is in excellent agreement with experiment, unlike in our previous work 32 using the Boltzmann's equation v) In the region 140 K < T < T N the MC result of ρ is slightly smaller than experimental data. In the search for an explanation, we see that the magnetization obtained by the MC simulation, though in good agreement with experiments at low T and yielding the precise value of T N , is slightly smaller than the experimental one in the intermediate temperature region. This is shown in Fig. 3. The magnetization deficit may be due to the fact that the magnetic anisotropy was too small D = 0.12 K taken from Ref. 20 , it is not strong enough to enhance the magnetization.

IV. CONCLUSION

We have shown in this paper the MC results of the spin resistivity ρ as a function of temperature in MnTe. We have taken into account the main interaction which governs the resistivity behavior, namely the interaction between itinerant spins and the lattice Mn spins. Our result is in agreement with experiments : it reproduces the correct Néel temperature as well as the shape of the peak at the phase transition. Note that the theory by Haas 18 predicts the absence of a peak in ρ in the temperature region of the phase transition for antiferromagnetic MnTe. We finally emphasize that our excellent agreement was possible because most importantly we have correctly taken into account the temperature dependence of the lattice spin relaxation time in the simulation. 37

Figure 1 :

 1 Figure 1: Structure of MnTe of NiAs type is shown. Antiparallel spins are shown by black and white circles. Nearestneighbor (NN) interaction is marked by J1, next NN interaction by J2, and third NN one by J3.

Figure 2 :

 2 Figure 2: Spin resistivity ρ versus temperature T . Black circles are from Monte Carlo simulation, white circles are experimental data taken from He et al. 31 . The parameters used in the simulation are J1 = -21.5K, J2 = 2.55 K, J3 = -9 K, I0 = 2 K, D = 0.12 K, D1 = a = 4.148 Å, E = 2 * 10 5 V/m, L = 30.

Figure 3 :

 3 Figure 3: Magnetization M (in unit of µB) versus temperature T (in unit of K). Black circles are results of Monte Carlo simulation, white circles are experimental data taken from Efrem D'Sa et al. 30 . The parameters are the same as those given in the caption of Fig. 2.