J Agrisuelas

C Delgado

C Gabrielli

J J García-Jareño

H Perrot

O Sel

F Vicente

The role of NH 4 + cations on the electrochemistry of Prussian Blue studied by electrochemical, mass and color impedance spectroscopy

Keywords: Prussian Blue, ammonium cation, electrochemical impedance spectroscopy, mass impedance spectroscopy, color impedance spectroscopy

The role of the ammonium cation on the reversible electrochemistry of Prussian Blue thin films was analyzed through in situ combination of three different impedance techniques.

Electrochemical impedance spectroscopy provides information on the electron transfer. Mass impedance spectroscopy allows the exchange of free water, ammonium and proton ions to be elucidated. Color impedance spectroscopy provides the kinetics of electrochromic changes of Prussian Blue structure (main backbone structure, ferrocyanide vacancies and trapped structures). The simultaneous measurement of the three impedances gives detailed information on the mechanism of the whole process, specifically one faster and two slower, which have been identified during the electrochemical reactions of Prussian Blue films in NH 4 Cl acidic solutions.

Introduction

Prussian Blue (PB, ferric ferrocyanide) is a well-known inorganic electrochromic compound which can easily be electrodeposited on various types of electrode substrates [START_REF] Neff | Electrochemical Oxidation and Reduction of Thin Films of Prussian Blue[END_REF][START_REF] Itaya | Spectroelectrochemistry and electrochemical preparation method of Prussian blue modified electrodes[END_REF].

The good stability of PB films and other metal ferrocyanide analogs makes these materials the subject of many electrochemical studies and many interesting technological applications going from sensors to batteries [START_REF] Karyakin | Prussian Blue and its analogues: Electrochemistry and analytical applications[END_REF][START_REF] Neff | Some Performance-Characteristics of a Prussian Blue Battery[END_REF].

In particular, PB films freshly electrodeposited from equimolar solutions of K 3 Fe(CN) [START_REF] Mortimer | Electrochemical Polychromicity in Iron Hexacyanoferrate Films, and a New Film Form of Ferric Ferricyanide[END_REF] and FeCl 3 correspond to the mixed valence form of Fe III /Fe II [START_REF] Mortimer | Iron Hexacyanoferrate Films -Spectroelectrochemical Distinction and Electrodeposition Sequence of Soluble (K+-Containing) and Insoluble (K+-Free) Prussian Blue, and Composition Changes in Polyelectrochromic Switching[END_REF][START_REF] Mortimer | Electrochemical Polychromicity in Iron Hexacyanoferrate Films, and a New Film Form of Ferric Ferricyanide[END_REF]. The oxidation state of PB can finely be controlled by an external source of potential. The films can be reduced to the colorless Everitt's salt form (ES, Fe II /Fe II ) or oxidized to the Prussian Yellow form (PY, Fe III /Fe III ). These electrochemical reactions involve the exchange of counterions to keep the electroneutrality of the films during the charge balance processes [START_REF] Feldman | Ion Flux During Electrochemical Charging of Prussian Blue Films[END_REF][START_REF] Garcia-Jareño | The role of potassium and hydrogen ions in the Prussian Blue reversible arrow Everitt's salt process[END_REF]. Predominantly, electrogravimetric studies have proved that this balance takes place by cation exchanges [START_REF] Gabrielli | Ac-Electrogravimetry Study of Electroactive Thin Films. I. Application to Prussian Blue[END_REF][START_REF] Agrisuelas | Usefulness of F(dm/dQ) function for elucidating the ions role in PB films[END_REF].

Initially, the structure of freshly prepared PB films has been described as a K + free structure and therefore, a direct PB oxidation to form PY films results in the structure breakdown of the films [START_REF] Herren | Neutron-Diffraction Study of Prussian Blue[END_REF]. However, if freshly prepared PB films were previously cycled around the PB⇄ ES system by cyclic voltammetry, K + cations occupy key position in the inner structure of PB and then, the oxidation to the PY form can take place without destruction of the films [START_REF] Mortimer | Iron Hexacyanoferrate Films -Spectroelectrochemical Distinction and Electrodeposition Sequence of Soluble (K+-Containing) and Insoluble (K+-Free) Prussian Blue, and Composition Changes in Polyelectrochromic Switching[END_REF][START_REF] Feldman | Ion Flux During Electrochemical Charging of Prussian Blue Films[END_REF][START_REF] Roig | Stability of Prussian Blue Films on Ito Electrodes -Effect of Different Anions[END_REF][START_REF] Bueno | Synchrotron structural characterization of electrochemically synthesized hexacyanoferrates containing K(+): A revisited analysis of electrochemical redox[END_REF][START_REF] Agrisuelas | Identification of electroactive sites in Prussian Yellow films[END_REF]. Once PB films are stabilized in acid KCl solutions by cyclic voltammetry, the voltammetric peaks of the PB⇄ ES system appear to be stable after hundred and even thousands of cycles [START_REF] Roig | Voltammetric Study on the Stability of Deposited Prussian Blue Films Against Successive Potential Cycling[END_REF]. In recent papers [START_REF] Bueno | Synchrotron structural characterization of electrochemically synthesized hexacyanoferrates containing K(+): A revisited analysis of electrochemical redox[END_REF][START_REF] Agrisuelas | Identification of electroactive sites in Prussian Yellow films[END_REF], the stable PB structure has been described as Fe 4 3+ [Fe 2+ (CN) 6 ] 3 •[(K + ) 2 •(OH -) 2 •(mH 2 O)] 3 . The PB⇄ ES system has been studied by mass impedance spectroscopy and the role of potassium cations has been elucidated [START_REF] Gabrielli | Ac-Electrogravimetry Study of Electroactive Thin Films. I. Application to Prussian Blue[END_REF][START_REF] Agrisuelas | Innovative Combination of Three Alternating Current Relaxation Techniques: Electrical Charge, Mass, and Color Impedance Spectroscopy. Part II: Prussian Blue reversible arrow Everitt's Salt Process[END_REF][START_REF] Agrisuelas | Identification of Processes Associated with Different Iron Sites in the Prussian Blue Structure by in Situ Electrochemical, Gravimetric, and Spectroscopic Techniques in the dc and ac Regimes[END_REF]:

On the contrary, the PB⇄ PY system is not perfectly described and the participation of counterions is more complicated. The structure change can hinder the exchange of cations during this redox process. Previously, this process was described with the exclusive participation of anions as counterions [START_REF] Itaya | Spectroelectrochemistry and electrochemical preparation method of Prussian blue modified electrodes[END_REF]. However, electrogravimetric results showed a decrease of mass during the oxidation of PB to the PY form, and an increase of the mass during the reverse reaction (PY→PB) indicating the participation of cations [START_REF] Agrisuelas | Usefulness of F(dm/dQ) function for elucidating the ions role in PB films[END_REF]. According to the

Fe 4 3+ [Fe 2+ (CN) 6 ] 3 •[(K + ) 2 •(OH -) 2 •(mH 2 O)] 3 + 4K + +4e - ⇄ K 4 Fe 4 2+ [Fe 2+ (CN) 6 ] 3 •[(K + ) 2 •(OH -) 2 •(mH 2 O)] 3 (1)
structure proposed here, there are only two K + cations for three Fe 2+ sites. This means that there are not enough cations within the PB film to be expelled during the balance of the electric charge associated to the oxidation of the three iron atoms per unit cell. Thus, the participation of another cation (hydronium) or anion is necessary during the PB→PY process. As a consequence, PB⇄ PY system shows a low electrochemical response. Recently, a possible reaction scheme for the PB⇄ PY system has been proposed involving both cations and anions [START_REF] Agrisuelas | Identification of electroactive sites in Prussian Yellow films[END_REF]:

After a voltammetric stabilization in KCl acid solution, the counter ions, which participate during the electrochemical reactions of the PB films, can be exchanged using different bathing solutions [START_REF] Feldman | Ion Flux During Electrochemical Charging of Prussian Blue Films[END_REF][START_REF] Navarro-Laboulais | The correlation between electrochemical impedance spectra and voltammograms of PB films in aqueous NH4Cl and CsCl[END_REF][START_REF] Sanmatias | The role of inner counterions within PB films during electrochemical processes[END_REF]. In the case of NH 4 + cations, voltammograms show two well-defined voltammetric peaks, but the anodic peak appears wider and smaller than that observed in the case of K + transfer. Another interesting difference is observed during the oxidation process (PB⇄PY), where the voltammetric peaks appear much smaller than theses ones observed in the presence of K + cations [START_REF] Navarro-Laboulais | The correlation between electrochemical impedance spectra and voltammograms of PB films in aqueous NH4Cl and CsCl[END_REF][START_REF] Sanmatias | The role of inner counterions within PB films during electrochemical processes[END_REF]. Thus, NH 4 + should play an important role during these electrochemical processes.

The aim of this paper is to elucidate the role of NH 4 + during the electrochemical processes of PB films in a 0.5 M NH 4 Cl acid solution. For that, the PB⇄ES system was investigated by impedance spectroscopy. Today, the impedance spectroscopy can be used to study any analogic signals susceptible to be sinusoidally modulated and properly analyzed by a frequency response analyzer. Through a perusal of the literature, one can find studies of the conducting films by color impedance spectroscopy or CIS [START_REF] Amemiya | Investigation of Dynamics of Faradaic Processes in Polypyrrole Films by Electrochemical Impedance and Color Admittance Spectroscopies[END_REF][START_REF] Amemiya | Dynamics of Faradaic Processes in Polypyrrole Polystyrenesulfonate Composite Films in the Presence and Absence of a Redox Species in Aqueous-Solutions[END_REF][START_REF] Avellaneda | Synthesis and electrochromic behavior of lithium-doped WO3 films[END_REF][START_REF] Garcia-Belmonte | Relaxation processes in the coloration of amorphous WO3 thin films studied by combined impedance and electro-optical measurements[END_REF][START_REF] Kim | Color impedance and electrochemical impedance studies of WO3 thin films: Behavior of thinner films in non-aqueous electrolyte[END_REF][START_REF] Kim | Color impedance and electrochemical impedance studies of WO3 thin films: H+ and Li+ transport[END_REF], mass impedance spectroscopy or MIS (the ac-electrogravimetry) [START_REF] Gabrielli | Ac-Electrogravimetry Study of Electroactive Thin Films. I. Application to Prussian Blue[END_REF][START_REF] Gabrielli | ac Electrogravimetry on conducting polymers. Application to polyaniline[END_REF][START_REF] Gabrielli | Separation of ionic and solvent transport during charge compensation processes in electroactive polymers by a.c. electrogravimetry[END_REF][START_REF] Gabrielli | Ions and solvent transport across conducting polymers investigated by ac electrogravimetry. Application to polyaniline[END_REF][START_REF] Yang | Mass transport investigated with the electrochemical and electrogravimetric impedance techniques .2. Anion and water transport in PMPy and PPy films[END_REF][START_REF] García-Jareño | EIS and Ac-Electrogravimetry Study of PB Films in KCl, NaCl, and CsCl Aqueous Solutions[END_REF] or both of them together with electrochemical impedance spectroscopy (EIS) [START_REF] Agrisuelas | Innovative Combination of Three Alternating Current Relaxation Techniques: Electrical Charge, Mass, and Color Impedance Spectroscopy. Part II: Prussian Blue reversible arrow Everitt's Salt Process[END_REF][START_REF] Agrisuelas | Identification of Processes Associated with Different Iron Sites in the Prussian Blue Structure by in Situ Electrochemical, Gravimetric, and Spectroscopic Techniques in the dc and ac Regimes[END_REF][START_REF] Gabrielli | Lithium Insertion in Wo3 Studied by Simultaneous Measurements of Impedance, Electrogravimetric and Electrooptical Transfer-Functions[END_REF][START_REF] Agrisuelas | Innovative Combination of Three Alternating Current Relaxation Techniques: Electrical Charge, Mass, and Color Impedance Spectroscopy. Part I: The Tool[END_REF]. The coupling of various impedance data has proved to be of special interest for studying the electrochemical response of conducting films. The electron transfer, counterions exchange and color changes which take place during the electrochemical reaction of conducting films can be deconvoluted from the global response by their time constant to obtain kinetic information [START_REF] Gabrielli | Ac-Electrogravimetry Study of Electroactive Thin Films. I. Application to Prussian Blue[END_REF][START_REF] Gabrielli | Ac-Electrogravimetry Study of Electroactive Thin Films. II. Application to Polypyrrole[END_REF][START_REF] Agrisuelas | Ionic and Free Solvent Motion in Poly(azure A) Studied by ac-Electrogravimetry[END_REF]. Here, the in situ combination of electrochemical impedance spectroscopy (EIS), mass impedance spectroscopy (MIS) and color impedance spectroscopy (CIS) was used to study PB films at two characteristic wavelengths (690 nm and 900 nm).

Fe 4 3+ [Fe 2+ (CN) 6 ] 3 •[(K + ) 2 •(OH -) 2 •(mH 2 O)] 3 +A - ⇄ Fe 4 3+ [Fe 3+ (CN) 6 ] 3 •[A -•(OH -) 2 •(mH 2 O)] 3 +2K + (2)

Experimental

Following the procedure described by Itaya et al. [ The experimental set-up and equipment required to simultaneously obtain the three impedance data have been described extensively in a previous work [START_REF] Agrisuelas | Innovative Combination of Three Alternating Current Relaxation Techniques: Electrical Charge, Mass, and Color Impedance Spectroscopy. Part I: The Tool[END_REF]. A PAR 263A galvanostat-potentiostat (Float and 98 options installed) together with a four-channel frequency response analyzer Solartron 1254 were used. A quartz crystal microbalance built at UMR 8235, CNRS (Paris, France), and a modified Vis-NIR spectrometer Spectronic 20+ with a silicon PIN photodiode OSD 100-6 (Centronic) were used to measure the mass impedance as Δ𝑚/Δ𝐸(ω) transfer function and the color impedance as Δ𝐴 𝜆 /Δ𝐸(ω) transfer function, respectively. The impedance data are recorded in the frequency range from 10 kHz to 0.01 Hz, with 5 points per decade. The amplitude of the potential perturbation was 25 mV rms.

The fitting of experimental data to the theoretical models was made by means of a Levenberg-Marquardt optimization routine implemented in Mathcad ® software, version 14 (PTC).

Results and discussion

Figure 1 shows a representative voltammetric cycle of PB film in a 0.5 M NH 4 Cl acid solution. In the case of NH 4 + cations, voltammograms show two well-defined voltammetric peaks, but the anodic peak is relatively wide and small. In Figure 1, the anodic peak intensity and the width of the anodic peak at half height are around 0.35 mA cm 2 and 275 mV, respectively. On the contrary, the cathodic peak shows values around 0.5 mA cm 2 and 180 mV. The electrochemical reduction of PB to the ES under these experimental conditions can be described by the following simplified reaction scheme:

Previous spectroelectrochemical studies of PB films in KCl solutions have shown that changes of absorbance at wavelengths close to 690 nm could be associated to an electronic transfer between low spin Fe II (Fe ls II ) and high spin iron sites (Fe hs III ) in the Fe ls II -CN-Fe hs III structure [START_REF] Agrisuelas | Innovative Combination of Three Alternating Current Relaxation Techniques: Electrical Charge, Mass, and Color Impedance Spectroscopy. Part II: Prussian Blue reversible arrow Everitt's Salt Process[END_REF]. The redox processes associated to the Fe hs III is the most of electrochemical response observed in the PB⇄ES system. This was attributed to the size changes in channel radii of the Prussian blue which inhibits the Fe ls II system [START_REF] Dostal | Lattice contractions and expansions accompanying the electrochemical conversions of Prussian blue and the reversible and irreversible insertion of rubidium and thallium ions[END_REF][START_REF] Hermes | The electrochemical determination of ammonium based on the selective inhibition of the low-spin iron(II)/(III) system of Prussian blue[END_REF]. However, electrogravimetric and spectroelectrochemical studies have shown that the voltammetric peaks in 𝑃𝐵 films is a combination of three different electrochemical processes [START_REF] Garcia-Jareño | The role of potassium and hydrogen ions in the Prussian Blue reversible arrow Everitt's salt process[END_REF][START_REF] Agrisuelas | Innovative Combination of Three Alternating Current Relaxation Techniques: Electrical Charge, Mass, and Color Impedance Spectroscopy. Part II: Prussian Blue reversible arrow Everitt's Salt Process[END_REF][START_REF] Agrisuelas | Identification of Processes Associated with Different Iron Sites in the Prussian Blue Structure by in Situ Electrochemical, Gravimetric, and Spectroscopic Techniques in the dc and ac Regimes[END_REF]. Thus, changes around 900 nm have been associated to at least three different processes [START_REF] Agrisuelas | Identification of Processes Associated with Different Iron Sites in the Prussian Blue Structure by in Situ Electrochemical, Gravimetric, and Spectroscopic Techniques in the dc and ac Regimes[END_REF]: i) a forbidden transition also associated to the transition at 690 nm, ii) an electrochemical process of Fe III sites near the ferrocyanide vacancies in the PB structure and iii) an electrochemical processes associated to the structure Fe ls III -CN-Fe hs II (trapping) in the PB structure. These electrochemical processes take place by the participation of different counterions in KCl solutions [START_REF] Feldman | Ion Flux During Electrochemical Charging of Prussian Blue Films[END_REF][START_REF] Garcia-Jareño | The role of potassium and hydrogen ions in the Prussian Blue reversible arrow Everitt's salt process[END_REF].

Figure 2 shows the complete electrochromic information of PB in the visible and near infrared region expressed as absorbance time-derivative, d𝐴 𝜆 /d𝑡, between 450 nm and 950 nm during a voltammetric experiment where the PB⇄ES process occurs in a NH 4 Cl solution. The solid and dotted lines of the contour plot represent positive and negative regions of d𝐴 𝜆 /d𝑡, respectively. The results are qualitatively similar to that obtained in the literature for PB films in KCl solutions where a decrease of absorbance is observed during the reduction of PB and an increase of absorbance takes place during the oxidation to ES [START_REF] Agrisuelas | Identification of electroactive sites in Prussian Yellow films[END_REF][START_REF] Agrisuelas | Electronic Perspective on the Electrochemistry of Prussian Blue Films[END_REF]. As it can be seen, the maximum positive and negative changes of absorbance close to 690 nm agree with the voltammetric peaks. However, the maximum positive and negative d𝐴 𝜆 /d𝑡 close to 900 nm are slightly displaced due the overlapped processes: the maximum negative is reached after the cathodic peak and the maximum positive is before the anodic peak considering the potential scan direction. Therefore, 690 nm and 900 nm are also characteristic wavelengths in NH 4 Cl solutions.

NH 4 Fe III [Fe II (CN) 6 ] + e -+ NH 4

+ 𝑘 i → 𝑘 i ' ← (NH 4 ) 2 Fe II [ Fe II (CN) 6 ] (3)
Figure 3 shows an example of EIS, MIS and CIS at both characteristic wavelengths and at a potential of 0.2 V. Electrochemical impedance spectra as Δ𝑞/Δ𝐸 appears as two loops in the first quadrant indicating that at least two ions are involved in the electrochemical process(Figure 3a). Therefore, the electrochemical reactions of PB films in NH 4 Cl solution prove more complicated than the simplistic reaction showed in equation [START_REF] Karyakin | Prussian Blue and its analogues: Electrochemistry and analytical applications[END_REF]. At this potential and as it occurs in KCl solutions, a major response as one loop on the third quadrant for the mass impedance data proving the main participation of cations as counterions is observed (Figure 3b). However, in this case a low frequencies contribution on in the fourth quadrant is also shown. Color impedance loops appear in the first quadrant at 690 nm (Figure 3c) and at 900 nm (Figure 3d) since the absorptivity for the oxidized form of the films proves to be larger.

However, compared with EIS, MIS and CIS in KCl solutions at that potential the first difference is that these responses appear as two loops and they are flattened [START_REF] Agrisuelas | Innovative Combination of Three Alternating Current Relaxation Techniques: Electrical Charge, Mass, and Color Impedance Spectroscopy. Part II: Prussian Blue reversible arrow Everitt's Salt Process[END_REF]. This non-ideal shape of these loops may be attributed to different reasons. One of the possibilities is that these flattened loops are the result of the overlapping of more than one ideal loop. There are other possible reasons such as a non-uniform electrode surface causing a potential distribution on the electrode surface. Another unexplored possibility is the non-reversible character of the electrochemical processes around the PB⇄ES system in solutions containing NH 4 + cations. If the voltammogram corresponding this redox process in a NH 4 Cl solution in Figure 1 was examined carefully, one can observe that the redox peaks appear less symmetric than that in the case of KCl solutions. Therefore, the parameters 𝐾 i and 𝐺 i can be expressed from the partial derivative of the flux of exchanged species by:

∆𝐽 i = -𝑗𝜔𝑑∆𝐶 i = 𝐾 i ∆𝐶 i + 𝐺 i ∆𝐸 (4)
where 𝐶 i sol corresponds to the concentration of the specie i in the solution, 𝐶 i max and 𝐶 i min the maximum and minimum concentration of sites for insertion in the electroactive polymer, respectively. The 𝑘 i and 𝑘 i ' parameters are the kinetics constants for direct and reverse insertion reaction, equation ( 3). These constants have a Butler-Volmer dependence on the potential:

where parameters 𝑏 i and 𝑏 i ' are related with the number of electrons participating during the redox process and with the transfer coefficient 𝛽:

As a first approach, we can consider that 𝛽 = 0.5 and then, 𝑏 i = -𝑏 i ′ . In this case, the dependence of log 𝐺 i on the applied potential proves to be symmetrical with respect to the formal potential 𝐸 i 0' . At steady state conditions, the dependence of 𝐺 i parameters on the applied potential can be expressed by [START_REF] Agrisuelas | Spectroelectrochemical identification of the active sites for protons and anions insertions into poly-(Azure a) thin polymer films[END_REF]:

where 𝐵 i /2 = 19.5 V 1 for a reversible process at 298 K considering equation [START_REF] Garcia-Jareño | The role of potassium and hydrogen ions in the Prussian Blue reversible arrow Everitt's salt process[END_REF]. 𝐺 i max represents the maximum value for this parameter and corresponds to the potential 𝐸 = 𝐸 i 0' .

Accordingly, the insertion law for each participating species can be mathematically expressed by this model as:

Therefore, the parameters 𝐵 i , 𝐸 i 0' and 𝐶 i max can be estimated by the appropriate fitting of the dependence of these parameters on the applied potential. Moreover, the parameter 𝑑 represents the film thickness and in most cases, it is often difficult to obtain a good estimation.

Therefore, we can include the thickness in the 𝐾 i parameter as 𝐾 di = 𝐾 i /𝑑. Consequently, 𝐺 i /𝐾 di is the insertion law in terms of surface concentration, d𝛤 i /d𝐸:

𝐾 i = ( 𝜕𝐽 i 𝜕𝐶 i ) 𝐸 = 𝑘 i + 𝑘 i ' 𝐶 i sol (5)
𝐺 i = ( 𝜕𝐽 i 𝜕𝐸 ) 𝐶 i = -𝑏 i 𝑘 i (𝐶 i -𝐶 i min ) + 𝑏 i ' 𝑘 i ' (𝐶 i max -𝐶 i )𝐶 i sol (6)
𝑘 i = 𝑘 i,0 exp [𝑏 i (𝐸 -𝐸 i 0 ' )] 𝑘 i ' = 𝑘 i,0 ' exp [𝑏 i ' (𝐸 -𝐸 i 0 ' )] (7)
𝑏 i = -𝛽 𝑛 i 𝐹 𝑅𝑇 𝑏 i ' = (1 -𝛽) 𝑛 i 𝐹 𝑅𝑇 ( 8
)
𝐺 i = 𝐺 i max cosh [ 𝐵 i (𝐸 -𝐸 i 0′ ) 2 ] ( 9
)
d𝐶 𝑖 d𝐸 = 𝐺 i 𝐾 i = 𝐵 i 4 𝐶 i max cosh 2 [ 𝐵 i (𝐸 -𝐸 i 0' ) 2 ] ( 10
)
where 𝛤 i max is the maximum surface concentration of sites for insertion in the electroactive polymer.

On the basis of this model, the faradaic impedance if we consider two different counterions can be written as [START_REF] Agrisuelas | Identification of Processes Associated with Different Iron Sites in the Prussian Blue Structure by in Situ Electrochemical, Gravimetric, and Spectroscopic Techniques in the dc and ac Regimes[END_REF][START_REF] García-Jareño | EIS and Ac-Electrogravimetry Study of PB Films in KCl, NaCl, and CsCl Aqueous Solutions[END_REF]:

This model has been previously tested in PB film immersed in KCl solutions and provided coherent results [START_REF] Agrisuelas | Innovative Combination of Three Alternating Current Relaxation Techniques: Electrical Charge, Mass, and Color Impedance Spectroscopy. Part II: Prussian Blue reversible arrow Everitt's Salt Process[END_REF][START_REF] Agrisuelas | Identification of Processes Associated with Different Iron Sites in the Prussian Blue Structure by in Situ Electrochemical, Gravimetric, and Spectroscopic Techniques in the dc and ac Regimes[END_REF].

Equation ( 12) can be rewritten as a charge/potential transfer function, Δ𝑞/Δ𝐸(𝜔):

This expression is also valid for mass impedance and color impedance at a given wavelength by replacing the Faraday constant by 𝛿 𝑀 i 𝑀 i for the mass impedance and 𝛿 𝜀 i 𝜀 i for the color impedance at a given wavelength obtaining the impedance transfer functions for MIS (Δ𝑚/Δ𝐸(𝜔)), and for CIS (Δ𝐴 𝜆 /Δ𝐸(𝜔)), respectively:

where 𝑀 i represents the molar mass of the inserted or expelled species and 𝜀 i the electrochromic efficiency at a given wavelength 𝜆. The parameters 𝛿 𝑀 i and 𝛿 𝜀 i can only be 1 or 1. If the mass

d𝛤 i d𝐸 = 𝐺 i 𝐾 i 𝑑 ⁄ = 𝐺 i 𝐾 di = 𝐵 i 4 𝛤 i max cosh 2 [ 𝐵 i (𝐸 -𝐸 i 0' ) 2 ] (11)
𝑍 F = 1 𝐹𝐺 1 1 + 𝐾 d1 coth(√𝑗𝜔𝜏 1 ) √𝑗𝜔/𝜏 1 + 𝐹𝐺 2 1 + 𝐾 d2 coth(√𝑗𝜔𝜏 2 ) √𝑗𝜔/𝜏 2 (12) Δ𝑞 Δ𝐸 (𝜔) = 1 𝑗𝜔 ( 𝐹𝐺 1 1 + 𝐾 d1 coth(√𝑗𝜔𝜏 1 ) √𝑗𝜔/𝜏 1 + 𝐹𝐺 2 1 + 𝐾 d2 coth(√𝑗𝜔𝜏 2 ) √𝑗𝜔/𝜏 2 ) (13)
Δ𝑚 Δ𝐸 (𝜔) = 1 𝑗𝜔 ( 𝛿 𝑀 1 𝑀 1 𝐺 1 1 + 𝐾 d1 coth(√𝑗𝜔𝜏 1 ) √𝑗𝜔/𝜏 1 + 𝛿 𝑀 2 𝑀 2 𝐺 2 1 + 𝐾 d2 coth(√𝑗𝜔𝜏 2 ) √𝑗𝜔/𝜏 2 ) (14)
Δ𝐴 𝜆 Δ𝐸 (𝜔) = 1 𝑗𝜔 ( 𝛿 𝜀 1 𝜀 1 𝐺 1 1 + 𝐾 d1 coth(√𝑗𝜔𝜏 1 ) √𝑗𝜔/𝜏 1 + 𝛿 𝜀 2 𝜀 2 𝐺 2 1 + 𝐾 d2 coth(√𝑗𝜔𝜏 2 ) √𝑗𝜔/𝜏 2 ) (15)
or the absorbance increases with the potential, it is positive and this value is negative if the opposite occurs.

It is our interest to obtain quantitative information about these electrochemical processes from these experiments. For that purpose, we can fit experimental impedance data to the equations ( 13)-( 15) corresponding to the theoretical insertion model for two counterions species. As an example, lines in Figure 3 show the fittings to the experimental data for the EIS, MIS and CIS for both wavelengths (690 nm and 900 nm) at 0.2 V. It should be noted that the shape of the loops is not perfectly reproduced. The experimental loops appear more flattened than the fitted-simulated loops. Therefore, we need at least two loops, but that is not the only reason of the non-ideal shape of loops and it will be discussed in the following.

In the case of MIS at some potentials, the low frequencies loop appears on the fourth quadrant and it means that the 𝛿 𝑀 changes from negative to positive values. In this case, a possible explanation is that the charge balance takes place by the participation of an anion or also that the exchange of cations is accompanied by the opposite flux of the solvent.

A deeper analysis is possible by examining the dependence on the stabilization potential of the parameters obtained from the fitting of experimental data to the model described by equations ( 13)-( 15) for two processes. Impedance measurements allow the responses due to the faster and slower processes to be separated by changing the frequency of the potential perturbation. Therefore, the responses will be seen as a slow process and a fast process. This difference is correlated to the time constant 𝜏 i obtained for each one of the processes in the four impedance functions analyzed. Figure 4 shows the variation of the time constant for the faster (a) and for the slower (b) processes. The fast process in all cases shows minimum time constants at potentials about 0.2 V, while for the slower one, the minimum is at potentials about 0.15 V.

At these potentials, the faradaic processes occur, thus the changes of mass and color are clearly related with faradaic processes in the PB films. However, for the faster process and at 900 nm a minimum of the time constant is obtained at potentials near 0.35 V (Figure 4a). At these potentials and in KCl solutions, it has also been detected a change of absorbance at 900 nm associated to the participation of H + as counterions [START_REF] Agrisuelas | Usefulness of F(dm/dQ) function for elucidating the ions role in PB films[END_REF]. Therefore, this could be extrapolated to these experimental conditions.

The dependence of dΓ i /d𝐸 on the applied potential is plotted in Figure 5 for the fast (a)

and for the slow (b) processes. This variable is a measure of the contribution of each process to the overall response. For the fast process, we obtain maximum values for this parameter at different potentials. A possible explanation is that the overall response is not only due to a single process. It can be better understood if the response associated to the CIS at 690 and at 900 nm in Figure 5a is carefully examined. Maximum values are obtained at different potentials. At potentials in the range 0-0.15 V there is no response at 690 nm, but a clear contribution appears at 900 nm. EIS, MIS and CIS at 900 nm maximum are obtained at larger potentials than that of the CIS at 690 nm measurements. This can be due to the fact that at these potentials there exists electrochemical processes associated to the ferrocyanide vacancies where the H 3 O + has been detected as a counterion [START_REF] Agrisuelas | Identification of Processes Associated with Different Iron Sites in the Prussian Blue Structure by in Situ Electrochemical, Gravimetric, and Spectroscopic Techniques in the dc and ac Regimes[END_REF]. This process does not involve color changes at 690 nm, and thus the contribution at this wavelength clearly decreases. Nevertheless, the mass does not change significantly between NH 4 + and H 3 O + .

There is also an interesting MIS behavior for the slow process at potentials in the range 0.15-0.2 V in Figure 5b, where the low frequencies loop appears on the fourth quadrant. This may be explained by a second contribution on the opposite flux direction of that of the cations.

This can be due to an anion participation as counterion and/or the flux of water molecules due to the exclusion effect associated to the insertion-expulsion of NH 4 + cation. From these results, it is not possible to discern between these two possibilities. However, studies of the role of inner water molecules on the electrochemistry of PB films have shown that an exchange of water molecules takes place at these potentials [START_REF] Garcia-Jareño | The role of potassium and hydrogen ions in the Prussian Blue reversible arrow Everitt's salt process[END_REF].

We can estimate the molar mass of participating species from the values of 𝑀 i 𝐺 i /𝐾 di obtained from the low frequencies limit of Δ𝑚/Δ𝐸, and the values of 𝐹𝐺 i /𝐾 di obtained from the low frequencies limit of Δ𝑞/Δ𝐸 for both processes. Similarly, the electrochromic efficiency 𝜀 𝑖 associated to each one of the electroactive processes are obtained by comparing Δ𝑞/Δ𝐸 and

Δ𝐴 𝜆 /Δ𝐸.
where 𝑧 is the number of electrons involved per active center in the electrochemical process.

In the potential ranged from 0.1 to 0.2 V the slowest process shows a very small associated molar mass of participating species (about 1 g mol 1 ) that can be attributed to an exchange of other species -probably water molecules -in the opposite direction of the

𝐹 Δ𝑚 Δ𝐸 ⁄ Δ𝑞 Δ𝐸 ⁄ = 𝐹 Δ𝑚 Δ𝑞 = 𝑀 𝑧 (16)
𝐹 Δ𝐴 𝜆 Δ𝐸 ⁄ Δ𝑞 Δ𝐸 ⁄ = 𝐹 Δ𝐴 𝜆 Δ𝑞 = 𝜀 𝑧 (17)
ammonium flux [START_REF] Garcia-Jareño | The role of potassium and hydrogen ions in the Prussian Blue reversible arrow Everitt's salt process[END_REF][START_REF] Giménez-Romero | Mechanism for Interplay between Electron and Ionic Fluxes in KhFek[Fe(CN)6]l•mH2O Compounds[END_REF]. It is better observed in Figure 6 where the crossed impedance functions 𝐹Δ𝑚/Δ𝑞 𝑎t 0.15 V decrease from high to low frequencies, which is in good agreement with the hypothesis of a slow process in the opposite sense. Figure 3b shows also that the fitting of MIS experimental data to the proposed model needs a second loop on the fourth quadrant.

At other potentials, the molar mass associated to this process is close to the expected molar mass for the ammonium cation (18 g mol 1 ). For the fast process, a molar mass about 18 g mol 1 is obtained in the full range of potentials. If compared with the case of PB films in KCl solutions, it should be noted here that in NH 4 Cl solutions we cannot discern between the hydrated proton and the salt cation since the molar masses are very similar. In spite of this, the participation of both species is expected by analogy with results of PB films in KCl solutions [START_REF] Agrisuelas | Innovative Combination of Three Alternating Current Relaxation Techniques: Electrical Charge, Mass, and Color Impedance Spectroscopy. Part II: Prussian Blue reversible arrow Everitt's Salt Process[END_REF][START_REF] Agrisuelas | Identification of Processes Associated with Different Iron Sites in the Prussian Blue Structure by in Situ Electrochemical, Gravimetric, and Spectroscopic Techniques in the dc and ac Regimes[END_REF].

𝐹Δ𝐴 𝜆 /Δ𝑞(𝜔) values at 690 nm and 900 nm are shown in Figure 7a and Figure 7b, respectively. The electrochromic efficiency at 900 nm estimated as 𝐹Δ𝐴 900 /Δ𝑞(𝜔) decreases with the applied potential obtaining the maximum value at potentials near 0.1 V, far from the redox potential of the PB⇄ES process. This indicates that the changes of absorbance at this wavelength are not associated to the main electrochemical process. This is not the case for the process at 690 nm, where the maximum of electrochromic efficiency is reached at potentials near the redox potential of the main process (0.25V). At potentials slightly higher than the redox potential, the electrochromic efficiency quickly decreases at this wavelength and no color change at 690 nm is observed.

Conclusion

Acquisition of three impedances simultaneously allowed the valuable information on the electrochemical behavior of PB films in NH 4 Cl solutions to be obtained. The impedance responses appear as double loops and more flattened than that in KCl solutions. The voltammograms in NH 4 Cl solutions clearly show a smaller and a wider anodic peak. This behavior could be the reason of the non-ideal loops. Ammonium cations have shown a large affinity for PB films [START_REF] Sanmatias | The role of inner counterions within PB films during electrochemical processes[END_REF] which means that there is no extra difficulty for these cations to be inserted in the film. However, the expulsion can be more difficult. The size of NH 4 + and K + cations is not very different, but the chemical affinity of iron sites for ammonium or potassium ions can be very different. This causes an apparent non-reversibility of the redox behavior and results in the non-ideal loops on the impedance plots.

In spite of the fact that two electrochemical processes (equations ( 13)-( 15)) were used to better fit the experimental data to our theoretical model, there is a point to be clarified here.

The electrochemical response of PB films in KCl solutions has been described as the overlap of at least three different processes. Working at a fixed potential can mean that one of these three processes is far from taking place, and thus this contribution can be neglected. These responses have been separated as a fast and a slow process; faster process is generally due to the main redox process, but the slower process is probably different when applied potential changes.

Most likely for this reason, we obtain two peaks for the slower process.

If these results are compared with those obtained for the PB films in KCl solutions, we can also consider three different processes. The main process is associated to the backbone structure of the PB films, which is related to the exchange of ammonium cations and to the changes of absorbance at 690 nm. The second process occurs at slightly larger potentials and is associated to the exchange of H 3 O + or NH 4 + cations (it is not possible to discern between these possibilities since both cations have a similar molar mass). At these potentials, there is no color change at 690 nm and a slight change of color at 900 nm. This process has been associated to the electrochemistry of the ferrocyanide vacancies. The third process is associated to an electron transition in trapped sites Fe ls III -CN-Fe hs II . This process is well localized at potentials near 0.1 V where the maximum of electrochromic efficiency at 900 nm is reached.

The 𝐹Δ𝑚/Δ𝑞 function shows clearly that at low frequencies an opposite flux of solvent takes place at potentials between 0.15 and 0.20 V. This explains the appearance of a second loop on the fourth quadrant in the mass impedance measurement.

NH 4 +

 4 cations could be easier inserted during the reduction reaction than expulsed during the oxidation reaction.The interpretation of experimental data provided by impedance techniques requires an examination of a kinetic model. In our case, an insertion model is used where the insertion/expulsion of species into the film controls the overall rate of the electrochemical process. The rate of transport related to the counterions, through the film, is characterized by the time constant parameter 𝜏[START_REF] Gabrielli | Ac-Electrogravimetry Study of Electroactive Thin Films. I. Application to Prussian Blue[END_REF][START_REF] García-Jareño | EIS and Ac-Electrogravimetry Study of PB Films in KCl, NaCl, and CsCl Aqueous Solutions[END_REF][START_REF] Gabrielli | Charge transport in electroactive thin films investigated by ac electrogravimetry[END_REF]. The change of flux of the specie i through the conducting film/solution interface caused by the sinusoidal potential perturbation can be written as[START_REF] Gabrielli | ac Electrogravimetry on conducting polymers. Application to polyaniline[END_REF][START_REF] Gabrielli | Separation of ionic and solvent transport during charge compensation processes in electroactive polymers by a.c. electrogravimetry[END_REF]:

Figure 1 . 6 Figure 2 .Figure 3 .Figure 4 .Figure 5 .Figure 6 .Figure 7 .

 16234567 Figures captions

Acknowledgments

Part of this work was supported by FEDER-CICyT project CTQ2011-28973/BQU.


Tushant Jha

Walid Belkhir
email: walid.belkhir@inria.fr

Chevalier Yannick

Michael Rusinowitch

Expressive Equivalence and Succinctness of Parametrized Automata with respect to Finite Memory Automata

We compare parametrized automata, a class of automata recently introduced by the authors, against finite memory automata with non-deterministic assignment, an existing class of automata used to model services. We prove that both classes have the same expressive power, while parametrized automata can be exponentially succinct in some cases. We then prove that deciding simulation preorder for parametrized automata is EXPTIME-complete, extending an earlier result showing it in EXPTIME.

Introduction

The simple and powerful formalism of finite automata (FAs in short) is widely used for service specification and verification. Considerable efforts have been devoted to extend finite automata to infinite alphabets: data automata [START_REF] Bojanczyk | Twovariable logic on words with data[END_REF], finite memory automata [START_REF] Kaminski | Finite-memory automata with non-deterministic reassignment[END_REF], usage automata [START_REF] Degano | Nominal automata for resource usage control[END_REF], fresh-variable automata [START_REF] Belkhir | Fresh-variable automata: Application to service composition[END_REF] and parametrized automata (PAs in short) [START_REF] Belkhir | Parametrized automata simulation and application to service composition[END_REF][START_REF] Belkhir | A parametrized propositional dynamic logic with application to service synthesis[END_REF], only to cite a few (see [START_REF] Manuel | Automata over infinite alphabets[END_REF] for a survey). They have been applied recently to formal verification, see e.g. [START_REF] Delzanno | Parameterized verification of broadcast networks of register automata[END_REF]. When developing formalisms over infinite alphabets, the main challenge is to preserve as much as possible useful properties such as compositionality (i.e. closure under basic operations) and decidability of basic problems such as nonemptiness, membership, universality, language containment, simulation, etc.

Our interest for simulation preorders is motivated by the composition synthesis problem for web services in which the agents (i.e. client and the available services) exchange data ranging over an infinite domain. One of the most successful approaches to composition amounts to abstract services as finite-state automata and synthesize a new service satisfying the given client requests from an existing community of services (e.g. [START_REF] Berardi | Automatic service composition via simulation[END_REF][START_REF] Muscholl | A lower bound on web services composition[END_REF]). This amounts to computing a simulation relation of the client by the community of the available services, e.g. [START_REF] Berardi | Automatic service composition via simulation[END_REF]. Simulation preorder can also be employed to efficiently underapproximate the language containment relation (e.g. [START_REF] Dill | Checking for language inclusion using simulation preorders[END_REF]), which has applications in verification.

Akroun et al. have used such classes of automata over infinite alphabet to model verification and synthesis problems for Web Services, and give a detailed study in [START_REF] Akroun | Decidability and complexity of simulation preorder for data-centric web services[END_REF]. Parametrized automata, a class of automata introduced by the authors, is shown to be equivalent to finite memory automata with nondeterministic reassignment (NFMAs) [START_REF] Kaminski | Finite-memory automata with non-deterministic reassignment[END_REF] in terms of the class of languages they can represent. We have shown in our previous works [START_REF] Belkhir | Fresh-variable automata: Application to service composition[END_REF][START_REF] Belkhir | Parametrized automata simulation and application to service composition[END_REF] how to extend the automata-based service composition approach to the case of infinite alphabets, also showing an EXPTIME solution for solving simulation preorder. Akroun et al. [START_REF] Akroun | Decidability and complexity of simulation preorder for data-centric web services[END_REF] further demonstrate that it is EXPTIME-complete. However, we also provide a simpler proof of the EXPTIME-completeness claim in this paper. Contributions. In this paper, we first compare the expressiveness of PAs and NFMAs, in Section 3, proving their expressive equivalence. However, we claim and prove, that for many languages, PAs provide a succinct representation against NFMAs. We prove this by showing a class of languages for which the smallest NFMA that recognize them are exponentially large as compared to smallest PA that recognize the same.

We then prove, in Section 4, the EXPTIME-completeness of deciding whether one PA can be simulated by other, extending the result from [START_REF] Belkhir | Parametrized automata simulation and application to service composition[END_REF], where its membership in EXPTIME was shown. We do this by providing a proof for the EXPTIME-hardness in this paper using reduction from Countdown Games, which were introduced and shown to be EXPTIME-complete by Jurdzinski et al. in [START_REF] Jurdziński | Model checking probabilistic timed automata with one or two clocks[END_REF].

Preliminaries

Before introducing formally the class of PAs, let us first explain the main ideas behind them. The transitions of a PA are labeled with letters or variables ranging over an infinite set of letters. Transitions can also be labeled with a guard, a conjunction of equalities and disequalities that permits to fire the transition only when the guard is true. We emphasize that while reading a guarded transition some variables of the guard might be free and we need to guess their value. Finally, some variables are refreshed in some states, that is, variables can be freed in these states so that new letters can be assigned to them. In other words, once a letter is assigned to a variable, this variable can not get another letter unless it is refreshed.

Technical preliminaries

Let X be a finite set of variables, Σ an infinite alphabet of letters. A substitution σ is an idempotent mapping {x 1 → α 1 , . . . , x n → α n } ∪ a∈Σ {a → a} with variables x 1 , . . . , x n in X and α 1 , . . . , α n in X ∪ Σ, for some n ∈ N. We call {x 1 , . . . , x n } its proper domain, and denote it by dom(σ). We denote by Dom(σ) the set dom(σ)∪Σ, and by codom(σ) the set {a ∈ Σ | ∃x ∈ dom(σ) s.t. σ(x) = a}. If all the α i , i = 1 . . . n are letters then we say that σ is ground. The empty substitution (i.e., with an empty proper domain) is denoted by ∅. The set of substitutions from X ∪ Σ to a set A is denoted by ζ X ,A , or by ζ X , or simply by ζ if there is no ambiguity. If σ 1 and σ 2 are substitutions that coincide on the domain dom(σ 1 ) ∩ dom(σ 2 ), then σ 1 ∪ σ 2 denotes their union in the usual sense.

If dom(σ 1 ) ∩ dom(σ 2 ) = ∅ then we denote by σ 1 σ 2 their disjoint union. We define the function V : Σ ∪ X -→ P(X ) by V(α) = {α} if α ∈ X , and V(α) = ∅, otherwise. For a function F : A → B, and A ⊆ A, the restriction of F on A is denoted by F |A . For n ∈ N + , we denote by [n] the set {1, . . . , n}.

Parametrized automata

Firstly, we introduce the syntax and semantics of guards. Definition 1. The set G of guards over Σ ∪ X , where Σ is an infinite set of letters and X is a finite set of variables, is inductively defined as follows:

G := true | α = β | α = β | G ∧ G,
where α, β ∈ Σ ∪ X . We write σ |= g if a substitution σ satisfies a guard g.

Note that a disjunction of guard expressions here is equivalent to multiple parallel edges, with those guards, as a result of Non-determinism.

For a guard g, we denote the set of variables used in g with V(g) and the set of constants used in g with Σ g , which can be defined inductively over guard expressions. Substitutions can be applied similarly, inductively, and we write σ g if there exists a substitution γ s.t. σ γ |= g.

The formal definition of PAs follows.

Definition 2. A PA is a tuple A = Σ, X , Q, Q 0 , δ, F, κ where -Σ is an infinite set of letters, -X is a finite set of variables, -Q is a finite set of states, -Q 0 ⊆ Q is a set of initial states, -δ : Q × (Σ A ∪ X ∪ {ε}) × G → 2 Q is a transition function where Σ A is a finite subset of Σ, -F ⊆ Q is a set of accepting states, and -κ : X → 2 Q is called the refreshing function.
The run of a PA is defined over configurations. A configuration is defined as a pair (γ, q) where γ is a substitution such that for all variables x in dom(γ), γ(x) can be interpreted as the current value of x, and q ∈ Q is a state of the PA.

Intuitively, when a PA A is in state q, and (γ, q) is the current configuration, and there is a transition q α,g → q in A then: i) if α is a free variable (i.e. α ∈ X \ dom(γ)) then α stores the input letter and some values for all the other free variables of γ(g) are guessed such that γ(g) holds, and A enters the state q ∈ δ(q, α, g), ii) if α is a bound variable or a letter (i.e. α ∈ Dom(γ)) and γ(α) is equal to the input letter l then some values for all the free variables of γ(g) are guessed such that γ(g) holds, and A enters the state q ∈ δ(q, α, g). Example 1. Let A 1 and A 2 be the PAs depicted above in Figure 1 where the variable y 1 is refreshed in the state p, and the variables x 2 , y 2 are refreshed in the state q. That is,

A 1 = Σ, {x 1 , y 1 }, {p, p }, {p}, δ 1 , {p }, κ 1 with δ 1 (p, y 1 , (y 1 = x 1 )) = {p} and δ 1 (p, x 1 , true) = {p }, and κ 1 (y 1 ) = {p} And A 2 = Σ, {x 2 , y 2 }, {q, q }, {q}, δ 2 , {q }, κ 2 with δ 2 (q, x 2 , true) = {q } and δ 2 (q , y 2 , (y 2 = x 2 )) = {q}, and κ 2 (x 2 ) = κ 2 (y 2 ) = {q}.
We notice that while making the first loop over the state p of A 1 , the variable x 1 of the guard (y 1 = x 1 ) is free and its value is guessed. Then the variable y 1 is refreshed in p, and at each loop the input letter should be different from the value of the variable x 1 already guessed. More precisely, the behaviour of A 1 on an input word is as follows. Being in the initial state p, either the automaton makes the transition p x1 → p by reading the input symbol and binding the variable x 1 to this input symbol, then enters the state p . Or, the automaton makes the transition p y1,y1 =x1 -→ p by: 1. reading the input symbol and binding the variable y 1 to it, 2. guessing a symbol in Σ that is different from the input symbol (i.e. the value of x 1 ) and binds the variable y 1 to the guessed symbol, then enters the state p, 3. in the state p the variable y 1 is refreshed, that is, it is no longer bound to the input symbol. Then, start again.

We illustrate the run of A 1 on the word w = abbc, starting from the initial configuration (∅, p) as follows:

(∅, p) a → ({x 1 → c}, p) b → ({x 1 → c}, p) b → ({x 1 → c}, p) c → ({x 1 → c}, p )
Notice that the variable y 1 does not appear in any of the configurations of this run since it is refreshed in the state p. Hence, the language L(A 1 ) consists of all the words in Σ in which the last letter is different from all the other letters. By following similar reasoning, we get

L(A 2 ) = {w 1 w 1 • • • w n w n | w i , w i ∈ Σ, n ≥ 1, and w i = w i , ∀i ∈ [n]}.
This language can be recognized by an NFMA [START_REF] Kaminski | Finite-memory automata with non-deterministic reassignment[END_REF] but not by a fresh-variable automaton [START_REF] Belkhir | Fresh-variable automata: Application to service composition[END_REF].

Comparison between PAs and NFMAs

In this section, we show that parametrized automata (PAs) and finite-memory automata with non-deterministic reassignment (NFMAs), which are discussed in [START_REF] Kaminski | Finite-memory automata with non-deterministic reassignment[END_REF], have the same expressive power (ie. for any language over infinite alphabet, there exists an NFMA recognizing it iff there exists a PA that recognizes it), but there are languages for which PAs can be exponentially more succinct than NFMAs.

Expressiveness

We recall that an NFMA (as defined in [START_REF] Kaminski | Finite-memory automata with non-deterministic reassignment[END_REF]) is a 8-tuple

F = Σ, k, Q, q 0 , u, ρ, δ, F where k ∈ N + is the number of registers, Q is a finite set of states, q 0 ∈ Q is the initial state, u : [k]
Σ is a partial function called the initial assignment of the k registers, ρ :

{(p, q) : (p, ε, q) ∈ δ} [k] is a function called the non- deterministic reassignment, δ : Q × ([k] ∪ {ε}) × Q is the
transition relation, and F ⊆ Q is the set of final states. Intuitively, if F is in state p, and there is an ε-transition from p to q and ρ(p, q) = l, then F can non-deterministically replace the content of the l th register with an element of Σ not occurring in any other register and enter state q. However, if F is in state p, and the input symbol is equal to the content of the l th register and (p, l, q) ∈ δ then F may enter state q and pass to the next input symbol. An ε-transition (p, ε, q) ∈ δ with ρ(p, q) = l, for a register l ∈ [k], is denoted by (p, ε/l, q).

Interpreting registers of the NFMAs as variables, the semantics of NFMAs can be given as a relation over configurations of the form (q, σ) where q is a state of the NFMA and σ is a substitution of registers with letters. It is easy to see, as illustrated in Fig 2, that any NFMA (with k registers) can be translated into a PA (with k variables) of linear size, that recognizes the same language. More precisely, as shown in Figure 2: i) a transition (p, m, p ) of the NFMA is translated as such, i.e. to (p, x m , p ); and, ii) a transition (p, ε/l, p ) of the NFMA is translated to two transitions (p, ε, p) and (p, (x l , g), p ) where g = i∈[k]\{l} (x l = x i ) and x l is refreshed in state p.

Lemma 1. For any NFMA over Σ with k registers and q states, there exists a corresponding PA with k variables and number of states linear in q, that recognizes the same language.

We show next that a PA can be translated into an NFMA recognizing the same language, by introducing an intermediary class of PAs, called PAs, in which the variables should have distinct values. The idea is that the ε-transitions of the NFMA are used to encode the refreshing of the variables of the PAs, which are translated into NFMA. Definition 3. Let PAs be the subclass of PAs such that every A in PAs, verifies i) A has no constants, i.e. Σ A = ∅, and ii) for every reachable configuration (σ, q) of A and for all x, y ∈ dom(σ), σ(x) = σ(y).

It can be shown that PAs and PAs recognize the same language, more precisely we have: For the proof and construction of the same, let X and X be two disjoint sets of variables, and let ψ be a total function from X to X , and let g be a conjunction of equalities between variables in X . Then define g ψ iff there exists x ∈ X s.t. ψ(x) = x for all x in V(g). And let A = Σ, X , Q, Q 0 , δ, F, κ be a PA with X = {x 1 , . . . , x k }.

Firstly, we transform the PA A into a PA A recognizing the same language and in which each state is labeled with the set of variables being free in this state. We define A = Σ, X , Q, Q 0 , F , δ, κ by:

     Q = {(q, X) | q ∈ Q and X ⊆ X }, Q 0 = {(q, X ) | q ∈ Q 0 }, F = {(q, X) | q ∈ F and X ⊆ X }.
The transition function δ is defined by (q , X ) ∈ δ((q, X), α, g), where α ∈ Σ ∪X and g is a guard, if and only if, X = (X \ ({α} ∪ V(g))) ∪ κ -1 (q ). Finally, the refreshing function κ is defined by κ(x) = {(q, X) | q ∈ κ(x)}. Secondly, we can assume w.l.o.g. that A has no constants and the variables are refreshed only in the states preceded by ε-transitions. The constants can be replaced by additional variables that have to be initialized with the related constants using an ε-transition outgoing from the initial state. And, if some variables, say X ⊆ X , are refreshed in a state, say q, then we add an ε-transition q ε → q where the variables X are refreshed in q instead of q and the outgoing transitions of q become the outgoing transitions of q. Thus, the guards of A are of the form φ ∧ φ where φ (resp. φ ) is a conjunction of equalities (resp. inequalities) between variables.

Thirdly, we let A to be the PA A = Σ, X , Q , Q 0 , δ , F , κ defined by

         X = {x 1 , . . . , x k } Q = Q × X X Q 0 = Q 0 × X X κ = κ × X X
and δ is defined by [where g (resp. g ) is a conjunction of equalities (resp. inequalities)] :

((q 1 , X 1 , ψ 1 ), (α, ψ 1 (g ∧ g )), (q 2 , X 2 , ψ 1 )) ∈ δ iff               
((q 1 , X 1 ), (α, g ∧ g ), (q 2 , X 2 )) ∈ δ and α = ε and g ψ 1 and V(g ) = codom(ψ 1 ) and

V(g ∧ g ) ∩ X 1 = ∅ And, ((q 1 , X 1 , ψ 1 ), (ε, ψ 1 (g ∧ g )), (q 2 , X 2 , ψ 2 )) ∈ δ iff                        ((q 1 , X 1 ), (ε, g ∧ g ), (q 2 , X 2
)) ∈ δ and V(g ) = codom(ψ 1 ) and V(g ∧ g ) ⊆ X 1 and

ψ 2 = ψ 1 ∪ {x → x 0 | x ∈ V(g)}∪ {x → y 0 | x ∈ V(g )} x 0 = get(X \ codom(ψ 1 )) y 0 = get X \ (codom(ψ 1 ) ∪ {x 0 })
Therefore having proved the expressive equivalence of PA and PA, we now show every PA can be turned into an NFMA recognizing the same languages by encoding the refreshing of the variables of the PAs with ε-transitions. Hence, Lemma 3. For every PA with k variables and n states there exists an NFMA with n • k! states recognizing the same languages.

Theorem 1. For every language L over Σ, there exists an NFMA F such that L(F) = L, if and only if there exists a PA A such that L(A) = L.

Succinctness of PAs over NFMAs

We next show that while PAs and NFMAs have the same expressive power, PAs can be exponentially succinct than NFMAs. That is, we prove that there exists a class of PAs such that any NFMA that recognizes the same language must be exponentially larger.

Theorem 2. There exists a countably infinite class of languages {L 1 , L 2 , ...}, such that for every n, there exists a PA A n , of size O(log n), such that L(A n ) = L n , but there does not exist any NFMA F, of size o(n), such that L(F) = L n .

We prove the existence by taking the class of languages L n = {a n }. We first argue in Lemma 4 the existence of a PA with O(log n) states and O(log n) variables, that recognizes L n . Then we prove in Lemma 6 that any NFMA that accepts the language L n must have at least Ω(n) states.

Lemma 4. For every n ≥ 1, there exists a PA A n with O(log n) states and

O(log n) variables, such that L(A n ) = L n = {a n }.
It has already been shown in [START_REF] Belkhir | Parametrized automata simulation and application to service composition[END_REF] that addition and comparison for bounded integers can be implemented in PAs, with constants to denote 0 and 1, in O(log n) states and O(log n) variables that encode bit representation of an integer. To construct a PA for the language L n = {a n }, we construct a PA that acts as a Counter, ie. the value encoded by variables is incremented every time a is read, until i=1,...,m (x i = c i ), which allows transition from the seed state to an accepting state, where c 1 c 2 . . . c m is the binary representation of n.

Such a PA, acting as a Counter, recognizes only L n = {a n }, by counting till n using the variables for bit representation.

We now show that any NFMA that recognizes the L n = {a n } must require at least O(n) states. Let us take an NFMA F, with L(F) = L n .

Since F accepts a n , we know that there exists a configuration path

℘ = c 1 → c 2 ... → c m = (q 1 , σ 1 ) → (q 2 , σ 2 )... → (q m , σ m ) (1) such that trace(℘) = a n ( 2
)
Where ℘ is a path over the set of configurations of F, and m ≥ n. Since a is a constant, and L n includes only a n , we argue that a must be stored in some NFMA register initially, which we can call without loss of generality l 0 . Lemma 5. ℘ (from equation ( 1), a path in F that accepts a n ) contains only ε-transitions and l 0 -transitions.

Proof. It can be easily seen that l 0 -transitions are the only non-ε-transitions in ℘. Since the trace contains only a's, if on the contrary there was some l ktransition for any k = 0, it would require σ(l k ) = a at that transition. However, due to implicit dis-equality, since σ 1 (l k ) = a, there must be some i such that c i ε/l k -→ c i+1 , and σ i (l k ) = a for all k = k, at which stage l k stored a. But if this holds, then it is also possible for l k to get assigned to some completely different letter b, such that b = σ i (l k ) for any k , from the infinite alphabet Σ, at the i th transition. Since this would imply that F also accepts another string with some a's in trace(℘) replaced with b's, hence by contradiction, we know that ℘ only contains ε-transitions and l 0 -transitions. We observe ∀i : σ i (l 0 ) = a, and therefore the sub-NFMA F , with only the ε-transitions and l 0 labelled transitions of F is sufficient for recognizing the singleton language. In fact, all accepting paths in F are accepting paths in F .

We now define the notion of strong bisimilarity for NFMAs to argue for an important assertion for our proof.

Definition 4 (NFMA Bisimulation). Two NFMA configurations (q 1 , σ 1 ) and (q 2 , σ 2 ) are said to be strongly bisimilar, i.e. (q 1 , σ 1 ) ∼ (q 2 , σ 2 ) ↔ (q 2 , σ 2 ) ∼ (q 1 , σ 1 ), if 1. for all α ∈ Σ, if there exists (q 1 , σ 1 ) with (q 1 , σ 1 ) α -→ (q 1 , σ 1 ), then there must exist (q 2 , σ 2 ), such that (q 2 , σ 2 ) α -→ (q 2 , σ 2 ) and (q 2 , σ 2 ) ∼ (q 1 , σ 1 ). And vice versa. 2. if there exists (q 1 , σ 1 ) such that (q 1 , σ 1 ) ε -→ (q 1 , σ 1 ), then there must exist (q 2 , σ 2 ) with (q 2 , σ 2 ) ε -→ (q 2 , σ 2 ), such that (q 2 , σ 2 ) ∼ (q 1 , σ 1 ). And vice versa. Lemma 6. For an NFMA with all non-ε-transitions restricted to registers in a subset L of the set of registers, if σ 1 agrees with σ 2 over L then (q, σ 1 ) is bisimilar to (q, σ 2 ), for all states q. This follows by observing that:

for all transitions (q, l j , q ) ∈ δ, with l j ∈ L and σ 1 (l j ) = σ 2 (l j ), (q, σ 1 ) α -→ (q , σ 1 ) if and only if (q, σ 2 ) α -→ (q , σ 2 ), for any α ∈ Σ.

for all transitions (q, ε/l j , q ), if (q, σ 1 ) ε -→ (q , σ 1 ), with σ 1 (l j ) = β, for some β ∈ Σ without loss of generality, then there exists σ 2 , where σ 2 (l j ) = β and σ 2 (l k ) = σ 2 (l k ) for all k = j, such that (q, σ 2 ) ε -→ (q , σ 2 ). And vice versa. Now applying Lemma 6 to the F for which L(F ) = L n and contains only ε-transitions and l 0 labelled transitions, as argued above, we claim that F must contain Ω(n) states. Lemma 7. An NFMA F that recognizes {a n } has at least n + 1 states.

Proof. Towards a contradiction, let us assume that there are less than n + 1 states in ℘ (from equation ( 1)). Then we can argue that ∃i = j : q i = q j and the trace from configuration c i to c j is a n1 for n 1 > 0. Since, otherwise, if there are no such i and j then there must be at least n + 1 states. Now, let the trace from c 1 to c i be a n0 , from c i to c j be a n1 , and c j to c m be a n2 , with n 0 , n 1 , n 2 > 0. And thus n 0 + n 1 + n 2 = n.

But since q i = q j , thus the path from c j to c m can also be simulated from c i , by Lemma 6, since the substitutions already agree on l 0 . Hence the automata F also accepts a (n0+n2) , which is in contradiction to the language.

Hence by contradiction there are at least n + 1 states in F, which is exponential in the size of comparable PA, proving Theorem 2.

Complexity of simulation preorder over PAs

Theorem 3. Deciding the simulation preorder over PA is EXPTIME-complete.

An EXPTIME algorithm for deciding if a PA simulates another PA was given in [START_REF] Belkhir | Parametrized automata simulation and application to service composition[END_REF], and we show that this problem is indeed EXPTIME-complete, by reduction from Countdown Games(CG) [START_REF] Jurdziński | Model checking probabilistic timed automata with one or two clocks[END_REF].

In [START_REF] Jurdziński | Model checking probabilistic timed automata with one or two clocks[END_REF], Jurdzinski et al. introduce Countdown Games (CG), and prove that the problem of deciding the winner for these games is EXPTIME-complete. We reduce the problem of deciding winner to deciding simulation of PA by giving a construction for PAs A ∀ and A ∃ , for any CG, such that Eloise wins the game iff A ∀ is simulated by A ∃ .

The countdown game is defined as a tuple (Q, , q 0 , k * ) where Q is a finite set of states,

⊆ Q × N \ {0} × Q is a transition relation, q 0 ∈ Q is the initial
state, and k * is the final value. We write q r if (q, , r) ∈ . A configuration of the game is an element (q, k) ∈ Q×N. The game starts in configuration (q 0 , 0) and proceeds in moves: if the current configuration is (q, k) ∈ Q × N, first Player 0 chooses a number with 0 < ≤ k * -k and q r for at least one r ∈ Q; then Player 1 chooses a state r ∈ Q, with q r. The resulting new configuration is (r, k + ). Player 0 wins if she hits a configuration from Q × {k * }, and she loses if she cannot move (and has not yet won).

We proceed by reducing this game to a Simulation game, played between a Duplicator (Eloise) and a Spoiler (Abelard). Thus, Abelard wins if he is able to make a transition on A ∀ which cannot be simulated on A ∃ , and Eloise otherwise.

To explicitly describe the construction, we first define a function λ :

Q → 2 Z + ,
where for each state q, λ(q) = { | ∃q : q q } We also note that the number of positive integers that occur in a CG will be less than the number of edges, and thus cannot be superpolynomial in the size of the description of the game. Let us denote these integers that occur as labels by the set Λ = { 1 , 2 , ...} = q∈Q λ(q) Now let us define A ∀ , as a PA, with the set of states, Q ∀ = {p 0 , p ⊥ , p 1 , p 2 , ...}, with a state for each label in Λ, in addition to an initial state and a dump state. We associate a letter α i from the infinite alphabet Σ, to every integer i ∈ Λ, and define the transitions as:

-For each i ∈ Λ, there is p 0 αi -→ p i and p i + i -→ p 0 , -And finally, we have p 0 β,k=k * -→ p ⊥ , where β ∈ Σ and is not equal to any α i We now define A ∃ as a PA, given a corresponding CG with states Q. The states of A ∃ are Q ∃ = Q {q } ( ), with the following transitions:

-For each q j q in the CG, we have q αj -→ (q, j , q ) and (q, j , q ) + j -→ q -For each q i ∈ Q, we have q i x,x∈Λ\λ(qi) -→ q -For each q i ∈ Q, we have q i

x,k>k * -→ q -And we ensure that q is a universal simulator, ie. q can simulate any PA transition, by allowing q y -→ q and making it a refresh state for y.

Notice that the "macro" transitions p i +αi -→ p 0 and q i x,k>k * -→ q can be translated into a series of transitions of a PA of linear size, by implementing corresponding adders and comparators, using log(k * ) variables, as shown earlier in [START_REF] Belkhir | Parametrized automata simulation and application to service composition[END_REF].

We now show that Player 0 wins the CG iff Abelard wins the corresponding simulation game. In fact, we prove that a configuration (q, k) of CG is a winning configuration for Player 0 iff [A ∀ : (p 0 , k), A ∃ : (q, k)] is a winning configuration for Abelard in the simulation game.

We know that for any configuration of simulation game where A ∃ is at q will be a losing state for Abelard, by definition, since q can simulate all transitions. Similarly, any configuration of simulation game, where A ∀ is at p ⊥ and A ∃ is not at q , will be a winning state for Abelard since Eloise cannot otherwise duplicate a β-transition.

Abelard wins in [A ∀ : (p 0 , k), A ∃ : (q, k)] iff either k = k * , since p ⊥ is then reachable with a β-transition, or k < k * and there exists an α i -transition to a winning state. However, for i / ∈ λ(q), Eloise can move to q , therefore if there exists an α i -transition to a winning state, then i ∈ λ(q). Such a transition can be duplicated only by q αi -→ (q, i , q ), by Eloise for some q , resulting in subsequent duplication of p i + i -→ p 0 with (q, i , q ) + i -→ q . Thus, if k < k * then there exists an α i -transition to a winning state iff there is an i ∈ λ(q) such that for all q such that q αi -→ (q, i , q ) (which iff q j q in CG), [A ∀ : (p 0 , k + i ), A ∃ : (q , k + i )] are all winning states.

Since Player 0 wins in configuration (q, k) iff k = k * or if k < k * and ∃ i ∈ λ(q) : ∀q : q j q =⇒ (q , k + i ) is a winning state, therefore we coinductively prove that Abelard wins in [A ∀ : (p 0 , k), A ∃ : (q, k)] iff Player 0 wins in (q, k).

Therefore the problem of deciding a winner for any CG can be polynomially reduced to the problem of deciding the winner for the simulation game over PAs. This proves that deciding simulation preorder over PAs is EXPTIMEhard, which coupled with previous results, implies that simulation is EXPTIMEcomplete.

Conclusion

We have shown that PAs can be exponentially smaller than NFMAs for some languages and that simulation preorder over PAs is EXPTIME-complete. Finding a good lower bound for deciding simulation preorder over NFMAs, which has an upper bound of EXPTIME, will also reveal more about the relationship between the two models. It is easy to see that it is NP-hard, which also means that for languages where PAs are succinct with respect to NFMAs, while deciding simulation in NFMAs cannot possibly be done in polynomial time in n, checking the same over PAs would require time exponential in log(n), ie. polynomial in n.

A2Fig. 1 .

 1 Fig. 1. Two PAs A 1 and A 2 where the variable y 1 is refreshed in the state p, and the variables x 2 , y 2 are refreshed in the state q.

Fig. 2 .

 2 Fig. 2. A translation schema of NFMA to PA. The registers of the NFMA A are {1, . . . , k}, they correspond to the variables {x 1 , . . . , x k } of the PA A . The variable x l is refreshed in the state p of A .

Lemma 2 .

 2 For every PA A with k variables and n states there is a PA with k + m variables and O(n • (k + m)!) states recognizing the same languages, where m = |Σ A |.

Further, it will be interesting to see if there are interesting subclasses of PAs, for which language containment is decidable or simulation preorder is efficiently decidable.