Yohann Meynadier
email: yohann.meynadier@lpl-aix.fr

Yulia Gaydina
email: gaydina_yulia@live.fr

Aerodynamic and durational cues of phonological voicing in whisper

Keywords: phonetics, voicing, whisper, aerodynamics, segmental duration

This paper presents analyses on the phonological voicing contrast in whispered speech, which is characterized by the absence of vocal fold vibrations. In modal speech, besides glottal vibration, the contrast between voiced and unvoiced consonants is realized by other phonetic correlates: e.g. consonant and pre-consonantal vowel durations, intraoral pressure differences. The analysis of these voicing cues shows they are well preserved in whispered speech. The results are consistent with previous studies supporting the perception of the voicing contrast even without physical voicing. Additionally, the patterns observed for P o during obstruents could reflect constraints connected to competing needs of intelligibility and of discretion in whisper.

Introduction

Whisper is a mode of phonation naturally used in order to reduce the perceptibility of speech. In modal phonation ("normal voice"), the fully adducted vocal cords allow them to vibrate for voiced segments. In whisper, the vocal folds are adducted only in their front part, with a small posterior opening between arytenoids left for exhaust air. This Y-like configuration allows the establishment of glottal aerodynamic turbulences generating the noisy sound source.

Besides the lack of voicing and the different laryngeal configuration, whispered voice induces many changes in different phonetic dimensions: (i) spectral changes as a significant loss of energy especially at low frequencies, a flattening of high frequencies and higher vowel formants [START_REF] Schwartz | Power spectral density measurements of oral and whispered speech[END_REF][START_REF] Lehiste | Suprasegmentals[END_REF][START_REF] Faraco | Comparaison des intonations affirmative et interrogative en voix normale et chuchotée[END_REF][START_REF] Ito | Analysis and recognition of whispered speech[END_REF][START_REF] Jovicic | Acoustic analysis of consonants in whispered speech[END_REF][START_REF] Vercherand | Production et perception de la parole chuchotée en français: analyse segmentale et prosodique[END_REF][START_REF] Sharifzadeh | A comprehensive vowel space for whispered speech[END_REF]; (ii) temporal changes as a lengthening of syllables or segments or a lowering of speech rate [START_REF] Faraco | Comparaison des intonations affirmative et interrogative en voix normale et chuchotée[END_REF][START_REF] Jovicic | Acoustic analysis of consonants in whispered speech[END_REF][START_REF] Vercherand | Production et perception de la parole chuchotée en français: analyse segmentale et prosodique[END_REF][START_REF] Schwartz | Syllable duration in oral and whispered reading[END_REF][START_REF] Schwartz | Bilabial closure durations for /p/, /b/, and /m/ in voiced and whispered vowel environments[END_REF]; (iii) aerodynamic changes as an increase of airflow and air consumption [START_REF] Schwartz | Air consumption, per syllable, in oral and whispered speech[END_REF][START_REF] Stathopoulos | Respiratory and laryngeal function during whispering[END_REF][START_REF] Konnai | Whisper and phonation: aerodynamic comparisons across adduction and loudness levels[END_REF] and equivocal findings on subglottal and intraoral pressures, [START_REF] Stathopoulos | Respiratory and laryngeal function during whispering[END_REF][START_REF] Konnai | Whisper and phonation: aerodynamic comparisons across adduction and loudness levels[END_REF] for a review; (iv) supraglottal articulatory changes towards some kind of hyperarticulation [START_REF] Higashikawa | Lip kinematics for /p/ and /b/ production during whispered and voiced speech[END_REF][START_REF] Traunmüller | Acoustic effects of variation in vocal effort by men, women, and children[END_REF][START_REF] Osfar | Articulation of whispered alveolar consonants[END_REF].

Concerning the perception of whispered speech, studies on a small number of languages reported that most segmental and suprasegmental information is more or less preserved, as (i) vowel identity [START_REF] Kallail | The identifiability of isolated whispered and phonated vowel samples[END_REF][START_REF] Tartter | Identifiability of vowels and speakers from whispered syllables[END_REF][START_REF] Eklund | Comparative study of male and female whispered and phonated versions of the long vowels of Swedish[END_REF]; (ii) consonant place and manner [START_REF] Tartter | What's in a whisper?[END_REF]; even (iii) intonation, accent [START_REF] Faraco | Comparaison des intonations affirmative et interrogative en voix normale et chuchotée[END_REF][START_REF] Vercherand | Production et perception de la parole chuchotée en français: analyse segmentale et prosodique[END_REF][START_REF] Trim | Cues to the recognition of some linguistic features of whispered speech in English[END_REF][START_REF] Nicholson | How to tell beans from farmers: cues to the perception of pitch accent in whispered Norwegian[END_REF][START_REF] Heeren | Perception and production of boundary tones in whispered Dutch[END_REF] or tone [START_REF] Jensen | Recognition of word tones in whispered speech[END_REF] (but see [START_REF] Miller | Word tone recognition in Vietnamese whispered speech[END_REF][START_REF] Gao | Tones in whispered Chinese: articulatory features and perceptual cues[END_REF]); and (iv) voicing feature in [START_REF] Vercherand | Production et perception de la parole chuchotée en français: analyse segmentale et prosodique[END_REF][START_REF] Tartter | What's in a whisper?[END_REF][START_REF] Dannenbring | Perceptual discrimination of whispered phoneme pairs[END_REF][START_REF] Munro | Perception of 'voicing' in whispered stops[END_REF][START_REF] Higashikawa | Perceptual, acoustical and aerodynamic study of whispering[END_REF][START_REF] Mills | Cues to voicing contrasts in whispered Scottish obstruents[END_REF][START_REF] Mills | Speech motor control variables in the production of voicing contrasts and emphatic accent[END_REF][START_REF] Knyazev | O svyazi osobennostej articulyazionnoj bazy govora s harakterom protivopostavleniya gluhih i zvonkih, tverdyh i myagkih soglasnyh[END_REF], that is targeted in our study.

This study focuses on the duration of pre-consonantal vowels and, on the duration and intraoral pressure of obstruents as secondary phonetic properties involved in maintaining the perception of phonological voicing in whispered speech, i.e. without phonetic (physiological and acoustic) voicing. In modal speech, apart from the periodic vibration of the vocal folds, these properties (or their acoustic consequences) are part of numerous secondary phonetic cues commonly reported for voicing [START_REF] Delattre | Les indices acoustiques de la parole[END_REF][START_REF] Catford | Fundamental problems in phonetics[END_REF][START_REF] Lisker | Voicing in English: a catalogue of acoustic features signaling /b/ versus /p/ in trochees[END_REF]. The duration of consonants and pre-consonant vowels has long been observed: (i) vowels are longer before voiced than before voiceless consonants and, (ii) voiceless obstruents are longer than voiced ones [START_REF] Lehiste | Suprasegmentals[END_REF], see [START_REF] Abdell-Beruh | The stop voicing contrast in French sentences: contextual sensitivity of vowel duration, closure duration, voice onset time, stop release and closure voicing[END_REF][START_REF] Fowler | Vowel duration and closure duration in voiced and unvoiced stops: there are no contrast effects here[END_REF] for a review.

While the voiced-voiceless difference in duration of preconsonantal vowels is not still well understood [START_REF] Lehiste | Suprasegmentals[END_REF][START_REF] Lisker | On 'explaining' vowel duration variation[END_REF][START_REF] Raphael | The physiological control of durational differences between vowels preceding voiced and voiceless consonants in English[END_REF], the difference of obstruent duration has usually been explained by the Aerodynamic Voicing Constraint [START_REF] Ohala | Aerodynamics of phonology[END_REF]. A minimal difference between subglottal (P s ) and intraoral (P o ) pressures (P = P s -P o ) is required to start and to maintain vocal vibration. Indeed, below 1 to 2 hPa [START_REF] Catford | Fundamental problems in phonetics[END_REF][START_REF] Ohala | Aerodynamics of phonology[END_REF] vibration ceases because of the weakness of translaryngeal airflow. This constraint at work for voiced obstruents would account for their frequent devoicing and their shortening to avoid devoicing. Voiceless consonants are not subject to this aerophonatory requirement. Also, the laryngeal resistance of adducted vocal folds during voicing (Glottal Resistance Hypothesis) induces a decrease of the translaryngeal airflow. Hence, the voiced obstruents show a lower P o than the unvoiced ones [START_REF] Ohala | Aerodynamics of phonology[END_REF], see [START_REF] Malécot | An experimental study of force of articulation[END_REF] for a short review. The lower P o results in a lower energy of the burst or the frication noise of voiced obstruents, which is a cue of voicing.

With regard to whisper, one may logically think that these aerodynamic constraints (on consonant duration and spectral energy) do not operate due to a static abduction of the vocal folds during speech, as largely described in phonetic textbooks, see [START_REF] Weismer | Segmental gestures at the laryngeal level in whispered speech: evidence from an aerodynamic study[END_REF] for references. But, some other phoneticians suggested (without empirical evidences) a more dynamical view of the glottis during whisper [START_REF] Catford | Fundamental problems in phonetics[END_REF][START_REF] Laver | Principles of phonetics[END_REF] (see [START_REF] Mills | Speech motor control variables in the production of voicing contrasts and emphatic accent[END_REF] for other references) that could support the voicing contrast. A narrower glottis (as in Y-like whisper phonation) would distinguish the whispered voiced obstruents from the unvoiced obstruents phonated with a larger glottis close to the V-like voiceless abduction produced in modal speech. To our knowledge, only three studies ( [START_REF] Mills | Speech motor control variables in the production of voicing contrasts and emphatic accent[END_REF] on English, [START_REF] Zeroual | Physiological study of whispered speech in Moroccan Arabic[END_REF] on Moroccan Arabic, [START_REF] Malécot | An optical device for recording glottal adduction-abduction during normal speech[END_REF] on French) have attempted to test this proposition by direct empirical data on the state of the glottis during whispered speech. While aerodynamics provides indirect information on the configuration of the glottis [START_REF] Ladefoged | Investigating phonation types in different languages[END_REF], few studies have used indirect P o measurement to assess glottal adjustments related to the consonant voicing contrast in whisper. Unfortunately, they reported equivocal findings. In Japanese, higher P o for whispered unvoiced than voiced obstruents are established by Higashiwaka [START_REF] Higashikawa | Perceptual, acoustical and aerodynamic study of whispering[END_REF] but not by Soda et al. [START_REF] Soda | Intraoral pressure change in Japanese consonants[END_REF]. In English, Murry and Brown [START_REF] Murry | Peak intraoral pressures in whispered stop consonants[END_REF] did not find any support to this contrast. Weismer and Longstreth's [START_REF] Weismer | Segmental gestures at the laryngeal level in whispered speech: evidence from an aerodynamic study[END_REF] results showed only a trend. However, their measurements of airflow peak and P o slope seem to attest a possible narrower glottis adjustment for whispered voiced obstruents, even if this seems insufficient to cause such a significant large P o drop as in modal speech. So, at this time, direct (optical) or indirect (P o ) observations provides no clear and strong evidence that the Glottal Resistance Hypothesis is operating in whispered speech.

Concerning the duration of vowels and consonants in whisper, more data are available. First, works on modal speech show that, besides VOT cue (especially for English), gating experiments on the closing-phase consonant duration ( [START_REF] Wajskop | Voicing cues in oral stop consonants[END_REF] on French) and on the pre-consonantal vowel duration ( [START_REF] Raphael | Preceding vowel duration as a cue to the perception of the voicing characteristic of word-final consonants in American English[END_REF][START_REF] Hogan | Evaluation of vowel duration as a cue for the voicing distinction in the following word-final consonant[END_REF] on English) modify significantly the perception of the voicing feature of obstruents. Although no such psycholinguistic test has been done in whispered speech, some studies show that the perception of the voicing contrast is generally preserved [START_REF] Tartter | What's in a whisper?[END_REF][START_REF] Dannenbring | Perceptual discrimination of whispered phoneme pairs[END_REF][START_REF] Munro | Perception of 'voicing' in whispered stops[END_REF][START_REF] Higashikawa | Perceptual, acoustical and aerodynamic study of whispering[END_REF][START_REF] Mills | Cues to voicing contrasts in whispered Scottish obstruents[END_REF][START_REF] Mills | Speech motor control variables in the production of voicing contrasts and emphatic accent[END_REF][START_REF] Knyazev | O svyazi osobennostej articulyazionnoj bazy govora s harakterom protivopostavleniya gluhih i zvonkih, tverdyh i myagkih soglasnyh[END_REF]. Only a pilot test by Vercherand [START_REF] Vercherand | Production et perception de la parole chuchotée en français: analyse segmentale et prosodique[END_REF] supports these results for French. None of them allows connecting precisely this performance in whisper on any identified secondary properties of voicing. Nevertheless, vowel and consonant durations are always approached as major secondary cues of consonant voicing. The reason is that studies on the production of vowel and consonant durations in whisper all converge to account for a preserved durational contrast for vowels and obstruents, even reduced, in whispered speech, as in English [START_REF] Mills | Cues to voicing contrasts in whispered Scottish obstruents[END_REF][START_REF] Mills | Speech motor control variables in the production of voicing contrasts and emphatic accent[END_REF][START_REF] Sharf | Vowel duration in whispered and in normal speech[END_REF][START_REF] Kinsey | Phonological voice in whispered speech[END_REF], Serbian [START_REF] Jovicic | Acoustic analysis of consonants in whispered speech[END_REF], Dutch [START_REF] Velde Van Der | Compensatory strategies for voicing of initial and medial stops and fricatives in whispered speech in Dutch[END_REF], Russian and Hungarian [START_REF] Knyazev | O svyazi osobennostej articulyazionnoj bazy govora s harakterom protivopostavleniya gluhih i zvonkih, tverdyh i myagkih soglasnyh[END_REF] and French [START_REF] Vercherand | Production et perception de la parole chuchotée en français: analyse segmentale et prosodique[END_REF].

Our study on whispered speech production in French focuses on these questions. In a first experiment, we examine durational cues of the voicing feature, in order to confirm and to complete previous results obtained by Vercherand [6]. The second experiment tests the Glottal Resistance Hypothesis by means of indirect P o measurement. This is the first attempt to support Malécot and Peebles's observation [START_REF] Malécot | An optical device for recording glottal adduction-abduction during normal speech[END_REF], concerning glottal adjustments as function as the phonological voicing of French obstruents in whispered speech.

Voicing-dependant durations

This first experiment concerns the analysis of the acoustic duration of voiced vs. unvoiced obstruents and of their preconsonantal vowels in modal vs. whispered speech.

Corpus and data

Recorded in an anechoic room, 4 French speakers (2 males, 2 females, not linguistic experts or students) read aloud at normal speaking rate two randomized lists of words presented in isolation. After a brief training session, they produced each list 5 times alternatively for each phonation mode.

A first list was composed of 12 non-sense words pooled with 36 fillers. The targeted words patterned as VC 1 VC 2 V, wherein V was always /e/ and, C 1 and C 2 obstruent target always different from the voiced-unvoiced pairs: /b-p/, /t-d/, /k-g/, /f-v/, /s-z/ and /ʃ-ʒ/, e.g. /epeʒe/ (written épéjé) and /edese/ (written édécé). Fillers met the same pattern, but included at least one non-target consonant, e.g. /ekene/ (written équéné) or /eleme/ (written élémé). The occurrence frequency of consonants was balanced inside the list. Only consonants in C 1 position are analyzed here.

A second list consisted of 12 target conjugated verbs, randomly pooled with 72 fillers of the same phonological template. The obstruents were intervocalic and in (unstressed) non-final syllable of words. (Syllable-initial obstruents in word-final position were recorded too, but not analyzed here). The preceding vowel was /e/ in all cases, except 4 (/a/). To control for the following vowel, voiced-unvoiced consonants are part of minimal pairs, e.g. (il) écoutait /ekute/ [(he) listened to] vs. (il) égouttait /egute/ [(he) dripped]. Speakers read aloud only the words between brackets to produce only three-syllable sequences.

The duration of pre-consonantal vowels and consonants were acoustically measured with Praat.

Measures and analyses

To ensure same measurements between phonation modes, segmentation was mostly done on spectrogram, from the F2-F3 onset and offset of vowels. The beginning and end of vowels correspond respectively to the end and beginning of consonants. The manual labeling was carried out with Praat.

For consonants, two articulatory phases were identified (Figure 1). For stops, the closure (T) was labeled from the end of the preceding vowel to the beginning of the burst. The release (R) was measured from the beginning of the burst to the beginning of the following vowel. The friction noise after the burst may have formant traces, the release phase can also be seen as CV transition phase. For fricatives, the steady-state of the constriction (T) was separated from its release (R) identified at the beginning of stronger formant traces of the following vowel during fricative noise (i.e. CV transition). The durations of consonant and preceding vowels were analyzed by repeated-measure ANOVA tests with speaker and lexical status (word vs. non-sense word) as random factors. The independent factors are phonation mode (modal vs. whisper), voicing (voiced vs. unvoiced) and manner of articulation (stop vs. fricative). Lexical and non-sense words were pooled. All reported values are mean durations (in ms).

Results and discussion

Obstruents

First, obstruent durations significantly, but weakly, increase in whisper (107 ms) compared to modal phonation (98 ms) [F(1,3) = 13.881; p = 0.03368]. This does not completely fit Vercherand's results [START_REF] Vercherand | Production et perception de la parole chuchotée en français: analyse segmentale et prosodique[END_REF] on text-reading French where a phonation effect is only for 2/4 speakers on unvoiced fricatives. This is in agreement with studies on others languages [START_REF] Jovicic | Acoustic analysis of consonants in whispered speech[END_REF][START_REF] Schwartz | Syllable duration in oral and whispered reading[END_REF][START_REF] Schwartz | Bilabial closure durations for /p/, /b/, and /m/ in voiced and whispered vowel environments[END_REF] related to slower speech rate in whisper.

Concerning the voicing contrast, as expected in modal phonation, unvoiced obstruents (118 ms) are longer than the voiced ones (78 ms) [F(1,3) = 161.79; p = 0.00105]. Unvoiced fricatives and stops are longer than voiced counterparts: respectively 133 and 102 ms vs. 85 and 74 ms, as showed in Figure 2. Similarly, in whispered speech, unvoiced consonants are significantly 31 ms longer than voiced ones [F(1,3) = 56.014; p = 0.00494]: respectively, 136 vs. 99 ms for fricatives and 108 vs. 82 ms for stops. The durational difference associated with the phonological voicing contrast of obstruents is also kept in whisper. The difference between unvoiced and voiced fricatives reduces from modal ( = 48 ms) to whisper ( = 37 ms). For stops, the difference remains constant: 28 in modal speech and 26 ms in whisper.

Figure 2: Duration of consonants (top), of their steady-state (bottom) and of their release (middle)

The analysis brings out a noticeable difference between the steady-state and the release of obstruents (Figure 2). In modal words, both these take significantly part to the durational distinction between voiced and unvoiced consonants. It is not the case in whisper where the release duration seems to play no role in the voicing contrast.

For whispered stops, the closure is significantly longer for the unvoiced (84 ms) than voiced (59 ms) ones Whispered voiced fricatives present shorter durations of the steady-state phase voiced (90 ms) [F(1,3) = 49.841; p = 0.00584]. The difference is 36 ms with unvoiced fricatives (126 ms). Unlike stops, there is a slight reduction compared to 41 ms measured in modal phonation. Here again, no effect is observed on the duration of their release in whisper, in opposition to modal phonation.

Thus, it is mainly the steady-state of obstruents which seems to support voicing information in whisper, and not the release duration in this French corpus. Few data are available to discuss this point here. Languages without aspiration reported closure and global duration lengthening of obstruents without any remark on the release duration [START_REF] Jovicic | Acoustic analysis of consonants in whispered speech[END_REF][START_REF] Vercherand | Production et perception de la parole chuchotée en français: analyse segmentale et prosodique[END_REF][START_REF] Knyazev | O svyazi osobennostej articulyazionnoj bazy govora s harakterom protivopostavleniya gluhih i zvonkih, tverdyh i myagkih soglasnyh[END_REF][START_REF] Velde Van Der | Compensatory strategies for voicing of initial and medial stops and fricatives in whispered speech in Dutch[END_REF]. In languages with aspiration (English), consonant [START_REF] Mills | Cues to voicing contrasts in whispered Scottish obstruents[END_REF], closure [START_REF] Osfar | Articulation of whispered alveolar consonants[END_REF] or aspiration [START_REF] Kinsey | Phonological voice in whispered speech[END_REF] are only alternatively reported. Kinsey [START_REF] Kinsey | Phonological voice in whispered speech[END_REF] observed an effect on release and not on closure.

Finally, our main results on longer values for unvoiced than voiced obstruents in whisper confirm and complete previous data.

Vowels

A longer vowel precedes voiced obstruents and vice versa (Figure 3). Similar significant differences are observed whatever the phonation mode and the manner of articulation of Our data strengthen results observed once on French [START_REF] Vercherand | Production et perception de la parole chuchotée en français: analyse segmentale et prosodique[END_REF]. They corroborate that the phonological voicing of obstruents is also marked in French by a difference of the pre-consonantal vowel duration in whisper, as in modal speech, just as in others languages [START_REF] Mills | Cues to voicing contrasts in whispered Scottish obstruents[END_REF][START_REF] Knyazev | O svyazi osobennostej articulyazionnoj bazy govora s harakterom protivopostavleniya gluhih i zvonkih, tverdyh i myagkih soglasnyh[END_REF][START_REF] Sharf | Vowel duration in whispered and in normal speech[END_REF][START_REF] Kinsey | Phonological voice in whispered speech[END_REF][START_REF] Velde Van Der | Compensatory strategies for voicing of initial and medial stops and fricatives in whispered speech in Dutch[END_REF].

Glottal Resistance Hypothesis

This second experiment focuses on the difference of intraoral pressure (P o ) as function of voiced/unvoiced contrast of labial obstruents in whispered speech. The P o is seen as an indirect measurement of the glottal opening in order to assess the Glottal Resistance Hypothesis in whisper.

Corpus and data

In an anechoic room, 8 French speakers (6 females, 2 males) read aloud at normal speaking rate a balanced randomized list of 72 isolated words, once in modal voice and once in whisper. The labial obstruents /p-b/ and /f-v/ were produced in initial and final positions of monosyllable words, and in median position of bisyllabic words. Vocalic contexts were: (i) /a ɛ ɔ / for initial and final position, e.g. vache /vaʃ/ (cow), beige /bɛʒ/ (beige), pomme /pɔm/ (apple) or, chef /ʃɛf/ (chief), rap /ʁap/ (rap), robe /ʁɔb/ (dress); (ii) /a__a ɛ ɔ/ for median position, e.g. savate /savat/ (old shoe), affaire /afɛʁ/ (case), rapport /ʁapɔʁ/ (report). Each vowel context was iterated in two different words, totaling per speaker 18 occurrences of each consonant in each phonation mode. Acoustic signal, oral airflow and P o were recorded synchronously with the EVA aerophonometer, [START_REF] Ghio | Evaluation of the acoustic and aerodynamic constraints of a pneumotachograph for speech and voice studies[END_REF] for technical details. P o was measured via the mouth in oral cavity by a special fine tube which ends approximately 1 cm behind the central incisors. When labial closure or labiodental constriction was realized, a positive increase of P o is captured.

Measures and analyses

P o measures were carried out with Phonedit (http://www.lplaix.fr/~lpldev/phonedit). Expressed in hectopascal (hPa), the maximal P o value was measured at the peak of the P o curve reached during the consonant.

The statistical analyzes were repeated-measure ANOVA. Speaker, syllable position and vowel context are random factors. Phonation (modal vs. whisper), voicing (voiced vs. unvoiced) and manner of articulation (plosive vs. fricative) are independent factors. All reported values are mean P o .

Results and discussion

P o does not differ regularly between modal and whispered phonation. The variability between subjects across phonations shows that P o is not systematically lower in whisper (Table 1). It is confirmed by previous equivocal findings on the decrease P s or P o in whisper [START_REF] Stathopoulos | Respiratory and laryngeal function during whispering[END_REF][START_REF] Konnai | Whisper and phonation: aerodynamic comparisons across adduction and loudness levels[END_REF][START_REF] Higashikawa | Perceptual, acoustical and aerodynamic study of whispering[END_REF][START_REF] Weismer | Segmental gestures at the laryngeal level in whispered speech: evidence from an aerodynamic study[END_REF][START_REF] Soda | Intraoral pressure change in Japanese consonants[END_REF][START_REF] Murry | Peak intraoral pressures in whispered stop consonants[END_REF]. Table 1. P o peak of labial obstruents in modal (Mod) and whisper (Whi) phonations. Speakers in rows. account for a significant effect (Figure 4).

In both phonations, the unvoiced labial obstruents were produced with a greater P o than voiced ones: respectively 5.42 vs. 3.56 hPa in modal voice and, 4.91 vs. 4.02 hPa in whisper. This result supports similar trends observed by Weismer and Longstreth in English [START_REF] Weismer | Segmental gestures at the laryngeal level in whispered speech: evidence from an aerodynamic study[END_REF] and Higashiwaka [START_REF] Higashikawa | Perceptual, acoustical and aerodynamic study of whispering[END_REF] in Japanese. In our knowledge, these results are unique for French.

This finding could be seen as a new support for the Glottal Resistance Hypothesis in whispered speech. Indeed, a dynamic adjustment of the glottis as function of the phonological voicing of consonant could explain in part the P o differences observed here. As expected [START_REF] Catford | Fundamental problems in phonetics[END_REF][START_REF] Laver | Principles of phonetics[END_REF], among others (see [START_REF] Mills | Speech motor control variables in the production of voicing contrasts and emphatic accent[END_REF]), the glottal opening would reduce from unvoiced to voiced consonants in whisper. According to these authors, it is produced by a narrower glottis exclusively for whispered voiced consonants. This is partly supported by Mills' endoscopy study [START_REF] Mills | Speech motor control variables in the production of voicing contrasts and emphatic accent[END_REF] who finds no glottal difference for unvoiced obstruents in function of phonations and, a trend to a closer glottis for voiced compared to unvoiced obstruents. Malécot and Peebles [START_REF] Malécot | An optical device for recording glottal adduction-abduction during normal speech[END_REF] did a single similar observation on French, but not Zeroual et al. [START_REF] Zeroual | Physiological study of whispered speech in Moroccan Arabic[END_REF] for Moroccan. Nonetheless, the voicing*phonation interaction (Figure 4, lines for interaction) may indicate a more complex pattern than a manifestation of a voicing contrast in whisper.

First, the P o differences supporting the voicing contrast is significantly halved from modal (1.86 hPa) to whispered (0.89 hPa) phonation. Thus, if the contrast is maintained at the glottal level in whisper, it is also weakened. Secondly, the reduction of the contrast is due to opposite behaviors of voiced and unvoiced consonants. On the one hand, the P o increases for voiced obstruents (from 3.47 to 4.04 hPa) from modal to whispered phonation. On the other, P o decreases for unvoiced ones (from 5.42 to 4.91 hPa). Indeed, the Glottal Resistance Hypothesis could only account for the behavior of voiced consonants produced by a Y-like whisper configuration [START_REF] Catford | Fundamental problems in phonetics[END_REF][START_REF] Laver | Principles of phonetics[END_REF]: P o reduces, because of the narrower glottis inducing a greater glottal resistance against the translaryngeal airflow. For unvoiced ones, it would suggest no change in P o from modal to whispered phonation, because of the constant V-like abduction, expected for their nil (silent) phonation. Hence, why should P o decrease for unvoiced obstruents?

A first hypothesis is that P s is lower in whisper. Nevertheless there are no previous results which would allow us to draw this conclusion, see [START_REF] Stathopoulos | Respiratory and laryngeal function during whispering[END_REF] vs. [START_REF] Konnai | Whisper and phonation: aerodynamic comparisons across adduction and loudness levels[END_REF]. Additionally, this could no longer account for increasing P o of voiced obstruents. Another possibility relies on the perceptual need to low acoustic energy required to whisper. Narrowing the glottis, and so strengthening the glottal resistance against the translaryngeal airflow, P o decreases. P o drop is a way to low the turbulent noise produced at the supraglottal constriction. This can be related to the -4dB weak difference in noise intensity of fricatives between modal and whispered speech [START_REF] Jovicic | Acoustic analysis of consonants in whispered speech[END_REF]. A weak decrease of intensity could be due to a weak difference of glottal abduction. The glottal constriction of whispered voiceless obstruents reported by Zeroual et al. [START_REF] Zeroual | Physiological study of whispered speech in Moroccan Arabic[END_REF] would support this hypothesis.

So, P o patterns in whisper may result from conflicting perceptual constraints relative to intelligibility or phonological requests (as voicing contrast) and needs for discreet communication by soft quiet speech.

Conclusions and perspectives

First, this study supports that the production of the voicing contrast in whispered speech is marked by secondary cues for vowel and obstruent durations, close to those commonly attested for modal speech. For French, only the previous work by Vercherand [START_REF] Vercherand | Production et perception de la parole chuchotée en français: analyse segmentale et prosodique[END_REF] approached this question. Moreover, the more original contribution of the paper concerns the analysis of intraoral pressure (P o ) of obstruents in function of their phonological voicing in whisper compared to modal speech. The observed patterns could surface constraints connected to competing needs for intelligibility and discretion in whisper. So, while the P o increases between modal and whispered phonations for voiced obstruents, it decreases for unvoiced ones. The former pattern could be based on a phonological voicing control, the latter on a constraint of lowintensity speech mode. In both cases, perception seems to play a central role. But, it is no clear what role these kinds of physiological constraints could also have.

Voicing contrast in whisper seems to be another new paradigm of interest to weigh the different constraints of various kinds and levels (physiological, phonological, perceptual or communicative) that operate on speech and communication processes.

Figure 1 :

 1 Figure 1: Segmentation of consonant and preceding /e/ for [ege(pe)] (left) and [eze(te)] in modal (top) and whisper (bottom) speech.

  [F(1,3) = 55.134; p = 0.00505]. The difference ( = 25 ms, i.e. 84 to 59 ms from voiced to unvoiced obstruents) is enhanced compared to that in modal speech ( = 18 ms, 72 to 54 ms). No effect of voicing on the release duration of whispered stops is observed (24 and 23 ms for unvoiced and voiced ones), unlike modal produced with a 50% difference (30 and 20 ms for unvoiced and voiced ones) [F(1,3) = 13.670; p = 0.03434].

  obstruents:  = 15 ms in modal speech [F(1,3) = 93.103; p = 0.00236] and  = 16 ms in whisper [F(1,3) = 245.76; p = 0.00056].

Figure 3 :

 3 Figure 3: Duration of pre-consonantal vowels

Figure 4 :

 4 Figure 4: P o peak of labial obstruents The data clearly show that voicing has a main effect in modal speech [F(1, 7) =135; p = 0.000008] and, by contrast with previous studies, strikingly still in whisper [F(1, 7) =26.2023; p =0.001371]. Among all factors and interactions, only voicing [F(1, 7) = 138.162; p = 0.00007] and the voicing*phonation interaction [F(1,7) = 16.631; p = 0.0047]account for a significant effect (Figure4).In both phonations, the unvoiced labial obstruents were produced with a greater P o than voiced ones: respectively 5.42 vs. 3.56 hPa in modal voice and, 4.91 vs. 4.02 hPa in whisper. This result supports similar trends observed by Weismer and Longstreth in English[START_REF] Weismer | Segmental gestures at the laryngeal level in whispered speech: evidence from an aerodynamic study[END_REF] and Higashiwaka[START_REF] Higashikawa | Perceptual, acoustical and aerodynamic study of whispering[END_REF] in Japanese. In our knowledge, these results are unique for French.This finding could be seen as a new support for the Glottal Resistance Hypothesis in whispered speech. Indeed, a dynamic adjustment of the glottis as function of the phonological voicing of consonant could explain in part the P o differences observed here. As expected[START_REF] Catford | Fundamental problems in phonetics[END_REF][START_REF] Laver | Principles of phonetics[END_REF], among others (see[START_REF] Mills | Speech motor control variables in the production of voicing contrasts and emphatic accent[END_REF]), the glottal opening would reduce from unvoiced to voiced consonants in whisper. According to these authors, it is produced by a narrower glottis exclusively for whispered voiced consonants. This is partly supported by Mills' endoscopy study[START_REF] Mills | Speech motor control variables in the production of voicing contrasts and emphatic accent[END_REF] who finds no glottal difference for unvoiced obstruents in function of phonations and, a trend to a closer glottis for voiced compared to unvoiced obstruents. Malécot and Peebles[START_REF] Malécot | An optical device for recording glottal adduction-abduction during normal speech[END_REF] did a single similar observation on French, but not Zeroual et al.[START_REF] Zeroual | Physiological study of whispered speech in Moroccan Arabic[END_REF] for Moroccan. Nonetheless, the voicing*phonation interaction (Figure4, lines for interaction) may indicate a more complex pattern than a manifestation of a voicing contrast in whisper.First, the P o differences supporting the voicing contrast is significantly halved from modal (1.86 hPa) to whispered (0.89

Acknowledgements

This work is granted by the Ministère de la Recherche et l'Enseignement supérieur and the Région PACA.


David Janin
email: janin@labri.fr

Walking automata in free inverse monoids

Walking automata, be they running over words, trees or even graphs, possibly extended with pebbles that can be dropped and lifted on vertices, have long been defined and studied in Computer Science. However, questions concerning walking automata are surprisingly complex to solve. In this paper, we study a generic notion of walking automata over graphs whose semantics naturally lays within inverse semigroup theory. Then, from the simplest notion of walking automata on birooted trees, that is, elements of free inverse monoids, to the more general cases of walking automata on birooted finite subgraphs of Cayley's graphs of groups, that is, elements of free E-unitary inverse monoids, we provide a robust algebraic framework in which various classes of recognizable or regular languages of birooted graphs can uniformly be defined and related one with the other.

Introduction

General context. Walking automata, be they running over words, trees or even graphs, possibly extended with pebbles, have long been defined and studied in Computer Science [START_REF] Engelfriet | Tree-walking pebble automata[END_REF][START_REF] Engelfriet | Nested pebbles and transitive closure[END_REF]. For instance, tree walking automata with pebbles have been an important subject of study the last decades since they are natural abstract models of machine for XML query languages such as XPATH, or XML transformation languages such as XSL [START_REF] Engelfriet | XML transformation by treewalking transducers with invisible pebbles[END_REF].

Although based on well studied computation models: finite state machines or pushdown automata, questions about walking automata are often surprisingly complex to solve and, to a lesser extent, quite dependent on such or such details in automata's definition.

For instance, in the case of tree languages, bounding the number of pebbles an automaton leads to defining classes of recognizable languages. Various logical characterizations of these classes have been obtained [START_REF] Engelfriet | Nested pebbles and transitive closure[END_REF] and difficult separation results have also been proved [START_REF] Bojańczyk | Tree-walking automata do not recognize all regular languages[END_REF][START_REF] Bojańczyk | Expressive power of pebble automata[END_REF][START_REF] Bojańczyk | Tree-walking automata[END_REF]. However, for separation results, proof arguments apply to the case of pebbles that are marked and visible [START_REF] Bojańczyk | Tree-walking automata do not recognize all regular languages[END_REF][START_REF] Bojańczyk | Expressive power of pebble automata[END_REF], leaving open the cases of unmarked and/or invisible pebbles.

Even though walking automata are sequential machines much like string automata, the classical algebraic tools that have been developed to study word automata are not easily applicable to tree walking automata. Despite numerous results, little is known about the underlying mathematical framework, say in algebra, that walking automata may induce.

Contribution of the paper. In this paper, we initiate the development of an algebraic framework, within inverse semigroup theory, for walking automata. We provide a generic notion of automata walking on edge-labeled graphs. They act as some kind of observers of their input graphs much in the same way observational semantics has been defined in concurrency theory by Hennessy and Milner [START_REF] Milner | Communication and concurrency[END_REF].

Unlike most classical definitions, we do not require walking automata to start and end in the same vertex, neither do we require the complete traversal of input structures. Moreover, the capacity given to a walking automaton to check or not the absence of an (incoming or outgoing) edge labeled by a given letter induces two possible semantics for walking automata, much in the same way there are various observational semantics in [START_REF] Milner | Communication and concurrency[END_REF], with or without observable failures.

The languages recognized by our walking automata are languages of birooted graphs, that is, graphs extended with an input root: the vertex where the run starts, and an output root: the vertex where the run ends. These languages are shown to be closed under root preserving graph morphisms (Lemma 12). Moreover, the sequential composition of partial runs of walking automata is shown to induce a composition of the traversed birooted graphs, yielding an inverse monoid structure (see Remark 3 and Theorem 22).

Then we prove (Theorem 16) that, in many cases, the stronger semantics (with observable reading failures) can be uniformly encoded in the weaker semantics (with unobservable reading failures).

As particular cases, walking automata in Cayley's graphs of finitely generated groups are considered in Section 4. The recognized languages are subsets of monoids known as freest E-unitary inverse monoids [START_REF] Margolis | E-unitary inverse monoids and the Cayley graph of a group presentation[END_REF][START_REF] Meakin | Groups and semigroups: connections and contrasts[END_REF]. Then, based on the underlying monoid structure, an extension of regular expressions is defined and shown (Theorem 25) to characterize the classes of recognizable languages induced by limiting numbers of allowed pebbles.

Graphs

It is very likely that most concepts and properties detailed here have already appeared in the literature. However, for the sake of completeness we provide our own presentation.

Graphs and morphisms. Let

A = {a, b, c, • • • } be a finite alphabet. A (rela- tional) graph on the edge alphabet A is a pair G = V, E with a set of vertex V and sets of a-labeled (directed) edges E(a) ⊆ V × V for all a ∈ A. A graph mor- phism, or simply morphism, from G 1 = V 1 , E 1 to G 2 = V 2 , E 2 is a mapping f : V 1 → V 2 such that f (E 1 (a)) ⊆ E 2 (a), for every a ∈ A. Such a morphism is denoted by f : G 1 → G 2 .
Walking paths. Let Ā = {ā, b, c, • • • } be a copy of the alphabet A. Let (A+ Ā) * be the free monoid generated by A + Ā with the unit (empty word) denoted by 1 and the concatenation of two words u, v ∈ (A + Ā) * simply denoted by uv.

A (back and forth) walking path on the graph G from a vertex x to a vertex y is an alternating sequence of vertices of V and letters of A + Ā of the form

π = x 0 z 1 x 1 z 2 x 2 • • • x n-1 z n x n such that x = x 0 , y = x n and, for every 1 ≤ i ≤ n, we have (x i-1 , x i ) ∈ E(z i )
where, for every a ∈ A, the relation E(ā) denotes the inverse relation

E -1 (a) = {(x, y) ∈ V × V : (y, x) ∈ E(a)}.
The vertex x is the source of such a path. It is denoted by sr(π). The vertex y is the target of such a path. It is denoted by tg(π).

In such path, a letter a ∈ A models a forward traversal of an a-labeled edge and a letter ā ∈ Ā models a backward traversal of an a-labeled edge. The inverse path π -1 of the path π is defined by

π -1 = x n z -1 n-1 x n-1 • • • x 2 z -1 1 x 1 z -1 0 x 0
with (a) -1 = ā and (ā) -1 = a for every a ∈ A. We easily observe that π -1 is indeed a walking path in the graph G from x n to x 0 . As a particular case, the graph G is bideterministic when for every z ∈ A+ Ā, for every (p, q), (p , q ) ∈ E(z), if p = p then q = q . In this case, every path π as above, emanating from a given vertex x, is completely determined by its source x and the path label

λ(π) = z 1 z 2 • • • z n ∈ (A + Ā) * obtained from π by deleting all vertices. Path-induced birooted subgraph. Let π = x 0 z 1 x 1 z 2 x 2 • • • x n-1 z n
x n be a path on the graph G. The subgraph G|π of graph G induced by the path π is defined by G|π = V |π, E|π with the set of vertices V |π = {x 0 , x 1 , • • • , x n } and, for every a ∈ A, the set of a-labeled edges (E|π)(a) defined as the set of pairs (x, y) ∈ V × V such that either xay or yāx occurs as a subsequence in the path π. Then, the following lemma is immediate. Lemma 1. The graph G|π induced by the path π is finite and the inclusion mapping ι : V |π → V that maps every vertex to itself is a one-to-one morphism, i.e. graph G|π is a finite subgraph of graph G.

Definition 2 (Birooted induced subgraphs).

Let π be a path of G. The triple θ G (π) = (G|π, sr(π), tg(π)) defined by distinguishing the source and the target of the path π in the subgraph G|π, is called the birooted subgraph of G induced by the path π. Remark 3. It is an easy observation that the trivial birooted subgraph product θ G (π 1 ) • θ G (π 2 ) defined to be the graph (G|π 1 ∪ G|π 2 , sr(π 1 ), tg(π 2 )) (with union defined over subsets of vertices and edges) when tg(π 1 ) = sr(π 2 ) and 0 otherwise (with 0 an additional zero element) yields an inverse semigroup: for every element x there is a unique element x -1 such that xx -1 x = x and x -1 xx -1 = x -1 . Indeed, we have 0 -1 = 0 and θ G (π) -1 = θ G (π -1 ), and, additionally, it can be shown that the non zero idempotent elements exactly correspond to the birooted graphs induced by cyclic paths.

The much more interesting case when the birooted subgraphs are invariant under translation (in Cayley's graphs) is detailed in Section 4 below.

Vertex-labeled graphs. So far, the graphs we consider have no vertex label. The following definition and lemma shows that this fact does not reduce the generality of our language theoretical study.

Definition 4 (Induced vertex label). The vertex label of a vertex

x ∈ V in a graph G = V, E is defined to be the set λ V (x) = {a ∈ A : (x, x) ∈ E(a)}.
The following lemma, whose proof is immediate, emphasizes the relevance of this notion.

Lemma 5.

Let G = V, E be a graph on the edge alphabet A. Let g : V → P(B) be a vertex labeling function with some new alphabet B disjoint from A. Let G, g be the resulting vertex-labeled graph and let ϕ( G, g ) = V , E be the edge-labeled graph defined by V = V , by E (a) = E(a) for every a ∈ A, and

E (b) = {(x, x) ∈ V × V : b ∈ g(v)} for every b ∈ B.
Then, the vertex identity mapping from V into V is a one-to-one and onto graph morphism from G into ϕ( G, g ). Moreover, ϕ is a one-to-one mapping from the class of graphs with A-labeled edge and P(B)-labeled vertices into the class of (A ∪ B)-labeled edges such that, given the vertex labeling λ V : V → P(A + B) as defined above, then, for every v ∈ V = V , we have

g(v) = λ V (v) ∩ B.
In other words, graphs with vertex labels are easily encoded into graphs without vertex labels. Moreover, in the case both A and B are finite, such a mapping induces a fairly simple MSO-transduction (see [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF] Chap. 7). It follows that every MSO-definable language of graphs with A-labeled edges and P(B)-labeled vertices can be encoded into an MSO-definable language of graphs with A ∪ Blabeled edges. Since graphs with unlabeled vertices are particular case of graphs with labeled vertices this really says that, up to MSO definable languages, studying languages of edge-labeled graphs or languages of edge-and-vertex-labeled graphs is essentially the same.

Walking on graphs

In this paper, a walking automata is sort of a graph observer that traverses the input graph possibly dropping and lifting (in the reverse order) some pebbles. Since walking automata cannot jump between disconnected graphs, all graphs considered from this point are assumed to be connected via walking paths.

Definition 6 (Walking automata with pebbles). A walking automata with pebbles on the alphabet A is a tuple

A = Q, I, T, δ, ∆ with set of states Q, initial states I ⊆ Q, terminal states T ⊆ Q, edge transitions δ(z) ⊆ Q × Q for every z ∈ A+ Ā,
and pebble transitions ∆((r, s)) ⊆ Q×Q for every (r, s) ∈ Q×Q.

Informally, from a given vertex, the automaton can traverse forward any outgoing a-labeled edge (reading a) or it can traverse backward any incoming alabeled edge (reading ā). In both cases, the automaton state is updated according to the first-order transition function δ applied to the traversed edge label a or ā. Additionally, the automaton may drop a pebble on that vertex, interrupting the current run and starting a new subrun. It may also lift a pebble, ending the current subrun and resuming the former run. When ending a subrun, the automaton state is updated according to the second-order transition function ∆ applied to the pair of states resulting from the start state and the stop state of the subrun.

Definition 7 (Automaton configuration). Let

A = Q, I, T, δ, ∆ be a walk- ing automaton. Let G = V, E be a graph on the alphabet A. An automaton configuration Γ ∈ (Q × Q × V ) + is a non-empty stack of (dot separated) triples over Q × Q × V .
In a stack of the form Γ.(p, q, x) with p, q ∈ Q and x ∈ V , the triple (p, q, x) describes the current run configuration: from state p, the automaton A walked to the current vertex x reaching current state q. The additional stack Γ , possibly empty, contains the configurations of formerly interrupted runs.

As formalized in the next definition, when dropping a pebble on a vertex x, the automaton interrupts the current run, pushes its configuration (p 1 , q 1 , x) on the stack, and starts a subrun in a configuration (p 2 , p 2 , x).

On the contrary, when lifting a pebble from a vertex x, the automaton terminates a subrun in a configuration (p 1 , q 1 , x), pops the saved configuration (p 2 , s, x), and resumes the former run in an updated configuration (p 2 , q 2 , x), chosen according to the (second-order) transition condition (s, q 2 ) ∈ ∆((p 1 , q 1 )).

Definition 8 (Automaton transition and run).

On a graph G = V, E , a transition step from a configuration Γ 1 .(p 1 , q 1 , x) to a configuration Γ 2 .(p 2 , q 2 , y) reading z ∈ {1} ∪ A ∪ Ā is defined according to one of the following three cases:

(1) edge traversal: z ∈ A∪ Ā, Γ 1 = Γ 2 , p 1 = p 2 , (q 1 , q 2 ) ∈ δ(z) and (x, y) ∈ E(z), (2) pebble drop: z = 1, y = x, Γ 2 = Γ 1 • (p 1 , q 1 , x) and q 2 = p 2 , (3) pebble lift: z = 1, y = x, Γ 1 = Γ 2 • (p 2 , s, x) and (s, q 2 ) ∈ ∆((p 1 , q 1 )).
Such a transition step is denoted by

Γ 1 .(p 1 , q 1 , x) z Γ 2 .(p 2 , q 2 , y).
An run of the automaton A on the graph G from a vertex x to a vertex y is then defined as a sequence of transition steps

ρ = Γ 0 .(p 0 , q 0 , x 0 ) z1 Γ 1 .(p 1 , q 1 , x 1 ) • • • zn Γ n • (p n , q n , x n ) with x 0 = x and x n = y, also denoted by ρ = Γ 0 • (p 0 , q 0 , x 0 ) * u Γ n • (p n , q n , x n ) with u = z 1 z 2 • • • z n . The path π(ρ) induced by run ρ is defined by π(ρ) = x 0 z 1 x 1 z 2 x 2 • • • x n-1 z n x n
Such a run ρ is an accepting run from x to y when Γ 0 is the empty stack with p 0 = q 0 ∈ I (the first configuration is initial), and Γ n is the empty stack with p n ∈ I and q n ∈ T (the last configuration is terminal).

Given an integer k ≥ 0, the run ρ is k-accepting run when it is accepting and |Γ i | ≤ k for every 0 ≤ i ≤ n, where |Γ i | is the length of the sequence Γ i . For notational purpose, an accepting run with no bound on the number of allowed pebbles is also called an ∞-accepting run. Example 9. An example of run is depicted Figure 1 where configuration stacks are depicted vertically.

(p0, p0, x0) (p0, p1, x1) (p0, p2, x1) (p0, p3, x2) (q0, q0, x1) (q0, q1, x1) u1 u2 u3 drop lift (Γ0) (Γ1) (Γ2) (Γ3) Figure1. A run Γ 0 * u1 Γ 1 * u2 Γ 2 * u3 Γ 3 .
In this run, when no other pebble but the one depicted above is used, then first order transition conditions imply that (p 0 , p 1 ) ∈ δ(u 1 ), (q 0 , q 1 ) ∈ δ(u 2 ) and (p 1 , p 2 ) ∈ δ(u 3 ), with an obvious extension of δ to (A + Ā) * , and second order transition conditions imply that (p 1 , p 1 ) ∈ ∆((q 0 , q 1 )).

Definition 10 (Recognized languages).

Given a class of graphs G (possibly omitted when clear from the context), the language recognized (resp. krecognized) by the automaton A in the class of graph G is the set

L ∞ G (A) (resp. L k G (A)
) of birooted graphs (G, x, y) with G ∈ G and x, y two vertices of G, such that there is an accepting run (resp. a k-accepting run) of the automaton A over G from x to y. Remark 11. The walking automata defined here are walking automata with unmarked and invisible pebbles in the sense of [START_REF] Engelfriet | XML transformation by treewalking transducers with invisible pebbles[END_REF]. However, generalizing Pécuchet's study of two-way automata on strings [START_REF] Pécuchet | Automates boustrophedon, semi-groupe de Birget et monoide inversif libre[END_REF] (see also [START_REF] Janin | On languages of one-dimensional overlapping tiles[END_REF][START_REF] Dicky | Two-way automata and regular languages of overlapping tiles[END_REF]), we do not require that accepting runs starts and ends in the same vertex of the input structures. Moreover, our definition also differs from the definition proposed in [START_REF] Engelfriet | XML transformation by treewalking transducers with invisible pebbles[END_REF][START_REF] Bojańczyk | Tree-walking automata[END_REF] in the sense that, a priori, the absence of edges cannot be detected by the automata and the walking automaton is not required to traverse the entire structure. The consequences of these facts are discussed below.

Lemma 12. Let A be a walking automaton on the alphabet

A. Let G 1 = V 1 , E 1 and G 2 = V 2 , E 2 be

two graphs on the same alphabet. Assume that there is a graph morphism

f : G 1 → G 2 . Then, for every 0 ≤ k ≤ ∞ and x, y ∈ V 1 , if (G 1 , x, y) ∈ L k (A) then (G 2 , f (x), f (y)) ∈ L k (A).
In general, the converse does not hold. However, as detailed below, the converse holds in the case the graph G 1 is the subgraph of G 2 induced by an accepting run.

Definition 13 (Graphs induced by a run).

Let ρ : Γ 1 Γ 2 be a run in a graph G from x to y. The graph induced by a run ρ is defined to be the subgraph G ρ = G|π(ρ) induced by the path π(ρ) traversed by A in G.

Then we have: Lemma 14. Let G be a graph such that (G, x, y) ∈ L k (A) via an accepting run ρ. Let G ρ be the graph induced by the run ρ. Then (G ρ , x, y) ∈ L k (A).

The more classical notion of accepting runs defined by complete traversals of the input structure can be related with ours as follows.

Definition 15 (Strict recognizability).

A birooted graph (G, x, y) is strictly recognized (resp. strictly k-recognized) by an automaton A when there is an accepting (resp. k-accepting) run ρ of A over G from x to y such that (G ρ , x, y) and (G, x, y) are isomorphic.

As an immediate corollary of Lemma 1, Lemma 12 and Lemma 14, we thus have: Theorem 16. Let A be a walking automaton. For every k ≥ 0, let L k S (A) be the class of birooted graphs strictly k-recognized by A and let L k (A) the class of birooted graphs k-recognized by A. Then L k (A) is the morphism closure of the language L k S (A), that is, (G, x, y) ∈ L k (A) if, and only if, there exists

(G , x , y ) ∈ L k S (A) and a graph morphism f : G → G such that f (x ) = x and f (y ) = y.
In particular, when the birooted structures cannot be related by morphisms (as with end markers in two-way word automata [START_REF] Dicky | Two-way automata and regular languages of overlapping tiles[END_REF]), studying strict recognizability just amounts to study recognizability.

Walking in Cayley's graphs of groups

So far, we have not much used the fact that walking automata recognize sets of birooted graphs. When the underlying graph G is the Cayley's graph of a (presented) group, then the (isomorphic classes of) finite birooted subgraphs induced by paths form a inverse monoid (see [START_REF] Margolis | E-unitary inverse monoids and the Cayley graph of a group presentation[END_REF] for more details and also [START_REF] Meakin | Groups and semigroups: connections and contrasts[END_REF] for a general presentation). Based on the underlying monoid structure, various classes of languages can then be defined and characterized by means of certain restriction of walking automata.

Definition 17 (The Cayley graph of a presented group).

Let G be a group generated by A ⊆ G and let ϕ : (A + Ā) * → G be the corresponding inverse-preserving monoid morphism1 . Then, the Cayley graph of the presented group G is defined to be the graph C G = V, E with vertex set defined by V = G and, for every a ∈ A, edge set defined by

E(a) = {(x, y) ∈ V × V : x • ϕ(a) = y}.
For convenience, we extend the edge relation function

E to (A + Ā) * by taking E(u) = {(x, y) ∈ G × G : x • ϕ(u) = y}.
As a particular case, since ϕ is inverse-preserving and G is a group, we indeed have E(ā) = E(a) -1 which is consistent with our previous extension of the edge relations.

Remark 18. Clearly, the Cayley graph C G of the group G is a (possibly infinite) bideterministic graph as well as its (finite) birooted subgraphs. Depending on the chosen group, various interesting examples can be defined (see [START_REF] Meakin | Groups and semigroups: connections and contrasts[END_REF]).

For instance, taking the free group F G(A) we have birooted trees. Taking the group defined from A = {a, b, c, d} by cc = 1, dd = 1 and cd = 0, we obtain vertex-labeled birooted trees with edges labeled by a or b and, following Remark 5, vertices labeled over P({c, d}). Thanks to the axiom cd = 0, only the birooted graph encoding zero has a vertex labeled by both c and d. The language theory of these vertex-labeled birooted graphs has been studied in [START_REF] Janin | Algebras, automata and logic for languages of labeled birooted trees[END_REF][START_REF] Janin | On labeled birooted trees languages: Algebras, automata and logic[END_REF].

Another example, taking the group defined from A = {a, b, c, d} by ab = ba, cc = 1 and dd = 1 and cd = 0, we obtain vertex-labeled birooted grids with (say) horizontal edges labeled by a, vertical edges labeled by b, and, similarly, vertices labeled over P({c, d}).

In other words, this group-theoretic based approach to graphs leads to a vast variety of classes of birooted graphs.

Definition 19 (Induced graphs revisited).

Let G be a group presented by a morphism ϕ, and let C G be its Cayley graph. For every u ∈ (A + Ā) * , let C G |u be the graph induced by u defined by

C G |u = V, E with set of vertices V = ϕ(Pref (u)) where Pref (u) = {v ∈ (A + Ā) * : ∃w ∈ (A + Ā) * , u = vw}
is the set of word prefixes of u, and sets of edges E(a) defined as the union of

{(ϕ(v 1 ), ϕ(v 2 )) ∈ V × V : v 1 a = v 2 } and {(ϕ(v 2 ), ϕ(v 1 )) ∈ V × V : v 1 a -1 = v 2 }.
The next lemma, whose proof is immediate, relates our two definitions of induced subgraphs.

= (V, E, 1, x) where V ⊆ G is a finite subset of G such that 1, x ∈ V , E(a) ⊆ {(x, y) ∈ V × V : x • ϕ(a)
= y} for every a ∈ A, and such that, the resulting subgraph V, E is connected. The set of such finite birooted subgraphs of C G is denoted by BSG(G). Then, the product of two birooted finite subgraphs

B 1 = (V 1 , E 1 , 1, x 1 ) and B 2 = (V 2 , E 2 , 1, x 2 ) is defined by B 1 • B 2 = (V 1 ∪ x 1 • V 2 , E, 1, x 1 • x 2 ) with E(a) = E 1 (a) ∪ x 1 • E 2 (a) with the notation x 1 • E 2 (a) = {(x, y) ∈ (x 1 • V 2 , x 1 • V 2 ) : (x, y) ∈ E 2 (a)} for every a ∈ A.
Theorem 22 (Margolis,Meakin [START_REF] Margolis | E-unitary inverse monoids and the Cayley graph of a group presentation[END_REF]). The set BSG(G) with birooted graph product is an inverse monoid. The mapping θ G : (A + Ā) * → BSG(G) is an onto monoid morphism, and, for every u ∈ (A + Ā) * , we have θ G (u) -1 = θ G (u -1 ) and θ G (u) is idempotent if and only if ϕ(u) = 1. free group generated by A. They have to be read non-strict in all other cases.

0-PWA S ⊂ 1-PWA S ⊆ • • • k-PWA S • • • ⊆ ω-PWA S = = = REC ⊂ 0-REG ⊂ 1-REG ⊆ • • • k-REG • • • ⊆ k k-REG ⊂ ⊂ ⊂ 0-REG ↓ ⊂ 1-REG ↓ ⊆ • • • k-REG ↓ • • • ⊆ k k-REG ↓ = = = 0-PWA ⊂ 1-PWA ⊆ • • • k-PWA • • • ⊆ ω-PWA
Proof. Each horizontal inclusion follows from the definition. The separation result REC ⊂ 0-REG is known over languages of birooted trees [START_REF] Silva | On free inverse monoid languages[END_REF]. The separation 0-PWA S ⊂ 1-PWA S follows from the language example of idempotent birooted trees that cannot, by a simple pumping argument, be recognized by an automaton without pebble but that can easily be recognized with a single pebble (see below).

The first row of (vertical) equalities follows from Lemma 26, proven below. Over birooted trees, that is, in the case G = F G(A), these equalities imply the separation result 0-REG ⊂ 1-REG. Indeed, over birooted trees the language of idempotent trees is recognizable by a one-pebble automaton while a simple argument shows that is cannot be recognized without pebble.

The second row of (vertical) inclusions follows from the known fact [START_REF] Stephen | Presentations of inverse monoids[END_REF] (see also [START_REF] Janin | Inverse monoids of higher-dimensional strings[END_REF]) that, for all birooted graphs x, y ∈ BSG(G), there is a root-preserving graph morphism f : y → x if and only if x ≤ y in the natural order defined by x ≤ y when x = e • y for some idempotent element e.

It follows that, we have X ↓ = E(BSG(G)) • X for all language X ⊆ BSG(G), and the language (BSG(G)) E of all idempotent elements of BSG(G) belongs to 1-REG as shown by the one-state automaton A = {p, q}, {p}, {q}, δ, ∆ with δ(z) = {(p, p)} for every z ∈ A + Ā and ∆((r, s)) = {(p, q)} when r = s = p and ∆((r, s)) = ∅ otherwise. The fact these inclusions are strict follows, for language of birooted trees, from the fact that the language {θ G (a)} is not closed under morphisms since it is not closed under natural order.

The last row of (vertical) equalities follows from the first row of vertical equalities and Theorem 16.

2

Lemma 26. For every ≥ 0, we have k-PWA S = k-REG.

Proof (sketch of). Direct inclusion (⊆)

. Let A = Q, I, F, δ, ∆ be a finite-state walking automaton. For every pair of states p, q ∈ Q, let L k S (p, q) ⊆ BSG(G) be the class of languages strictly k-recognized by the automaton A from an initial configuration of the form (p, p, x) to a terminal configuration of the form (p, q, y) for some vertices x, y. Let E k S (p, q) be restriction of that language to the case x = y, or, equivalently, E k S (p, q) = (L k S (p, q)) E . Then, much like in the proof of Kleene's theorem for regular languages of strings, by mimicking walking automata transition rules, we can define a system of equations relating the languages L k S (p, q) and E k S (p, q) which resolution yields the expected regular expressions.

Reverse inclusion (⊇). This can be proved by induction on the syntactic complexity of regular expressions. More precisely, we first prove that the singleton languages {θ G (1)} and {θ G (z)} for every z ∈ A + Ā, are strictly 0-recognizable by finite automata. Then, it suffices to show that the class of languages strictly k-recognized by finite walking automata is closed under sum, product and star, and that, if X is strictly k-recognized by a finite walking automaton, then X E is (k + 1)-recognized by a finite walking automaton.

It must be noticed that the existence of second order transitions makes these constructions slightly more complex than in the case of string languages. In particular, building an automaton A * such that L k S (A * ) = (L k S (A)) * is done from k + 1 copies of the automaton A. Indeed, this allows to count in any state the number of pebbles that have been dropped and to ensure, between two runs of the automaton A simulated in the automaton A * , that all pebbles have been lifted. 2

Conclusion

We have defined walking automata on graphs. By allowing automata to start and stop in arbitrary graph vertices, we have defined the language recognized by a walking automaton in terms of birooted graphs that form inverse semigroups. Although we do not require walking automata to perform complete traversal of their input structures, thanks to the preorder relation induced by root preserving graph homomorphisms, we eventually provide a correspondence between our notion of recognizability and the more classical one.

In the particular case of Cayley's graphs of groups, we obtain a rather rich array of classes of recognizable languages of birooted graphs, and a notion of kregular expressions that characterizes the number of allowed pebbles in accepting runs (Theorem 25). How these induced hierarchies of languages of trees or graphs may be related is left as an intriguing open problem.

We conjecture that the hierarchy induced by the number of pebbles is strict for languages of birooted trees. The strictness of the hierarchies for languages of birooted graphs induced by other groups than the free group is also an open problem. Ideally, the algebraic framework proposed here may provide simpler arguments than in [START_REF] Bojańczyk | Expressive power of pebble automata[END_REF] for solving these questions.

It has already been observed that an adequate algebraic theory for inverse monoid morphisms can be developed by means of certain kind of premorphisms instead of morphisms [START_REF] Janin | Quasi-recognizable vs MSO definable languages of one-dimensional overlapping tiles[END_REF][START_REF] Janin | Algebras, automata and logic for languages of labeled birooted trees[END_REF][START_REF] Janin | Towards a higher dimensional string theory for the modeling of computerized systems[END_REF][START_REF] Janin | On labeled birooted trees languages: Algebras, automata and logic[END_REF]. As a matter of fact, transition monoids of walking automata induce a different type of premorphisms that could also be investigated as new language recognizers.

Lemma 20 .

 20 Let π be a path in C G . Let λ(π) ∈ (A + Ā) * be the word of (A + Ā) * obtained from π by deleting all vertices. The birooted subgraph θ C G (π) induced by the path π isn the graph C G is isomorphic to the birooted graph (C G |λ(π), 1, ϕ(u)). This leads us to the following definition: Definition 21 (Birooted subgraphs and their product). A birooted finite subgraph of the Cayley graph C G of the presented group G is a quadruple B

The group G is presented by the morphism ϕ.

Remark 23. In [START_REF] Margolis | E-unitary inverse monoids and the Cayley graph of a group presentation[END_REF], it is proved that BSG(G) is the freest inverse monoid generated by A whose group image is the group G. This result is much stronger than Theorem 22.

A subset X ⊆ BSG(C G ) of the monoid BSG(G) is called a G-language. Following our previous definitions, given 0 ≤ k ≤ ∞, the G-language X is krecognized (resp. strictly k-recognized) by a walking automaton A when

. Then, let k-PWA (resp. k-PWA S ) be the class of G-languages k-recognized (resp. strictly k-recognized) by a finite state walking automaton.

We aim at providing a Kleene-like characterization of these classes of languages by means of regular expressions. For such a purpose, the following operations are defined over G-languages:

(1) sum :

A k-regular expression is defined to be any finite expression built over the alphabet A ∪ Ā ∪ {1}, combined with sum, product, star and idempotent restriction operators such that the nesting depth of idempotent projection is at most k. A language X ⊆ BSG(G) is a k-regular language when it can be defined by a k-regular expressions, mapping 1 to θ G (1) and every letter z ∈ A + Ā to its birooted image θ G (z) ∈ BSG(G).

The class of k-regular languages is denoted by k-REG. The class of languages recognizable by finite monoids M and morphisms from BSG(G) onto M is denoted by REC . Observe that, by definition, the usual class REG of languages definable by finite Kleene regular expressions equals 0-REG. Last, for every class of languages X, let X ↓ be the class of closure of the languages of X under root-preserving graph morphisms within BSG(G).

Remark 24. Observe that the notion of k-recognizability is not necessarily preserved under (inverse) monoid morphisms. Indeed, given an inverse monoid morphism ϕ : M → N , we certainly have ϕ(X E ) ⊆ ϕ(X) E for every X ⊆ M . However, the reverse inclusion may be false as illustrated by the expression abā b. Indeed, it induces a non-idempotent birooted tree in the free inverse semigroup but a cycle in any E-unitary inverse semigroup induced by a group in over which the equation ab = ba is satisfied.

Theorem 25 (Hierarchy). For every presented group G generated by A, the following equalities and inequalities holds. In this figure, strict inequalities ⊂ are only known to hold in the free inverse monoid, that is, when G = F G(A): the