Zhenpeng Cui

Cecilia Coletta

Alexandre Dazzi

Patrice Lefrancois

Matthieu Gervais

Stéphane Néron

Samy Remita

Radiolytic Method as a Novel Approach for the Synthesis of Nanostructured Conducting Polypyrrole

Keywords: Radiolysis, Conducting polymers, Polypyrrole, Nanostructures, AFM-IR

In this study, a novel and extremely facile method for the synthesis of conducting polypyrrole (PPy) was achieved in aqueous solution. This radiolytic method is totally free of template and environmentally friendly compared with traditional chemical methods. According to ultraviolet-visible (UV-vis) spectroscopy and Fourier transform infrared (FTIR) spectroscopy analysis, pyrrole (Py) monomers were polymerized into PPy thanks to their oxidation by HO• radicals produced by the radiolysis of water when exposed to γ irradiation. The morphology of PPy was characterized by Cryo-transmission electron microscopy (Cryo-TEM) in aqueous solution and by scanning electron microscopy (SEM) after deposition. In an original way, high resolution atomic force microscopy, coupled with infrared nanospectroscopy, is used to probe the local chemical composition of PPy nanostructures. The results demonstrated that spherical and chaplet-like PPy nanostructures were formed by γ-radiolysis. Thermogravimetric analysis (TGA) and electronic conductivity measurements showed that radiosynthesized PPy had good thermal stability and an electrical conductivity higher than that of chemically synthesized PPy.

Introduction

Conducting polymers (CPs), as a novel generation of polymers, [1][2][3] have been intensively investigated due to their intrinsically unique π-conjugated systems which enable their potential applications in various fields such as conducting materials, 4 photovoltaic cells, 5 field effect transistors, 6 chemical or biological sensors and anti-corrosion materials. [7][8][9] Since their discovery, a variety of π-conjugated CPs have been developed and these typical CPs include poly (3,4-ethylenedioxythiophene) (PEDOT), 10 polypyrrole (PPy), 11 polyaniline (PANI) and their derivatives. 12 All these CPs are characterized to possess both environmental stability and high conductivity which are attracting great interests currently. 13 Among these typical CPs, PPy has been mostly investigated due to its relatively easier synthesis and greater stability. Generally, the polymerization of pyrrole monomers, Py, into PPy (Scheme 1) could be achieved by traditional chemical (e.g., K 2 S 2 O 8 , FeCl 3 , H 2 O 2 ) and electrochemical methods while some alternative ways, such as enzymatic method, remain rarely proposed in literature. [14][15][16][17][18] Although the polymerization technologies of chemical and electrochemical methods are quite different, the first step of polymerization corresponds to the preliminary oxidation of Py monomers into their ionic states which systematically preceeds and initiates the polymerization process. 19,20 Although the synthesis of PPy polymers has been widely studied for a long time, many efforts are still being spent on simplifying their preparation and optimizing their properties. 21,22 Compared with the common chemical and electrochemical methods, radiolytic method is based on the interaction of high energy ionizing radiations with matter. Instead of using external oxidative chemicals to initiate polymerization as in the case of chemical method, γ-radiolysis of aqueous solution leads to the quantitative and selective in situ production of radicals which come from the more abundant species present in the medium: the solvent molecules. These radicals, such as hydroxyl radicals (HO•) which are known to be very oxidative species should then act as initiators of PPy synthesis. 23 In this way, the synthetic procedure is easier and environmentally friendly. In other words, water is used as the solvent without addition of chemical oxidants.

We recently, and for the first time in literature, succeeded in the synthesis of a CP in aqueous solution, namely poly (3,4-ethylenedioxythiophene), PEDOT, thanks to the use of different oxidizing species produced by water radiolysis. 24 We showed that the polymerization growth of CP proceeds through a recurrent step-by step oxidation process. This means that for a quantitative polymerization the concentration of oxidizing species must be at least two times higher than that of monomers. Also, we demonstrated that the nature of the oxidizing species produced from water radiolysis determines the morphology as well as the physicochemical properties of the radiosynthesized PEDOT nanostructures. 25 In this work, we extend our original radiolytic methodology to the synthesis of another CP, the polypyrrole (PPy) in aqueous solution under N 2 O atmosphere. Under these conditions, the hydroxyl radical (HO•) produced by water radiolysis should act as an oxidizing species towards Py monomers leading to PPy polymers. For comparison purpose, PPy polymers are also synthesized by traditional chemical method using K 2 S 2 O 8 as oxidant and as polymerization initiator. The morphology and the properties of PPy synthesized by both methods are compared in details.

Experimental

Materials

Pyrrole (Py) (≥ 98%, Sigma Aldrich) was used as monomer and ultrapure water (Millipore system 18.2 MΩ cm) was used as the solvent. K 2 S 2 O 8 (Reagent grade, Touzart & Magnon) was used as the oxidant during chemical polymerization. N 2 O (Air liquid Co.) was used to degas the aqueous solutions of pyrrole before γ irradiation. Acetonitrile solvent (≥ 99.8%, Sigma Aldrich), containing NOBF 4 (≥ 95%, Sigma Aldrich) as the dopant, was used during the electrical conductivity measurements.

PPy synthesis methodologies

Radiolytic method

Within the nanosecond timescale, γ-irradiation of deoxygenated diluted aqueous solutions at neutral pH, generates the following radiolytic species which come from the direct effect of ionizing radiation on the more abundant species, namely water molecules: [START_REF] Spinks | An introduction to radiation chemistry[END_REF][START_REF] Ferradini | [END_REF][28]

G (HO•) = 5.6×10 -7 mol•J -1 (3)
The concentration of hydroxyl radical [HO•] produced by water radiolysis can then be expressed as a function of the irradiation dose, D expressed in Gray (Gy, 1 Gy corresponds to 1 J•kg -1 or 1 J•L -1 for diluted solution) according to:

[HO•] (mol•L -1 ) = D (Gy) × G (HO•) (mol•J -1 ) (4)
As demonstrated in our previous work, 24,25 for quantitative polymerization of CP, the concentration of oxidative species (HO• here) should be twice that of monomers (Py here), [Py] 0 .

As a consequence, the dose D max needed for a quantitative polymerization can be calculated as follows:

D max (Gy) = (5)
It thus amounts to 3.6 kGy for 1 mM in Py and to 72 kGy for 20 mM in Py.

Aqueous solutions containing different concentrations in pyrrole ranging between 1 and 20 mM were prepared. Note that these concentrations are both by far lower than Py solubility in water (0.9 M). These concentrations also remain very much lower than water molecules concentration (55.5 M). This enables to neglect the direct effect of ionizing radiation on Py. Then, the samples were degassed with N 2 O for 20 min and irradiated with a 60 Co γ source (available at LCP laboratoire, Université Paris-Sud) at a dose rate of 6 kGy•h -1 up to D max .

Chemical method

For comparison purpose, PPy was also synthesized by a chemical method. Aqueous solution containing both pyrrole monomers (20 mM) and K 2 S 2 O 8 oxidant (40 mM) was prepared and stirred for another 24 h to ensure that Py monomers fully polymerized into polypyrrole. 29 As in the case of radiolytical method, the molar ratio of monomer to oxidant was 1:2 to ensure quantitative polymerization.

Lyophilization

All the solutions of Py after polymerization were dried by lyophilization with a Heto PowerDry® LL1500 (Thermo Electron Co., France) to obtain dehydrated powders. The drying procedures were carried out as follows: first, all the solutions were transfered to culture dishes and frozen into ices; then, the frozen samples were moved to the drying chamber and lyophilized at -110 o C for 48 h. After lyophilization, all the samples were further directly investigated by ATR-FTIR, SEM and TGA.

Characterization of PPy

UV-vis absorption spectroscopy

In order to check whether the polymerization of pyrrole monomers occurred, Ultravioletvisible (UV-vis) spectra of pyrrole aqueous solutions or suspensions before and after polymerization were recorded on a UV-vis scanning spectrophotometer (HP 8453) in quartz cell with an optical path length of 0.2 cm. The reference was always ultrapure water.

ATR-FTIR spectroscopy

To further identify PPy and its chemical composition, the Fourier transform infrared (FTIR) spectra of lyophilized PPy were recorded using a FTIR spectrometer (Bruker Vertex 70) with diamond ATR attachment (PIKEMIRACLE crystal plate diamond/ZnSe) and MCT detector with a liquid nitrogen cooling system. The lyophilized powder was deposited onto the ZnSe diamond and scanning was conducted from 4000 to 600 cm -1 with a 4 cm -1 spectral resolution for 100 times and averaged for each spectrum.

Cryo-transmission electron microscopy

In order to observe the morphology of radiosynthesized PPy polymers in aqueous solutions, in-situ observation of the morphology of PPy was carried out on a transmission electron microscope in a cryogenic environment (Cryo-TEM), known to be adapted to low density contrasts. A drop of each solution was deposited on ''quantifoil''® (Quantifoil Micro Tools Gmbh, Germany) 200 mesh holey-carbon-coated grids. After being blotted with filter paper, the grids were quench-frozen by being rapidly plunged into liquid ethane in order to form a thin ice film avoiding water crystallization. The grids were then transferred into the microscope using a side entry Gatan 626 cryoholder cooled at -180 o C with liquid nitrogen. Images were taken with an Ultrascan 2k CCD camera (Gatan, USA) by using a LaB6 JEOL JEM 2100 (JEOL, Japan).

Advantages of Cryo-TEM are not only ensuring the observation of soft nanostructures but also avoiding the phase transition and aggregation which should result from the drying procedures.

AFM-IR spectromicroscopy

In order to check whether the radiosynthesized PPy maintained its original morphology during the drying process, after γ irradiation, a small drop of the solution was deposited onto the upper surface of ZnSe prism (transparent in the mid-IR) and dried naturally at air. The dried deposit was observed by nanoIR TM (@Anasys Instruments) an AFM-IR system that combines the AFM with a pulsed infrared OPO laser to perform spectromicroscopy. AFM which has a visible laser focusing on the cantilever and a four quadrants detector measuring its deflection, was used for the superficial morphology characterization in contact mode. [30][31][32] To obtain relevant infrared spectra, the pulsed infrared laser setup covers the wavenumbers from 3600 cm -1 to 1000 cm -1 .

During the measurement, the tip of the AFM remained in contact with the object. When the sample absorbs IR laser pulse, the absorbing region warms via the photothermal effect and a rapid thermal expansion occurs which then impacts the tip of the AFM cantilever and causes its oscillation. As the amplitude of oscillations is proportional to the absorption, scanning the surface with a given wavenumber enables the drawing of chemical map of the sample, while changing the wavelength on a fixed position of the tip gives a local infrared spectrum.

SEM microscopy

In order to check the morphology of PPy polymers synthesized by radiolytic and chemical methods, PPy powder obtained after lyophilization was sprinkled onto carbon tape adhered to aluminum mounts and the images were obtained with EVO MA10 scanning electron microscope (SEM). Magnification, accelerating voltage and scale bar were 5 K X, 150 kV and 1 μm.

TGA analysis

The thermal stability and composition analysis of lyophilized PPy was performed on a thermogravimetric analysis instrument TGA Q500 (TA instruments, USA) under a nitrogen flow of 50 mL/min. The temperature ranged from 40 to 800 0 C at a heating rate of 20 0 C/min.

Conductivity test

To measure the conductivity of PPy, spin-coated films of PPy were obtained by spinning a small drop of PPy suspensions on an ITO substrate. Before measurements, the nanostructures of PPy solutions or suspensions were doped with NOBF 4 at a concentration of 10 -2 M in acetonitrile.

A Kelvin four-point probe technique was used for measuring the resistance of PPy film and a 3

Veeco Dektak 150 surface profiler was used for the thickness measurement of the film.

The conductivity, ρ (S•cm -1 ) was determined thanks to the following equation: (6) where V is the voltage difference (V), t the film thickness (cm) and I the applied current (A).

Results and discussion

HO•-induced oxidation of Py monomers

Aqueous solution containing 1 mM in Py was prepared under N 2 O atmosphere. Its UV-vis absorption spectrum presented in Figure 1 displays the 205 nm characteristic peak of Py monomers which corresponds to a π-π* transition. [START_REF] Silverstein | Spectrometric identification of organic compounds[END_REF] The molar extinction coefficient amounts to: [START_REF] Silverstein | Spectrometric identification of organic compounds[END_REF] We irradiated this solution at increasing doses up to 3.6 kGy and recorded the UV-vis absorption spectra as a function of the dose (results not shown). We reported in Figure 1 (inset), the absorption of Py at 205 nm as a function of the dose. One can observe the decrease of the absorption as a function of the irradiation dose, which means that Py is progressively consumed (according to a pseudo-first order exponential decay).

ε 205 = 6730 L•mol -1 •cm -1 .
The initial radiolytic yield of Py consumption, G -Py0 , corresponds to the value of the initial slope of the curve which can be deduced thanks to an exponential fit of the experiment curve:

G -Py0 (mol•J -1 ) = = 6.0 × 10 -7 mol•J -1 (7)
We clearly find that: G -Py0 ≈G (HO•). This indicates that a concentration of 1 mM in Py is sufficient to scavenge all the HO• radicals produced by radiolysis and demonstrates that only HO• radicals react with Py monomers. Indeed, HO• is a strong oxidizing species since its standard redox potential in neutral medium (pH=7) amounts to E 0′ HSE (HO•/H 2 O) = 2.31 V HSE enabling oxidation of Py (E 0′ HSE (Py + /Py) = 0.76 V ENH ). [START_REF] Koppenol | [END_REF]35 Therefore, it is clear that, in our experimental conditions, the radiation induced polymerization of pyrrole can only be initiated by HO• as expected. Therefore, as previously explained, the dose needed for quantitative polymerization of Py could be easily calculated according to formula (5). In particular, 72 kGy are needed for 20 mM in Py.

3.2

Highlighting γ-PPy radioinduced synthesis, a comparison with chemical synthesis

Identification of γ-PPy by spectroscopic studies

While relatively low concentrations in Py monomers (1 mM, see previous section) were needed for the follow-up of their oxidation mechanism by UV-vis absorption spectroscopy, higher concentrations in Py were used for the characterization of PPy polymers.

Aqueous solutions containing 20 mM in Py were irradiated at doses up to 72 kGy (Figure 2).

We can note that after a 72 kGy-irradiation (spectrum b), only a shoulder is observable at 205 nm indicating that polymerization is indeed almost quantitative at 72 kGy since only a small amount of Py monomers remains in solution. Py disappearance parallels the formation of species which absorb at 300 nm as observed in spectrum b. According to literature, 36 the shoulder at 300 nm should be attributed to terpyrrole. Also, after a 72 kGy-irradiation, continuous scattering (long absorption tail) in the range 400~1000 nm whose intensity increases with irradiation dose, is observed in the extinction spectrum b. This is characteristic of the π-π* transition of PPy materials with higher molecular weight. [36][37][38] This scattering should result from the presence of a black suspension in the medium as observed in Figure 3 (image b). This suspension becomes denser and the solution appears more turbid as the irradiation dose increases. As it will be demonstrated later, this suspension corresponds to PPy polymers formed at high doses thanks to the HO•-induced oxidation process. These polymers formed by radiolysis are called γ-PPy. Note that this suspension remains relatively stable and that no sedimentation process is observed in this case over few days. This may be explained by a relatively low molecular weight of the polymers.

In addition, the absence of any deposition implies that γ-PPy polymers are not hydrophobic.

In order to compare our radiolytic procedure with a more common chemical methodology, we added 40 mM of K 2 S 2 O 8 as oxidant to a solution containing 20 mM in Py (ratio Py/ K 2 S 2 O 8 = 1:2) under stirring. After 24 hours, we recorded the absorption spectrum of the solution (Figure 2, spectrum c). This spectrum is somewhat different from the spectrum b. Indeed, one can note the presence of residual Py monomers characterized by the absorption at 205 nm meaning that, in our experimental conditions, chemical polymerization is less complete than radiation induced one.

While no peak at 300 nm, characteristic of terpyrrole, is observed in spectrum c of Figure 2, a continuous absorption in the range 400~1000 nm is present such as in the case of radiolytical method. This is once again characteristic of PPy materials with higher molecular weight.

Nevertheless, the lower intensity of the extinction spectrum c in comparison with that of spectrum b could be explained by the sedimentation process which was systematically observed in the case of chemical method. Indeed, contrarily to radiolytical method, a black powder deposits in this latter case at the bottom of the solution as observed in Figure 3 (image c).

Thus, as in the case of radiolysis, PPy polymers are formed in aqueous solution thanks to chemical oxidation of Py. These polymers are called χ-PPy. Nevertheless, these chemically synthesized polymers (χ-PPy) should be more hydrophobic than radiosynthesized ones (γ-PPy) or could have higher molecular weight since they precipitate.

In order to perform ATR-FTIR experiments for comparing the chemical nature of both γ-PPy and χ-PPy, the two samples (images b and c of Figure 3) were lyophilized. In both cases, black powder was obtained (images d and e of Figure 3). Note that the solid volume obtained after lyophilization of γ-PPy is higher when the suspension is denser and when the irradiation dose increases. While the powder obtained after irradiation is only polymers, the powder obtained after chemical oxidation should also contain K 2 S 2 O 8 and its conjugated reducing species. This prevents any comparison between the chemical and radiolytical polymerization yields. On another hand, we attempted to estimate the molecular weights of γ-PPy and χ-PPy polymers by Size-Exclusion Chromatography (SEC). However, the solubility of our polymers was too low in the different solvents usually used in SEC chromatography (ethanol, acetone, acetonitrile, THF…).

The ATR-FTIR spectrum of γ-PPy is presented in Figure 4 (spectrum b) in the wavenumber region 600~4000 cm -1 together with those of χ-PPy (spectrum c) and pure non irradiated Py liquid sample (spectrum a). Note that the deposition of Py liquid phase is translated by a better resolution when compared with the solid phase deposition of polymer films.

The three obtained spectra are in good agreement with those previously reported for Py and PPy in literature. 36,39,40 In addition, no significant difference exists between spectra b and c. Only small shifts in the vibration mode can be observed. Starting from what is known in literature about Py, vibration at 3396 cm -1 observed in spectrum a can be attributed to the in plane stretching of N-H. 38,41 The bands at 1571 and 1467 cm -1 are due to C-C in-ring-stretch mode and stretching vibration of pyrrole rings respectively. 29,39 The band at 1047 cm -1 is mostly attributed to C-C out-of-plane deformation vibration. 39,41 The strong band at 726 cm -1 results from the C-H wag vibration at α, α′ positions. 40 After polymerization, the C-H wag vibration and N-H in plane stretching, observed in spectra b and c, decrease obviously indicating that free pyrrole monomers are not observable here, suggesting that polymerization of pyrrole is relatively quantitative.

In the case of chemically synthesized PPy (Figure 4, spectrum c), the broad band at 3120 cm -1 corresponds to the stretch of N-H bond and the peak at 1700 cm -1 corresponds to the stretch of C=O. 42 The presence of this latter bond seems surprising. Nevertheless, C=O bond has already been observed in literature in the case of chemical polymerization of Py and assigned to the overoxidation of polypyrrole. 36 The bands at 1556, 1481 and 1043 cm -1 correspond to stretching mode of C=C, C-N and C-C out-of-plane vibration indicating the formation of PPy. 39 The bands at 1184 and 916 cm -1 are attributed to the S=O group and stretching vibration of PPy showing that chemically synthesized PPy is doped with the oxidant. 29,41 In the case of PPy synthesized by radiolytical method (Figure 4, spectrum b), some bands are more or less displaced. The bands at 1180, 1099 and 1045 correspond to C-H, =C-H in-plane and C-C out-of plane vibration proving the successful preparation of PPy. 36,39,41 Nevertheless, there is an obvious carbonyl C=O group peak at 1674 cm -1 which is more intense than the C=O peak observed at 1700 cm -1 in the case of χ-PPy. The presence of this peak obviously demonstrates that γ-PPy is overoxidized. 36,43 The spectrum of γ-PPy also exhibits a very large band around 3251 cm -1 . As in the case of χ-PPy (spectrum c), this band is attributed to the N-H bond. The observation of such a very large band should result from the N-H groups of the polymers. On the other hand, this very large and relatively intense band observed in the case of γ-PPy could also come from the -OH functionalization of the polymers by HO• radicals. This has already been established in the case of radiation induced synthesis of PEDOT and is in very good agreement with literature since HO• radicals are known to add to the double bonds of organic molecules. 39,44,45 .

Therefore, PPy was successfully synthesized by both radiolytical and chemical methods.

Nevertheless, radiosynthesized PPy polymers could be functionalized by both O-H and C=O groups which should then explain their higher hydrophilicity in comparison with that of χ-PPy.

As the solubility in water of PPy synthesized by radiolytic method (γ-PPy) is relatively high, the in-situ observation of the morphology of γ-PPy is possible by Cryo-TEM. Aqueous solutions containing 20 mM in Py and irradiated at 72 kGy were observed by cryo-transmission electron microscopy just after irradiation. Representative images showed the presence of low density globular structures forming polydisperse spherical nanoparticles the diameter of which was comprised between 80 and 200 nm as observed on Figure 5a (mean diameter of 100 nm). Also, these particles systematically appeared self-assembled into nanochaplets as observed in Figure 5b.

These results are in good agreement with previous observations reported in literature concerning such polymer systems. 46,47 Since no other low density objects were observed during Cryo-TEM experiments, we deduce that these more or less spherical nanoparticles are made up of radiosynthesized PPy polymers.

Each globular structure observed on Figure 5 should correspond to the self-assembly of independent amorphous PPy polymer chains which interact all together by Hydrogen-bonds as already reported in literature. 45,48 Also, the packing of the polymers into supramolecular nanochaplets should also result from such intermolecular interactions.

In order to definitely prove the PPy nature of these spherical nanoparticles, in order to characterize the morphology of the polymers after a deposition procedure and also to check whether a drying process is able to affect the morphology of PPy, a drop of the solution containing the PPy black suspension obtained after a 72 kGy-irradiation (polymers of Figure 5)

was deposited onto a ZnSe prism, then dried naturally at air, and finally imaged and characterized by AFM-IR as shown in Figure 6. According to the AFM image of γ-PPy recorded in contact mode (Figure 6a), the top dark areas having no thickness correspond to the substrate. The topography of γ-PPy displayed as the bright areas correspond to the thicker regions made up of isolated bigger spherical PPy nanoparticles and closely packed smaller ones (200~300 nm in average). 49 This AFM observation agrees well with the morphology of γ-PPy particles previously observed in aqueous solution by Cryo-TEM (Figure 5) without any significant change in the mean size and in the shape. Then, the packing of the particles and their flattening onto the substrate when deposited and dried do not seem to affect the morphology of γ-PPy polymers.

In order to confirm that the nanoparticles observed by Cryo-TEM (Figure 5) and by AFM in contact mode (Figure 6a) are made-up of PPy polymers, the sample was observed by AFM-IR in the range of 1600~1800 cm -1 (Figure 6b). The spectrum of Figure 6b displays a peak at 1674 cm -1 which is characteristic of C=O bonds. Now, these bonds have been detected by ATR-FTIR spectroscopy in γ-PPy polymers (Figure 4, spectrum b) and not in Py monomers (Figure 4, spectrum a). This demonstrates that the globular structures observed in both Figure 5 and Figure 6a contain close-packed PPy polymers.

Since the AFM-IR technique also enables the chemical mapping of the sample, this wavenumber 1674 cm -1 was chosen for AFM-IR chemical mapping of our sample (Figure 6c). In Figure 6c, the red and yellow areas indicate a stronger absorption at the characteristic wavenumber which is caused by a thick layer of γ-PPy (~500 nm) linked onto the prism.

Compared with the topography of the sample (Figure 6a), we notice that these thick areas correspond to the bright regions of the γ-PPy. As the distribution of γ-PPy nanoparticles on the prism is inhomogeneous, the appearance of AFM-IR is not totally the same as its topography.

Nevertheless, the signal of AFM-IR (Figure 6c) fits well with the thickness of γ-PPy (Figure 6a).

Thus, we can definitely assume that the nanoparticles observed on Figure 6 are essentially composed of γ-PPy polymers. Nevertheless, the presence of some residual Py monomers trapped into PPy nanoparticles couldn't be totally excluded.

This result does not only prove that radiosynthesized PPy are spherical nanoparticles but also further explains their hydrophilicity and their packing into nanochaplets. Indeed, the presence of C=O bonds at the surface of the PPy nanoparticles, as demonstrated by AFM-IR, should enhance the probable effect of O-H functionalities, leading to strong hydrogen-bonds interactions between the self-assembled nanoparticles as well as with the aqueous solvent.

In order to check whether the lyophilization procedure and whether the substrate nature affect the morphology of γ-PPy nanoparticles, the lyophilized PPy powder obtained after a 72 kGy-irradiation was observed by SEM microscopy. Typical image is displayed on Figure 7a.

Once again, γ-PPy polymers appear as more or less spherical nanoparticles with a mean size of 100 nm. This definitely proves that the presence of the solvent, that the lyophilization, that the nature of the substrate have no influence on the morphology of the polymers. This would imply the existence of very strong hydrogen-bond interactions into each nanoparticle.

In order to compare the morphology of γ-PPy with that of χ-PPy, the lyophilized PPy powder obtained in the presence of 40 mM in K 2 S 2 O 8 was also observed by SEM (Figure 7b). χ-PPy polymers also appear as more or less close-packed spherical nanoparticles. 50 However, the value of the mean-size (~200 nm) and that of the polydispersity are much higher than those corresponding to γ-PPy. This result proves that our radiolytic methodology does not only lead to more hydrophilic PPy polymers, but also to smaller and less polydisperse PPy nanoparticles. The lower hydrophilicity and the bigger size of χ-PPy nanoparticles in comparison with those of γ-PPy structures could explain their sedimentation observed just after their chemical synthesis into water (Figure 3, image c).

Physico-chemical properties of γ-PPy, a comparison with χ-PPy

Thermal stability

We wanted to check and to compare the thermal stability of γ-PPy and χ-PPy previously synthesized and obtained as powders after lyophilization. The thermo gravimetric analysis (TGA) plots of both PPy polymers are shown in Figure 8. The inset displays the temperature at which the weight loss of PPy occurs. In the case of γ-PPy (Figure 8a), the weight loss exhibits three stages of decomposition which is in agreement with literature. 51 From 40 to 100 0 C, the main loss of weight happens at 50 0 C which may be caused by the loss of some unreacted pyrrole. Then, in the range 100-400 0 C, the weight loss at 176 0 C may be caused by the loss of terpyrrole which was observed by UV-visible absorption spectroscopy (Figure 2, spectrum b), while the main weight loss which occurs at about 330 0 C may correspond to the decomposition of some γ-PPy oligomers characterized by relatively low molecular weights. 36 Finally, the decomposition of the backbone of PPy occurs around 600 0 C. This TGA analysis is in very good agreement with TGA data already reported in literature concerning PPy polymers. 41,52 Note that the same thermal stability is found for χ-PPy as observed on Figure 8b. This result indicates that the size of the PPy polymer nanoparticles as well as their functionalization by C=O or O-H groups seem to have no effect on their thermal behavior.

Electrical conductivity

We wanted to check and to compare the electrical conductivity of γ-PPy and χ-PPy by four point probe technique. In this aim, we doped both samples with NOBF 4 (10 mM). We found that the electrical conductivity of χ-PPy is 1.2 ×10 -2 S•cm -1 . This value is similar to those reported in literature. 53 Nevertheless, the electrical conductivity of γ-PPy synthesized by our original radiolytical procedure was found to be higher: 5.7×10 -2 S•cm -1 . This result proves that, even if the thermal stability of γ-PPy is not better than that of χ-PPy, the value of the electrical conductivity of γ-PPy is nearly five times higher than that of χ-PPy. The higher conductivity of γ-PPy could be related to the smaller particles size and the bigger surface areas. 54,55 Indeed, as the diameter decreases, more ordered chains of connected structure of γ-PPy networks could counteract the influence of insulated cavities and bigger surface areas could enhance the delocalisation of charge carriers over an extended region of the polymer chains. We think that both aspects contribute to a relatively higher electrical conductivity of γ-PPy.

Conclusion

We recently succeeded in the development of a new -radiolysis-based alternative way for synthesizing PEDOT polymers in solution. In the present paper, we extended this methodology as an alternative green way for the synthesis of conducting PPy polymers in aqueous solution.

PPy polymers synthesized by radiolysis are characterized by a very good long-term stability at air in a humid environment. We showed that the as-prepared PPy polymers remain welldispersed in water, can be easily dried and are quite simply redispersed in protic solvents. As revealed by ATR-FTIR spectroscopy, the probable presence along the polymeric chains of O-H and C=O functionalities, which should come from the addition of hydroxyl radicals during the polymer growth, could explain the hydrophilic properties of the radiosynthesized PPy polymers.

This could also justify the existence in aqueous solution of the globular self-assembled structures made up of PPy polymeric chains and their packing into nanochaplets as observed by cryo-TEM.

After deposition onto substrate, the radiosynthesized PPy polymers appear as more or less spherical nanoparticles as revealed by AFM and SEM observations. Moreover, in an original way, high resolution atomic force microscopy, coupled with infrared nanospectroscopy was used to probe the local chemical composition of PPy nanostructures.

A detailed investigation enabled the comparison between the properties of radiosynthesized PPy and those of PPy synthesized by a conventional chemical polymerization. We found that radiosynthesized PPy nanoparticles are more hydrophilic, smaller and less polydisperse than chemically synthesized PPy. Besides, we demonstrated that radiosynthesized PPy nanostructures are characterized by a very good thermal stability and an electrical conductivity which is five times higher than that of chemically synthesized PPy.

Work is in due course in order to enhance the conductivity of radiosynthesized PPy polymers by the way of the improvement of their doping level and thanks to the increase in their conjugation length. Also, in order to control the growth and the morphology of the radiosynthesized PPy polymers, soft templates such as hexagonal mesophases or spherical micelles will be used.

Finally, the study of the influence of polymerization mechanism remains poorly investigated in literature in the field of conducting materials. We thus aim to progress in this domain in order to find out the better way to optimize the preparation of nanostructured conducting polymers with adjusted morphologies and tuned properties. Pulsed radiolysis studies are underway in order to identify the first steps of the polymerization mechanism and in order to better understand the growth process of PPy polymers in aqueous solution.

Scheme 1 . 20 Figure 1 Figure 1 . 21 Figure 2 Figure 2 . 22 Figure 3 Figure 3 . 23 Figure 4 Figure 4 . 24 Figure 5 Figure 5 . 25 Figure 6 Figure 6 . 26 Figure 7 Figure 7 . 27 Figure 8 Figure 8 .

 120112122223323442455256626772788 Scheme 1. Chemical structures of pyrrole (Py) and polypyrrole (PPy). The free α, α′ positions at which polymerization occurs are shown in the pyrrole structure.

ACKNOWLEDGEMENTS

We acknowledge the financial support from the China Scholarship Council (CSC). We thank Fabrice Goubard and Pierre-Henri Aubert (LPPI, Université Cergy-Pontoise, France) for conductivity measurements. Also, we thank Jean-Michel Guigner (IMPMC, Université Pierre et Marie Curie, France) for Cryo-TEM experiments.

AUTHOR INFORMATION

*Corresponding author. E-mail: samy.remita@u-psud.fr. Tel.: +33 (0)1 69 15 44 41;


Adrien Boiret

Vincent Hugot

Joachim Niehren

Ralf Treinen

Logics for Unordered Trees with Data Constraints on Siblings

We study counting monadic second-order logics (CMso) for unordered data trees. Our objective is to enhance this logic with data constraints for comparing string data values attached to sibling edges of a data tree. We show that CMso satisfiability becomes undecidable when adding data constraints between siblings that can check the equality of factors of data values. For more restricted data constraints that can only check the equality of prefixes, we show that it becomes decidable, and propose a related automaton model with good complexities. This restricted logic is relevant to applications such as checking well-formedness properties of semi-structured databases and file trees. Our decidability results are obtained by compilation of CMso to automata for unordered trees, where both are enhanced with data constraints in a novel manner.

Introduction

Logics and automata for unordered trees were studied in the last twenty years mostly for querying Xml documents [START_REF] Seidl | Numerical document queries[END_REF][START_REF] Boneva | Automata and logics for unranked and unordered trees[END_REF][START_REF] Zilio | XML schema, tree logic and sheaves automata[END_REF] and more recently in the context of NoSql databases [START_REF] Benzaken | Static and dynamic semantics of NoSQL languages[END_REF]. They were already studied earlier, for modeling syntactic structures in computational linguistics [START_REF] Smolka | Feature constraint logics for unification grammars[END_REF] and records in programming languages [START_REF] Smolka | Records for logic programming[END_REF][START_REF] Müller | The First-Order theory of ordering constraints over feature trees[END_REF][START_REF] Niehren | Feature automata and recognizable sets of feature trees[END_REF]. In our own work, we also find them relevant to the modeling and static verification of file trees, i.e. structures representing directories, files, their contents etcetera, and their transformations, i.e. programs or scripts moving, deleting, or creating files.

Using unordered trees means expressing and evaluating properties on setsor multisets -of elements, e.g. the data values of the children at the current position. Naturally, this amounts to counting: for instance in a file tree "there are at least 2 values that match *.txt" (where * matches any string), or in a bibliographical database "there are fewer values inproceedings than book". Where the existing approaches differ is in the expressive power available for that counting; for instance, is it possible to compare two variable quantitiesas in the second example -or just one variable quantity and a constant -as in the first. In all cases, however, each element is considered alone, in isolation from its brothers. We previously studied the complexity of decision problems for automata using various such formalisms as guards for their bottom-up transitions in [START_REF] Boiret | Deterministic Automata for Unordered Trees[END_REF]. The focus was on devising good notions of deterministic machines capable of executing such counting operations, sufficiently expressive but allowing for efficient algorithms. Our present focus, in contrast, is to extend the expressive power of the counting formalisms, while preserving decidability. Since the bottomup automaton's structure does not play a great role in that, and the yardsticks of expressive power for counting tests are logics, this paper mostly deals directly with second-order logics rather than automata.

Our main goal in this paper is to extend existing formalisms with the ability to express data constraints on unordered data trees, so that each data value may be considered not only in isolation, but also along with sibling values with which it is in relation. Such constraints arise naturally in various circumstances.

By way of example, consider a directory containing L A T E X resources, which may be represented by an edge-labeled tree in the style of Figure 1, given in Json (JavaScript Object Notation) syntax, where each data value corresponds to a file name or, in the case of leaves, file contents.

Suppose that we want to check whether the contents of a L A T E X repository have been properly compiled, which is to say that for every main L A T E X file -i.e. a file whose name has suffix ".tex", and whose contents begin with "\documentclass"there exists a corresponding pdf file following the version 1.5 of the standard.

To express this property, sibling data values -here representing files in the same directory -are put in relation by

θ tex2pdf = { (w".tex", w".pdf") | w is a word } . (1)
Schematically, we express constraints of the form "any value d whose subtree satisfies some property P has a brother d = θ tex2pdf (d) whose subtree satisfies another property P ".

We need to integrate that kind of data constraints in existing formalisms for unordered trees; the two yardsticks of expressive power that have emerged in the literature are the extensions of weak monadic second-order logic (Mso) by horizontal Presburger constraints [START_REF] Seidl | Numerical document queries[END_REF], and by the weaker, but more tractable, counting constraints [START_REF] Courcelle | The monadic second-order logic of graphs. i. recognizable sets of finite graphs[END_REF], capable of expressing that the cardinality of a set variable is less than m or equal to m modulo n, but not of comparing the cardinalities of two set variables directly, unlike Presburger logic. We choose Mso with counting constraints as our starting point, which we write CMso. We denote by Γ (Θ) and CMso(Θ) the extensions of counting constraints and CMso, respectively, with tests on siblings for a certain class Θ of binary relations on data words. Provided that this class contains the relation θ tex2pdf defined above, our example property that, everywhere in the file tree, every T E X file has a corresponding pdf is expressed by the CMso({

θ tex2pdf }) formula ∀x . x ∈ (#( * ".tex" ∧ X doc ∧ ¬θ tex2pdf .X pdf15 ) = 0) (2)
where X doc and X pdf15 are free set variables assumed to contain the nodes satisfying the "main T E X file" and "valid pdf" properties. Intuitively: "all nodes in the file tree are among the nodes such that the number of their children whose label matches *".tex", which are main T E X documents, and for which there does not exist a corresponding *".pdf" sibling that is a pdf version 1.5, is zero." We shall give the full, closed formula at the end of Sec. 3

[p5] .
Note that, even for ordered data words and in the case of equality tests, -simpler than even the suffix correspondences exemplified by θ tex2pdf -satisfiability, and the emptiness problem in the case of automata, become rapidly intractable or undecidable. This has been studied for register automata, first-order logic, and XPath, [START_REF] Bojanczyk | Two-variable logic on data words[END_REF][START_REF] Figueira | On XPath with transitive axes and data tests[END_REF], among others. For instance, satisfiability of F O 2 (=, +1, <), i.e. firstorder logic with two variables and successor and linear order relations, while decidable, is not known to be primitive recursive [START_REF] Bojanczyk | Two-variable logic on data words[END_REF]. Unorderedness simplifies matters in this case.

Nevertheless, the choice of the class of string relations Θ to which we have access in our constraints greatly influences the complexity and decidability of the counting constraints using them. We have found that even relatively conservative choices of Θ entail undecidability: merely allowing the replacement of factors of up to three letters, or the addition and deletion of suffixes and prefixes of one letter, suffices. However, we exhibit a relatively large class which is decidable, and capable of expressing that the prefixes of two data values are the same, or even in the same regular language, while the suffixes belong to two different languages; this largely covers our envisioned applications. We have also found further restrictions for which the complexities become more reasonable.

Outline:

After a few preliminaries, Section 3 introduces the logic CMso(Θ), which is CMso extended with the ability to put an edge's data value in relation with one of its siblings', the string relation being a member of Θ. In Section 4, we show that if relations allow both prefix and suffix manipulations, even restricted to addition or removal of a single letter, CMso(Θ) becomes undecidable. After recalling the logic WSkS, which covers a large class of suffix-only manipulations, Section 5 shows that CMso(Θ WSkS ), where allowed relations are WSkS-definable relations, is decidable in non-elementary time, by translating it into automata with horizontal tests in WSkS. Section 6 presents an algorithm that decides emptiness for the automaton model equivalent to a fragment of the logic where string relations are limited to disjoint suffix replacements. Its complexity is NExpTime -or PSpace if the automaton is deterministic. Section 7 concludes and hints at possible extensions and different ways of tackling the problem.

MSO and Counting Constraints

We recall the definition of MSO and of counting constraints. As models we restrict ourselves to data trees, even though general graph structures could be chosen.

Data

("file.tex", {| ("\doc...", {| | }) | }), ("dir", . . . ) | }.
To simplify the formalisation, we shall not manipulate edges as distinct objects, but instead see an edge label as a property of the node into which the edge leads. Thus we assimilate t to a structure V t , t , ↓ t , where V t is the set of nodes of t, t (v) is the data value labeling the edge leading into the node v -undefined for the root node, -and v ↓ t v holds if v is a child of v. For our convenience, we also define the "sibling-or-self" relation:

v t v ⇔ ∃v . v ↓ t v ∧ v ↓ t v
. By extension of the language of ranked trees, we use the word arity to refer to either the multiset of outgoing edge labels of a node, or the set of outgoing edges.

MSO.

Let A be a data alphabet and X a countable set of variables of two types, node variables and set variables. A variable assignment I into some tree t will map any node variable x ∈ X to a node I(x) ∈ V t and any set variable X ∈ X to a set of nodes I(X) ⊆ V t .

As a parameter of our logic we assume a set Ψ of formulae called node selectors, which may contain letters from A and variables from X . The only assumption we make is that any node selector ψ ∈ Ψ defines for any tree t and variable assignment I into t a set of nodes ψ t,I ⊆ V t . For instance, we could choose

Ψ = Ψ 0 = {π | π regular expression over A} ∪ {↓ x | x ∈ X node variable} such that π t,I = {v | t (v)
matches π} is set of all nodes whose incoming edge is labeled by a word in A * that matches regular expression π, and ↓ x t,I = {v | v ↓ t I(x)} is the set of nodes of which I(x) is a child. Or else, we could also choose Ψ = Ψ 0 ∪ {↓ X | X ∈ X set variable}, where a formula ↓ X requires that some child belongs to I(X). The formulae of MSO over Ψ are:

ξ ∈ Mso(Ψ ) ::= x ∈ ψ | x ∈ X | ∃x . ξ | ∃X . ξ | ξ ∧ ξ | ¬ξ ,
were ψ ∈ Ψ . Whether a formula is true for a given tree t and variables assignment I into t is defined as follows:

t, I |= x ∈ ψ ⇔ I(x) ∈ ψ t,I t, I |= ξ ∧ ξ ⇔ t, I |= ξ and t, I |= ξ t, I |= x ∈ X ⇔ I(x) ∈ I(X) t, I |= ¬ξ ⇔ not t, I |= ξ t, I |= ∃x . ξ ⇔ t, I[x → v] |= ξ for some v ∈ V t t, I |= ∃X . ξ ⇔ t, I[X → V ] |= ξ for some finite V ⊆ V t
As syntactic sugar, we will freely use the usual additional logical connectives and set comparisons that can be easily encoded, i.e. formulae ∀x.ξ, ∀X.ξ, ξ ⇔ ξ , ξ ⇒ ξ , as well as X ⊆ X , X = ψ, and ψ = ∅ .

Children Counting Constraints.

A children counting constraint selects a node of a tree by testing the number of its children satisfying some property. Which properties can be tested is defined by the parameter Φ of node selectors. As before, we use as parameter set of node selectors Φ such that φ t,I ⊆ V t is defined for all φ ∈ Φ, and which may contain variables in X and letters in A. For instance, we could chose Φ = {π | π regular expression over A} ∪ X . A counting constraint over Φ is a formula with the following syntax, where φ ∈ Φ and n, m are natural numbers including 0:

γ ∈ Γ (Φ) ::= #φ n | #φ ≡ m n | γ ∧ γ | ¬γ .
The first two kinds of formulae can test whether the number of children satisfying φ is less or equal to n or equal to n modulo m. Note that we cannot write #φ #φ , which would lead to the richer class of Presburger formulae.

Any counting constraint γ defines a set of nodes γ t,I for any variables assignment I to t, so counting constraints themselves can be used as node selectors:

#φ n t,I = { v ∈ V t | Card({ v | v ↓ t v ∧ v ∈ φ t,I }) n } , #φ ≡ m n t,I = { v ∈ V t | Card({ v | v ↓ t v ∧ v ∈ φ t,I }) ≡ m n } , γ ∧ γ t,I = γ t,l ∩ γ t,l , ¬γ t,I = V t \ γ t,l .
Note that we define #φ n as ¬(#φ n) ∧ ¬(#φ ≡ n+1 n), and thus we can also define #φ = n.

Counting MSO for Data Trees: CMso(Θ)

We now introduce counting MSO for data trees with comparisons of sibling data values. Which precise comparisons are permitted is a parameter of the logic.

As before we assume a set of variables X and a data alphabet A. In addition, we fix a set Θ of binary relations on A * that are called string comparisons. We then define a set of node selectors with regular expressions for matching data values and comparisons of sibling data values from Θ. Such a node selector has the following syntax where θ ∈ Θ, π is a regular expression over A, and x, X ∈ X : The sets of selected nodes are defined as follows for formula φ ∈ Φ rel , any tree t and variable assignment I into t:

φ ∈ Φ rel (
π t,I = {v | t (v) matches π} φ ∧ φ t,I = φ t,I ∩ φ t,I x t,I = {I(x)} ¬φ t,I = V t \ φ t,I X t,I = I(X) θ.φ t,I = {v | ∃v . v t v ∧ ( t (v), t (v )) ∈ θ ∧ v ∈ φ t,I }
In particular, a node selector θ.φ selects all nodes that have a sibling-or-self, so that the data values of these two nodes satisfy comparison θ.

Definition 1. We define the children counting contraints for data trees with comparisons of data values Γ (Θ) by Γ (Φ rel (Θ)) and the counting MSO for data trees with comparison of sibling data values CMso(Θ) by Mso(Γ (Θ)).

Note that the childhood x ↓ x can be defined in CMso(Θ) by x ∈ (#x = 1) independently of the choice of Θ. Hence, sibling-or-self contraints x

x can also be defined by ∃x . (x ↓ x ∧ x ↓ x ) for any Θ. The elements of Θ intervene only if one wants to compare the data values of sibling nodes.

Example 1. Recall the T E X compilation example of equation [START_REF] Benzaken | Static and dynamic semantics of NoSQL languages[END_REF] [p3] and its free variables. There remains to bind X doc and X pdf15 to the relevant sets of nodes in a closed formula. A T E X main document (resp. a valid pdf version 1.5) is represented by a node with a single outgoing edge, whose label is prefixed by "\documentclass" (resp. "%PDF-1.5"), leading to a leaf. Thus the closed CMso({ θ tex2pdf }) formula:

∃X leaf . ∃X doc . ∃X pdf15 . X leaf = (#( * ) = 0) ∧ X doc = (#( * ) = 1 ∧ #("\documentclass" * ∧ X leaf ) = 1) ∧ X pdf15 = (#( * ) = 1 ∧ #("%PDF-1.5" * ∧ X leaf ) = 1) ∧ ∀x . x ∈ (#( * ".tex" ∧ X doc ∧ ¬θ tex2pdf .X pdf15 ) = 0) .
Example 2. Another useful thing to require of a data tree is the feature tree property, stating that no two sibling edges may share the same label. This property can be used to specify files systems, since one needs to state that no two files in the same directory have the same name. Taking θ id as the identity relation, we can define feature trees in CMso({θ id }) as follows:

∀x . (#(x ∧ θ id .¬x) 1) = ∅ .
Example 3. Consider now a transformation θ bck , which to w associates w".bck", thus relating a file's name to that of its automatic backup. Suppose that the system can back up a backup, and so on, up to a certain point, and we need to check that this bound is not overstepped. That is to say, given n ∈ N, we want to write a formula ξ n enforcing that there is no chain of backups of length greater than n. Suppose we had a least-fixed point operator µ among our child-selectors, following the syntax -µX.φ -and semantics of µ-calculus. Then we could write ξ n in CMso({θ bck }):

∀x . (#µX.(x ∨ θ bck .X) > n + 1) = ∅ .
µX.(x ∨ θ bck .X) intuitively captures the set of nodes related to x by successive iterations of θ bck ; we can do the same thing without needing µ by explicitly binding a set variable Y to the least fixpoint of x ∨ θ bck .X, wrt. X:

∀x . ∃Y . (#((x ∨ θ bck .Y ) ∧ ¬Y ) 1) = ∅ ∧ Y . Y ⊆ Y ∧ (#((x ∨ θ bck .Y ) ∧ ¬Y ) 1) = ∅ ∧ ∀x . [#Y > n + 1] = ∅ .
The first line establishes Y as a fixed point, as it means that there are no nodes with a child satisfying x ∨ θ bck .Y but not Y . The second line states that there is no smaller fixpoint than Y . This encoding can be generalised to any use of µ.

Undecidable Instances of CMso(Θ)

In this section, we exhibit conditions on the expressive power of the class of data constraints Θ sufficient to render satisfiability for Γ (Θ), and therefore for CMso(Θ), undecidable. As we shall see, not much is needed. Even merely allowing Θ to express the addition or removal of a single letter at the beginning or end of a word is enough; the argument developed in the next theorem is that even this is sufficient to encode the solution of the Post Correspondence Problem. Theorem 1. Let Θ 1 be the set of string relations of the forms w → wa, w → aw, wa → w, or aw → w, with a ∈ A, w ∈ A * . Then CMso(Θ 1 ) is undecidable.

Proof. We reduce PCP, with input dominoes [ u1 v1 ], . . . , [ un vn ]. Let us write the relations in Θ 1 as θ +a , θ a+ , θ -a , and θ a-, respectively. Given a word w = a 1 . . . a m , by abuse of notation we abbreviate θ +am . . . . θ +a1 .φ into θ +w .φ. Although Θ 1 is not closed by composition, this construction enables us to pretend that it is -the difference is that it requires the existence of siblings for each intermediate step, which does not affect us. θ -w .φ is defined likewise. θ a1+ . . . . θ am+ .φ is written θ w+ .φ, and likewise for θ w-.φ. Let $ 1 , $ 2 ∈ A be symbols not appearing in any domino, serving as markers for the first and the second phase of the construction. The mirror of u is written u. The operation for "placing domino i around previous dominoes" is defined as θ i .φ ≡ θ $1+ .θ ui+ .θ +vi .θ $1-.φ; "accepting dominoes" is θ acc .φ ≡ θ $2+ .θ $1-.φ; "reading a on both ends" is θ a .φ ≡ θ $2+ .θ -a .θ a-.θ $2-.φ. Abbreviating θ. * or θ.true into simply θ, consider now the formula γ

∈ Γ (Θ 1 ) = #$ 1 = 1 ∧ #$ 2 = 1 ∧ #($ 1 * ∧¬(θ 1 ∨ • • • ∨ θ n ∨ θ acc )) = 0 ∧ #($ 2 * ∧¬( a =$1,$2 θ a )) = 1 .
It is satisfiable iff there is a tree whose arity contains $ 1 , $ 2 , and such that every label beginning with $ 1 (i.e. phase one) has a sibling (along with the intermediate siblings) obtained either by placing some domino so that u i mirrors v i , staying in phase one, or by moving to phase two. At this point, a label is of the form $ 2 u i k . . . u i1 v i1 . . . v i k . Furthermore, all but one label beginning with $ 2 (i.e. all but $ 2 ) have a sibling obtained by removing the same letter at the beginning and the end; all letters must be read until only $ 2 remains. Thus, γ is satisfiable iff there are i 1 , . . . , i k such that u i1 . . . u i k = v i1 . . . v i k . This shows that Γ (Θ 1 ) is undecidable. This carries over to CMso(Θ 1 ): consider the formula ∃x . x ∈ γ.

Satisfiability of CMso(Θ WSkS ) is Decidable

We shall now see that, in spite of the bleak picture painted by the previous section, Θ can be made rather large and useful without forgoing decidability. Indeed, the most frequent operation in applications, illustrated in particular by the T E X example [START_REF] Abiteboul | Recursive queries on trees and data trees[END_REF] [p2] , is suffix replacement. The property that we really need is thus decidability of satisfiability for CMso(Θ suffix ), where the relations of Θ suffix are of the form θ u,u = { (wu, wu ) | w ∈ A * }, for u, u ∈ A * . We show decidability for a class that is actually more general: WSkS-definable relations.

The well-known logic Weak Monadic Second-Order Logic with k Successors (WSkS) [START_REF] Büchi | Weak second-order arithmetic and finite automata[END_REF], for any k 1, is based on first-order variables z, and second-order variables Z. Terms τ and formulae ω of this logic are defined by

τ ::= | z | τ i 1 i k ω ::= τ = τ | τ ∈ Z | ω ∧ ω | ¬ω | ∃z . ω | ∃Z . ω
First-order variables range over words in { 1, . . . , k } * , and second-order variables range over finite subsets of { 1, . . . , k } * . The constant denotes the empty word, and each of the functions i, written in postfix notation, denotes appending the symbol i at the end of a word. Validity and satisfiability of formulae in WSkS are decidable [START_REF] Thatcher | Generalized finite automata theory with an application to a decision problem of second-order logic[END_REF], even though with a non-elementary complexity [START_REF] Stockmeyer | Word problems requiring exponential time[END_REF]. Some useful relations expressible in WSkS are z pref z (prefix partial order on words), z lex z (lexicographic total order on words), z ∈ r for any regular expression r, Z ⊆

Z , Z = Z ∪ Z , Z = Z ∩ Z , Z = Z (complement), Z = ∅, |Z| ≡ n m
for any constants n, m. Most of those are shown in [7, p88].

The unary predicates on words definable in WSkS are precisely the regular sets [START_REF] Rabin | Automata on Infinite Objects and Church's Problem[END_REF][START_REF] Läuchli | Monadic second order definable relations on the binary tree[END_REF]

. A binary relation R ⊆ { 1, . . . , k } * × { 1, . . . , k } * is called special if it is of the form { (ab, ac) | a ∈ L, b ∈ M, c
∈ N } for some regular sets L, M , and N . A binary relation on words is definable in WSkS iff it is a finite union of special relations [START_REF] Läuchli | Monadic second order definable relations on the binary tree[END_REF]. Some relations which are known not to be expressible in WSkS are z = z z , z = iz , z is a suffix of z , z and z have the same length, Z and Z have the same cardinality. Let us note that what is definable largely includes the kinds of suffix manipulations which we need for applications and, conversely, that the dangerous properties highlighted in the previous section are not expressible: one cannot manipulate suffixes and prefixes at the same time.

Let Θ WSkS be the set of WSkS-definable relations, with the letters of A taken as successor functions, along with a fresh letter $; we sketch the proof of decidability of CMso(Θ WSkS ). Child-selectors φ and counting constraints ψ are encoded into WSkS, and thus shown decidable. The Mso layer can then be translated into automata, yielding a model of automata for unordered trees as in [START_REF] Boiret | Deterministic Automata for Unordered Trees[END_REF], for which the emptiness problem is known to be decidable under certain conditions, which are here satisfied.

We encode multisets A of edge labels w as sets of WSkS strings, accounting for multiplicities A(w) by appending different numbers of $ to ws to differentiate them. Let t be a tree and A t v the arity -the multiset of labels -of node v; the encoding of A t v is denoted by A t v and that of v by v, such that

A t v = w$ k 1 k A t v (w) = v v ↓ t v ,
where v = t (v )$ i for some i. Note that all children sharing the same label must get a different i; while there are several valid encodings depending on that assignment, we simply choose one, indifferently. Taking X as fresh WSkS set variables, this encoding extends to interpretations in the obvious way. We can now encode any child-selector φ as a WSkS formula φ with free variables z, Z (standing for the current node and its arity), such that for any tree t, interpretation I, and nodes v ↓ t v:

t, I, v |= φ ⇐⇒ I[z → v, Z → A t v ] |= φ .
Our building blocks are: ( ) z |= π, where π is a regular expression, which is known to be WSkS-expressible, ( ) zθz is expressible by definition, since θ is a WSkS-expressible relation, and ( ) z -$, which removes all the $ at the end of the word, testing its well-formedness at the same time it restitutes the edge-label, and is encoded as

z = z -$ ≡ z $ pref z ∧ z |= A * .
Using this, we have the following encodings:

π ≡ (z -$) |= π, X ≡ z ∈ X, θ.φ ≡ ∃z ∈ Z . (z -$)θ(z -$) ∧ φ[z ← z ] .
There remains to handle counting constraints ψ, which is simply a matter of showing that WSkS can encode the primitives |Z| m -which is easy -and |Z| ≡ n m -which rests on a total order such as the lexicographic one, and on the idea of affecting each element in turn to a second-order variable corresponding to the value of the modulo. (Note that the same cannot be said of Presburger logic's |X| = |Y | tests, which are not expressible in WSkS, and whose addition would make it undecidable.) With this done, all decidability results for WSkS carry over to Γ (Θ WSkS ); in particular:

Lemma 1. Satisfiability of Γ (Θ WSkS ) is decidable.
There now remains to deal with the Mso layer; it could be encoded in WSkS as well (as it is a second order logic with sufficient expressive power), but it is simpler to take an automaton-based viewpoint, similar to [START_REF] Seidl | Counting in trees[END_REF][START_REF] Boiret | Deterministic Automata for Unordered Trees[END_REF] (with the addition of θs). We summarise the model of automata for our unordered trees, aut(Θ), as bottom-up automata with rules ψ → q, where ψ are formulae of Γ (Θ) whose child-selectors have an additional test q determining whether a child node has been evaluated in q previously (this corresponds to an "X q " test). A tree language L is said to be CMso(Θ)-definable if there exists a closed formula ξ L ∈ CMso(Θ)

such that L = { t | t |= ξ L }.
Through straightforward adaptations of the usual encodings [START_REF] Thatcher | Generalized finite automata theory with an application to a decision problem of second-order logic[END_REF][START_REF] Comon | Tree automata techniques and applications[END_REF], and further noting that aut(Θ) are effectively closed by all boolean operations, we obtain: Lemma 2. A set of trees is CMso(Θ)-definable iff it is accepted by an aut(Θ).

Of course, this result is constructive, and we can then adapt the usual reachability algorithm: provided that Γ (Θ) is decidable, so is emptiness for aut(Θ), and, in turn, so is CMso(Θ). In particular:

Theorem 2. Satisfiability of CMso(Θ WSkS ) is decidable.

More Efficient Fragments

We can further gain in efficiency by further restricting the θ relation. To this end, we consider mutually exclusive suffix replacement: we pick a set of suffixes L = {w 1 , . . . , w n } such that w i is never a suffix of another w j . Let Θ L be the set of string relations θ wi,wj linking uw i to uw j , we denote Γ sufL the counting formulae of Γ (Θ L ), with the additional restriction that regular expressions testing labels are of the form A * • w i . We use a small-model argument to find an efficient algorithm for satisfiability. We will later use this logic in bottom-up automata of aut(Θ L ) as we did in Part 5.

We consider that our arities are already annotated by set variables X ∈ X . These variables will later correspond to state labelings of an automaton of aut(Θ). If we consider vertically deterministic automata of aut(Θ) [START_REF] Boiret | Deterministic Automata for Unordered Trees[END_REF], where each tree is evaluated in at most one state, the variables X are mutually exclusive. By restricting ourselves to mutually exclusive suffixes, we only need to consider the edges labeled in uL, i.e. the orbit of uw i under the action of all θ wi,wj . This allows us to guessing a valid arity for φ ∈ Γ sufL orbit by orbit. All we need then is a small-model theorem: if #φ n appears in a formula ψ, we need to keep track of how many elements are selected by φ in a counter that stops at n. if #φ ≡ m n appears in ψ, we need to keep track of how many elements are selected by φ in a counter modulo m. This leads to an exponential number of configurations, which means that, if ψ is satisfiable, then we can find a solution using an exponential number of orbits of exponential size. We finally get:

Lemma 3. The satisfiability problem for an arity formula of Γ sufL is decidable in NExpTime. Furthermore, if the variables X are mutually exclusive, the satisfiability problem for an arity formula of Γ sufL is decidable in PSpace.

We can then use the techniques of [START_REF] Seidl | Counting in trees[END_REF][START_REF] Boiret | Deterministic Automata for Unordered Trees[END_REF], to extend our results to a class aut(Θ L ) of bottom-up automata with rules ψ → q, where ψ are formulae of Γ sufL .

Theorem 3. The emptiness problem for automata in aut(Θ L ) is decidable in NExpTime. Furthermore, for deterministic automata of aut(Θ L ), the emptiness problem is decidable in PSpace.

Conclusions and Future Works

We have introduced the logic CMso(Θ WSkS ) on unordered data trees. It is an extension of CMso to data trees, where tests on a given child may include enforcing the existence of a sibling whose label is in relation with that child's own label, the relation being WSkS-definable. That logic's expressive power is largely sufficient for concrete applications, such as the verification of common constraints on file trees, which usually involve suffix manipulations, largely captured by WSkS.

We have shown that satisfiability for CMso(Θ WSkS ) is decidable. However, we have also shown that any attempt to allow additional data relations for both prefix and suffix manipulations, even of the simplest kind, would render the logic undecidable. We have also studied the complexity of the emptiness tests for automata where horizontal counting constraints are restricted to relations that only involve disjoint suffixes, and shown that the test is then NExpTime for alternating automata, and only PSpace for deterministic automata.

There are two main ways in which this work can be extended. One is to find more expressive string relations for which the logic remains decidable; our undecidability results indicate that such an extension may not be very natural. Another is to extend the reach of the string relation from merely the set of siblings to something larger. In a first step towards that, the proof of Thm 3 can be extended to support equality constraints between brother subtrees without changing the NExpTime complexity. Another promising direction is the use of Monadic Datalog on data trees [START_REF] Abiteboul | Recursive queries on trees and data trees[END_REF], which is capable of expressing relations not only with siblings but also with parents, cousins etcetera, and for which efficient algorithms are known.

Fig. 1 .

 1 Fig. 1. Unordered trees in Json format, describing a typical file tree.

  Θ) ::= π incoming edge label matches π, | x | X equal to x or member of X, | θ.φ ∃ sibling satisfying φ with labels related by θ, | φ ∧ φ | ¬φ conjunction and negation.


domain: info stat

text:
Zhaoxin Chen
email: zhaoxin.chen@irisa.fr

Eric Anquetil
email: eric.anquetil@irisa.fr

Harold Mouchère
email: harold.mouchere@univ-nantes.fr

Christian Viard-Gaudin
email: christian.viard-gaudin@univ-nantes.fr

A graph modeling strategy for multi-touch gesture recognition

Keywords: Multi-touch, gesture recognition, graph embedding I

In most applications of touch based human computer interaction, multi-touch gestures are used for directly manipulating the interface such as scaling, panning, etc. In this paper, we propose using multi-touch gesture as indirect command, such as redo, undo, erase, etc., for the operating system. The proposed recognition system is guided by temporal, spatial and shape information. This is achieved using a graph embedding approach where all previous information are used. We evaluated our multi-touch recognition system on a set of 18 different multi-touch gestures. With this graph embedding method and a SVM classifier, we achieve 94.50% recognition rate. We believe that our research points out a possibility of integrating together raw ink, direct manipulation and indirect command in many gesture-based complex application such as a sketch drawing application.

INTRODUCTION

With the development of touchscreen technology, touchbased interaction gains a lot of popularity in the recent decade. A highly sensitive touchscreen with its underlying recognition system allows many different gesture commands such as flicking, pinching, scrolling, etc., which gives users a more convenient way to interact with computing devices.

Basically, there are three kinds of touch-based interaction, 1) Raw ink, which records the raw freehand sketching data, e.g. a handwriting notepad or a paint application [START_REF] Tevfik Metin Sezgin | Sketch based interfaces: early processing for sketch understanding[END_REF]. 2) Direct manipulation, which manipulates the interface when a real-time feedback is needed from the system to the user such as scaling, panning, etc. [START_REF] Hao Lü | Gesture coder: a tool for programming multi-touch gestures by demonstration[END_REF][START_REF] Oh | MRF-based Particle Filters for Multi-touch Tracking and Gesture Likelihoods[END_REF]. 3) Indirect command, where an input gesture is treated as a shortcut for triggering a corresponding action [START_REF] Bailly | Design and evaluation of finger-count interaction: Combining multitouch gestures and menus[END_REF][START_REF] Madhvanath | GeCCo: Finger gesture-based command and control for touch interfaces[END_REF][START_REF] Appert | Using strokes as command shortcuts: cognitive benefits and toolkit support[END_REF]. Prior works show that multi-touch gestures are mostly employed for direct manipulation while indirect command studies focus more on single-finger gestures.

In this paper, we present a novel multi-touch gesture recognition strategy for indirect command issue, where the recognition procedure is launched after a multi-touch gesture being performed. The shape and relationship between strokes may have a certain meaning that can be associated with a certain action. It allows the users to perform a multi-touch gesture as a shortcut for a command rather than seeking an explicit button or a keyboard shortcut. This idea of using gesture as command is not quite a new one, one of our recent application Varchitect (Found in Windows Store) enables the user to efficiently draw a pre-defined object with a single stroke gesture (Fig. 1). But to the best our knowledge, few studies address the multi-touch gesture as indirect command issue. The motivation of our work is to extend the variety of command gestures by employing multi-touch gesture. At this stage of our research, we focus on the problem to recognize a multi-touch gesture from its temporal, spatial and shape information. We begin with a discussion of previous research works related to the problem of gesture recognition (Section 2). We then present the approach we use to model a gesture by graph. The definition of the multi-touch gesture model by a graph is the main contribution of this paper. This approach is enriched by the presentation of a graph embedding strategy that results in an explicit embedding of graphs from graph domain in a real vector space (Section 3). In Section 4, the recognition performance of our strategy is explored by using LibSVM [START_REF] Chang | LIBSVM: a library for support vector machines[END_REF] classifier on a dataset containing a total of 1800 samples of 18 different multi-touch gestures. The associated discussions illustrate how we want to implement this approach on a sketch drawing application.

II. RELATED WORK

To begin with, it is important first to distinguish between direct manipulation recognition and indirect command recognition. The former should measure the spatial relationship between fingers and give a continuous feedback during fingers moving. For example, a scaling action requires the system continuously changing the target size in accordance with the fingers gathering or spreading. As for the latter, the motion's global features, such as the shape of trajectory becomes more useful. The recognition is done after gesture ending and triggers a discrete action for the system.

A large number of works concern gestures that directly manipulate the interface. Oh et al. [START_REF] Oh | MRF-based Particle Filters for Multi-touch Tracking and Gesture Likelihoods[END_REF] calculated motion likelihoods as feature during fingers' moving. Three basic motions, translation, scaling and rotation, can be recognized if their likelihood values exceeds a certain threshold. Lu and Li [START_REF] Hao Lü | Gesture coder: a tool for programming multi-touch gestures by demonstration[END_REF] proposed a Gesture Code approach where a finger's event sequence is used to learn a state machine for recognition. But learning based on individual motion segment does not allow the capture of a motion's global features. A very similar method from Kin et al. [START_REF] Kin | Proton: multitouch gestures as regular expressions[END_REF] specified a sequence of touch events that comprises a gesture as a regular expression. These methods commonly extract the dynamic features for recognition.

Concerning indirect commands, Madhvanath et al. [START_REF] Madhvanath | GeCCo: Finger gesture-based command and control for touch interfaces[END_REF] presented their GeCCo which uses finger gestures as command and control. Dynamic Time Warping (DTW) with k nearest neighbor (KNN) is employed for recognition, but only singlefinger gesture is supported. Appert and Zhai [START_REF] Appert | Using strokes as command shortcuts: cognitive benefits and toolkit support[END_REF] also investigated using stroke gestures as shortcut. They concluded that stroke shortcuts can be as effective as keyboard shortcut in actual performance but have cognitive advantages in learning and recall. Bailly et al. [START_REF] Bailly | Design and evaluation of finger-count interaction: Combining multitouch gestures and menus[END_REF] introduced a Finger-Count interaction where the system just need to count the number of finger contacts. Twenty five different input configurations can be expressed when using both hand.

It is worth to note that most of the studies on multi-touch gesture are limited in a small set of commands. Few studies focus on recognizing multi-touch gesture as indirect commands especially when we need to deal with a large number of different gestures.

III. GRAPH MODELING AND EMBEDDING

We introduce here our new recognition system for multitouch gestures. We will first discuss the graph modeling approach where the strokes and their spatial and temporal relations are represented by a set of vertices and edges in the graph. We then introduce a graph embedding strategy to encode the graph into a fixed size vector to make the pattern recognition task easier.

A. Graph modeling

A multi-touch gesture modeling should consider three kinds of information: spatial, temporal and shape information. A spatial information shows the relative position of each single stroke with reference to the others inside the gesture, while a temporal information illustrates the written order between the different strokes and the duration of each one. The last information should retain knowledge about the intrinsic shape of the stroke, allowing to distinguish between a simple straight line from a more complex curve.

In a first step, we consider representing each stroke by three vertices in the graph. Consider a two stroke gesture as an example (Fig. 2), each stroke is depicted by a begin vertex (V b ), a stroke vertex (V s ) and an end vertex (V e ). The spatial and temporal relationships between vertices are described by the edges E s (x, y), E st (x, y, t) and A st (x, y, t). The subscripts s and st indicate that only spatial or both spatial and temporal relationships are measured between the vertices, respectively. The differences between E st and A st will be explained in the following paragraph. To complete the preceding representation, and make it specific for a given spatial-temporal configuration, the edges are marked with one or several discrete labels. We make use of the Allen's relations [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] which originally characterized the inferences about time by discrete labels. In our approach, we extend the applicability of these relations on characterizing also the spatial relationships. There are two general cases for labeling the edges.

1) Edges between stroke vertices (A st ): The Allen's relations are used to measure the relationships with respect to time, x-axis position and y-axis position. Consider the flick gesture in Fig. 3(a), Fig. 3(b) shows the spatial relationships between strokes with respect to the x and y axis. According to the Allen's relations, the label Equal_X (E_X) and Before_Y (B_Y) are associated to the edge A st . Fig 3(c) depicts that the two strokes of flick were performed simultaneously. Therefore an Equal_Time (E_T) label is assigned to the edge A st . Finally the edge A st will be:

A st (x, y, t) = {E_X, B_Y, E_T} . Fig. 4 gives another example of an anchor rotate gesture. Comparing to the flick gesture, since they have different spatial relationships, a graph with different structure and labels is shown in Fig. 4(d). It proves that our graph modeling strategy has the ability to characterize different multi-tocuh gesture with different graph models. These differences could be used by a classifier to make a recognition.

2) Edges between extremity vertices (E s and E

B. Stroke shape quantization

In this step we intend to integrate the shape information into our graph strategy in order to differentiate the gestures which have same graph but different stroke shape. To describe the shape of the gesture, we will use the feature set HBF49 proposed in [START_REF] Delaye | HBF49 feature set: A first unified baseline for online symbol recognition[END_REF]. The shape feature will be studied from two perspectives:

1) Local Shape Feature (LSF): A multi-touch gesture may be composed by various shapes of strokes. We describe the shape of each stroke by a feature vector from HBF49. Each stroke will then be represented by a label extracted from a codebook previously built with a clustering algorithm (Kmeans). The corresponding label will be assigned to the stroke vertex of that stroke in the graph. Shown in Fig. 3(d), the labels of vertices V s have been replaced by the labels of the cluster, the strokes belong to.

2) Global Shape Feature (GSF): We also extract the shape features for the entire gesture. However, this HBF49 feature vector will not be integrated into the graph but concatenated after the graph embedding feature vector. This GSF can be regarded as a complement for our graph embedding strategy. More details will be explained in the experimental section.

C. Graph embedding

A graph embedding method aims to transform the graph structure into a feature vector for the benefit of using statistical classification method. In this paper, we adopt a graph embedding approach introduced by Sidere et al. [START_REF] Sidère | Vector Representation of Graphs: Application to the Classification of Symbols and Letters[END_REF]. The basic idea of this approach is to build a matrix where each row is relative to a label of vertices or edges while each column corresponds to a sub structures P j of the graph. The value of the matrix at [L i , P j ] is the number of occurrences of the label L i in each sub graph P k which is isomorphic to the sub structures P j . The construction of the vectorial representation can then be performed by transforming the matrix into vector feature space.

In our case, we empirically choose three sub structures which are one vertex, two vertices with one edge and three vertices with three edges for the column of the matrix. The row involves the seven Allen's relations for three aspects (time, x-axis and y-axis), cluster number (typically 9) and labels of begin and end for the vertex. On the whole, 32 labels will be related to the rows. Accordingly, a feature vector with a length of 96 will be generated after the graph embedding.

IV. EXPERIMENTS

We conducted experimental evaluation of our proposed recognition method over a multi-touch gesture dataset which will be depicted in the following subsection. We make use of LIBSVM for the classifier to test the recognition rate by using our graph embedding features. The result is then compared with our previous work, HBF49 features, which is used as a baseline method for evaluating symbol recognition system.

A. Dataset

Since a public dataset for multi-touch recognition can hardly be found, we recently collected a total of 1,800 multitouch gesture samples, written by 10 persons, for the experiment. This dataset contains 18 different kinds of multitouch gestures which could be used as command (Fig. 5). These gestures are composed of points, linear segments and arcs with a varying number of strokes. Note that most of them have an apparent distinction according to their shape except two pairs, Command C-1 versus Command C-2 and Flick versus Flick twice. The gesture C-1 is performed firstly the 'dot' in the left side, then the 'C' shape in the right side. On the contrary, gesture C-2 is performed firstly the 'C' shape and then the 'dot'. As for the other pair, the Flick gesture is performed by two fingers flicking simultaneously, whereas the Flick-twice gesture is done by one finger but flicking twice. These two pairs of gestures have the same shape respectively but are different from a temporal point of view. We introduce them in the dataset to evaluate the capability of our recognition method to discriminate gestures from temporal information.

B. Classifier

Since the graph features have been embedded in a vector features, we chose SVM as the classifier. The LIBSVM with a Gaussian kernel and default parameters appeared to provide adequate capability for gesture classification.

C. Experimental design

To fully evaluate our graph embedding strategy, five experiments were conducted with different methods or method combinations respectively.  Graph: In the first experiment, we tried to evaluate our graph modeling strategy without shape information. Only spatial and temporal information were integrated in the graph for recognition.

 GSF: In this second experiment, we use directly the HBF49 features without any graph modeling. This could be considered as a baseline system. .

 Graph+GSF: In this trial, the feature vector of GSF was simply concatenated after the graph features from the first experiment to achieve a conjoint feature vector, the length of feature vector would be 87+49=136.

 Graph(LSF):

The fourth experiment evaluated the performance of integrating the LSF into the graph. The cluster number K is set to an optimal value 9. The comparison of different values of K will be presented below.

 Graph(LSF)+GSF: Finally, we combined the graph information with both global and local shape information. It was achieved by concatenating the feature vector of GSF after the vector obtained in the fourth experiment.

All the experiments adopted a 5-cross-validation (CV) scheme for testing writer-independent (WI) performance.

D. Experimental result

Table II summarizes the recognition rates obtained by different methods or their combination.

The results show that the graph strategy, containing only spatial and temporal information, obtains 87.50% recognition rate which is lower than the HBF49 based GSF method (90.44 %). With a deeper investigation from the confusion matrix in Fig. 5, most of the misclassifications by graph strategy happens between the gesture Command C-1, Command C-2 and Command X because they have similar spatial relationships between strokes (Fig. 6(a)). We can note that GSF is able to classify the majority of multi-touch but fails to make a distinction between Command C-1 versus Command C-2 and Flick versus Flick-twice since they are similar in shape, respectively (Fig. 6(b)). The Graph+GSF method results in 90.11% which is slightly lower than GSF method. However, when we integrate the shape information of each stroke inside the graph by using clustering method, the recognition rate of Graph (LSF) rises to 92.56%. In accordance to what can be expected, the final experiment, Graph (LSF) + GSF which integrates all the information together achieves the best recognition rate, 94.50%, that is significantly better than others. Meanwhile, by evaluating the standard deviation of 5-cross-validation, the two strategies with LSF inside produce smaller variations than the other three strategies in the WI situation.

The cluster number K used in the clustering process is also a factor of great concern for the recognition. The comparison results of the recognition rate under different values of K are illustrated in Fig. 7. It shows that the same trend in the relationship between cluster number K and recognition rate can be observed from both methods. The peak appears when K is chosen to 9. Neither too large nor too small cluster number are able to well perform. The comparison also proves that the Graph (LSF) + GSF method is always better than the Graph (LSF) method.

V. CONCLUSION AND FUTURE WORK

In this paper, we have investigated a method to recognize the multi-touch gestures. Unlike many other works, we study this problem from a new perspective considering a multi-touch gesture as an indirect command. We believe that three kinds of information, spatial, temporal and shape information, of the gesture should be processed for the recognition. We first proposed a graph modeling method which measures the spatial and temporal relationships between strokes of the gesture. In order to integrate the shape information into the graph, a clustering method is employed to label the shape of the stroke inside the graph as a local shape feature. Another globe shape feature is extracted with our previous baseline method HBF49 features.

We are currently further developing our graph based recognition technologies. Instead of using discrete prototypes, we are considering using numerical features to give a more precise measurement for the spatial and temporal information. In another effort, our proposal of multi-touch gesture as indirect command is planned to be integrated into a sketch drawing application to evaluate its usability. We hope this strategy may offer a more convenient switching mode between raw ink, direct manipulation and indirect command.

Fig. 1 .

 1 Fig. 1. User may perform a gesture to efficiently draw a pre-define object in our Varchitect application.

Vb:Fig. 2 .

 2 Fig. 2. An example of a general graph modeling for a two strokes gesture.

1 b V and 2 bVb

 12 st ): Since the extremity vertices represent each of the finger-down and finger-up positions, only Equal property for the time (E_T), x-axis position (E_X) and y-axis position (E_Y) is used for characterizing the edges between vertices. Fig.3(d)shows the graph of a flick gesture with all the edges labeled. The label E st ={E_X, E_T} between indicates the two starting points are written in the same region on x-axis and in the same time. Same property will also be found between the two V e vertices. The label E st ={E_Y} between 1 b V and 1 e V means that they are written in the same region on y-axis. Noted that not all edges between extremity vertices have to be generated if the Equal property is not satisfied. Comparing to the general case in Fig.2, the edges between 1 b) are removed since these two points are not located in the same position on neither x-axis nor y-axis.

Flick

Fig. 3 .Fig. 4 .

 34 Fig. 3. a) A flick gesture. b) Spatial relationship between strokes. c) Temporal relationship between strokes. d) Graph model with labels.

Fig. 6 .

 6 Fig. 6. Confusion matrix of some typical misclassified gestures of different classification methods. The row relates to the ground truth.

Fig. 7 .

 7 Fig. 7. Performance evaluation of different values of cluster number K

  Table I shows the illustration and examples of Allen's relations.

TABLE I

 I

		.	EXAMPLES OF ALLEN'S RELATIONS
	Relation	Example	Relation	Example
		Str 1 :			Str 1 :
	Before (B)	Str 2 :		During (D)	Str 2 :
		Str 1 :			Str 1 :
	Equal (E)	Str 2 :		Start (S)	Str 2 :
		Str 1 :			Str 1 :
	Meet (M)	Str 2 :		Finish (F)	S t r 2 :
	Overlap	Str 1 :
	(O)	Str 2 :

TABLE II .

 II RECOGNITION RATE OBTAINED BY DIFFERENT METHODS

	Method	Length of features	Recognition rate (%)	Std. Deviation
	Graph (without shape feature)	87	87.50	0.037
	GSF	49	90.44	0.034
	Graph + GSF	136	90.11	0.035
	Graph (LSF)	96	92.56	0.013
	Graph (LSF) + GSF	145	94.50	0.020

ACKNOWLEDGMENT

The authors would like to thank Somia Rahmoun and Boussad Ghedamsi for fundamental research in their master's internship early in this study.