Justine Layec

Florence Ansart

Nathalie Sandrine

Viviane Duluard

Maëlenn Turq

Marie-Pierre Aufray

Labeau

Sandrine Duluard

Viviane Tmq

Maelenn Aufray

Marie-Pierre Labeau

Development of new surface treatments for the adhesive bonding of aluminum surfaces

Keywords:

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

Adhesive bonding is one out of many joining technologies [START_REF] Campbell | Adhesive bonding and integrally cocured structure : a way to reduce assembly costs through parts integration[END_REF][START_REF] Banea | Joining processes based on adhesion forces principles of adhesive bonding[END_REF], along with welding and riveting to nan1e a few. lt produces a continuous and homogeneous joint line or joint sm f ace rather than localized contact points. This continuous joint smface presents several advantages versus welding and riveting: i) more unifom1 stress distribution over the bonded surface [START_REF] Banea | Joining processes based on adhesion forces principles of adhesive bonding[END_REF][START_REF] Lathabai | Joining of aluminium and its alloys[END_REF][START_REF] Shields | Adhesive bonding[END_REF], il) good dan1ping properties for noise and vibra tions, which therefore in1proves the comfort of drivers and passengers [START_REF] Banea | Joining processes based on adhesion forces principles of adhesive bonding[END_REF][START_REF] Wheeler | Aluminum structured vehicle technology -a comprehensive approach to vehicle design and manufacturing in aluminum[END_REF], ili) an increased stiffness (in1proved safety in the case of car bodies), iv) no galvanic corrosion issue (metal-to-polymer contacts instead of metal-to-rivet contacts), v) a weight reduction [START_REF] Birch | Aluminium spaceframe technology[END_REF] (adhesives have a much lower density than mechanical fasteners). However, regarding light weighting, the largest gain comes from the replacement of steel by aluminum, which was actually enabled by adhesive bonding. Indeed, aluminum, easier to recycle and lighter than steel, is an attrac tive alternative to steel but its drawback is a lower aptitude to welding. Aluminum started to be massively used in the automotive industry [START_REF] Barnes | Joining techniques for aluminum spaceframes used in automobiles. Part II -adhesive bonding and mechanical fasteners[END_REF], and especially for the body-in-white, when surface tr•eatment technol ogies yielding durable adhesive joints and applicable at lar•ge scale were

• Corresponding author.

E-mail address: layec@chinùe.ups-dse.fr (J. Layec). https:/ /doi.org/10.1 0l 6/j.ijadhadh.2021.103006 developed. Severa! automotive manufacturers embar•ked on the design of so called "aluminum-intensive cars" [START_REF] Wheeler | Aluminum structured vehicle technology -a comprehensive approach to vehicle design and manufacturing in aluminum[END_REF][START_REF] Vasilash | The lotus elise : a technological tour de force[END_REF][START_REF] Komatsu | Application of all aluminum automotive body for HONDA NSX[END_REF], which allowed them to reduce the fuel consumption [START_REF] Cavezza | A review on adhesively bonded aluminium joints in the automotive industry[END_REF]. As a matter of fact, adhesive bonding as method of assembly allows to linut the CO 2 enussions of vehicles into the atmosphere by reducing their weight (about 30%) [START_REF] Birch | Aluminium spaceframe technology[END_REF], by replacing steel with lighter alununum [START_REF] Wheeler | Aluminum structured vehicle technology -a comprehensive approach to vehicle design and manufacturing in aluminum[END_REF][START_REF] Barnes | Joining techniques for aluminum spaceframes used in automobiles. Part II -adhesive bonding and mechanical fasteners[END_REF][START_REF] Hirsch | Aluminium alloys for automotive application[END_REF]. The bonding assembly method was set up as well as the prepar• ation and surface tr•eatments in order to promote the joint durability and the adhesion of compounds to an alununum surface [START_REF] Venables | Adhesion and durability of metal-polymer bonds[END_REF][START_REF] Matienzo | Environmental and adhesive durability of aluminium-polymer systems protected with organic corrosion inhibitors[END_REF][START_REF] Van Den Brand | Improving the adhesion between epoxy coatings and aluminium substrates[END_REF][START_REF] Mccleary | Organophosphonic or organophosphonic acid coating for aluminum alloy vehicle assemblies[END_REF]. It is precisely the ain1 and development of these surface treatments, also called bonding layer (BL).

For decades, smface treatments prior to bonding relied on inorganic technologies (anodization, titanium and/or zirconium hexafluorides, titanium and/or zirconium hexafluorides combined with organic poly me1ic adhesion promotors). Very recently, BLs exclusively consisting in organic molecules and especially organic polymers, were developed [START_REF] Ulman | formation and structure of self-assembled monolayers[END_REF][START_REF] Attavar | Passivation of aluminum with alkyl phosphonic acids for biochip applications[END_REF]. These polymers contain different bonding functions with, on one hand, the alununum substrate and, on the other hand, with the adhesive. Thus, the transition from inorganic to organic treatments, by varying the nature of the anchor i ng functions (the lateral functions) within the polymers to optinuze their role as bridging agent between two different All treated substrates undergo the same surface preparation, as well as the same method of deposition of BL. This takes place via successive immersions in different baths placed on a heated orbital table (Fig. 1) set at 45 rpm and at 80 • C so that the solutions reach a temperature of 50

• C ± 3 • C.
The very first step consists in immersing the aluminum surfaces in a commercial solution of DBT Alu 200 from Chemtec, which is a "two-inone" solution, cleaning and etching (c/e), to save time compared to conventional processes which involve first an alkaline degreasing step, followed by an acidic step. The sheets of aluminum were produced by rolling processes, the near surface deformed layer (NSDL) resulting from this process contains lubricant residues on the surface and in inclusions, as well as particles of fragmented intermetallics and oxides. This step (c/ e) aims at removing this NSDL and also at activating the surface by removing and replacing native alumina with controlled aluminum hydroxides groups, to generate a surface adequate for surface treatments. According to the recommendations of the technical data sheet, the substrates are dipped for 3 min (at 50 • C) in a concentrated bath at 50 g/ L. This is followed by two successive rinses by immersion in two separate baths of distilled water (also at 50 • C) for 1 min each.

The c/e reference is obtained after the rinsing and drying steps, coarsely with compressed air at first and then in an oven for 10 min at 80 • C to remove traces of water. All the other samples, after the rinsing steps, are directly immersed in the BL baths (at 50 • C), either for 120 or for 3 s, then rinsed again, but this time under distilled running water for 1 min and finally dried exactly the same way as described above.

Materials characterization 2.2.1. TEM analysis

To characterize the morphology of BLs and more precisely the thickness of the BL, cross-sectional observations were made with a transmission electron microscope (TEM) for BL Addibond 021 and Addibond 275 on AA5754.

First of all, the samples were metallized with gold (200 nm thick layer) using a Cressington 118 Auto metallizer (England), and secondly with platinum (2-3 μm thick layer) inside the FIB in order to protect the BL before slicing the sample using a focused ionic beam (FIB).

A focused ion beam coupled with a scanning electron microscope was therefore used because this method makes it possible to cut and observe a sample slice with very high cutting precision. The region of interest is therefore observed to determine the thickness of the BL on the aluminum substrate.

Taking into account the scales observed and analyzed, the observation of the morphology of the BLs was carried out under a transmission electron microscope using a JEOL JEM 2100 F device (Japan). The source is field emission with an acceleration speed of 200 kV and a resolution of 2.3 Å.

XPS analysis

X-Ray photoelectron spectroscopy (XPS) analyses were carried out on Addibond 021 and Addibond 275 at two immersion times respectively 120 and 3 s, as well as at three different concentrations, low, medium and high, as well as on a raw reference. These analyses made it types of compounds to ensure efficient and durable structural bonding, constitutes a novelty in the field of surface treatments for adhesive bonding. For this, polymers having different functions such as, phosphonic acids and carboxylic acids have been developed. These functions will form covalent bonds with the aluminum hydroxides of the substrate and the functions present in the adhesive, such as epoxy and amine functions. Different reaction mechanisms have been determined, a dehydration reaction between the phosphonic acid function and the aluminum hydroxides [START_REF] Zhao | Recent development in phosphonic acid-based organic coatings on aluminum[END_REF][START_REF] Hoque | Alkylphosphonate modified aluminum oxide surfaces[END_REF][START_REF] Rotole | Aluminum phosphate by XPS[END_REF][START_REF] Davies | The chemisorption of organophosphorus compounds at an Al(1 1 1) surface[END_REF] and an esterification reaction between the acrylic acid functions and the epoxides of the adhesive [START_REF] Alvey | Investigation of the epoxide-carboxylic acid reaction in model compound and polymerization reactions[END_REF][START_REF] Alexander | Plasma polymer chemical gradients for evaluation of surface reactivity: epoxide reaction with carboxylic acid surface groups[END_REF]. The bonds formed as a result of these reactions were demonstrated by XPS, ATR-IR and 13 C NMR analyzes. Also, Nitowski et al. [START_REF] Nitowski | Topographic and surface chemical aspects of the Adhesion of structural epoxy resins to phosphorus oxo acid treated aluminum aluminum adherends[END_REF] also put in evidence nucleophilic additions between the vinyl groups (when present in the surface treatment formulation) and amine functions of the adhesive [START_REF] Matveeva | Efficient synthesis of racemic β-aminophosphonates via aza-Michael reaction in water[END_REF][START_REF] Rulev | Aza-Michael reaction: achievements and prospects[END_REF]. This kind of BL has been developed to be convenient for various applications and different application methods, including spraying and dipping processes (for parts and coil processes). This work focuses on one hand on the nature of polymers and on the other hand on the impact of the polymer concentration in the surface treatment bath and immersion time in these treatment baths. In this study, immersion times of 120 or 3 s (to approach contact times typical of parts immersion processes and coil processes, respectively) were investigated, and correlated to the morphology of BLs and on their adherence performance using various mechanical tests.

Experimental

.1. Materials and sample preparation

The aluminum grade AA5754 is an alloy widely used in the automotive industry. We used AA5754 supplied by FBCG (Al: 94.9%, Mg: 2.6-3.6%, Fe: 0.4%, Si: 0.4%, Mn: 0.5%, Cr: 0.3%, Zn: 0.2%, Cu: 0.1%, Ti: 0.03%). The treated coupons are 100 mm long 25 mm wide and 3 mm thick.

The adhesive used for the micro-scratch and the single lap shear tests is a commercial epoxy-dicyandiamide, Betamate 1496 F from Dupont company. The curing step is carried out in an oven at 180 • C during 40 min.

The second adhesive used for the three-point bending test is a twocomponent epoxy-amine at low viscosity, Araldite AY103 with HY991 from Gaches supplier. The curing cycle is 1 h at 130 • C in oven.

The two systems used in this study are described in the following table (Table 1). The first one consists in a poly (vinyl phosphonic acid-coacrylic acid) supplied by Solvay (Addibond 021), while the second system (Addibond 275) contains the same polymer plus the vinyl phosphonic acid monomere itself (VPA). They are compared with a commercial formulation, which is composed of a polymeric adhesion promotor and an inorganic H 2 (Ti, Zr)F 6 part which forms a conversion layer. This product was selected as reference because it is already on the market and is used in aluminum surface treatment for structural bonding applications.

possible to determine on one hand the binding energies between the BL and the aluminum substrate and on the other hand the elemental composition in atomic percentage of the BL at the extreme surface.

A ThermoFisher Scientific K-ALPHA spectrometer (United States of America) was used for XPS surface analysis with a monochromatized AlKα source (hν 1486.6 eV) and a 200 μm X-Ray spot size. A pressure of 10 -7 Pa was reached in the chamber when transferring the raw, Addibond 021 and Addibond 275 samples. The full spectra (0-1320 eV) were recorded with a constant pass energy of 200 eV and high resolution spectra with a constant pass energy of 40 eV. Charge neutralization was applied during analysis and depth profiles were fulfilled with an Ar + ion gun (500 eV energy). The depth sequence was divided into 14 levels (0, 8, 16, 24, 39, 55, 70, 86, 117, 148, 179, 211, 242, 289 nm) in order to finely probe the extreme surface of the material. High resolution spectra (i.e. C1s, O1s, N1s, P2p, P2s, Al2p, Cu2p, Mg1s, and F1s) were quantified through Scofield sensitivity factors using the AVANTAGE software provided by ThermoFisher Scientific.

Model reaction with the adhesive and related analyses

The reaction between the Addibond 021 and the epoxide adhesive was investigated with glycidyl ether 4-methoxylphenyl, model for the epoxide adhesive. The Addibond 021 was dried as a very thin film at room temperature on a glass panel, further dried in an oven at 80 • C for 10 mn. On the resulting thin film was then added an excess of glycidyl ether 4-methoxylphenyl, and the blend was heated till 50 • C, to melt down the epoxide. Both were then mixed with a spatula and heated to 180 • C for 40 mn, conditions typically used to cure the structural epoxide adhesives. The resulting product was then combined with both water and chloroform, to solubilize unreacted polymer (in the water phase) and the unreacted epoxide (in the chloroform phase). The whole product was recovered after filtration of the water phase: there was no product found i) in the chloroform phase after chloroform evaporation, ii) in the water phase while all the product was recovered as being insoluble in the water phase. This insoluble matter was analyzed by solid NMR and ATR-IR. A blank experiment was done with the polymer alone (Addibond 021, no added epoxide): the film was prepared in the very same conditions and then submitted to the same temperature profile. The objective was to get reference NMR spectra and ATR-IR chromatograms. 13 C Experiments were performed on a Neo Avance Solid 400 MHz Bruker spectrometer (9,4 T) equipped with a 4 mm probe (France). For the high power decoupling (HPDEC) the length of the P90 pulse was 3.8 μs and the recycling delay was set to 30 s. The proton was decoupled at 80 KHz and MAS frequency was set to 6 KHz. Adamantane was used as the 13 C chemical shift reference (δ 38,5 ppm for the left peak).

Solid NMR analysis.

ATR-IR analysis.

The product prepared as described above was also analyzed by ATR-IR. Products were analyzed by ATR-IR (Attenuated Total Reflection -Infrared) on a Bruker spectrometer (France), Tensor 27, with the adequate ATR-diamond set. Wave lengths were varied from 650 to 4000 cm -1 , with a 4 cm -1 resolution and 35 scans were performed for each sample.

Micro-scratch test

The scratch resistance of the systems was evaluated using a microscratch test with increasing normal loading, with normal forces in the Newton range. This technique is based on the comparison of the critical normal forces values, leading to typical damages of the studied systems (plastic deformation, ductile/brittle transition with cracking of the layer or of the substrate itself, lateral displacement of material, chipping or delamination of the layer, etc.).

A semi-complete system was produced for this test: a treated aluminum coupon is coated with the adhesive (Betamate 1496 F) on its tip and a Teflon coupon is then placed on top so that a 25 mm wide by 12.5 mm long overlap is obtained. After the adhesive curing cycle, the Teflon coupon is removed to obtain the sample to be scratched (Fig. 2).

The thickness of the adhesive is heterogeneous, but lies around 200 μm, and contains small air bubbles due to the non-adhesion of the Teflon coupon.

The scratches are performed with a Scratch-Test REVETEST equipment from CSM Instrument (Switzerland) by applying a progressively increasing normal force from 55 to 100 N over a total distance of 4 mm with a scratch speed of 1 mm/min. For each sample, three scratches were made to evaluate the repeatability.

To compare BLs to each other, the normal force of adhesive delamination, corresponding to the aluminum substrate baring, was chosen (full black cross on Fig. 3), which corresponds to the normal applied force at which the interface between adhesive and treated substrate

Three-point bending test

For this mechanical test was operated according to the ISO 14679-1997 standard, which specifies the use of substrates 50 mm long, 10 mm wide and 1.5 mm thick. An adhesive cube is made using a three-part mold (Fig. 4) to form 25 mm long, 5 mm wide and 4 mm thick cube by applying 0.5 mL of adhesive using a 1 mL syringe.

The test is conducted by an INSTRON traction machine (model 3369, France) equipped with a 500 N load sensor and a jaws system suitable for the three-point bending where the distance between supporting pins is 35 mm. The speed of the test is 0.5 mm/min. The force at break (N) is obtained from the graph showing the force values (N) as a function of the displacement (mm).

While the standard recommends at least 6 samples per series, 24 samples were performed per series and the Dean and Dixon statistical test [START_REF] Dean | Simplified statistics for small numbers of observations[END_REF] was used to rule out the most aberrant results. One sample per series (in average) was discarded, with a percentage of 5%.

Single lap shear test

The single lap shear (SLS) is a very widespread and mastered test in the industry, it is also easy to implement, which is why it is very often used as a routine test, especially in automotive applications.

The treated coupons are glued together with a 25 mm by 12.5 mm overlap and the bond line (adhesive film thickness) is 200 μm, controlled by the presence of glass beads (with a diameter between 150 and 250 μm) within the adhesive itself.

The test is carried out on the same traction machine as the threepoint bending test, but equipped with a 30 kN load sensor. The assembly is placed such that the jaws (of 30 kN) grasp the coupon tips over 50 mm. The pulling speed is set at 10 mm/min. The load at break (N) was retained, as well as the stress at break (MPa) which corresponds to the force required to break the adhesive joint. Five samples are tested per series to obtain average values.

For this test, assemblies were tested "fresh" and after ageing. "Fresh" means the SLS assemblies are tested shortly after their production. "Ageing" means that assemblies are placed in a corrosion chamber and submitted to 500 cycles at 49 • C, each 2 h-long, consisting in an acetic acid salt spray for 30 mn followed by 1h30 at 98% relative humidity, according to the ASTM G85-A3 standard. The solution used in the corrosion chamber consists of sodium chloride (42 g/L) and acetic acid (10 mL/L) to reach a pH between 2.8 and 3.0. Total ageing time is 1000 h.

Results and discussion

Characterization of the bonding layeraluminum substrate interface 3.1.1. Adsorption mechanisms of the bond layer

The BL is located between the aluminum substrate and the adhesive (epoxy-dicyandiamide). For effective bonding this BL should be strongly linked to both parts. This guided the design of the polymers tested here, that is why the Addibond polymers have several reactive functions with the aim of reacting covalently with the species present on the one hand on the aluminum substrate and on the other hand in the adhesive.

First of all, it has been shown by X-Ray photoelectron spectrometry analyses [START_REF] Zhao | Recent development in phosphonic acid-based organic coatings on aluminum[END_REF], that the phosphonic acid functions present in Addibond 021 and Addibond 275 react covalently with aluminum oxides by a dehydration reaction described in Fig. 5.

Esterification reactions between the carboxylic acid functions of polymers and the epoxide functions of the adhesive according to the following mechanism (Fig. 6) also take place. These reactions were evidenced by 13 C solid NMR and ATR-IR.

Starting from peaks typical of carboxylic acids, a new peak appears at 175 ppm in 13 C solid NMR (Fig. 7), while a new signal appears at 1700 cm -1 in ATR-IR (Fig. 8). These new signals are typical of ester functions, in line with the reaction shown Fig. 6.

Also, by mechanisms less known but shown in the work of Nitowski [START_REF] Nitowski | Topographic and surface chemical aspects of the Adhesion of structural epoxy resins to phosphorus oxo acid treated aluminum aluminum adherends[END_REF], there is a nucleophilic addition reaction (Michael addition) between the vinyl functions (of the vinyl phosphonic acid monomer) and the amine functions of the adhesive (Fig. 9), [START_REF] Matveeva | Efficient synthesis of racemic β-aminophosphonates via aza-Michael reaction in water[END_REF][START_REF] Rulev | Aza-Michael reaction: achievements and prospects[END_REF].

Finally, all these mechanisms make it possible to ensure a chemisorption of the polymers constituting the BLs with respect to the substrate and the adhesive.

Bond layer morphology

By TEM observations with FIB preparation, it was possible to distinguish in Fig. 10 a thin layer between 5 and 10 nm thick which would represent the BL of Addibond 021 (the same observations has been seen on Addibond 275 sample). The thin 5-10 nm layer appears on images of clear contrast between the aluminum (light grey) and the gold layer (black).

It was noted on the sample of Addibond 021 areas where the BL appears to be denser and more porous areas (dotted black circles) where the gold from the metallization diffuses into the BL. This phenomenon seems to indicate that the polymers of the BL do not organize themselves in the same way over the entire surface of the substrate, and perhaps testifies to an inhomogeneity in the reactions between the aluminum hydroxides and the phosphonic acid and carboxylic acid functions of polymers.

It was possible to observe the layer thicknesses (between 5 and 10 nm) on all Addibond samples, in both cases of 120 or 3 s immersion times (see Table 2), which means that this time is not a key parameter on the formation and therefore on the morphology of the layer.

However, for the commercial formulation, the immersion time is clearly impacting because for short immersion times, the layers are around 50 nm while for long times the layers are between 150 and 250 nm thick. This is explained by the nature of this layer which is in part a conversion layer. The formation of a conversion layer based on zirconium and/or titanium is initiated by the dissolution of the native aluminum oxide layer present at the surface by the fluoride ions, then by the precipitation of the zirconium and/or titanium caused by a local increase in pH at the surface due to dissolved oxygen reduction reactions. This precipitation corresponds to the formation and thickening of the conversion layer, which is a function of the immersion time in the treatment bath, and preferably occurs around the cathode intermetallic particles present on the surface of the aluminum alloy. This phenomenon therefore causes variations in thickness, as the layer is more irregular close to the intermetallic particles [START_REF] Adhikari | Hexafluorozirconic acid based surface pretreatments: characterization and performance assessment[END_REF].

Surface analysis with XPS

To confirm the chemisorption of Addibond to aluminum surfaces, previously discussed, XPS analyses were performed at the extreme surface of the aluminum substrate, between 0 and 5 nm thick, which corresponds to the thickness of the BL. It was possible to note on the spectra of interest, aluminum, oxygen and phosphorus binding energies (Table 3). Indeed, Al (2p) was identified between 75.1 and 73.3 eV, between 532.1 and 532.3 eV for O (1s), between 190.7 and 191.3 eV for P (2s) and finally between 133.7 and 133.9 eV for P (2p) corresponding all to Al-O-P bonds. These binding energies demonstrate the formation of a covalent bond between the aluminum substrate and the phosphonic acid functions of the polymers [START_REF] Zhao | Recent development in phosphonic acid-based organic coatings on aluminum[END_REF]. We can illustrate this covalent bond according to the previous reaction mechanism of dehydration (Fig. 5).

We can specify that beyond the thickness of 5 nm analyzed (at the extreme surface), we no longer find the energies at 75.3 eV for Al (2p), and no energy peaks for P (2s) and P (2p). This means that the constituent polymers of the BLs are no longer present and that the bulk of the aluminum has therefore been reached. Indeed, over an analyzed thickness of 5-289 nm, binding energies were identified at 72.9 eV for Al (2p), corresponding to Al-metal bonds, characterizing the aluminum alloy.

The phosphorus rate in atomic percentage at the extreme surface of the substrate (always between 0 and 5 nm thick) were checked to confirm the presence of polymers at different concentrations (low, medium and high) and immersion times (120 and 3 s) in Fig. 11.

As expected Addibond 275 contains a little more phosphorus than Addibond 021 thanks to the presence of the VPA monomer which provides more phosphorus. In addition, it is noted that at constant concentration the immersion time has no significant effect, especially for Addibond 275. Thus the formation and the morphology of the BL seem to be similar for short or long immersion times, which means that the polymers are chemisorbed in the first seconds of immersion. But concentration seems to be a critical parameter, and in our conditions, the optimal solution is generally observed at medium concentration (except for Addibond 021 immersion 120 s). At lower concentrations the quantity of polymer is probably not sufficient to ensure a maximum of bonds with the substrate. At higher concentrations it would appear that the polymers adsorb less to the surface because the surface is probably already saturated, and that potentially there would be residual nonchemisorbed polymers on the surface that would not be taken into account during the XPS analysis.

Characterizations of the bond layeradhesive interface

To characterize the performance of the bonding layers at the aluminum bond layer substrate interface, several mechanical tests, such as micro-scratch test, three-point bending test and single lap shear test, were carried out and compared.

Micro-scratch test

This test was carried out on the raw substrates and at each step of the process (cleaned and etched (c/e), Addibond 021 deposition on c/e, Addibond 275 deposition on c/e and commercial formulation on c/e, at two immersion times (120 and 3 s) at a concentration called « medium », which is of about 1500 ppm for Addibond.

First, on Fig. 12, we can notice the benefit of surface preparation over a raw substrate can be noticed. Indeed, the normal force of the raw reference (X symbol) is 7 N lower than that of the reference having undergone a surface preparation c/e (right cross symbol). This confirms the interest of carrying out a surface preparation to promote and improve the mechanical anchoring of the adhesive and/or the

Table 2

Final thickness of BLs (nm). physicochemical phenomena such as the controlled formation of aluminum hydroxides with respect to a "raw" substrate.

The normal delamination force of the reference c/e sample is similar to that of the samples with the surface treatments. For these samples, the failure being always cohesive for SLS test (in the adhesive used for the test), the value corresponds to the cohesive force of the adhesive, and these similar values for the different samples shows both the high performances of the surface treatments as well as the validity of the testing set-up. Moreover, the micro-scratch test depends on several factors including the surface roughness, but it has been seen by measurements of roughness with the interferometer that the value of roughness Sa is of the order of 0.3 μm, for the c/e reference as well as for those with BLs references, which could explain that these samples have similar results in normal force of delamination (N).

Nevertheless, we can compare the results of the normal force leading to delamination for the Addibond 021 and Addibond 275 systems. First, we can notice that Addibond 275, which contains more phosphonic acid functions (82.5% versus 30% for Addibond 021), shows the highest normal force results (75 versus 70 for Addibond 021), especially for the 3 s sample. Thus, the possibility to generate more covalent bonding with the substrate for Addibond 275 [START_REF] Zhao | Recent development in phosphonic acid-based organic coatings on aluminum[END_REF], seems favorable to the increase of the critical normal force of delamination.

In addition, we find that the immersion time moderately impacts Addibond systems compared to the commercial formulation. This means that the Addibond systems can also be used as a spray or in immersion systems. This versatility in application processes is an advantage for these products. On the contrary, commercial formulation is impacted by short or long immersion time: for the sample at 120 s Of immersion the force of exposure of the substrate is clearly lowered, becoming even lower than that of the raw substrate. This phenomenon could be explained by the presence of the inorganic part which forms an H 2 (Zr, Ti)F 6 conversion layer. For this type of compound, the longer the immersion time, the thicker the conversion layer [START_REF] Adhikari | Hexafluorozirconic acid based surface pretreatments: characterization and performance assessment[END_REF], as discussed previously.

Thus the formation of a thick BL is harmful to the adhesion, and this according to the theory of the layers of weak cohesion [START_REF] Bikerman | Causes of poor adhesion : weak boundary layers[END_REF] which describes that the interfacial forces are always stronger than the force of cohesion of the thicker layer component of the assembly, here the BL. It follows that the failure will always take place in the layer with the weakest cohesive force.

Consequently, these two different types of chemistry (organic for Addibonds, organic and inorganic for the commercial formulation) intended for the same application, which is structural bonding, present different performances, with greater robustness for Addibonds.

Three-point bending test

As the micro-scratch test, the three-bending test was conducted on the same references namely: raw, c/e, Addibond 021, Addibond 275 and commercial formulation, for all samples at two immersion times (120 and 3 s) at a medium concentration.

In this test, Araldite AY103 with HY991 adhesive, with a formula very similar to that of Betamate 1496 F, was used to evaluate the universal side of BL against different adhesives.

According to the results of force at break (N) (Fig. 13) it is observed a very similar tendency as that obtained with the micro-scratch test. Indeed, it appears once again that the cleaning-etching is beneficial for thickness is too predominant on the results to conclude on the effect of the concentration.

We can also discuss the fracture facies of the samples. It is possible to correlate the highest breaking stress results with cohesive breaks (Fig. 15), notably for c/e, Addibond 021, Addibond 275 (120 and 3 s for both), as well as the commercial formulation at 3 s. For the lowest results, a distinction is made between adhesive ruptures (raw sample and the commercial formulation at 120 s) which testifies to a fragility at the BL -adhesive interface.

Then for the results after ageing (hatched bars), it is noted exactly the same tendency as before ageing, that it is on the level of the results of stresses at break or of the facies of fracture (Fig. 16). We can note that there are no results for the raw references because the five samples broke during the salt spray ageing cycle, the same for the commercial formulation at 120 s at medium and high concentration. That is why only 1 sample has could be tested for each (that is why there are no error bars in Fig. 17).

As the trend of the results is the same before and after ageing, it is interesting to calculate the percentage of retention rate, which corresponds to the ratio of the stress at break after aging to that before ageing according to equation [START_REF] Campbell | Adhesive bonding and integrally cocured structure : a way to reduce assembly costs through parts integration[END_REF].

R%

Stress at break after ageing Stress at break before ageing × 100

If we look at the retention rates on Fig. 17, we see that those of Addibond 021, Addibond 275, and the commercial solution at 3 s are between 92 and 100%, or even more than 100% (which means in this case, the samples after ageing have higher breaking stresses than before ageing), while the c/e reference is at 86%. It can then be confirmed that Addibond products provide a better resistance to ageing than a simple cleaning-etching as a surface preparation and that the performances of the BLs are well improved.

It is also noted the commercial formulation at 120 s which exhibited low stresses at break and cohesive fracture facies does not exceed the retention rate of the c/e reference. This means that the weak results before ageing remain after ageing, and that there is not the phenomenon of exacerbated performance after ageing as observed for the other samples. As reported in the work of Otto Lunder [START_REF] Lunder | Chromate-free pre-treatment of aluminium for adhesive bonding[END_REF], it is during the ageing step of the samples (in a salt spray for example) that the performances of bonding layers are exacerbated.

Thus, as it was seen previously, the three types of mechanical tests are well correlated. Indeed, the surface preparation (c/e) is always seen to be beneficial as compared to a raw sample, and the BLs, always have improving adhesion phenomena, and that BL Addibonds are moderately impacted by the immersion time. On the other hand, the commercial formulation is again influenced by the formation of a thick BL, which considerably lowers the force at break. So, both mechanical tests are very well correlated.

.3. Single lap shear test

The following graph (Fig. 14) summarizes the single lap shear results in stress at break (MPa) before and after ageing of raw sample, c/e, Addibond 021, Addibond 275 and the commercial formulation at two immersion times (120 and 3 s) and three different concentrations (low, medium and high).

It was also noted the fracture facies of the samples, cohesive or adhesive. For similar stress at break, it is preferable to obtain cohesive rupture because this means that the weak point is the adhesive and not the interface of interest, BL -adhesive.

As previously on both three-point bending and micro-scratch test, the results of stress at break (MPa) before ageing (full bar) show better results after cleaning etching (second bar on the left) as compared to a raw sample (first bar on the left), it is determined a gain of almost 50%. Also, for Addibonds, the effect of concentration affects the results in stress at break more than the immersion time, taking into account the error bars. Indeed, it is observed that at a medium concentration the breaking forces are higher than for low and high concentrations (particularly for Addibond 021). This can be compared with the XPS analyses where it was observed that at this same medium concentration there was a higher atomic percentage of phosphorus at the extreme surface, which translates more chemisorbed polymers at the surface and therefore an improvement in the adhesion phenomena on either side of adherents, substrate and adhesive.

For commercial formulation before ageing, the reverse phenomenon operates. Indeed, the long immersion time (120 s) forms thicker, brittle layers according to the theory of weak boundary layers, and therefore the breaking force results are lower, in good agreement with the previous mechanical tests. However, at short immersion time (3 s), the results are at the same level as the Addibonds, because the BL is thinner (around 50 nm), this therefore confirms the hypothesis of weak boundary layers for thicker layers. On the other hand, the effect of the concentration for the samples at 3 s is clearly null. This can be explained by the fact that it is a precisely formulated solution (containing additives, adhesion promoters, etc.) which visibly allows the effects of concentration to be controlled. For the samples at 120 s, the effect of the BL the same effect whatever the immersion time and the concentration in the tested range.

Conclusions

The morphology and reactions of BL Addibond systems were determined: the Addibond BLs are effectively chemisorbed on each side of the adherents, the aluminum substrate and the epoxy-dicyandiamide adhesive, by dehydration reactions, esterification or even nucleophilic addition. The Addibond polymers appear to organize into a 5-10 nm thick polymeric monolayer to form BL. This layer does not vary in thickness despite the immersion time (120 or 3 s) in the treatment bath containing the polymers, since the polymers will be chemisorbed at the surface of the aluminum in the early stages of immersion.

The thickness of the commercial BL seems to be very decisive subsequently in the mechanical tests since it was shown in tests of microscratch, three-point bending and single lap shear (before and after ageing), that Addibond 021 and Addibond 275 products which form thin BLs (5-10 nm) and commercial BL of 50 nm thick showed higher results in terms of strength or stress at break than thicker BLs (150-250 nm) formed by commercial formulation at 120 s of immersion.

In addition, it was seen in the three types of mechanical tests conducted, that the results exhibited the same trends and are very well correlated. This means that despite different stresses, scratching, bending or shearing, the same behavior operated.

Finally, through single lap shear tests, it was observed, after an aging process (1000 h), that the stress and break results of Addibond products approach those of the c/e reference. The calculation of the retention rate could effectively demonstrate the advantage of BLs compared to a simple cleaning-etching (c/e) since the retention rate of Addibond products is at least greater than or equal to 92%, while the c/e reference is around 86%.

Fig. 1 .

 1 Fig. 1. General process of depositing bond layers on AA5754 substrates.

Fig. 2 .

 2 Fig. 2. Sample before and after scratched on treated AA5754 with Betamate 1496 F adhesive.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Example of a micro scratch with represented by the dotted cross the start of exposure of the substrate and by the full cross the complete exposure of the substrate.

Fig. 5 .

 5 Fig. 5. Reaction mechanism between phosphonic acid functions and aluminum oxides.

Fig. 6 .

 6 Fig. 6. Reaction mechanism between carboxylic acid function and epoxide functions.

Fig. 7 .

 7 Fig. 7. Solid 13 C NMR spectrum, black spectrum: Addibond 021 alone, grey spectrum: Addibond 021 with 4-methoxyphenyl glycidyl ether (epoxy adhesive model).

Fig. 8 .Fig. 9 .

 89 Fig. 8. ATR infrared spectrum, black spectrum: Addibond 021 alone, red spectrum: Addibond 021 with 4-methoxyphenyl glycidyl ether (epoxy adhesive model). (For interpretation of the references to colour in this figure legend, the reader is referred to the Web version of this article.)

Fig. 10 .

 10 Fig. 10. Thickness of Addibond 021 at 120 s of immersion time on AA5754 observed with TEM.

Fig. 11 .

 11 Fig. 11. Atomic percentage of phosphorus at the extreme surface, between 0 and 5 nm thick, of Addibond 021 and Addibond 275 at two immersion times (120 and 3 s) and three concentrations (low, medium and high concentration) on AA5754 substrate.

Fig. 12 .

 12 Fig. 12. Normal force of delamination (N) obtained by micro-scratch for Addibond 021, Addibond 275 and the commercial formulation systems, at 120 and 3 s of immersion time for each, on AA5754 substrate with the adhesive Betamate 1496 F.

Fig. 13 .

 13 Fig. 13. Force at break (N) obtained by three-bending point for Addibond 021, Addibond 275 and the commercial formulation, at 120 and 3 s of immersion time for each, on AA5754 substrate with the adhesive Araldite AY103 and HY991.

Fig. 14 .

 14 Fig. 14. Stress at break (MPa) obtained by single lap shear, before and after ageing, for Addibond 021, Addibond 275 and the commercial formulation, at 120 and 3 s of immersion time for each, on A5754 substrate with the adhesive Betamate 1496 F

Fig. 15 .

 15 Fig. 15. Fracture facies obtained by single lap shear of raw, c/e, Addibond 021, Addibond 275 and commercial formulation samples, on AA5754 substrates with the adhesive Betamate 1496 F, before ageing.

Fig. 16 .

 16 Fig. 16. Fracture facies obtained by single lap shear of raw, c/e, Addibond 021, Addibond 275 and commercial formulation samples, on AA5754 substrates with the adhesive Betamate 1496 F, after ageing.

Fig. 17 .

 17 Fig. 17. Retention rate in percentage of stress at break obtained by single lap shear for Addibond 021, Addibond 275 and the commercial formulation, at 120 and 3 s of immersion time for each, on a substrate AA5754 with the adhesive Betamate 1496 F

Table 1

 1 Nature of polymers forming BL.

		Addibond 021	Addibond 275	Commercial formulation
	Nature of the BL	Organic	Organic	Mixed organic/inorganic

Lateral function (%mol)

Phosphonic acid (30%) Acrylic acid (70%) Phosphonic acid (82.5%) Acrylic acid (17.5%) Organic part + Conversion coating H2(Ti,Zr)F6

Table 3

 3 Binding

	Binding energy (eV)	Al (2p)	75.1-73.3
		O (1s)	532.1-532.3
		P (2s)	190.7-191.3
		P (2p)	133.7-133.9
	Characteristic bonds		Al-O-P

energy (eV) by XPS of Addibond 021 and 275 between 0 and 5 nm thick on AA5754 substrate.

Spectra

Addibond 021 and 275 (120 and 3 s)

Acknowledgement

Thanks to the Raimond Castaing center, especially Claudie Josse and to the Placamat center especially Christine Labrugère for their respective help to the MEB-FIB, TEM, and to the XPS.

Thanks also to Antoine Dubernard for his work on the three-point bending tests.

The reactions between the polymer and a model epoxy have been established by Guillaume Gody and Audreay Gratia at Solvay. Thank to them.


Andrew Ryzhikov
email: ryzhikov.andrew@gmail.com

Synchronization Problems in Automata without Non-trivial Cycles

Keywords: synchronizing automaton, computational complexity, inapproximability, weakly acyclic automaton, subset rank, synchronizable set

We study the computational complexity of various problems related to synchronization of weakly acyclic automata, a subclass of widely studied aperiodic automata. We provide upper and lower bounds on the length of a shortest word synchronizing a weakly acyclic automaton or, more generally, a subset of its states, and show that the problem of approximating this length is hard. We investigate the complexity of finding a synchronizable set of states of maximum size. We also show inapproximability of the problem of computing the rank of a subset of states in a binary weakly acyclic automaton and prove that several problems related to recognizing a synchronizable subset of states in such automata are NP-complete.

Introduction

The concept of synchronization is widely studied in automata theory and has a lot of different applications in such areas as manufacturing, coding theory, biocomputing, semigroup theory and many others [START_REF] Volkov | Synchronizing automata and the Černý conjecture[END_REF]. Let A = (Q, Σ, δ) be a complete deterministic finite automaton (which we simply call an automaton in this paper), where Q is a set of states, Σ is a finite alphabet and δ : Q × Σ → Q is a transition function. Note that our definition of an automaton does not include initial and accepting states. The function δ can be naturally extended to a mapping Q×Σ * → Q, which we also denote as δ, in the following way: for x ∈ Σ and a ∈ Σ * we recursively set δ(q, xa) = δ(δ(q, x), a). An automaton is called synchronizing if there exists a word that maps all its states to a fixed state. Such word is called a synchronizing word. A state q ∈ Q is called a sink state if all letters from Σ map q to itself.

In this paper synchronization of weakly acyclic automata is studied. A simple cycle in an automaton A = (Q, Σ, δ) is a sequence q 1 , . . . , q k of its states such that all the states in the sequence are different and there exist letters x 1 , . . . , x k ∈ Σ such that δ(q i , x i ) = q i+1 for 1 ≤ i ≤ k -1 and δ(q k , x k ) = q 1 . A simple cycle is a self-loop if it consists of only one state. An automaton is called weakly acyclic if all its simple cycles are self-loops. In other words, an automaton is weakly acyclic if and only if there exists an ordering q 1 , q 2 , . . . , q n of its states such that if δ(q i , x) = q j for some letter x ∈ Σ, then i ≤ j (such ordering is called a topological sort). Since a topological sort can be found in polynomial time [START_REF] Cormen | Introduction to Algorithms[END_REF], this class can be recognized in polynomial time. Weakly acyclic automata are called acyclic in [START_REF] Jirásková | On the state and computational complexity of the reverse of acyclic minimal DFAs[END_REF] and partially ordered in [START_REF] Brzozowski | Languages of R-trivial monoids[END_REF], where the class of languages recognized by such automata is characterized.

/ Procedia Computer Science 00 (2018) 1-13 2 Weakly acyclic automata arise naturally in synchronizing automata theory. For example, the automata in the reductions showing the hardness of the problem of finding a shortest synchronizing word of Eppstein [START_REF] Eppstein | Reset sequences for monotonic automata[END_REF] and Berlinkov [START_REF] Berlinkov | On two algorithmic problems about synchronizing automata[END_REF] are weakly acyclic. More precise inapproximability results for this problem in weakly acyclic automata are provided in [START_REF] Ryzhikov | Finding Short Synchronizing Words for Prefix Codes[END_REF]. Surprisingly, most of the computational problems that are hard for general automata remain very hard in this class despite its very simple structure. Thus, investigation of weakly acyclic automata provides good lower bounds on the complexity of many problems for general automata. An automaton is called aperiodic if for any word w ∈ Σ * and any state q ∈ Q there exists k such that δ(q, w k ) = δ(q, w k+1 ), where w k is a word obtained by k concatenations of w [START_REF] Trahtman | The Cerný conjecture for aperiodic automata[END_REF]. Obviously, weakly acyclic automata form a proper subclass of aperiodic automata, thus all hardness results hold for the class of aperiodic automata.

The concept of synchronization is often used as an abstraction of returning control over an automaton when there is no a priori information about its current state, but the structure of the automaton is known. If the automaton is synchronizing, we can apply a synchronizing word to it, and thus it will transit to a known state. If we want to perform the same operation when the current state is known to belong to some subset of states of the automaton, we come to the definition of a synchronizable set. A set S ⊆ Q of states of an automaton A is called synchronizable if there exists a word w ∈ Σ * and a state q ∈ Q such that the word w maps each state s ∈ S to the state q. The word w is said to synchronize the set S . It follows from the definition that an automaton is synchronizing if and only if the set Q of all its states is synchronizable. Consider the problem Sync Set of deciding whether a given set S of states of an automaton A is synchronizable.

Sync Set

Input: An automaton A and a subset S of its states; Output: Yes if S is a synchronizable set, No otherwise. The Sync Set problem is PSPACE-complete [START_REF] Rystsov | Polynomial complete problems in automata theory[END_REF][START_REF] Sandberg | Homing and synchronizing sequences[END_REF], even for binary strongly connected automata [START_REF] Vorel | Subset synchronization and careful synchronization of binary finite automata[END_REF] (an automaton is called binary if its alphabet has size two, and strongly connected if any state can be mapped to any other state by some word). In [START_REF] Natarajan | An algorithmic approach to the automated design of parts orienters[END_REF] it is shown that the Sync Set problem is solvable in polynomial time for orientable automata if the cyclic order respected by the automaton is provided in the input. This problem is also solvable in polynomial time for monotonic automata [START_REF] Ryzhikov | Subset synchronization in monotonic automata[END_REF]. The problem of deciding whether the whole set of states of an automaton is synchronizable is also solvable in polynomial time [START_REF] Volkov | Synchronizing automata and the Černý conjecture[END_REF].

One of the most important questions in synchronizing automata theory is the famous Černý conjecture stating that any n-state synchronizing automaton has a synchronizing word of length at most (n -1) 2 . The conjecture is proved for various special cases, including orientable, Eulerian, aperiodic and other automata (see [START_REF] Volkov | Synchronizing automata and the Černý conjecture[END_REF] for references), but is still open in general. For more than 30 years, the best upper bound was n 3 -n 6 , obtained in [START_REF] Pin | On two combinatorial problems arising from automata theory[END_REF]. Recently, a small improvement of this bound has been proved in [START_REF] Szykuła | Improving the Upper Bound on the Length of the Shortest Reset Word[END_REF]: the new bound is still cubic in n but improves the coefficient 1 6 at n 3 by 4 46875 . While there is a simple cubic bound on the length of a synchronizing word for the whole automaton, there exist examples of automata where the length of a shortest word synchronizing a subset of states is exponential in the number of states [START_REF] Vorel | Subset synchronization and careful synchronization of binary finite automata[END_REF]. For orientable n-state automata, a tight upper bound of (n -1) 2 is known [START_REF] Eppstein | Reset sequences for monotonic automata[END_REF], and this bound is also asymptotically tight for monotonic automata [START_REF] Ryzhikov | Subset synchronization in monotonic automata[END_REF]. On the other hand, a trivial upper bound 2 nn -1 on the length of a shortest word synchronizing a subset of states in a n-state automaton is known [START_REF] Vorel | Subset synchronization and careful synchronization of binary finite automata[END_REF]. In [START_REF] Cardoso | The Černý Conjecture and Other Synchronization Problems[END_REF] Cardoso considers the length of a shortest word synchronizing a subset of states in a synchronizing automaton.

We assume that the reader is familiar with the notions of an NP-complete problem (refer to the book by Sipser [START_REF] Sipser | Introduction to the Theory of Computation[END_REF]), an approximation algorithm and a gap-preserving reduction (for reference, see the book by Vazirani [START_REF] Vazirani | Approximation Algorithms[END_REF]).

Given an automaton A, the rank of a word w with respect to A is the number |{δ(s, w) | s ∈ Q}|, i.e., the size of the image of Q under the mapping defined in A by w. More generally, the rank of a word w with respect to a subset S of states of A is the number |{δ(s, w) | s ∈ S }|. The rank of an automaton (resp. of a subset of states) is the minimum among the ranks of all words w ∈ Σ * with respect to the automaton (resp. to the subset of states).

In this paper we provide various results concerning computational complexity and approximability of the problems related to subset synchronization in weakly acyclic automata. In Section 2 we prove some lower and upper bounds on the length of a shortest word synchronizing a weakly acyclic automaton or, more generally, a subset of its states. We also show that the problem of finding the length of a shortest word synchronizing a subset is hard to approximate. In Section 3 we study inapproximability of the problem of finding a subset of states of maximum size. In Section 4 we give strong inapproximability results for computing the rank of a subset of states in binary weakly acyclic automata.

In Section 5 we show that several other problems related to recognizing a synchronizable set in a weakly acyclic automaton are hard.

A preliminary conference version of this paper was published in [START_REF] Ryzhikov | Synchronization problems in automata without non-trivial cycles[END_REF].

Bounds on the Length of Shortest Synchronizing Words

Each synchronizing weakly acyclic automaton is a 0-automaton (i.e., an automaton with exactly one sink state), which gives an upper bound n(n-1) 2 on the length of a shortest synchronizing word [START_REF] Rystsov | Reset words for commutative and solvable automata[END_REF]. The same bound can be deduced from the fact that each weakly acyclic automaton is aperiodic [START_REF] Trahtman | The Cerný conjecture for aperiodic automata[END_REF]. However, for weakly acyclic automata a more accurate result can be obtained, showing that weakly acyclic automata of rank r behave in a way similar to monotonic automata of rank r (see [START_REF] Ananichev | Synchronizing monotonic automata[END_REF]). Proposition 1. Let A = (Q, Σ, δ) be a n-state weakly acyclic automaton, such that there exists a word of rank r with respect to A. Then there exists a word of length at most nr and rank at most r with respect to A.

Proof. Observe that the rank of a weakly acyclic automaton is equal to the number of sink states in it. The conditions of the theorem imply that A has at most r sink states.

Consider the sets S 1 , . . . , S t constructed in the following way. Let p i be the state in S i-1 with the smallest index in the topological sort such that p i is not a sink state. Let x i , 1 ≤ i ≤ t, be a letter mapping the state p i to some other state, where S i = {δ(q, x i ) | q ∈ S i-1 }, 1 ≤ i ≤ t, and S 0 = Q. Since A has at most r sink states, we can thus construct step by step a word w = x 1 . . . x t with t ≤ nr that has rank at most r with respect to A.

The following simple example shows that the bound is tight even for the case of alphabet of size one. Consider an automaton A = (Q, {x}, δ) with states q 1 , . . . , q n . For the letter x define the transition function δ(q i , x) = q i+1 for 1 ≤ i ≤ nr and δ(q i , x) = q i for nr + 1 ≤ i ≤ n. Obviously, A has rank r and shortest words of rank r with respect to A have length nr. For an example with a larger alphabet one can duplicate the letter x. Proposition 2. Let S be a synchronizable set of states of size k in a weakly acyclic n-state automaton A = (Q, Σ, δ). Then the length of a shortest word synchronizing S is at most k(2n-k-1)

2

.

Proof. Consider a topological sort q 1 , . . . , q n of the set Q. Let q s be a state such that all states in S can be mapped to it by a shortest word w = x 1 . . . x t . We can assume that the images of all words x 1 . . . x j , j ≤ t, are pairwise distinct, otherwise some letter in this word can be removed. Then a letter x j maps at least one state of the set {δ(q, x 1 . . . x j-1 ) | q ∈ S } to some other state. Thus the maximum total number of letters in w sending all states in S to

q s is at most (n -k) + (n -k + 1) + . . . + (n -1) = k(2n-k-1)

2

, since application of each letter of w increases the sum of the indices of reached states by at least one.

Consider a binary automaton

A = (Q, {0, 1}, δ) with n states q 1 , . . . , q k-1 , s 1 , . . . , s , t, where = n -k. Define δ(q i , 0) = q i , δ(q i , 1) = q i+1 for 1 ≤ i ≤ k -2, δ(q k-1 , 1) = s 1 . Define also δ(s i , 0) = s i+1 for 1 ≤ i ≤ -1, δ(s i , 1) = t for 1 ≤ i ≤ -1.
Define both transitions for s and t as self-loops. Set S = {q 1 , . . . , q k-1 , s }. The shortest word synchronizing S is (10 l-1 ) k-1 of length (k -1)(nk). The automaton in this example is binary weakly acyclic, and even has rank 2. Figure 1 gives the idea of the described construction. As was noted by an anonymous reviewer, for alphabet of size n -2, a better lower bound of (k-1)(2n-k-2) 2 can be shown as follows.

q 1 q 2 1 q k-1 . . . s 1 1 s 2 0 s . . . t 0, 1 0 0 0 1 1 0, 1
Let Q = {-1, 0, 1, . . . , n -2}, Σ = {a 1 , . . . , a n-2 }, δ(k, a i ) =                k if k > i, k -1 if k = i, -1 if 0 < k < i, k if k ∈ {-1, 0}
If k < n and S = {0, n -2, n -3, . . . , n -k}, then it is easy to see that the shortest word synchronizing S has length

(n -k) + (n -k + 1) + . . . + (n -2) = (k-1)(2n-k-2) 2 .
For each n and k, this is less than the upper bound of Proposition 2 by n -1 only.

Consider now the following problem. Shortest Set Sync Word Input: An automaton A and a synchronizable subset S of its states; Output: The length of a shortest word synchronizing S . It follows from Proposition 2 that the decision version of this problem (asking whether there exists a word of length at most k synchronizing S ) is in NP for weakly acyclic automata, so it is reasonable to investigate its approximability.

Theorem 1. The Shortest Set Sync Word problem for n-state binary weakly acyclic automata cannot be approximated in polynomial time within a factor of O(n Proof. To prove this theorem, we construct a gap-preserving reduction from the Shortest Sync Word problem in p-state binary automata, which cannot be approximated in polynomial time within a factor of O(p 1-) for any > 0 unless P = NP [START_REF] Gawrychowski | Strong inapproximability of the shortest reset word[END_REF]. Let a binary automaton

A = (Q, {0, 1}, δ) be the input of Shortest Sync Word. Let Q = {q 1 , . . . , q p }. Construct a binary automaton A = (Q , {0, 1}, δ ) with the set of states Q = {q ( j) i | 1 ≤ i ≤ p, 1 ≤ j ≤ p + 1}. Define δ (q ( j) i , x) = q ( j+1) k for 1 ≤ i ≤ p, 1 ≤ j ≤ p, x ∈ {0, 1}, where k is such that q k = δ(q i , x). Define δ (q (p+1) i , x) = q (p+1) i for 1 ≤ i ≤ p and x ∈ {0, 1}. Take S = {q (1) i | 1 ≤ i ≤ p}.
Observe that any word synchronizing S in A is a synchronizing word for A because of the definition of δ . In the other direction, we note that a shortest synchronizing word for a p-state automaton in the construction of Gawrychowski and Straszak [START_REF] Gawrychowski | Strong inapproximability of the shortest reset word[END_REF] has length at most p. Hence, a shortest synchronizing word for A also synchronizes S in A . Thus, the length of a shortest synchronizing word for A is equal to the length of a shortest word synchronizing S in A , and we get a gap-preserving reduction with gap O(p 1-) = O(n 1 2 -), as A has O(p 2 ) states. Finally, it is easy to see that A is binary weakly acyclic.

Finding a Synchronizable Set of Maximum Size

One possible approach to measure and reduce initial state uncertainty in an automaton is to find a subset of states of maximum size where the uncertainty can be resolved, i.e., to find a synchronizable set of maximum size. This is captured by the following problem.

Max Sync Set Input: An automaton A; Output: The maximum cardinality of a synchronizable set of states in A. Türker and Yenigün [START_REF] Türker | Complexities of some problems related to synchronizing, non-synchronizing and monotonic automata[END_REF] study a variation of this problem, which is to find a set of states of maximum size that can be mapped by some word to a subset of a given set of states in a given monotonic automaton. They reduce the N-Queens Puzzle problem [START_REF] Bell | A survey of known results and research areas for N-queens[END_REF] to this problem to prove its NP-hardness. However, their proof is unclear, since the input has size O(log N), and the output size is polynomial in N. Also, the N-Queens Puzzle problem is solvable in polynomial time [START_REF] Bell | A survey of known results and research areas for N-queens[END_REF].

First we investigate the PSPACE-completeness of the decision version of the Max Sync Set problem, which we will denote as Max Sync Set-D. Its formulation is the following: given an automaton A and a number c, decide whether there is a synchronizable set of states of cardinality at least c in A.

Proposition 3. The Max Sync Set-D problem is PSPACE-complete for binary automata.

Proof. The Sync Set problem is in PSPACE [START_REF] Sandberg | Homing and synchronizing sequences[END_REF]. Thus, the Max Sync Set-D problem is also in PSPACE, as we can sequentially check whether each subset of states is synchronizable and compare the size of a maximum synchronizable set to c.

To prove that the Max Sync Set-D problem is PSPACE-hard for binary automata, we will reduce a PSPACEcomplete Sync Set problem for binary automata [START_REF] Vorel | Subset synchronization and careful synchronization of binary finite automata[END_REF] to it. Let an automaton A and a subset S of its states be an input to Sync Set. Let n be the number of states of A. Construct a new automaton A by initially taking a copy of A. For each state s ∈ S , add n + 1 new states to A and define all the transitions from these new states to map to s, regardless of the input letter. Define the set S to be a union of all new states and take c = |S | = (n + 1)|S |.

Let S 1 be a maximum synchronizable set in A not containing at least one new state q. As S 1 is maximum, it does not contain other n new states that can be mapped to the same state as q. Thus, the size of S 1 is at most n + (n + 1)|S | -(n + 1) < (n + 1)|S | = c. Hence, each synchronizable set of size at least c in A contains S . The set S is synchronizable in A if and only if S is synchronizable in A , as each word w synchronizing S in A corresponds to a word xw synchronizing S in A , where x is an arbitrary letter. Thus, A has a synchronizable set of size at least c if and only if S is synchronizable in A. Now we proceed to inapproximability results for the Max Sync Set problem in several classes of automata. We will need some results from graph theory. An independent set I in a graph G is a set of its vertices such that no two vertices in I share an edge. The size of a maximum independent set in G is denoted α(G). The Independent Set problem is defined as follows.

Independent Set Input: A graph G; Output: An independent set of maximum size in G. Zuckerman [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF] has proved that, unless P = NP, there is no polynomial p1-ε -approximation algorithm for the Independent Set problem for any ε > 0, where p is the number of vertices in G.

Proposition 4. The problem Max Sync Set for weakly acyclic n-state automata over an alphabet of cardinality O(n) cannot be approximated in polynomial time within a factor of O(n 1-ε ) for any ε > 0 unless P = NP.

Proof. We will prove this theorem by constructing a gap-preserving reduction from the Independent Set problem. Given a graph G = (V, E), V = {v 1 , v 2 , . . . , v p }, we construct an automaton A = (Q, Σ, δ) as follows. For each v i ∈ V, we add two states s i , t i in Q. We also add a state f to Q. Thus, |Q| = 2p + 1. The alphabet Σ consists of letters ṽ1 , . . . , ṽp corresponding to the vertices of G.

The transition function δ is defined in the following way. For each 1 ≤ i ≤ p, the state s i is mapped to f by the letter ṽi . For each v i v j ∈ E the state s i is mapped to t i by the letter ṽ j , and the state s j is mapped to t j by the letter ṽi . All yet undefined transitions map a state to itself. Lemma 1. Let I be a maximum independent set in G. Then the set S = {s i | v i ∈ I} ∪ { f } is a synchronizable set of maximum cardinality (of size α(G) + 1) in the automaton A = (Q, Σ, δ).

Proof. Let w be a word obtained by concatenating the letters corresponding to I in arbitrary order. Then w synchronizes the set S = {s i | v i ∈ I} ∪ { f } of states of cardinality |I| + 1. Thus, A has a synchronizable set of size at least α(G) + 1.

In other direction, let w be a word synchronizing a set of states S of maximum size in A. We can assume that after reading w all the states in S are mapped to f , as all the sets of states that are mapped to any other state have cardinality at most two. Then there are no edges in G between any pair of vertices in I = {v i | s i ∈ S }, since each time some state s i is mapped to f , each state s j such that v j and v i share an edge in G, is mapped to t j . Hence I is an independent set of size |S | -1 in G. Thus the maximum size of a synchronizable set in A is equal to α(G) + 1.

Thus we have a gap-preserving reduction from the Independent Set problem to the Max Sync Set problem with a gap Θ(p 1-ε ) for any ε > 0. It is easy to see that n = Θ(p) and A is weakly acyclic, which concludes the proof of the theorem.

Next we move to a weaker inapproximability result for binary automata.

Proposition 5. The problem Max Sync Set for binary n-state automata cannot be approximated in polynomial time within a factor of O(n Proof. Again, we construct a gap-preserving reduction from the Independent Set problem extending the proof of Proposition 4. Given a graph G = (V, E), V = {v 1 , v 2 , . . . , v p }, we construct an automaton A = (Q, Σ, δ) in the following way. Let Σ = {0, 1}. First we construct the main gadget A main having a synchronizable set of states of size α(G). For each vertex v i ∈ V, 1 ≤ i ≤ p, we construct a set of new states

L i = V i ∪ U i in Q, where V i = {v (i) j : 1 ≤ j ≤ p}, U i = {u (i) j : 1 ≤ j ≤ p}.
We call L i the ith layer of A main . We also add a state f to Q. For each i, 1 ≤ i ≤ p, the transition function δ imitates taking the vertices v 1 , v 2 , . . . , v p into an independent set one by one and is defined as:

δ(v (i) j , 0) =        u (i) j if i = j, v (i+1) j otherwise δ(v (i) j , 1) =        u (i) j if there is an edge v i v j ∈ E, v (i+1) j otherwise
Here all v (n+1) j , 1 ≤ j ≤ p, coincide with f . For each state u (i) j , the transitions for both letters 0 and 1 lead to the originating state (i.e. they are self-loops).

We also add a p-state cycle A cycle attached to f . It is a set of p states c 1 , . . . , c p , mapping c i to c i+1 and c p to c 1 regardless of the input symbol. Finally, we set c 1 to coincide with f . Thus we get the automaton A 1 . Figure 2 presents an example of A 1 for a graph with three vertices v 1 , v 2 , v 3 and one edge v 2 v 3 . The main property of A 1 is claimed by the following lemma.

v (1) 1 v (2) 1 1 v (3) 1 0,1 f 0,1 u (1) 1 0 v (1) 2 v (2) 2 0,1 v (3) 2 1 0 u (2) 2 0 v (1) 3 v (2) 3 0,1 v (3)
Lemma 2. The size of a maximum synchronizable set of states from the first layer in A 1 equals α(G).

Proof. Let I be a maximum independent set in G. Consider a word w of length p such that its ith letter is equal to 0 if v i I and to 1 if v i ∈ I. By the construction of A 1 , this word synchronizes the set {v (1) j | v j ∈ I}. Conversely, a synchronizable set of at least three states from the first layer can be mapped only to some vertex of A cycle , and the corresponding set of vertices in G is an independent set, since application of each letter corresponds to taking or not taking a vertex into an independent set, and after taking some vertex all the states corresponding to the neighbors of this vertex are sent to separate sink states. Some layer in the described construction can contain a synchronizable subset of size larger than the maximum synchronizable subset of the first layer. To avoid that, we modify A 1 by repeating each state (with all transitions) of the first layer p times. More formally, we replace each pair of states v (1) j , u (1) j with p different pairs of states such that in each pair all the transitions repeat the transitions between v (1) j , u (1) j , and all the other states of the automaton. We denote the automaton thus constructed as A.

The following lemma claims that the described procedure of constructing A from G is a gap-preserving reduction from the Independent Set problem in graphs to the Max Sync Set problem in binary automata. Lemma 3. If α(G) > 1, then the maximum size of a synchronizable set in A is equal to pα(G) + 1.

Proof. Note that since the length of the cycle in A cycle equals p, each synchronizable set of A is either a subset of a single layer of A together with a state in A cycle (if this set is first mapped to f ) or a subset of a set {v (i) j | 2 ≤ i ≤ }∪{u ( ) j } for some and j, together with p new states that replaced v (1) j (if this set is mapped to u ( ) j ). Consider the first case. If some maximum synchronizable set S contains a state from the ith layer of A and i > 1, then its size is at most p + 1. A maximum synchronizable set containing some states from the first layer of A consists of pα(G) states from this layer (according to Lemma 2) and some state of A cycle , so this set has size pα(G) + 1 ≥ 2p + 1. In the second case, the maximum size of a synchronizable set is at most p + (p -1)

+ 1 = 2p < pα(G) + 1.
It is easy to see that the constructed reduction is gap-preserving with a gap Θ(p 1-ε ) = Θ(n 1 2 -ε ), where n is the number of states in A, as n = Θ(p 2 ). Thus the Max Sync Set for n-state binary automata cannot be approximated in polynomial time within a factor of O(n 1 2 -ε ) for any ε > 0 unless P = NP, which concludes the proof of the theorem.

Proposition 5 can also be proved by using Proposition 4 and a slight modification of the technique used in [START_REF] Vorel | Subset synchronization and careful synchronization of binary finite automata[END_REF] for decreasing the size of the alphabet. However, in this case the resulting automaton is far from being weakly acyclic, while the automaton in the proof of Proposition 4 has only one cycle. The next theorem shows how to modify our technique to prove an inapproximability bound for Max Sync Set in binary weakly acyclic automata.

Theorem 2. The Max Sync Set problem for binary weakly acyclic n-state automata cannot be approximated in polynomial time within a factor of O(n 1 3 -ε ) for any ε > 0 unless P = NP.

Proof. We modify the construction of the automaton A main from Proposition 5 in the following way. We repeat each state (with all transitions) of the first layer p 2 times in the same way as it is done in the proof of Proposition 5. Thus we get a weakly acyclic automaton A wa with n = Θ(p 3 ) states, where p is the number of vertices in the graph G. Furthermore, similar to Lemma 3, the size of the maximum synchronizable set of states in A wa is between p 2 α(G) and p 2 α(G) + p(p -1) + 1, because some of the states from the layers other than the first can be also mapped to f . Both of the values are of order Θ(p 2 α(G)), thus we have an gap-preserving reduction providing the inapproximability within a factor of O(p 1-ε ) = O(n 1 3 -ε ) for any ε > 0, where n is the number of states in A wa .

We finish by noting that for two classes of automata the Max Sync Set problem is solvable in polynomial time. Proposition 6. The problem Max Sync Set can be solved in polynomial time for unary automata.

Proof. Consider the digraph G induced by states and transitions of an unary automaton A. By definition, each vertex of G has outdegree 1. Thus, the set of the vertices of G can be partitioned into directed cycles and a set of vertices not belonging to any cycle, but lying on a directed path leading to some cycle. Let n be the number of states in A. It is easy to see that after performing n transitions, each state of A is mapped into a state in some cycle, and all further transitions will not map any two different states to the same state. Thus, it is enough to perform n transitions and select such state s that the maximum number of states are mapped to s.

A more interesting case is covered by the following proposition. An automaton A = (Q, Σ, δ) is called Eulerian if there exists k such that for each state q ∈ Q there are exactly k pairs (q , a), q ∈ Q, a ∈ Σ, such that δ(q , a) = q. Proposition 7. The problem Max Sync Set can be solved in polynomial time for Eulerian automata.

Proof. According to Theorem 2.1 in [START_REF] Friedman | On the road coloring problem[END_REF] (see also [START_REF] Kari | Synchronizing finite automata on eulerian digraphs[END_REF] for the discussion of the Eulerian case), each word of minimum rank with respect to an Eulerian automaton synchronizes the sets S 1 , S 2 , . . . , S r forming a partition of the states of the automaton into inclusion-maximal synchronizable sets. Moreover, according to this theorem all inclusion-maximal synchronizable sets in an Eulerian automaton are of the same size, thus each inclusion-maximal synchronizable set has maximum cardinality. A word of minimum rank with respect to an automaton can be found in polynomial time [START_REF] Rystsov | Rank of a finite automaton[END_REF], which concludes the proof.

Computing the Rank of a Subset of States

Assume that we know that the current state of the automaton A belongs to a subset S of its states. Even if it is not possible to synchronize S , it can be reasonable to minimize the size of the set of possible states of A, reducing the uncertainty of the current state as much as possible. One way to do it is to map S to a set S of smaller size by applying some word to A. Recall that the size of the smallest such set S is called the rank of S . Consider the following problem of finding the rank of a subset of states in a given automaton.

Set Rank Input: An automaton A and a set S of its states; Output: The rank of S in A. The rank of an automaton, that is, the rank of the set of its states, can be computed in polynomial time [START_REF] Rystsov | Rank of a finite automaton[END_REF]. However, since the automaton in the proof of PSPACE-completeness of Sync Set in [START_REF] Rystsov | Polynomial complete problems in automata theory[END_REF] has rank 2 (and thus each subset of states in this automaton has rank either 1 or 2), it follows immediately that there is no polynomial capproximation algorithm for the Set Rank problem for any c < 2 unless P = PSPACE. It also follows that checking whether the rank of a subset of states equals the rank of the whole automaton is PSPACE-complete. For monotonic weakly acyclic automata, this problem is hard to approximate within a factor of 9 8 -for any > 0 [START_REF] Ryzhikov | Subset synchronization in monotonic automata[END_REF]. For general weakly acyclic automata it is possible to get much stronger bounds, as it is shown by the results of this section.

We will need the Chromatic Number problem. A proper coloring of a graph G = (V, E) is a coloring of the set V in such a way that no two adjacent vertices have the same color. The chromatic number of G, denoted χ(G), is the minimum number of colors in a proper coloring of G. Recall that a set of vertices in a graph is called independent if no two vertices in this set are adjacent. A proper coloring of a graph can be also considered as a partition of the set of its vertices into independent sets.

Chromatic Number

Input: A graph G; Output: The chromatic number of G. This problem cannot be approximated within a factor of O(p 1-) for any > 0 unless P = NP, where p is the number of vertices in G [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF]. Proof. We will prove this theorem by constructing a gap-preserving reduction from the Chromatic Number problem, extending the technique in the proof of Proposition 4. Given a graph G = (V, E), V = {v 1 , v 2 , . . . , v p }, we construct an automaton A = (Q, Σ, δ) as follows. The alphabet Σ consists of letters ṽ1 , . . . , ṽp corresponding to the vertices of G, together with a switching letter ν. We use p identical synchronizing gadgets T (k) , 1 ≤ k ≤ p, such that each gadget synchronizes a subset of states corresponding to an independent set in G. Gadget T (k) consists of a set {s (k) i ,

t (k) i | 1 ≤ i ≤ p} ∪ { f (k) } of states.
The transition function δ is defined as follows. For each gadget T (k) , for each 1 ≤ i ≤ p, the state s (k) i is mapped to f (k) by the letter ṽi . For each v i v j ∈ E the state s (k) i is mapped to t (k) i by the letter ṽ j , and the state s (k) j is mapped to t (k) j by the letter ṽi . All yet undefined transitions corresponding to the letters ṽ1 , . . . , ṽp map a state to itself. It remains to define the transitions corresponding to ν. For each 1 ≤ k ≤ p -1, ν maps t (k) i and s (k) i to s (k+1) i , and f (k) to itself. Finally, ν acts on all states in T (p) as a self-loop.

Define S = {s (1) i | 1 ≤ i ≤ p}. We will prove that the rank of S is equal to the chromatic number of G. Consider a proper coloring of G with the minimum number of colors and let I 1 ∪ . . . ∪ I χ(G) be the partition of G into independent sets defined by this coloring. For each I j , consider a word w j obtained by concatenating the letters corresponding to the vertices in I j in some order. Consider now the word w 1 νw 2 ν . . . νw χ(G) . This word maps the set S to the set { f (i) | 1 ≤ i ≤ χ(G)}, which proves that the rank of S is at most χ(G).

In the other direction, note that after each reading of ν all states except f (k) , 1 ≤ k ≤ p -1, are mapped to the next synchronizing gadget (except the last gadget T (p) which is mapped to itself). Note that each time a state s (k) i is mapped to f (k) , each state s (k) j such that v j and v i share an edge in G, is mapped to t (k) j . Thus, only a subset of states corresponding to an independent set of vertices can be mapped to some particular f (k) , and the image of S after reading any word is a subset of the states in some gadget together with some of the states f (k) , 1 ≤ k ≤ p. Hence, the rank of S is at least χ(G).

Thus we have a gap-preserving reduction from the Chromatic Number problem to the Set Rank problem with gap Θ(p 1-ε ) for any ε > 0. It is easy to see that n = Θ(p 2 ), A is weakly acyclic and its alphabet has size O( √ n), which finishes the proof of the theorem.

Using the classical technique of reducing the alphabet size (see [START_REF] Vorel | Subset synchronization and careful synchronization of binary finite automata[END_REF]), O(n 1 3 -) inapproximability can be proved for binary automata. To prove the same bound for binary weakly acyclic automata, we have to refine the technique of the proof of the previous theorem.

Theorem 3. The Set Rank problem for n-state binary weakly acyclic automata cannot be approximated within a factor of O(n Proof. To prove this theorem we construct a gap-preserving reduction from the Chromatic Number problem, extending the proof of the previous theorem.

Given a graph G = (V, E), V = {v 1 , v 2 , . . . , v p }, we construct an automaton A = (Q, {0, 1}, δ). In our reduction we use two kinds of gadgets: p synchronizing gadgets T (k) , 1 ≤ k ≤ p, and p waiting gadgets R (k) , 1 ≤ k ≤ p. Gadget T (k) consists of a set {v (k) i, j | 1 ≤ i, j ≤ p} of states, together with a state f (k) , and

R (k) , 1 ≤ k ≤ p, consists of the set {u (k) i, j | 1 ≤ i, j ≤ p}.
For each i, j, k, 1 ≤ i, j, k ≤ p, the transition function δ is defined as:

δ(v (k) i, j , 0) =        u (k) i, j if i = j, v (k) i+1, j otherwise δ(v (k) i, j , 1) =        u (k) i, j if there is an edge v i v j ∈ E, v (k) i+1, j otherwise Here all v (k) p+1, j , 1 ≤ j ≤ p, coincide with f (k) . We set δ(u (k) i, j , x) = u (k) i+1, j for x ∈ {0, 1}, 1 ≤ i, k ≤ p -1, 1 ≤ j ≤ p, and δ(u (k) p, j , x) = v (k+1) 1, j for 1 ≤ j ≤ p, 1 ≤ k ≤ p -1, x ∈ {0, 1}.
The states u (p) i, j are sink states: both letters 0 and 1 act on them as self-loops. Finally, we set S = {v (1) 1, j | 1 ≤ j ≤ p}. Figure 3 gives an idea of the described construction. The idea of the presented construction is essentially a combination of the ideas in the proofs of Proposition 5 and Proposition 8, so we provide only a sketch of the proof. A synchronizing gadget T (k) synchronizes a set S (k) ⊆ S of states corresponding to some independent set in G. All the states corresponding to the vertices adjacent to vertices corresponding to S (k) are mapped to the corresponding waiting gadget R (k) , and get to the next synchronizing gadget T (k+1) only after the states of S (k) are synchronized (and thus mapped to f (k) ). Hence, the minimum size of a partition of V into independent sets is equal to the rank of S . The number of states in A is O(p 3 ). Thus, we get Θ(n 1 3 -) inapproximability.

Subset Synchronization

In this section, we obtain complexity results for several problems related to subset synchronization in weakly acyclic automata. We adapt Eppstein's construction from [START_REF] Eppstein | Reset sequences for monotonic automata[END_REF], which is a powerful and flexible tool for such proofs. We will need the following NP-complete SAT problem [START_REF] Sipser | Introduction to the Theory of Computation[END_REF].

The complexity of the following problem can be obtained from Proposition 10.

Positive Matrix Input: A set M 1 , . . . , M k of n × n binary matrices; Output: Yes if there exists a sequence M i 1 × . . . × M i k of multiplications (possibly with repetitions) providing a matrix with all elements equal to 1, No otherwise.

Corollary 1. Positive Matrix is NP-hard for two upper-triangular and two lower-triangular matrices.

Proof. The proof uses the idea from [START_REF] Gerencsér | Primitive sets of nonnegative matrices and synchronizing automata[END_REF]. Consider three transition matrices corresponding to the letters of the automaton constructed in the proof of Proposition 10. Add the matrix corresponding to the letter mapping the state f to all states and undefined for all other states. Any sequence of matrices resulting in a matrix with only positive elements must contain the new matrix, and before that there must be a sequence of matrices corresponding to a word carefully synchronizing the automaton from the proof of Proposition 10. Thus we get a reduction from Careful Synchronization for aperiodic partial automata over a three-letter alphabet to Positive Matrix. It is easy to see that the reduction uses two upper-triangular and two lower-triangular matrices.

Finally, we show the hardness of the following problem (PSPACE-complete in general [START_REF] Bondar | Completely reachable automata[END_REF]). Subset Reachability Input: An automaton A = (Q, Σ, δ) and a subset S of its states; Output: Yes if there exists a word w such that {δ(q, w) | q ∈ Q} = S , No otherwise.

Theorem 5. Subset Reachability is NP-complete for weakly acyclic automata.

Proof. Consider a topological sort of Q. Let w be a shortest word mapping Q to some reachable set of states. Then each letter of w maps at least one state to a state with a larger index in the topological sort. Thus w has length O(|Q| 2 ), since the maximum total number of such mappings is (|Q| -1) + (|Q| -2) + . . . + 1 + 0. Thus, the considered problem is in NP.

For the NP-hardness proof, we again reduce the SAT problem. Given an instance of SAT, construct A base first. Next, add a transition δ(y ( j) n+1 , a) = f for 1 ≤ j ≤ m, a ∈ {0, 1}, resulting in a deterministic automaton A. Similar to the proof of Proposition 10, C is satisfiable if and only if the set S = {z (n+1) j | 1 ≤ j ≤ m}∪{ f } is reachable in A. Indeed, consider the word w = a 1 a 2 . . . a n where a i is the value of x i in an assignment satisfying C. Then the image of Q under the mapping defined by w equals S . On the other hand, any word w with {δ(q, w) | q ∈ Q} = S has length exactly n, since the application of each new letter increases by one the minimal index i such that a state y ( j) i or z ( j) i is reached. Let w = a 1 a 2 . . . a n . If the assignment x i = a i does not satisfy a clause c j , then {δ(q, w) | q ∈ Q} contains y ( j) n+1 , and thus cannot be equal to S .

Conclusions and Open Problems

As shown in this paper, weakly acyclic automata serve as an example of a small class of automata where most of the synchronization problems are still hard. More precisely, switching from general automata to weakly acyclic usually results in changing a PSPACE-complete problem to a NP-complete one.

Some problems for weakly acyclic automata are still open. One of them is to study the approximability of the Shortest Sync Word problem: there is a drastic gap between known inapproximability results and the O(n)approximation algorithm for general automata. Another natural problem is to study the Max Sync Set and Set Rank problems complexity in strongly connected automata. The technique used by Vorel for proving PSPACE-completeness of the Sync Set problem in strongly connected automata [START_REF] Vorel | Subset synchronization and careful synchronization of binary finite automata[END_REF] seems to fail here.

Figure 1 .

 1 Figure 1. The automaton providing the lower bound for subset synchronization

1 2 -

 2 ) for any > 0 unless P = NP.

1 Figure 2 .

 12 Figure 2. An example of A 1 . Unachievable states and self-loops are omitted.

Proposition 8 . 2 -

 82 The Set Rank problem for n-state weakly acyclic automata with alphabet of size O( √ n) cannot be approximated within a factor of O(n 1 ) for any > 0 unless P = NP.

1 3 -

 3 ) for any > 0 unless P = NP.

-ε ) for any ε > 0 unless P = NP.

Acknowledgments

I would like to thank Peter J. Cameron for introducing me to the notion of synchronizing automata, and Vojtěch Vorel, Yury Kartynnik, Vladimir Gusev and Ilia Fridman for very useful discussions. I also thank Mikhail V. Volkov and anonymous reviewers for their great contribution to the improvement of the paper.

1,1 u (1) 2,1 u (1) 3,1 u (1) 1,2 u (1) 2,2 u (1) 3,2 u (1) 1,3 u (1) 2,3 u (1) 3,3 v (1) 1,1 v (1) 2,1 v (1) 3,1 f (1) v (1) 1,2 Proof. Because of the polynomial upper bound on the length of a shortest word synchronizing a subset of states proved in Proposition 2, we can use such word as a certificate. Thus, the problem is in NP.

We reduce the SAT problem. Given X and C, we construct an automaton A = (Q, {0, 1}, δ). For each clause c j , we add n + 1 states y ( j) i , 1 ≤ i ≤ n + 1, to Q. We introduce also a state f ∈ Q. The transitions from y ( j) i correspond to the occurrence of x i in c j in the following way: for 1 ≤ i ≤ n, 1 ≤ j ≤ m, δ(y ( j) i , a) = f if the assignment x i = a, a ∈ {0, 1}, satisfies c j , and δ(y ( j) i , a) = y ( j) i+1 otherwise. The transition function δ also maps y ( j) n+1 to itself for all 1 ≤ j ≤ m and both letters 0 and 1.

Let S = {y ( j) 1 | 1 ≤ j ≤ m}. The word w = a 1 a 2 . . . a n synchronizes S if a i is the value of x i in an assignment satisfying C, and vice versa. Thus, the set is synchronizable if and only if all clauses in C can be satisfied by some assignment of binary values to the variables in X.

By identifying the states y ( j) n+1 for 1 ≤ j ≤ m and adding f to S it is also possible to prove that the problem of checking whether the rank of a subset of states equals the rank of an automaton is coNP-complete for binary weakly acyclic automata (cf. the remarks in the beginning of Section 4).

The proof of Theorem 4 can be used to prove the hardness of a special case of the following problem, which is PSPACE-complete in general [START_REF] Kozen | Lower bounds for natural proof systems[END_REF] and NP-complete for weakly acyclic monotonic automata over a three-letter alphabet [START_REF] Ryzhikov | Subset synchronization in monotonic automata[END_REF].

Finite Automata Intersection

Input: Automata A 1 , . . . , A k (with initial and accepting states); Output: Yes if there is a word which is accepted by all automata, No otherwise. Proposition 9. Finite Automata Intersection is NP-complete when all automata in the input are binary weakly acyclic.

Proof. Observe first that if there exists a word which is accepted by all automata, then a shortest such word w has length at most linear in the total number of states in all automata. Indeed, for each automaton consider a topological sort of the set of its states. Each letter of w maps at least one state in some automaton to some other state, which has larger index in the topological sort of the set of states of this automaton. Thus, the considered problem is in NP.

For the hardness proof, we use the same construction as in Theorem 4. Provided X and C, define A in the same way as in Theorem 4. Define A j = (Q j , {0, 1}, δ j ) as follows. Take Q j = {y ( j) i , 1 ≤ i ≤ n + 1} ∪ { f } and δ j to be the restriction of δ to the set Q j . Set y ( j)

1 to be the input state and f to be the only accepting state of A j . Then there exists a word accepted by automata A 1 , . . . , A m if and only if all clauses in C are satisfiable by some assignment.

To obtain the next results, we will need a modified construction of the automaton from the proof of Theorem 4, as well as some new definitions. A partial automaton is a triple (Q, Σ, δ), where Q and Σ are the same as in the definition of a finite deterministic automaton, and δ is a partial transition function (i.e., a transition function which may be undefined for some argument values). Given an instance of the SAT problem, construct a partial automaton A base = (Q, {0, 1}, δ) as follows. We introduce a state f ∈ Q. For each clause c j , we add n + 1 states y ( j) i , 1 ≤ i ≤ n + 1, to Q. For each c j , add also states z ( j) i for h i + 1 ≤ i ≤ n + 1, where h i is the smallest index of a variable occurring in c j . The transitions from y ( j) i correspond to the occurrence of x i in c j in the following way: for 1

if the assignment x i = a, a ∈ {0, 1}, satisfies c j , and δ(y ( j) i , a) = y ( j) i+1 otherwise. For a ∈ {0, 1}, we set δ(z

The transition function δ also maps z ( j) n+1 , 1 ≤ j ≤ m, and f to f for both letters 0 and 1. A word w is said to carefully synchronize a partial automaton A if it maps all its states to the same state q, and each mapping corresponding to a prefix of w is defined for each state. The automaton A is then called carefully synchronizing. We use A base to prove the hardness of the following problem.

Careful Synchronization Input: A partial automaton A; Output: Yes if A is carefully synchronizing, No otherwise. For binary automata, Careful Synchronization is PSPACE-complete [START_REF] Martyugin | Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA[END_REF]. For monotonic automata over a fourletter alphabet it is NP-hard. We call a partial automaton aperiodic if for any word w ∈ Σ * and any state q ∈ Q there exists k such that either δ(q, w k ) is undefined, or δ(q, w k ) = δ(q, w k+1 ). Proposition 10. Careful Synchronization is NP-hard for aperiodic partial automata over a three-letter alphabet.

Proof. We reduce the SAT problem. Given X and C, we first construct A base . Then we add an additional letter r to the alphabet of A base and introduce m new states s ( j) , 1 ≤ j ≤ m. For 1 ≤ i ≤ n, 1 ≤ j ≤ m, we define δ(s ( j) , r) = y ( j) 1 , δ(y ( j) i , r) = y ( j) 1 , δ(z ( j) i , r) = y ( j) 1 , δ( f, r) = f . All other transitions are left undefined. Let us call the constructed automaton A.

The automaton A is carefully synchronizing if and only if all clauses in C can be satisfied by some assignment of binary values to the variables in X. Moreover, the word w = rw 1 w 2 . . . w n 0, is carefully synchronizing if w i is the value of x i in such an assignment.

Indeed, note that the first letter of w is necessarily r, as it is the only letter defined for all the states. Moreover, each word starting with r maps Q to a subset of {y ( j) i , z ( j) i | 1 ≤ j ≤ m + 1} ∪ { f }. The only way for a word to map all states to f is to map them first to the set {z ( j) n+1 | 1 ≤ j ≤ m} ∪ { f }, because there are no transitions defined from any y ( j) n+1 , except the transitions defined by r. If only the states of the set {z ( j) n+1 | 1 ≤ j ≤ m} ∪ { f } are reached by a word ra 1 . . . a n , then for every clause in C there exists a variable x i such that taking x i = a i satisfies this clause. Thus there exists an assignment satisfying C.

The constructed automaton is aperiodic, because each cycle which is not a self-loop contains exactly one letter r.