[affiliation=1,2]Yu-KuanFu [affiliation=1]Cheng-KuangLee [affiliation=2]Hsiu-
HsuanWang [affiliation=2]Hung-yiLee

# Investigating the Effects of Large-Scale Pseudo-Stereo Data and Different
Speech Foundation Model on Dialogue Generative Spoken Language Model

###### Abstract

Recent efforts in Spoken Dialogue Modeling aim to synthesize spoken dialogue
without the need for direct transcription, thereby preserving the wealth of
non-textual information inherent in speech. However, this approach faces a
challenge when speakers talk simultaneously, requiring stereo dialogue data
with speakers recorded on separate channels—a notably scarce resource. To
address this, we have developed an innovative pipeline capable of transforming
single-channel dialogue data into pseudo-stereo data. This expanded our
training dataset from a mere 2,000 to an impressive 17,600 hours,
significantly enriching the diversity and quality of the training examples
available. The inclusion of this pseudo-stereo data has proven to be effective
in improving the performance of spoken dialogue language models. Additionally,
we explored the use of discrete units of different speech foundation models
for spoken dialogue generation.

###### keywords:

spoken dialogue modeling, speech generation, human-computer interaction

##  1 Introduction

Spoken dialogue, characterized by spontaneous turn transitions and occasional
overlaps, embodies the natural flow of human communication [1]. These moments
of silence, laughter, and overlapping speech are vital cues within
conversations [2, 3, 4]. Yet, current dialogue systems like Siri often
overlook these signals, relying on a conventional pipeline of transcribing,
generating textual response, and converting it to speech, resulting in
unnatural dialogues [5].

Advancements in self-supervised (SSL) models [6, 7, 8, 9] and textless spoken
language modeling [10, 11, 12] now enable encoding speech signals directly
into discrete tokens without implicitly transcribing to text. This preserves
both verbal and nonverbal cues, aligning with human turn-taking behaviors. The
introduction of the dialogue generative spoken language model (dGSLM) [13]
marks a milestone, employing a dual tower transformer to process input tokens
from separate channels and enhance dialogue generation. While dGSLM has shown
to generate natural human dialogue, it faces challenges in generating semantic
coherence dialogue due to limited data. The training data of dGSLM is a
notably scarce resource because it requires stereo dialogue data.

Acquiring stereo dialogue data is challenging. In contrast, single-channel
dialogue content is abundant. For example, in this paper, we gathered
approximately 20k hours of podcasts. While the speakers of podcasts are mixed
into one channel, which dGSLM can not directly use, we proposed a pipeline to
automatically generate pseudo-stereo data through the following process:
first, employing speaker diarization to pinpoint segments featuring two
speakers; next, leveraging source separation techniques to isolate overlapping
frames; and finally, applying speaker verification to allocate the separated
speech to its respective speakers. This meticulous process yielded a
substantial 15.6k hours of pseudo-stereo dialogue training data111We open
source our dataset: https://huggingface.co/datasets/YuKuanFu/Podcast_Dialogue.

Additionally, we explored the use of discrete units from state-of-the-art
(SOTA) foundation models for dGSLM. Our investigation revealed that merely
scaling foundation models led to poor vocoder performance when resynthesizing
speech from discrete units. However, employing an ASR fine-tuned foundation
model showed significant improvements across all aspects. By integrating the
ASR fine-tuned model with our pseudo-stereo data, dGSLM excelled in producing
dialogue semantic coherence222Generation samples can be found at
https://anonymous78264.github.io/pseudo-stereo-
data/?fbclid=IwAR0MGdFnQeUcnojhQGGk0HaAYgBxhnhblIpU3xnGRNfPPO_hxHOf6Ea_PGM.

##  2 Related Work

###  2.1 Speech Unit Language Modeling

The Textless NLP series of works introduced a framework to address speech
tasks using discrete NLP approaches. This framework can be broadly divided
into three components [10, 12]: encoding speech into discrete units by
clustering its pretrained self-supervised learning (SSL) representations [7,
8, 6, 9], autoregressively generating discrete units, and resynthesizing
speech from these discrete units[14].

Quantized unit sequences are shorter than the original signal, significantly
reducing computational costs and enabling the modeling of speech through NLP
approaches. Additionally, this framework has successfully generated natural
speech without textual information [10]. With more fine-grained discrete
units, it can preserve non-verbal vocalizations and even control the prosody
of speech [11].

###  2.2 Spoken Dialogue Generation

Current commercial spoken dialogue generation models (e.g., Siri, Alexa,
Google Assistant) divide spoken dialogue into three components: ASR, text-base
dialogue language model, and TTS [5]. These models primarily focus on semantic
content, often neglecting other speech related information, resulting in
unnatural dialogue.

Figure 1:  The pipeline of generating pseudo-stereo data from single-channel
dialogue data. We split the process into 3 steps: speaker diarization, source
separation, and speaker verification.

Recent work has focused on generating a diverse set of spoken dialogues that
incorporate turn-taking and acoustic information to mimic human-like
conversational flow [15, 16]. dGSLM [13] is the first spoken dialogue
generation model that can successfully generated natural dialogue with non-
verbal signals. It follows the three components mentioned in Sec.2.1. It first
encodes two speakers by clustering the representations of SSL models
separately, and generates two parallel discrete unit sequences from a dual-
tower transformer language model. Moreover, it splits the next unit prediction
into edge-unit prediction and duration prediction during training for better
performance. Although dGSLM can generate natural dialogue, the lack of data
results in poor performance in semantic coherence within dialogues.

##  3 Method

Our methodology is an enhancement of the dGSLM framework [13]. dGSLM
decomposes spoken dialogue generation into three components: the Speech-to-
Units encoder, the dual-tower unit dialogue language model, and the Units-to-
Speech vocoder. The original dGSLM model encountered difficulties in producing
semantically coherent dialogue, a problem attributed to insufficient data and
suboptimal unit encoding [13]. Thus in this study, we places emphasis on two
main objectives: augmenting the training of dGSLM with additional data and
improving the performance of unit encoding.

The following sections present a detailed overview of our approach, covering
the process of generating pseudo-stereo data from single-channel recording and
the Speech-to-Units encoders used.

###  3.1 Pseudo-stereo Data Generation

dGSLM utilized the Fisher Telephone conversation collection protocol [17] as
the training dataset for its components. The Fisher dataset is a well-known
benchmark for spoken dialogue datasets, containing around 2000 hours of
telephonic dialogues. Each conversation in the Fisher dataset involves two
speakers recorded in separate audio channels, resulting in a stereo audio
setup.

However, most available dialogue data do not separate speakers, often existing
as single-channel audio. To overcome this limitation, we developed a pipeline
to disentangle speakers from single-channel audio and store their speech into
separate channels, creating pseudo-stereo data. This strategy enhanced the
training dataset for dGSLM by incorporating a wider variety of data, which
enriched the model's learning process and boosted its overall performance. The
framework of this approach is illustrated in Fig. 1. This process is divided
into three steps:

####  3.1.1 Speaker Diarization

We used a Speaker Diarization model ($SD$) [18, 19] to disentangle speakers
from a segment of raw audio ($Mix$), resulting in a set of speaker-duration
tuples:

$SD(Mix)=\\{(p,s,e)\mid p\in\\{p_{1},p_{2}\\},\,e>s\\}$ (1)

Here, we only preserved segments that contains exactly two speakers. $p_{1}$
and $p_{2}$ represent the first and second speakers, while $s$ and $e$ are the
start and end frames of the segment that $p$ is speaking.

We created a 2-channel audio ($Psuedo$) filled with silences, matching the
length of $Mix$ (we use $Psuedo_{1}$, $Psuedo_{2}$ to indicate its first,
second channel respectively). With the output of $SD$, we identified non-
overlapping frames ($O^{\prime}$) and overlapping frames ($O$):

$\displaystyle O^{\prime}$ $\displaystyle=\\{(p,s,e)\mid\text{only p is
speaking from }s\text{ to }e\\}$ (2) $\displaystyle O$
$\displaystyle=\\{(s,e)\mid p_{1},p_{2}\text{ are both speaking from }s\text{
to }e\\}$

We then assigned non-overlapping intervals in $Mix$ to $Pseudo$ accoring to
$O^{\prime}$ (correspond to the step 1 in Fig. 1):

1:for $i$ in 1, 2; do

2: for $(p_{i},s,e)$ in $O^{\prime}$; do

3: $Pseudo_{i}[s:e]\leftarrow\text{Mix}[s:e]$

4: end for

5:end for

####  3.1.2 Source Separation

Source separation model ($SS$) [20, 21, 22] can effectively separate the
overlapping speech ($o$):

$SS(o)=sep_{1},sep_{2}$ (3)

Here, $sep_{1}$ and $sep_{2}$ represent the separated speech for the two
speakers (correspond to Step 2 Fig. 1). However, at this juncture, it remains
unclear which of these segments can be attributed to speaker $p_{1}$ and which
to speaker $p_{2}$.

Note that we can not directly apply $SS$ on entire $Mix$, as current source
separation algorithms struggle with sparse overlapping speech [23].

####  3.1.3 Speaker Verification

We match $sep_{1}$ and $sep_{2}$ their corresponding speaker by speaker
verification ($SV$) [24, 25]. $SV$ compares two audio clips and returns the
similarity of their speaker embeddings (correspond to the step 3 in Fig.1):

$SV(r_{i},sep_{j})=Sim_{i,j}$ (4)

Here, $r_{i}$ is a reference clip randomly selected from non-overlapping
frames from $p_{i}$ (see Fig.1). We assigned $sep_{1}$ and $sep_{2}$ based on
the similarities:

1:for $(s,e)$ in $O$; do

2: $sep_{1},sep_{2}=SS(Mix[s:e])$

3: $Sim_{i,j}=SV(r_{i},sep_{j})$ for $i$, $j$ in $(1,2)\times(1,2)$

4: if $Sim_{1,1}+Sim_{2,2}>Sim_{1,2}+Sim_{2,1}$ then

5: $Pseudo_{1}[s:e],Pseudo_{2}[s:e]\leftarrow sep_{1},sep_{2}$

6: else

7: $Pseudo_{1}[s:e],Pseudo_{2}[s:e]\leftarrow sep_{2},sep_{1}$

8: end if

9:end for

By employing this pipeline, we successfully disentangled speakers in spoken
dialogue, enabling scalable creation of diverse and large dialogue audio
corpora.

Table 1: This table shows the turn-taking metrics. We report their difference
with ground truth. Dur. indicates duration of events (seconds), and Occur.
indicates occurence (times)

Encoder Type $\Delta$ IPU $\Delta$ Gap $\Delta$ Overlap $\Delta$ Pause Dur.
Occur. Dur. Occur. Dur. Occur. Dur. Occur. (a) Ground Truth 0 (56.86) 0
(19.86) 0 (2.61) 0 (2.88) 0 (4.29) 0 (3.96) 0 (4.83) 0 (7.42) Fisher / Fisher
+ Pseudo-stereo Aduio (b) WavLM base+ 3.17 / -3.96 3.39 / -1.96 -0.37 / 1.02
1.49 / -0.57 2.23 / -0.83 4.47 / 0.95 -0.57 / 2.1 0.74 / 1.92 (c) large -3.72
/ 5.36 9.96 / 2.93 0.43 / -1.00 3.58 / 0.91 0.22 / 3.14 3.72 / 4.47 3.5 /
-1.24 5.54 / 0.62 (d) HuBERT base 4.35 / 9.38 5.66 / 5.5 -0.35 / -0.94 2.06 /
0.91 2.64 / 6.25 6.54 / 8.49 -1.26 / -2.2 -0.6 / -0.98 (e) large 16.13 / 12.59
8.62 / 5.89 -0.92 / -1.33 1.01 / -0.28 13.94 / 10.97 11.08 / 8.62 -1.28 /
-0.32 -0.81 / 0.7 (f) large ft 1.91 / 2.56 12.2 / 10.98 0.69 / -0.07 4.79 /
3.14 2.65 / 2.57 7.24 / 7.1 0.04 / 0.07 2.68 / 3.26

###  3.2 Discrete Units Encoder

The original dGSLM utilized HuBERT [7] pretrained on the Fisher dataset to
obtain better phonetic discriminated representations, followed by training a
k-means model to cluster its hidden representation. However, pretraining
HuBERT on target domain data is time-consuming and its generalizability is
uncertain. To investigate the suitability of existing publicly available
speech foundation models for spoken dialogue language model, we explored the
base and large versions of HuBERT and WavLM [8], which are state-of-the-art
speech foundation models.

Additionally, we incorporated HuBERT large fine-tuned (HuBERT large ft) as the
speech encoder. HuBERT large ft is obtained by fine-tuning HuBERT large by
connectionist temporal classification (CTC) objective. ASR models tend to
provide more phonetic information, which might be beneficial for the spoken
dialogue language modeling task333We are of the view that the investigation of
speech encoders can inclusively incorporate those trained on labeled data,
provided they can effectively model the nuances of non-verbal speech
information..

##  4 Experiment

###  4.1 Data Setup

In addition to Fisher Dataset [17] used in dGSLM [13], we scrape about 20k
hours of podcast raw audio from Apple Podcast444https://www.apple.com/apple-
podcasts/, and after applying our pipeline described in Sec. 3.1, we create
about 15.6k hours of pseudo-stereo spoken dialogue data.

To our knowledge, the existing large-scale datasets containing spoken dialogue
are GigaSpeech [26] and Spotify Podcast Dataset [27]. However, GigaSpeech
contains at most 7500 hours of raw dialogue data from Podcast and YouTube,
which does not increase the dataset too much (after filtering). While Spotify
Podcast Dataset comprises about 200k hours of podcast data, Spotify ceased
sharing this corpus, prompting us to scrape the podcast data by ourselves.

For validation and evaluation purposes, we randomly chose 1 conversation for
each speaker pair in the Fisher, respectively, and we randomly sampled 1% of
the pseudo-stereo data from uniform channels for validation and evaluation.
This subset represents a balanced selection for a fair comparison between
models.

###  4.2 Pseudo-Stereo Data Pipeline

Our approach to creating pseudo-stereo data involved several steps, utilizing
a combination of tools and models for effective speaker diarization, source
separation, and speaker verification.

For speaker diarization, we adopted the pyannote
toolkit555https://github.com/pyannote/pyannote-audio, we set the size of
segments from 30 seconds to 120 seconds depending on how long the two speakers
are speaking.

To separate overlapping speech segments and disentangle the speakers, we
trained a Sepformer model [20] on the 16k max split of the Libri2Mix dataset
[23] using the speechbrain toolkit [28]. Sepformer model is a SOTA
transformer-based model for source separation tasks, providing high-quality
separation of overlapping speech.

For speaker verification, we utilized an open-source ECAPA-TDNN
checkpoint666https://huggingface.co/speechbrain/spkrec-ecapa-voxceleb [24,
28]. ECAPA-TDNN model is a deep neural network architecture designed for
speaker recognition tasks, offering robust speaker embedding capabilities.

###  4.3 Model Training

For speech encoder, we select official checkpoints of HuBERT [7]
base/large/large ft, and WavLM [8] base+ /large. For each types of speech
encoder, we use two types of training data to train the dialogue language
model: the Fisher dataset [17] and the Fisher dataset combined with pseudo-
stereo data. This approach allows us to investigate the impact of
incorporating pseudo-stereo data on the performance of the spoken dialogue
modeling.

We follow the same architecture and training procedure of dialogue language
model and vocoder in dGSLM [13] but with different dataset and speech
encoders. We selected 100 hours of training data to clustered the last layer
of representations from speech encoder to encode speech into 500 clusters.

For vocoder, we utilized single-channel data from Fisher777Generated by the
script: https://gitlab.nrp-nautilus.io/ar-
noc/nemo/-/blob/master/scripts/process_fisher_data.py combined with VCTK [29]
for better generalizability of vocoder across Fisher and Podcast data.

###  4.4 Evaluation Metrics

####  4.4.1 Turn-taking Event Statistics

Table 2: The human evaluation of meaningfulness, with 95% confidence intervals. Semantic coherence generally improves with the addition of stereo audio, as indicated by bold scores. | Encoder | Type | M-MOS
---|---|---|---
| Fisher | Podcast
(a) | Ground Truth |  | 3.55 ± 0.23 | 4.2 ± 0.2
Fisher
(b) | WavLM | base+ | 3.14 ± 0.23 | 3.31 ± 0.24
(c) | large | 3.45 ± 0.25 | 3.17 ± 0.29
(d) | HuBERT | base | 3.29 ± 0.27 | 3.36 ± 0.31
(e) | large ft | 3.50 ± 0.31 | 3.67 ± 0.30
Fisher + Pseudo-stereo Aduio
(f) | WavLM | base+ | 3.25 ± 0.24 | 3.18 ± 0.27
(g) | large | 3.33 ± 0.37 | 3.49 ± 0.24
(h) | HuBERT | base | 3.47 ± 0.25 | 3.43 ± 0.17
(i) | large ft | 3.65 ± 0.25 | 3.74 ± 0.17

We follows the definition of turn-taking events in [13]. Inter-Pausal Unit
(IPU) indicates the frames that a speaker is speaking; Gap is the silence
frames occur between two speakers; Pause is the silence frames occur within
the same speaker; Overlap indicates the frames that two speakers are both
speaking.

We generated samples by promting the dialogue language model by 30 seconds
dialogue from test set, and hypothesize 60 seconds continuation. The decoding
temperature is set to 1.0, and sampling among the top 20 possible units. We
find silence frames by applying VAD5 to each channel separately, and compute
IPU, Gap, Pause, and Overlap.

####  4.4.2 Human Evaluation

We conducted human evaluation to assess semantic coherence of our dialogue
generation models.

We chose 30 10-second prompts each from the test sets of the Fisher dataset
and the pseudo-stereo data. These prompts were carefully selected for high
quality, considering factors like audio clarity and minimal noise. Then using
the same sampling configuration as described in Section 2, we generated
20-second continuations for each prompt. Workers are asked to rate the samples
based solely on the content and semantic coherence from 1 to 5.

We employed MTurk888https://www.mturk.com/ to recruit workers. Every hit is
composed by 20 samples, and each sample is evaluated by 3 workers. We rejected
all workers that their work time are less than 10 minutes, or gives 1 or 2 for
ground truth.

##  5 Results

###  5.1 Turn-taking Behaviors

Table 1 presents the turn-taking events discussed in Section 2 for different
settings. We report their differences from the ground truth, with a slash
separating whether the pseudo-stereo data was used during training.

Our initial observations reveal that most cases (row (b), (c), (d), (f))
successfully capture turn-taking behaviours similar to real dialogue.
Combining with pseudo-stereo data does not further improve the performance,
which indicate that limited dialogue data are suficient to model these turn-
taking behavior.

However, HuBERT large (row (e)) fail to correctly model spoken dialogue. This
discrepancy primarily stems from the vocoder trained on units encoded by
HuBERT large, which struggles to accurately resynthesize audio (even prompt
can not be correctly reconstruct, see our demo page2). It suggest that the
representations in the last layer of HuBERT large contains little information
about original audio. Conversely, fine-tuning the model with ASR gives better
phoneme discrimination for representations in the last layer, making it easier
to reconstruct the original speech from the discrete units. This makes the ASR
fine-tuned model more suitable for our case

We do not report the performance of HuBERT large in the following results, for
it is too corrupted.

###  5.2 Human Evaluations

Table 2 reports the M-MOS of generated speech from prompts in Fisher and
Podcast respectively. Combining pseudo-stereo data during training improves
the semantic coherence within speech as seen in row (h), (i), (f) for Fisher,
(g) for Podcast.

Additionally, HuBERT large ft model combined with pseudo-stereo data performs
exceptionally well among prompts from both Fisher and Podcast. In fact, the
performances even surpasses the ground truth of Fisher dataset.

This improvement may stem from the nature of the datasets. Fisher, being a
telephonic dialogue dataset, tends to have more casual conversations with less
information density. On the other hand, podcasts often have a central theme,
resulting in more semantically coherent dialogue. The large scale of the
pseudo-stereo data, when compared to Fisher, might also influence the models
to generate dialogue resembling podcasts, thus enhancing its meaningfulness.

It's worth noting that we did not directly report the naturalness of generated
audio in Table 2, although we conducted an Naturalness MOS (N-MOS) survey. We
evaluate the same data as M-MOS, along with the resynthesized ground truth.
The maximum difference between model generated continuation and resynthesized
ground truth was no greater than 0.4; while ground truth resynthesized by
different vocoder can vary by 0.8,

This observation suggests that our current resynthesis approach is not robust
enough and often generates noise or distorted speech, leading to testers
assessing mainly the vocoder's performance rather than the naturalness of
turn-taking behavior.

##  6 Conclusion

This work presents a novel solution to address the scarcity of stereo dialogue
data in Spoken Dialogue Modeling. Our developed pipeline transforms single-
channel dialogue into pseudo-stereo data, significantly expanding our training
dataset from 2,000 to 17,600 hours, and we open source our dataset for future
research.

Additionally, we explored the effectiveness of using discrete units from
various speech foundation models for dialogue generation. Our experiments
revealed that employing HuBERT large ft as our speech encoder, and combined
with pseudo-stereo data as training data notably improved the semantic
coherence of the generated dialogue.

In conclusion, our contributions provide practical solutions to the challenges
associated with limited stereo dialogue data and speech encoder selection. The
integration of pseudo-stereo data and HuBERT large ft encoder has led to
substantial improvements in spoken dialogue synthesis. However, it's important
to note that the current unit-to-speech vocoder is not yet robust enough,
impacting the quality of the generated audio. This suggests a potential avenue
for future research to further enhance the audio quality of speech resynthesis
from discrete units.

## References

  * [1] V. Nguyen, O. Versyp, C. Cox, and R. Fusaroli, ``A systematic review and bayesian meta-analysis of the development of turn taking in adult–child vocal interactions,'' _Child Development_ , vol. 93, no. 4, pp. 1181–1200, 2022.
  * [2] E. A. Schegloff, ``Discourse as an interactional achievement: Some uses of ‘uh huh’and other things that come between sentences,'' _Analyzing discourse: Text and talk_ , vol. 71, pp. 71–93, 1982.
  * [3] V. H. Yngve, ``On getting a word in edgewise,'' in _Papers from the sixth regional meeting Chicago Linguistic Society, April 16-18, 1970, Chicago Linguistic Society, Chicago_ , 1970, pp. 567–578.
  * [4] T. Stivers, N. J. Enfield, P. Brown, C. Englert, M. Hayashi, T. Heinemann, G. Hoymann, F. Rossano, J. P. De Ruiter, K.-E. Yoon _et al._ , ``Universals and cultural variation in turn-taking in conversation,'' _Proceedings of the National Academy of Sciences_ , vol. 106, no. 26, pp. 10 587–10 592, 2009.
  * [5] R. Huang, M. Li, D. Yang, J. Shi, X. Chang, Z. Ye, Y. Wu, Z. Hong, J. Huang, J. Liu _et al._ , ``Audiogpt: Understanding and generating speech, music, sound, and talking head,'' _arXiv preprint arXiv:2304.12995_ , 2023.
  * [6] A. Baevski, Y. Zhou, A. Mohamed, and M. Auli, ``wav2vec 2.0: A framework for self-supervised learning of speech representations,'' _Advances in neural information processing systems_ , vol. 33, pp. 12 449–12 460, 2020.
  * [7] W.-N. Hsu, B. Bolte, Y.-H. H. Tsai, K. Lakhotia, R. Salakhutdinov, and A. Mohamed, ``Hubert: Self-supervised speech representation learning by masked prediction of hidden units,'' _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 29, pp. 3451–3460, 2021.
  * [8] S. Chen, C. Wang, Z. Chen, Y. Wu, S. Liu, Z. Chen, J. Li, N. Kanda, T. Yoshioka, X. Xiao _et al._ , ``Wavlm: Large-scale self-supervised pre-training for full stack speech processing,'' _IEEE Journal of Selected Topics in Signal Processing_ , vol. 16, no. 6, pp. 1505–1518, 2022.
  * [9] A. v. d. Oord, Y. Li, and O. Vinyals, ``Representation learning with contrastive predictive coding,'' _arXiv preprint arXiv:1807.03748_ , 2018.
  * [10] K. Lakhotia, E. Kharitonov, W.-N. Hsu, Y. Adi, A. Polyak, B. Bolte, T.-A. Nguyen, J. Copet, A. Baevski, A. Mohamed _et al._ , ``On generative spoken language modeling from raw audio,'' _Transactions of the Association for Computational Linguistics_ , vol. 9, pp. 1336–1354, 2021.
  * [11] E. Kharitonov, A. Lee, A. Polyak, Y. Adi, J. Copet, K. Lakhotia, T.-A. Nguyen, M. Rivière, A. Mohamed, E. Dupoux _et al._ , ``Text-free prosody-aware generative spoken language modeling,'' _arXiv preprint arXiv:2109.03264_ , 2021.
  * [12] Z. Borsos, R. Marinier, D. Vincent, E. Kharitonov, O. Pietquin, M. Sharifi, D. Roblek, O. Teboul, D. Grangier, M. Tagliasacchi, and N. Zeghidour, ``Audiolm: a language modeling approach to audio generation,'' 2023.
  * [13] T. A. Nguyen, E. Kharitonov, J. Copet, Y. Adi, W.-N. Hsu, A. Elkahky, P. Tomasello, R. Algayres, B. Sagot, A. Mohamed _et al._ , ``Generative spoken dialogue language modeling,'' _Transactions of the Association for Computational Linguistics_ , vol. 11, pp. 250–266, 2023.
  * [14] A. Polyak, Y. Adi, J. Copet, E. Kharitonov, K. Lakhotia, W.-N. Hsu, A. Mohamed, and E. Dupoux, ``Speech resynthesis from discrete disentangled self-supervised representations,'' _arXiv preprint arXiv:2104.00355_ , 2021.
  * [15] J. Sakuma, S. Fujie, and T. Kobayashi, ``Response timing estimation for spoken dialog systems based on syntactic completeness prediction,'' in _2022 IEEE Spoken Language Technology Workshop (SLT)_ , 2023, pp. 369–374.
  * [16] K. Inoue, B. Jiang, E. Ekstedt, T. Kawahara, and G. Skantze, ``Real-time and continuous turn-taking prediction using voice activity projection,'' 2024.
  * [17] C. Cieri, D. Miller, and K. Walker, ``The fisher corpus: A resource for the next generations of speech-to-text.'' in _LREC_ , vol. 4, 2004, pp. 69–71.
  * [18] H. Bredin, ``pyannote. audio 2.1 speaker diarization pipeline: principle, benchmark, and recipe,'' in _24th INTERSPEECH Conference (INTERSPEECH 2023)_. ISCA, 2023, pp. 1983–1987.
  * [19] T. J. Park, N. R. Koluguri, J. Balam, and B. Ginsburg, ``Multi-scale speaker diarization with dynamic scale weighting,'' _arXiv preprint arXiv:2203.15974_ , 2022.
  * [20] C. Subakan, M. Ravanelli, S. Cornell, M. Bronzi, and J. Zhong, ``Attention is all you need in speech separation,'' in _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2021, pp. 21–25.
  * [21] Y. Luo, Z. Chen, and T. Yoshioka, ``Dual-path rnn: efficient long sequence modeling for time-domain single-channel speech separation,'' in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 46–50.
  * [22] Y. Luo and N. Mesgarani, ``Conv-tasnet: Surpassing ideal time–frequency magnitude masking for speech separation,'' _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 27, p. 1256–1266, Aug 2019. [Online]. Available: http://dx.doi.org/10.1109/TASLP.2019.2915167
  * [23] J. Cosentino, M. Pariente, S. Cornell, A. Deleforge, and E. Vincent, ``Librimix: An open-source dataset for generalizable speech separation,'' _arXiv preprint arXiv:2005.11262_ , 2020.
  * [24] B. Desplanques, J. Thienpondt, and K. Demuynck, ``Ecapa-tdnn: Emphasized channel attention, propagation and aggregation in tdnn based speaker verification,'' _arXiv preprint arXiv:2005.07143_ , 2020.
  * [25] N. R. Koluguri, T. Park, and B. Ginsburg, ``Titanet: Neural model for speaker representation with 1d depth-wise separable convolutions and global context,'' in _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 8102–8106.
  * [26] G. Chen, S. Chai, G. Wang, J. Du, W.-Q. Zhang, C. Weng, D. Su, D. Povey, J. Trmal, J. Zhang _et al._ , ``Gigaspeech: An evolving, multi-domain asr corpus with 10,000 hours of transcribed audio,'' _arXiv preprint arXiv:2106.06909_ , 2021.
  * [27] A. Clifton, A. Pappu, S. Reddy, Y. Yu, J. Karlgren, B. Carterette, and R. Jones, ``The spotify podcast dataset,'' _arXiv preprint arXiv:2004.04270_ , 2020.
  * [28] M. Ravanelli, T. Parcollet, P. Plantinga, A. Rouhe, S. Cornell, L. Lugosch, C. Subakan, N. Dawalatabad, A. Heba, J. Zhong _et al._ , ``Speechbrain: A general-purpose speech toolkit,'' _arXiv preprint arXiv:2106.04624_ , 2021.
  * [29] K. M. J. Yamagishi, C. Veaux, ``Cstr vctk corpus: English multi-speaker corpus for cstr voice cloning toolkit (version 0.92),'' 2019.


11institutetext: UCLouvain–ICTEAM
11email<EMAIL_ADDRESS>
# A Program That Simplifies Regular Expressions

(Tool paper)

Baudouin Le Charlier  0000-0002-2222-4203

###### Abstract

This paper presents the main features of a system that aims to transform
regular expressions into shorter equivalent expressions. The system is also
capable of computing other operations useful for simplification, such as
checking the inclusion of regular languages. The main novelty of this work is
that it combines known but distinct ways of representing regular languages
into a global unified data structure that makes the operations more efficient.
In addition, representations of regular languages are dynamically reduced as
operations are performed on them. Expressions are normalized and represented
by a unique identifier (an integer). Expressions found to be equivalent (i.e.
denoting the same regular language) are grouped into equivalence classes from
which a shortest representative is chosen.

The article briefly describes the main algorithms working on the global data
structure. Some of them are direct adaptations of well-known algorithms, but
most of them incorporate new ideas, which are really necessary to make the
system efficient. Finally, to show its usefulness, the system is applied to
some examples from the literature. Statistics on randomly generated sets of
expressions are also provided.

###### Keywords:

Simplification of expressions Regular languages Data structures.

##  1 The Background: a Global Data Structure

Regular expressions, regular languages, and deterministic finite automata are
well-known (see, e.g. [1, 5, 6, 9]). In this paper, symbols in chains are
lower case letters. The symbols $0$ and $1$ denote the empty set, and the set
only containing the empty chain, respectively. The system works on _normalized
expressions_. Letters and symbols $0$ and $1$ are normalized expressions. A
normalized iteration is of the form $E$*, where $E$ is different from $0$ and
$1$ and is not an iteration; a normalized concatenation is of the form
$E_{1}\,.\,E_{2}$ (also written $E_{1}\,E_{2}$), where $E_{1}$ and $E_{2}$ are
different from $0$ and $1$, and $E_{1}$ is not a concatenation; a normalized
union is of the form $E_{1}+\ldots+E_{n}$, where $n\geq 2$, and all
expressions $E_{i}$ are different from $0$ and are not unions; moreover the
sequence $E_{1},\ldots,E_{n}$ is strictly sorted. Thus, we assume a total
order on normalized expressions. For efficiency reasons, this order is
implementation dependent. Arbitrary regular expressions can be mapped in a
unique way to a normalized expression, thanks to three operations $E_{1}\oplus
E_{2}$, $E_{1}\odot E_{2}$, and $E^{\displaystyle\star}$, which compute
normalized expressions equivalent to $E1+E2$, $E_{1}.E_{2}$, and $E$*,
assuming that $E_{1}$, $E_{2}$, and $E$ are normalized. It is easy to see that
any two arbitrary regular expressions that can be shown equivalent using the
Kleene’s classical axioms111see [6], page 25 for $0$, $1$, ., and $+$, except
distributivity, as well as the axiom $\textrm{($E$*)*}=\textrm{$E$*}$, and
identities $\textrm{$0$*}=1$ and $\textrm{$1$*}=1$, are mapped onto the same
normalized expression.

The system uses a global data structure, called _the background_ , that
contains a set of normalized expressions and a set of equations relating (some
of) the regular expressions to their derivatives (see [5, 6]). Following [6],
such an equation can be written $E\>=\>o_{E}+\ldots+x.E_{x}+\ldots$, where
$o_{E}\in\\{0,1\\}$, $x$ is a letter, and every $E_{x}$ is a normalized
expression present in the background. The background evolves over time.
Actually, all operations executed by the system use expressions and/or
equations present in the background to create new expressions and equations,
which are added to it. The background also maintains an equivalence relation
between the normalized expressions it contains. As expected, expressions in
the same equivalence class must denote the same regular language. Moreover, in
each class, a shortest expression is chosen as _the representative_ of the
class. We note $\textrm{rep}(E)$ the representative of the equivalence class
of $E$. In an equation as above, it is required that $E=\textrm{rep}(E)$ and
$E_{x}=\textrm{rep}(E_{x})$ for every letter $x$. It is also natural to
require that no two equations may use the same left part $E$ or the same right
part $o_{E}+\ldots+x.E_{x}+\ldots$. Let us call this the invariant of the
background. But, as shown in Section 3, this condition may be violated when
two expressions are found equivalent. Thus, there is another global operation,
called normalize, which enforces the condition, when needed. This means that
some equivalence classes of expressions are merged, choosing a shortest
representative, and that some sets of equations are replaced by a single new
one, using new representatives. Replaced equations are discarded from the
background.

##  2 Implementation of the Background and its Operations

The implementation of the background almost only uses integers, arrays of
integers and arrays of arrays of integers, possibly “encapsulated” into
objects, for readability.222The program is written in Java, and can be
compiled with any version of it, including Java 1.0. It could be readily re-
coded in most imperative programming language. Normalized regular expressions
are (uniquely) identified by an integer (int). There is a unique array (of
arrays of integers) giving access to all expressions in the background. The
identifier of an expression $E$ gives access through this array to an array of
integers containing the identifiers of the direct sub-expressions of $E$. The
length of the main array determines the maximum number of expressions present
in the background.

Whenever all identifiers are used for expressions, it is often possible to get
rid of some of them, no longer strictly needed for the current task. This is
handled by a specialized garbage collector. To make it possible, all
identifiers are distributed into two lists: the used ones and the free ones.
These lists, and other needed ones, are made of arrays of integers, allowing
us to perform operations such as choosing and removing an identifier, or
checking its presence, all in constant time. When operations such as
$E_{1}\oplus E_{2}$, $E_{1}\odot E_{2}$, and $E^{\displaystyle\star}$ are
performed, they receive, as actual arguments, identifiers of expressions. A
hashtable is used to check whether the result already exists, or to create it
with a free identifier. When the result is a union, its direct sub-expressions
are merged in ascending order on the values of their identifiers, which makes
the time complexity of the operation proportional to the number of these sub-
expressions. This cannot be obtained by a priori defining a total ordering on
the expressions. In fact, the ordering is defined by the program execution
history.

Expressions in the background are gathered into equivalence classes. To
implement this, we use an array of identifiers organized as a Union-Find data
structure [7]. This provides a fast access to the identifier of
$\textrm{rep}(E)$ from the identifier of $E$.

To implement the operation normalize of the background, I first explain how
equations $E\,=\,o_{E}+\ldots+x.E_{x}+\ldots$ are represented. The right part
$o_{E}+\ldots+x.E_{x}+\ldots$ is represented by an array of identifiers tabD
where $\textit{tabD}\,[0]$ is the identifier of $o_{E}$ ($0$ or $1$). The
length of tabD is the number of different letters used by all expressions in
the background plus one and $\textit{tabD}\,[i_{x}]$ is the identifier of
$E_{x}$ (where $i_{x}$ is the rank of $x$ in the set of used letters (starting
at $1$)).333When expressions are normalized, their letters are renamed to use
the first ones of the alphabet. Arrays of identifiers themselves are given an
identifier using another hash-table. Additionally, an equation is represented
by a pair consisting of the identifiers of its left and right parts. Finally,
an identifier is given to each of these pairs, thanks to a third hash table.
This identifier is used to access two arrays where the identifiers of the left
and right parts of the equation are put. Let us assume that two expressions
$E_{1}$ and $E_{2}$ such that $\textrm{rep}(E_{1})\neq\textrm{rep}(E_{2})$ are
found equivalent and that $\textrm{rep}(E_{1})$ is shorter than
$\textrm{rep}(E_{2})$. Their equivalence classes are merged in the Union-Find
structure. Moreover, to maintain the invariant of the background, we replace
$\textrm{rep}(E_{2})$ by $\textrm{rep}(E_{1})$ in every equation where
$\textrm{rep}(E_{2})$ occurs. To make it efficiently, the background contains,
for every position $i_{x}$ and every representative $E$ of an equivalence
class, a list of all identifiers of arrays of identifiers tabD such that
$\textit{tabD}\,[i_{x}]$ is equal to the identifier of $E$. Assume that the
equations contain $n$ occurrences of $\textrm{rep}(E_{2})$. Then the old
equations containing $\textrm{rep}(E_{2})$ can be replaced by new equations
using $\textrm{rep}(E_{1})$ instead, in $O(n\times\ell_{\textit{tabD}}\,)$
where $\ell_{\textit{tabD}}\,$ is the length of arrays of identifiers tabD (on
the average, i.e. if the hash-tables work well). “Renaming”
$\textrm{rep}(E_{2})$ into $\textrm{rep}(E_{1})$, this way, does not maintain
the invariant of the background, in general: two equations may have
$\textrm{rep}(E_{1})$ as left part, and several equations may have the same
right part. Thus, the same process may have to be iterated until the invariant
holds anew. This is efficiently done using a stack of pairs of identifiers to
be put in the same equivalence class and other lists of identifiers of
equations having the same left or right parts. The whole process is guaranteed
to terminate since the number of distinct identifiers used by the equations
decreases at each iteration.

##  3 Simplification and Other Algorithms

The size (or length) of an expression is defined as the number of symbols
(occurrences) it is made of, excluding parentheses. I take the viewpoint that
simplifying an expression just means finding another expression that is
shorter and denotes the same regular language. The idea is that a shorter
expression is easier to understand than a larger one, in general. A more
elaborated simplicity measure is proposed in [13], aiming notably at limiting
the star height (see, e.g. [11]) of the expressions. With this measure, the
expression 1 + a(a + b)* is considered simpler than (a b*)*, a shorter one. It
would be possible to use this measure in my system at the price of losing some
efficiency.

In theory, simplifying a regular expression can be done, by hand, using
Kleene’s axioms, possibly extended with Salomaa’s rule [1, 6] or the more
logical rules proposed in [9]. However this requires some “expertise” [6, 9].
For relatively large expressions, the number of possibilities to try makes the
approach impractical. In [13], an approach is proposed where a strictly
decreasing sequence of expressions is constructed by choosing, at each step, a
smaller expression from a large set of expressions equivalent to the preceding
one. This approach also is inefficient for large expressions and unable to
simplify an expression such as c* + c*a(b + c*a)*c* into (c + ab*)* because
this requires building an intermediate expression strictly greater that the
first one (namely, (1 + c*ab*(c*ab*)*)c* ).

In this work, I suggest using other kinds of algorithms that are “more
deterministic”, making them able to work on larger expressions. They also take
advantage of the background, which allows them to reuse the results of
previous computations. The general simplification algorithm of an expression
works as follows. The expression first is normalized. Then the normalized
expression is put on a stack, with its sub-expressions, the shortest ones on
the top. Of course, identifiers are used to represent expressions on the
stack. (And, in general, “expression” means “identifier of expression”,
below.) Some sub-expressions may have been put on the stack and simplified
previously. They are not put on the stack again. Then sub-expressions are
removed from the stack one by one and processed as follows.

Let $E$ be the current (sub-)expression. It is first pre-simplified by
replacing its direct sub-expressions by their representative in the
background. In many cases this results in a much shorter expression
$E^{\prime}$. Then a complete set of equations is computed for the pre-
simplified expression. We say that a set of equations is _complete_ if every
expression used by its right part is the left part of an equation in the set.
A complete set of equations for $E^{\prime}$ must contain an equation of which
the representative of $E^{\prime}$ is the left part. It is equivalent to a
deterministic finite automaton (DFA) for $E^{\prime}$. The set of equations is
computed using derivatives (see, e.g. [5, 6]). Our algorithm uses a notion of
partial derivative similar to [3] and is efficient thanks to the use of
normalized expressions. The main algorithm does not compute the derivatives
one by one as in [6] but it uses an array of identifiers, as an accumulator to
compute the right part of an equation, and another accumulator to
progressively compute suffixes of partial derivatives. The set of all
syntactic partial derivatives of a normalized expression is finite and
syntactic derivatives are unions of partial derivatives. Thus, termination in
ensured. In many cases, however, computing all syntactic derivatives is not
needed because their representatives in the background already have a complete
set of equations. When a new equation is computed, it is added to the
background, which is then normalized. Thanks to normalization the size of the
set of equations actually computed for $E^{\prime}$ can be much smaller than
the set of equations that would be built by strictly using syntactic
derivatives of $E^{\prime}$. Nevertheless, normalization of the background
does not guarantee that two distinct representatives denote different regular
languages. This can be ensured using Moore’s well-known algorithm [12]. The
system uses it in three different ways: minimize the set of equations of
$E^{\prime}$, check the equivalence of two or more expressions, or make sure
that all representatives that have a complete set of equations denote
different regular languages.

Computing a set of equations for $E^{\prime}$ is often sufficient to determine
shorter equivalent expressions: some syntactic derivatives of $E^{\prime}$ may
denote the same language and be shorter, and they may have representatives
still shorter, detected by normalizing the background and minimizing the set
of equations. However, it is also possible and sometimes useful to create new
expressions from the set of equations for $E^{\prime}$. As an example (from
[6]), consider the case where $E=E^{\prime}=\textrm{(ab*a + ba*b)*(1 + ab* +
ba*)}$. This expression only has three syntactical derivatives and thus three
equations. The minimization of these equations gives only one equation :
$E=1+a.E+b.E$. Unless $E$ has a shorter representative somewhere in the
background, no improvement is obtained. However, applying Salomaa’s rule,
(see, e.g. [6]), we get that $E$ is equivalent to (a + b)*. More generally,
the system proposes an algorithm to solve equations, which can be applied to
those of $E^{\prime}$. This algorithm is quite different from the classical
algorithm explained in [1] since it attempts to find a short expression for
$E^{\prime}$ and performs a depth-first traversal of the set of equations. It
uses a number of heuristics to limit the depth of the traversal. Basically, it
treats the expressions in the equations as variables (as in [1]) but,
sometimes, it may choose to use their actual values to limit the depth of the
search.

Alternatively or complementarily to the algorithm above, the system is able to
apply to $E^{\prime}$ simplification rules similar to those in [13]. They make
a lot of use of an algorithm to decide inclusion of a regular language
(denoted by $E_{1}$) into another (denoted by $E_{2}$). The best method ([6])
seems to be to compute the derivatives of the (extended) expression
$E_{1}\setminus E_{2}$. Inclusion holds only if no such derivative contains
$1$. The computation often is fast (when inclusion does not hold.) (Another
(related) method proposed in [2] is more difficult to implement and less
efficient in general.) Inclusion is notably used to remove redundant sub-
expressions in unions and concatenations, decompose concatenations, and
compute coverings of unions. More powerful simplifications can be achieved
“under star” (in the sub-expression of an iteration). To the contrary of [13],
the algorithms do not transform unions and concatenations in all possible
ways, using associativity and commutativity because it is too costly for large
expressions. Heuristics to find “interesting” groupings of sub-expressions are
tried, instead.

Table 1: Simplification of random expressions of size 1000 with two letters algorithms |  | $\ell_{N}$ |  | $n_{\textit{min}}$ |  | $\ell_{\textit{avg}}$ | $\ell_{1/4}$ | $\ell_{1/2}$ | $\ell_{3/4}$ |  | $t_{\textit{avg}}$ | $t_{1/4}$ | $t_{1/2}$ | $t_{3/4}$ |  | gc
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
n |  | 715 |  | 0 |  | 620 | 613 | 637 | 656 |  | 0.45 | 0.15 | 0.35 | 0.62 |  | 7
|  | 715 |  | 24 |  | 269 | 5 | 59 | 614 |  | 0.91 | 0.26 | 0.5 | 1.01 |  | 6
s |  | 715 |  | 25 |  | 69 | 4 | 24 | 91 |  | 0.18 | 0.06 | 0.1 | 0.13 |  | 2
rS |  | 714 |  | 25 |  | 52 | 4 | 20 | 52 |  | 0.16 | 0.04 | 0.07 | 0.15 |  | 2
rsS |  | 715 |  | 25 |  | 49 | 4 | 19 | 50 |  | 0.17 | 0.04 | 0.07 | 0.16 |  | 1
frsS |  | 715 |  | 25 |  | 47 | 4 | 19 | 48 |  | 0.41 | 0.09 | 0.18 | 0.34 |  | 8

##  4 Examples and Statistics

Let us see how the system deals with some examples from the literature. In
[8], regular expressions are obtained from non deterministic finite automata:
the expression (aa + b)a*c(ba*c)*(ba*d + d) + (aa + b)a*d ($\ell=38$) is
obtained with some strategy, while a shorter one ($\ell=18$) is obtained for
the same automaton, with a better strategy. My system simplifies the long
expression to the shorter
(b + aa)(a + cb)*(1 + c)d ($\ell=18$), which is also nicer. As explained in
Section 2, the system also accepts expressions of the form $E_{1}\setminus
E_{2}$, which is enough to compute other boolean operations on expressions. In
[6], Conway asks to compute (xy* + yx)* $\cap$ (y*x + xy)* but he presents a
solution for (xy* + yx)* $\setminus$ (y*x + xy)*, instead. The system gives
(yx + x(1 + y(y*yx)*))* ($\ell=18$) and (yx + x(1 + y(y*yx)*))*xy(y(1 + x))*y
($\ell=31$) as respective solutions. The solution proposed by Conway is
(yx)*xx*y(yy*x + xx*y)*yy* ($\ell=31$), which is further simplified to
(yx)*xx*y(yx + x*y)*y ($\ell=23$) by the system.

Table 1 provides statistics on the accuracy and efficiency of the algorithms.
A set of 100 randomly chosen regular expressions of size 1000 using two
letters has been generated fairly, i.e. every possible expression has the same
probability to be chosen. All expressions are simplified using different
variants of the algorithms and statistics are computed on the sizes of
simplified expressions and execution times. The first column lists the chosen
algorithms. Column $\ell_{N}$ gives the average length of the normalized
expressions. Column $n_{\textit{min}}$ is the number of expressions simplified
to (a + b)* . Columns $\ell_{\textit{avg}}$, $\ell_{1/4}$, $\ell_{1/2}$ ,
$\ell_{3/4}$ provide the average length, first quartile, median, and third
quartile of simplified expressions. The next four columns give similar
information about the execution times (in seconds, on a MacBook Pro Early
2015). Column gc is the number of garbage collector calls for all
simplifications. The first line is the case where only derivatives are
computed (with normalization of the background). On the second line, the only
change is that a minimization of all equations is applied to the previous
results (in the end). The next three lines report on the cases where
simplication algorithms (s), minimization plus equation solving (rS), or both
(rsS) are applied. At the last line (frsS), a factorization algorithm is also
independently applied to every pre-simplified expression. We see that rS is
slightly better than s. Combining the two brings a little improvement at a
small cost. Adding factorization (f) is still more precise but more than two
times less efficient.

## References

  * [1] A.V. Aho and J.D. Ullman.  The Theory of Parsing, Translation, and Compiling: Compiling.  Prentice-Hall series in automatic computation. Prentice-Hall, 1972.
  * [2] Valentin M. Antimirov.  Rewriting regular inequalities (extended abstract).  In Horst Reichel, editor, Fundamentals of Computation Theory, 10th International Symposium, FCT ’95, Dresden, Germany, August 22-25, 1995, Proceedings, volume 965 of Lecture Notes in Computer Science, pages 116–125. Springer, 1995.
  * [3] Valentin M. Antimirov.  Partial derivatives of regular expressions and finite automaton constructions.  Theor. Comput. Sci., 155(2):291–319, 1996.
  * [4] Valentin M. Antimirov and Peter D. Mosses.  Rewriting extended regular expressions.  Theor. Comput. Sci., 143(1):51–72, 1995.
  * [5] Janusz A. Brzozowski.  Derivatives of regular expressions.  J. ACM, 11(4):481–494, 1964.
  * [6] J.H. Conway.  Regular Algebra and Finite Machines.  Chapman and Hall mathematics series. Dover Publications, Incorporated, 2012.
  * [7] Bernard A. Galler and Michael J. Fischer.  An improved equivalence algorithm.  Commun. ACM, 7(5):301–303, 1964.
  * [8] Yo-Sub Han and Derick Wood.  Obtaining shorter regular expressions from finite-state automata.  Theor. Comput. Sci., 370(1-3):110–120, 2007.
  * [9] Dexter Kozen.  A completeness theorem for kleene algebras and the algebra of regular events.  Inf. Comput., 110(2):366–390, 1994.
  * [10] Baudouin Le Charlier and Mêton Mêton Atindehou.  A data structure to handle large sets of equal terms.  In James H. Davenport and Fadoua Ghourabi, editors, 7th International Symposium on Symbolic Computation in Software Science, SCSS 2016, Tokyo, Japan, March 28-31, 2016, volume 39 of EPiC Series in Computing, pages 81–94. EasyChair, 2016.
  * [11] Sylvain Lombardy and Jacques Sakarovitch.  On the star height of rational languages: A new presentation for two old results.  In Masami Ito and Teruo Imaoka, editors, Proceedings of the International Colloquium on Words, Languages & Combinatorics III, Kyoto, Japan, March 14-18, 2000, pages 266–285. World Scientific, 2000.
  * [12] Edward F. Moore.  Gedanken-experiments on sequential machines.  In Claude Shannon and John McCarthy, editors, Automata Studies, pages 129–153. Princeton University Press, Princeton, NJ, 1956.
  * [13] Alley Stoughton.  Formal Language Theory: Integrating Experimentation and Proof.  https://alleystoughton.us/forlan/book.pdf, 2003–2022.  Open source book.

##  Appendix 0.A Downloading and Testing the System

In order to test the system described in this paper, you should download the
dropbox file at the address

    https://www.dropbox.com/sh/j0l4yt59k2w6tpi/AADLG9qFGg_RF2QQ3TkDd_usa?dl=0

and unzip it as a new directory. The directory contains a jar file and a sub-
directory with some test data. It also contains the file how-to-use.pdf
providing information on how to use the program.

##  Appendix 0.B More Examples

Let us start with an example showing that computing derivatives is sometimes
enough to get substantial simplifications. Consider the following expression:

((a + b)a*)* + (a + b(1 + b)b)aa(1 + a)

Computing its syntactic derivatives gives eight different equations (put in
the background) but normalization of the background reduces them to a single
one, of the form $E\>=\>1+a.E+b.E$. Therefore, the expression simplifies to
((a + b)a*)*, the shortest of its syntactic derivatives. No other algorithm is
needed: the program computes it with an empty list of algorithms (`’’`).
Assume that the background contains (a + b)* beforehand (with a corresponding
equation). Then the program produces (a + b)* instead of ((a + b)a*)* because
minimization of the set of all equations is applied once at the end of the
simplification. The result ((a + b)a*)* is obtained only with the option `n`,
which prevents the program from applying minimization in the end. The program
also produces (a + b)*, if it is not in the background beforehand, and any
combination of algorithms is used, except `n`, `nr`, `nf`, `nrf`.

Now, let us consider the problem of checking whether a regular expression
$E_{1}$ denotes a language included in the language denoted by another
expression $E_{2}$. We can ask the program to simplify $E_{1}\setminus E_{2}$.
For instance:

( (a*b)*aaaaaaa* $\setminus$ (a + b)*a(a + b)(a + b)(a + b)(a + b)(a + b))

The returned results is $0$, which indicates that the difference is the empty
set. But, we also can try the converse:

( (a + b)*a(a + b)(a + b)(a + b)(a + b)(a + b) $\setminus$ (a*b)*aaaaaaa*)

which eliminates the symbol $\setminus$ , giving:

(a + b)*a(aaa(ab + b(a + b)) +

(b(a + b)(a + b) + a(ba + (a + b)b))(a + b)(a + b))

This nice result is obtained thanks to the algorithm `S` for solving
equations.

To check equivalence of two regular expressions, we can compute their
symmetrical difference (noted `^`). For instance, simplifying

(((xy* + yx)* $\&$ (y*x + xy)*) `^` (yx)*(x + xy(yy*x)*)*)

returns $0$. (The character $\&$ is used to represent the operation $\cap$.)
More interesting examples can be found in the folder `testdata` of the dropbox
file.

##  Appendix 0.C More Statistics

In this section, I present more extensive statistics on the results produced
by the system on “large” expressions. Four files of expressions of length
1000, using 1, 2, 3, and 4 letters have been generated in a fair way, giving
to every expression the same probability to be chosen. (The files can be found
in the folder `testdata` of the dropbox file.) The system was run on those
files with various parametrizations. Tables 2 to 5 gather the statistics.
These tables have an additional column $\textit{gc}_{f}$ that counts the
number of garbage collector calls that were unable to reclaim enough
identifiers to complety process a sub-expression. In that case, the garbage
collector is called again but the sub-expressions remaining on the stack only
are pre-simplified. All executions use $1,000,000$ identifiers. Using less
identifiers can be preferable on some computers. The new tables present the
same kind of statistics than Table 1 but most combinations of algorithms are
considered. “Standard” combinations do a little more than appying the
algorithms in the list to all sub-expressions: they minimize the set of all
equations, just once, in the end (after complete simplification by other
algorithms) and they also try a last factorization of the result. The letter
`n` in the first column indicates that this last attempt to simplify is not
made. Other possibilities of letters have been explained before for Table 1.

Let us have a look at Table 2, first. We can see that good combinations of
algorithms must include `s` or `rS`. Systematic factorization (`f`) brings a
small improvement at a relatively high cost. The final minimization and
factorisation gives an improvement mostly when nor `s` nor `rS` are used. The
lines `nra` and `nraS` show what happens if a complete minimization of the set
of equations is applied for every sub-expression: the execution time grows
unacceptably without bringing better results. Finally, we see that most
combinations minimize $25$ expressions (to (a + b)*). Since the expressions
have been chosen fairly, this suggests that $25\%$ of all expressions with two
letters are equivalent to (a + b)*.

Table 3 presents the same statistics for expressions using only one letter.
Almost all combinations of algorithms give the same (or almost the same)
results. The combinations `nra` and `nraS` give precise results with good
execution times. This is probably because the program can detect that the set
of all equations was not modified since the last call to the minimization
algorithm, making its current execution useless. The values in the column
$n_{\textit{min}}$ suggest that $2/3$ of all expressions with one letter are
simplifiable to a*.

Now let us consider Tables 4 and 5. For three letters, only seven expressions
are found equivalent to (a + b + c)*. For four letters, no similar result is
reported. Globally, this suggests that when the number of letters increases
the proportion of simplifiable expressions decreases quickly. It does not
actually mean that my program is less able to simplify expressions with many
letters: one can only simplify what is simplifiable. With respect to the
execution time, a similar remark seems sensible. For one or two letters, the
pre-simplification of the sub-expressions often gives short expressions that
can be processed quickly by the algorithms. With more letters, pre-simplified
expressions are bigger, explaining the greater execution times.

Table 2: Simplification of random expressions of length 1000 with two letters algorithms |  | $l_{N}$ |  | $n_{\textit{min}}$ |  | $l_{\textit{avg}}$ | $l_{1/4}$ | $l_{1/2}$ | $l_{3/4}$ |  | $t_{\textit{avg}}$ | $t_{1/4}$ | $t_{1/2}$ | $t_{3/4}$ |  | gc | $\textit{gc}_{f}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
n |  | 715 |  | 0 |  | 620 | 613 | 637 | 656 |  | 0.44 | 0.15 | 0.33 | 0.59 |  | 7 | 0
nr |  | 715 |  | 0 |  | 391 | 300 | 415 | 525 |  | 0.2 | 0.03 | 0.08 | 0.22 |  | 3 | 0
ns |  | 715 |  | 25 |  | 76 | 4 | 31 | 114 |  | 0.11 | 0.02 | 0.03 | 0.06 |  | 1 | 0
nS |  | 715 |  | 0 |  | 386 | 303 | 413 | 466 |  | 0.27 | 0.08 | 0.17 | 0.35 |  | 3 | 0
nrs |  | 714 |  | 25 |  | 73 | 4 | 31 | 114 |  | 0.09 | 0.02 | 0.03 | 0.08 |  | 1 | 0
nrS |  | 714 |  | 25 |  | 54 | 4 | 20 | 64 |  | 0.11 | 0.04 | 0.06 | 0.1 |  | 1 | 0
nsS |  | 714 |  | 25 |  | 51 | 4 | 20 | 65 |  | 0.12 | 0.04 | 0.06 | 0.12 |  | 1 | 0
nrsS |  | 714 |  | 25 |  | 49 | 4 | 20 | 58 |  | 0.13 | 0.04 | 0.06 | 0.1 |  | 1 | 0
nf |  | 715 |  | 0 |  | 154 | 48 | 109 | 230 |  | 0.95 | 0.12 | 0.23 | 0.7 |  | 20 | 6
nfr |  | 715 |  | 0 |  | 143 | 45 | 86 | 219 |  | 0.99 | 0.09 | 0.23 | 0.48 |  | 20 | 6
nfs |  | 715 |  | 25 |  | 58 | 4 | 25 | 80 |  | 0.48 | 0.05 | 0.11 | 0.3 |  | 10 | 0
nfS |  | 715 |  | 14 |  | 96 | 17 | 51 | 142 |  | 0.78 | 0.08 | 0.17 | 0.44 |  | 16 | 2
nfrs |  | 715 |  | 25 |  | 58 | 4 | 25 | 80 |  | 0.47 | 0.06 | 0.11 | 0.31 |  | 10 | 0
nfrS |  | 715 |  | 25 |  | 49 | 4 | 20 | 53 |  | 0.46 | 0.06 | 0.11 | 0.24 |  | 8 | 0
nfsS |  | 715 |  | 25 |  | 48 | 4 | 20 | 64 |  | 0.4 | 0.07 | 0.13 | 0.25 |  | 8 | 0
nfrsS |  | 715 |  | 25 |  | 47 | 4 | 19 | 50 |  | 0.42 | 0.06 | 0.12 | 0.28 |  | 8 | 0
nra |  | 714 |  | 25 |  | 64 | 4 | 31 | 88 |  | 7.21 | 3.11 | 6.77 | 11.17 |  | 0 | 0
nraS |  | 714 |  | 25 |  | 53 | 4 | 20 | 64 |  | 19.4 | 6.16 | 14.05 | 28.27 |  | 1 | 0
|  | 715 |  | 24 |  | 269 | 5 | 59 | 614 |  | 0.94 | 0.28 | 0.53 | 1.08 |  | 6 | 0
r |  | 715 |  | 0 |  | 335 | 120 | 348 | 513 |  | 0.41 | 0.04 | 0.12 | 0.49 |  | 2 | 0
s |  | 715 |  | 25 |  | 69 | 4 | 24 | 91 |  | 0.18 | 0.07 | 0.1 | 0.13 |  | 2 | 0
S |  | 715 |  | 25 |  | 178 | 4 | 39 | 412 |  | 0.52 | 0.13 | 0.25 | 0.54 |  | 2 | 0
rs |  | 715 |  | 25 |  | 70 | 4 | 31 | 96 |  | 0.15 | 0.02 | 0.03 | 0.09 |  | 3 | 0
rS |  | 714 |  | 25 |  | 52 | 4 | 20 | 52 |  | 0.15 | 0.04 | 0.07 | 0.14 |  | 2 | 0
sS |  | 715 |  | 25 |  | 49 | 4 | 19 | 50 |  | 0.23 | 0.12 | 0.18 | 0.26 |  | 1 | 0
rsS |  | 715 |  | 25 |  | 49 | 4 | 19 | 50 |  | 0.19 | 0.04 | 0.07 | 0.18 |  | 1 | 0
f |  | 715 |  | 25 |  | 102 | 4 | 47 | 136 |  | 1.14 | 0.15 | 0.28 | 0.72 |  | 19 | 5
fr |  | 715 |  | 6 |  | 127 | 36 | 81 | 202 |  | 1.07 | 0.12 | 0.24 | 0.6 |  | 19 | 5
fs |  | 715 |  | 25 |  | 58 | 4 | 20 | 73 |  | 0.54 | 0.11 | 0.21 | 0.37 |  | 10 | 0
fS |  | 715 |  | 25 |  | 67 | 4 | 31 | 91 |  | 0.91 | 0.16 | 0.26 | 0.5 |  | 17 | 1
frs |  | 715 |  | 25 |  | 59 | 4 | 24 | 73 |  | 0.52 | 0.07 | 0.15 | 0.34 |  | 10 | 0
frS |  | 715 |  | 25 |  | 49 | 4 | 20 | 52 |  | 0.5 | 0.09 | 0.2 | 0.4 |  | 9 | 0
fsS |  | 715 |  | 25 |  | 47 | 4 | 18 | 47 |  | 0.48 | 0.17 | 0.27 | 0.41 |  | 8 | 0
frsS |  | 715 |  | 25 |  | 47 | 4 | 19 | 48 |  | 0.42 | 0.09 | 0.17 | 0.32 |  | 8 | 0
Table 3: Simplification of random expressions of length 1000 with one letter algorithms |  | $l_{N}$ |  | $n_{\textit{min}}$ |  | $l_{\textit{avg}}$ | $l_{1/4}$ | $l_{1/2}$ | $l_{3/4}$ |  | $t_{\textit{avg}}$ | $t_{1/4}$ | $t_{1/2}$ | $t_{3/4}$ |  | gc | $\textit{gc}_{f}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
n |  | 564 |  | 0 |  | 359 | 336 | 356 | 381 |  | 0.02 | 0.01 | 0.02 | 0.02 |  | 0 | 0
nr |  | 564 |  | 0 |  | 358 | 334 | 356 | 379 |  | 0.02 | 0.01 | 0.02 | 0.02 |  | 0 | 0
ns |  | 562 |  | 66 |  | 4 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nrs |  | 562 |  | 66 |  | 4 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nrS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nsS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nrsS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nf |  | 562 |  | 59 |  | 6 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nfr |  | 562 |  | 59 |  | 6 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nfs |  | 562 |  | 66 |  | 4 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nfS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nfrs |  | 562 |  | 66 |  | 4 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nfrS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nfsS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nfrsS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nra |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
nraS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
|  | 562 |  | 66 |  | 5 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
r |  | 563 |  | 20 |  | 91 | 4 | 20 | 187 |  | 0.02 | 0.01 | 0.01 | 0.02 |  | 0 | 0
s |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
S |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
rs |  | 562 |  | 66 |  | 4 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
rS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
sS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
rsS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
f |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
fr |  | 562 |  | 62 |  | 5 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
fs |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
fS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
frs |  | 562 |  | 66 |  | 4 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
frS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
fsS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
frsS |  | 562 |  | 66 |  | 3 | 2 | 2 | 4 |  | 0.01 | 0.01 | 0.01 | 0.01 |  | 0 | 0
Table 4: Simplification of random expressions of length 1000 with three letters algorithms |  | $l_{N}$ |  | $n_{\textit{min}}$ |  | $l_{\textit{avg}}$ | $l_{1/4}$ | $l_{1/2}$ | $l_{3/4}$ |  | $t_{\textit{avg}}$ | $t_{1/4}$ | $t_{1/2}$ | $t_{3/4}$ |  | gc | $\textit{gc}_{f}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
n |  | 783 |  | 0 |  | 729 | 718 | 733 | 751 |  | 1.51 | 0.26 | 0.53 | 1.49 |  | 19 | 0
nr |  | 783 |  | 0 |  | 596 | 517 | 678 | 721 |  | 1.07 | 0.12 | 0.38 | 0.75 |  | 13 | 0
ns |  | 783 |  | 7 |  | 315 | 97 | 321 | 516 |  | 2.89 | 0.13 | 0.27 | 1.16 |  | 21 | 3
nS |  | 783 |  | 0 |  | 620 | 566 | 632 | 668 |  | 1.44 | 0.28 | 0.47 | 1.36 |  | 17 | 0
nrs |  | 783 |  | 7 |  | 315 | 97 | 321 | 513 |  | 2.92 | 0.14 | 0.29 | 1.16 |  | 21 | 3
nrS |  | 783 |  | 7 |  | 311 | 79 | 283 | 518 |  | 0.79 | 0.11 | 0.23 | 0.54 |  | 8 | 0
nsS |  | 783 |  | 7 |  | 285 | 79 | 267 | 467 |  | 2.64 | 0.21 | 0.46 | 1.11 |  | 18 | 1
nrsS |  | 783 |  | 7 |  | 281 | 78 | 267 | 467 |  | 2.61 | 0.19 | 0.46 | 1.11 |  | 18 | 1
nf |  | 783 |  | 0 |  | 483 | 356 | 552 | 627 |  | 5.84 | 1.05 | 3.5 | 7.85 |  | 73 | 30
nfr |  | 783 |  | 1 |  | 461 | 309 | 547 | 626 |  | 5.77 | 0.99 | 3.39 | 7.96 |  | 72 | 29
nfs |  | 783 |  | 7 |  | 305 | 93 | 314 | 492 |  | 3.57 | 0.64 | 2.11 | 5.19 |  | 46 | 18
nfS |  | 783 |  | 0 |  | 358 | 189 | 371 | 527 |  | 4.2 | 0.8 | 2.58 | 6.09 |  | 54 | 18
nfrs |  | 783 |  | 7 |  | 305 | 93 | 314 | 492 |  | 3.63 | 0.66 | 2.2 | 5.13 |  | 46 | 18
nfrS |  | 783 |  | 7 |  | 293 | 89 | 279 | 480 |  | 3.27 | 0.69 | 1.68 | 5.21 |  | 39 | 17
nfsS |  | 783 |  | 7 |  | 282 | 79 | 266 | 449 |  | 3.37 | 0.69 | 1.86 | 5.15 |  | 42 | 16
nfrsS |  | 783 |  | 7 |  | 280 | 79 | 266 | 446 |  | 3.37 | 0.68 | 2.03 | 4.86 |  | 41 | 16
nra |  | 783 |  | 5 |  | 373 | 110 | 394 | 583 |  | 33.86 | 9.0 | 24.99 | 46.37 |  | 8 | 0
nraS |  | 783 |  | 7 |  | 310 | 79 | 283 | 516 |  | 69.77 | 19.26 | 59.45 | 102.78 |  | 8 | 0
|  | 783 |  | 3 |  | 643 | 694 | 722 | 741 |  | 3.43 | 0.77 | 1.49 | 3.15 |  | 12 | 0
r |  | 783 |  | 0 |  | 591 | 516 | 670 | 722 |  | 2.18 | 0.42 | 0.88 | 1.83 |  | 10 | 0
s |  | 783 |  | 7 |  | 313 | 96 | 319 | 504 |  | 4.0 | 0.41 | 0.67 | 1.71 |  | 18 | 3
S |  | 783 |  | 7 |  | 554 | 550 | 622 | 666 |  | 2.91 | 0.79 | 1.38 | 3.0 |  | 11 | 0
rs |  | 783 |  | 7 |  | 313 | 96 | 319 | 511 |  | 3.86 | 0.22 | 0.58 | 1.67 |  | 18 | 3
rS |  | 783 |  | 7 |  | 307 | 78 | 281 | 523 |  | 1.62 | 0.23 | 0.59 | 1.51 |  | 7 | 0
sS |  | 783 |  | 7 |  | 283 | 79 | 260 | 466 |  | 3.37 | 0.5 | 0.9 | 1.9 |  | 18 | 1
rsS |  | 783 |  | 7 |  | 280 | 78 | 260 | 466 |  | 3.27 | 0.36 | 0.71 | 1.87 |  | 17 | 1
f |  | 783 |  | 4 |  | 442 | 263 | 544 | 624 |  | 7.48 | 1.5 | 4.02 | 9.48 |  | 72 | 30
fr |  | 783 |  | 1 |  | 454 | 281 | 547 | 620 |  | 7.61 | 1.52 | 3.66 | 9.31 |  | 71 | 29
fs |  | 783 |  | 7 |  | 305 | 93 | 311 | 487 |  | 4.24 | 0.79 | 2.38 | 6.11 |  | 45 | 18
fS |  | 783 |  | 7 |  | 333 | 172 | 350 | 527 |  | 5.01 | 1.05 | 2.7 | 6.19 |  | 54 | 18
frs |  | 783 |  | 7 |  | 305 | 93 | 314 | 489 |  | 4.15 | 0.79 | 2.19 | 5.94 |  | 45 | 18
frS |  | 783 |  | 7 |  | 292 | 89 | 279 | 478 |  | 4.0 | 0.91 | 2.09 | 5.74 |  | 38 | 17
fsS |  | 783 |  | 7 |  | 282 | 79 | 266 | 445 |  | 4.15 | 0.89 | 2.13 | 5.29 |  | 42 | 16
frsS |  | 783 |  | 7 |  | 279 | 79 | 266 | 442 |  | 4.08 | 0.9 | 2.22 | 5.18 |  | 41 | 16
Table 5: Simplification of random expressions of length 1000 with four letters algorithms |  | $l_{N}$ |  | $n_{\textit{min}}$ |  | $l_{\textit{avg}}$ | $l_{1/4}$ | $l_{1/2}$ | $l_{3/4}$ |  | $t_{\textit{avg}}$ | $t_{1/4}$ | $t_{1/2}$ | $t_{3/4}$ |  | gc | $\textit{gc}_{f}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
n |  | 825 |  | 0 |  | 791 | 782 | 796 | 811 |  | 0.56 | 0.07 | 0.18 | 0.48 |  | 7 | 0
nr |  | 825 |  | 0 |  | 743 | 758 | 784 | 802 |  | 0.56 | 0.1 | 0.25 | 0.46 |  | 7 | 0
ns |  | 825 |  | 0 |  | 544 | 434 | 650 | 700 |  | 1.76 | 0.22 | 0.54 | 1.69 |  | 14 | 1
nS |  | 825 |  | 0 |  | 731 | 715 | 734 | 761 |  | 2.15 | 0.28 | 0.4 | 0.76 |  | 8 | 0
nrs |  | 825 |  | 0 |  | 544 | 434 | 650 | 700 |  | 1.81 | 0.25 | 0.58 | 1.74 |  | 14 | 1
nrS |  | 825 |  | 0 |  | 564 | 444 | 681 | 734 |  | 1.74 | 0.22 | 0.41 | 0.7 |  | 7 | 0
nsS |  | 825 |  | 0 |  | 531 | 416 | 645 | 688 |  | 2.98 | 0.42 | 0.88 | 1.91 |  | 15 | 1
nrsS |  | 825 |  | 0 |  | 528 | 416 | 640 | 688 |  | 3.29 | 0.44 | 0.91 | 1.94 |  | 15 | 1
nf |  | 825 |  | 0 |  | 660 | 668 | 709 | 733 |  | 9.02 | 2.63 | 7.07 | 11.61 |  | 71 | 26
nfr |  | 825 |  | 0 |  | 663 | 673 | 710 | 732 |  | 9.05 | 2.68 | 7.17 | 11.62 |  | 72 | 26
nfs |  | 825 |  | 0 |  | 526 | 420 | 621 | 681 |  | 8.25 | 2.04 | 4.83 | 11.57 |  | 61 | 17
nfS |  | 825 |  | 0 |  | 591 | 568 | 661 | 700 |  | 9.54 | 2.74 | 7.28 | 11.02 |  | 66 | 22
nfrs |  | 825 |  | 0 |  | 526 | 420 | 621 | 681 |  | 7.73 | 1.98 | 4.56 | 10.48 |  | 60 | 17
nfrS |  | 825 |  | 0 |  | 538 | 475 | 639 | 695 |  | 7.98 | 2.2 | 4.95 | 10.56 |  | 58 | 19
nfsS |  | 825 |  | 0 |  | 520 | 418 | 616 | 673 |  | 8.78 | 2.22 | 5.03 | 11.16 |  | 60 | 18
nfrsS |  | 825 |  | 0 |  | 524 | 451 | 616 | 673 |  | 8.21 | 2.17 | 4.94 | 10.69 |  | 60 | 19
nra |  | 825 |  | 0 |  | 624 | 535 | 744 | 777 |  | 199.37 | 52.23 | 191.99 | 308.54 |  | 5 | 0
nraS |  | 825 |  | 0 |  | 562 | 440 | 681 | 732 |  | 338.69 | 56.16 | 259.75 | 518.1 |  | 7 | 0
|  | 825 |  | 0 |  | 766 | 775 | 790 | 809 |  | 2.52 | 0.78 | 1.5 | 2.98 |  | 4 | 0
r |  | 825 |  | 0 |  | 742 | 759 | 782 | 802 |  | 2.05 | 0.44 | 1.16 | 2.56 |  | 4 | 0
s |  | 825 |  | 0 |  | 541 | 434 | 650 | 700 |  | 3.27 | 0.99 | 1.78 | 3.7 |  | 9 | 1
S |  | 825 |  | 0 |  | 704 | 709 | 734 | 756 |  | 3.61 | 1.31 | 2.28 | 3.68 |  | 1 | 0
rs |  | 825 |  | 0 |  | 541 | 434 | 650 | 700 |  | 2.61 | 0.59 | 1.23 | 3.32 |  | 9 | 1
rS |  | 825 |  | 0 |  | 563 | 444 | 684 | 734 |  | 3.3 | 0.78 | 1.57 | 3.47 |  | 4 | 0
sS |  | 825 |  | 0 |  | 528 | 416 | 645 | 688 |  | 4.67 | 1.53 | 2.65 | 4.42 |  | 11 | 1
rsS |  | 825 |  | 0 |  | 527 | 416 | 636 | 688 |  | 4.67 | 1.16 | 1.87 | 3.77 |  | 10 | 1
f |  | 825 |  | 0 |  | 658 | 668 | 707 | 732 |  | 10.87 | 3.72 | 7.59 | 13.25 |  | 70 | 26
fr |  | 825 |  | 0 |  | 661 | 670 | 706 | 731 |  | 10.84 | 3.54 | 8.06 | 14.12 |  | 71 | 26
fs |  | 825 |  | 0 |  | 530 | 456 | 621 | 681 |  | 9.19 | 2.83 | 5.38 | 11.81 |  | 61 | 18
fS |  | 825 |  | 0 |  | 584 | 549 | 661 | 700 |  | 10.47 | 3.85 | 7.36 | 13.31 |  | 66 | 22
frs |  | 825 |  | 0 |  | 526 | 420 | 621 | 681 |  | 9.29 | 2.68 | 5.4 | 12.65 |  | 60 | 17
frS |  | 825 |  | 0 |  | 538 | 475 | 639 | 695 |  | 9.86 | 3.4 | 6.05 | 11.7 |  | 58 | 19
fsS |  | 825 |  | 0 |  | 524 | 451 | 616 | 673 |  | 10.06 | 3.32 | 5.9 | 11.55 |  | 60 | 19
frsS |  | 825 |  | 0 |  | 520 | 418 | 616 | 673 |  | 9.9 | 3.31 | 5.75 | 11.73 |  | 59 | 18

###  0.C.0.1 Acknowledgements

I want to thank Yves Deville, Pierre Flener, and José Vander Meulen for their
interest in my work and their useful comments.


-titleNew technologies for probing the diversity of brown dwarfs and exoplanets 11institutetext: Institut d’Astrophysique de Paris, Université Pierre et Marie Curie, UMR7095 CNRS, 98bis bd. Arago, 75014 Paris, France 22institutetext: Observatoire de Haute Provence, CNRS/OAMP, 04870 St Michel l’Observatoire, France 33institutetext: Observatoire de Genève, Université de Genève, 51 Ch. des Maillettes, 1290 Sauverny, Switzerland

# Consequences of spectrograph illumination for the accuracy of radial-
velocimetry

Boisse  I 11<EMAIL_ADDRESS>Bouchy  F 11 2 2 Chazelas  B 33 Perruchot  S 22
Pepe  F 33 Lovis  C 33 Hébrard  G 11

###### Abstract

For fiber-fed spectrographs with a stable external wavelength source,
scrambling properties of optical fibers and, homogeneity and stability of the
instrument illumination are important for the accuracy of radial-velocimetry.
Optical cylindric fibers are known to have good azimuthal scrambling. In
contrast, the radial one is not perfect. In order to improve the scrambling
ability of the fiber and to stabilize the illumination, optical double
scrambler are usually coupled to the fibers. Despite that, our experience on
SOPHIE and HARPS has lead to identified remaining radial-velocity limitations
due to the non-uniform illumination of the spectrograph. We conducted tests on
SOPHIE with telescope vignetting, seeing variation and centering errors on the
fiber entrance. We simulated the light path through the instrument in order to
explain the radial velocity variation obtained with our tests. We then
identified the illumination stability and uniformity has a critical point for
the extremely high-precision radial velocity instruments (ESPRESSO@VLT,
CODEX@E-ELT). Tests on square and octagonal section fibers are now under
development and SOPHIE will be used as a bench test to validate these new feed
optics.

##  1 Introduction

High-precision radial-velocimetry (RV) is still a main technique in the search
and characterization of planetary systems. Up to date, most of the known
extrasolar planets have been detected with this method. It will remain at the
forefront of exoplanet science for the coming years thanks to its efficiency
in finding low-mass planets since HARPS has reached an RV accuracy less than
1ms-1 (ref. RefM ). In the aim to reach Earth-type planets and, also measure
the expansion of the universe, new spectrographs in the visible are now in
study to reach a precision of only few cms-1 in the near future (ESPRESSO@VLT
RefPa1 , CODEX@E-ELT RefPa2 ).

To reach this level of accuracy, we must avoid a certain number of
limitations. Among these, one can quote the stellar noise (activity,
pulsation, surface granulation), the contamination by external sources (moon,
close-by objects, background continuum), and what light may encounter during
its path (e.g. atmospheric dispersion). As part of instrumental factors, CCD
cosmetics, charge transfer inefficiency (ref. RefB1 ), wavelength calibration
(refs. RefL  and RefC ) should be mentioned. For an exhaustive discussion of
these limitations, we refer to RefP . The authors highlight the impact of the
spectrograph illumination as one of the main limiting factors, and the need to
analyze and quantify it. In this proceeding, we then focus on the limitation
due to the injection of light in the fiber-fed spectrograph. This work is
based on our experiment on two high-resolution, high-precision fiber-fed
spectrographs<EMAIL_ADDRESS>Observatoire de Haute-Provence (OHP), France
(refs. RefB2  and RefS ) and<EMAIL_ADDRESS>European Southern Observatory
(ESO)-La Silla, Chile (ref. RefM ).

Up to day, SOPHIE has a Doppler accuracy of about 5 ms-1, as most of high-
accuracy spectrographs involved in exoplanet survey. In service since November
2006, we identified that instrumental limitations mainly come from the old
Cassegrain Fiber Adaptater (developed for ELODIE spectrograph). In order to
reach the so far unique HARPS level of accuracy, we conducted tests that
illustrate the incomplete fiber scrambling. Detected with SOPHIE, these
effects were also characterized on HARPS at a lower level. In the development
of the future instruments, the optimization of SOPHIE is a bench test for the
improvement of the spectrograph illumination uniformity and stability.

The proceeding is structured as followed. In a the second section, we expose
the properties of the fiber-fed spectrographs and the light injection. The
third section reviews the different effects that are detected in the RV due to
the incomplete and imperfect scrambling obtained with the standard fibers. In
the last section, we describe solutions proposed to optimize the fibers
scrambling.

##  2 Fiber-fed spectrographs

HARPS and SOPHIE are fiber-fed spectrographs with simultaneous reference
calibrations. The stellar light collected by the telescope are lead to the
instrument through a standard step-index multi-mode cylindrical optical fiber.
SOPHIE has two observing mode using two different fibers, the High-Resolution
(HR) and the High-Efficiency mode (HE). In HR mode, the spectrograph is fed by
a 40.5-$\mu$m slit superimposed on the output of the 100-$\mu$m fiber,
reaching a spectral resolution of $\lambda/\Delta\lambda$ = 75,000. In HE
mode, the spectrograph is directly fed by the 100-$\mu$m fiber with a
resolution power of 40,000. Both SOPHIE fibers have an sky acceptance of
3-arcsec. HARPS has 70-$\mu$m fiber with a sky acceptance of 1-arcsec and a
spectral resolution of 110,000 (see Table 1).

Non-uniform illumination of the slit or output fiber at the spectrograph
entrance decreases the radial-velocity precision. Indeed, variations in
seeing, focus and image shape at the fiber entrance may induced non-uniform
illumination inside the pupil of the spectrograph. The optical aberrations
lead to variations in the centroids of the stellar lines on the focal plane.

Table 1: Comparison of parameters of fiber-fed spectrographs SOPHIE and HARPS. Instrument | Doppler prec. | 1 pixel | Resol. $\Delta\lambda/\lambda$
---|---|---|---
HARPS |  $\leqslant$ 1ms-1 | 800 ms-1 | 110,000
SOPHIE (HR) |  $\sim$ 4 ms-1 | 1400 ms-1 | 75,000
SOPHIE (HE) |  $\sim$ 10 ms-1 | 1400 ms-1 | 40,000

Optical fibers are used to lead the light from the telescope to the entrance
of the spectrograph. They have the properties to scrambler the atmospheric
effects and guiding and centering errors discussed previously. But the
scrambling ability of one multimode fiber is not perfect as shown in Fig. 1.
With an input off axes image, the azimuthal scrambling is good whereas it
remains some effects in the radial one. This pattern observed is bigger in far
field than in near field. Near field and far field are respectively defined
as, the brightness distribution across the output face of the fiber, and, as
the angular distribution of light of fiber output beam. Therefore, changes in
the input beam cause only circular symmetric changes in the fiber output
pattern. In contrast, imperfect radial scrambling allows small zonal errors to
remain.

Figure 1: Illumination at the output of one cylindrical optical fiber in the
near and the far field. Sources are off axes. A high degree of azimuthal
scrambling is observed. In contrast, it remains some effects in the radial
one.

HARPS and the SOPHIE HR mode are equipped with optical double scramblers. It
is used to increase and improve the uniformity and stabilization of the
illumination of the spectrograph entrance (refs. RefBr  and RefH ). The near
field of a circular fiber is observed to be better scramble than the far
field. In spite of only one fiber guiding the light from the telescope to the
instrument, double scrambler is composed of two fibers coupled with two
doublets. The system is designed to inverse near field and far field in order
to induce a better radial scrambling, although it causes flux losses (ref.
RefB0 ).

##  3 RV effects of fiber imperfect scrambling

###  3.1 Centering/Guiding on the fiber entrance

The degree of radial scrambling describes the stability of the output beam as
the input image is moved from the center to the edge of the fiber. It is
possible to detect in RV some variations due to the insufficiency of radial
scrambling. The light from a stable star is moved with the guiding/centering
system from an edge to the other of the fiber. We compute the RV with the data
reduction pipeline for different positions of the star. The test was done for
the two modes of SOPHIE and for HARPS. The results are computed in Table 2.

Table 2: Variation observed in RV as the input image (star) is moved from the center to the edge of the fiber. HARPS and SOPHIE with High-Resolution fiber used a double scrambler instead of the High-Efficiency mode of SOPHIE. Instrument | fib. diam. | RV effect [ms-1]
---|---|---
HARPS | 1” |  $\sim$ 3
SOPHIE (HR) | 3” |  $\sim$ 13
SOPHIE (HE) | 3” |  $\sim$ 36

Because the scrambling of the fiber is not perfect, the movement of the input
image corresponds to a shift on the detector. We observed first that, wider is
the fiber, more important is the RV variations. Moreover, the value of meter
per second per pixel vary as a function of the resolution power. Moving the
input image from the center to the edge is then expected to have a lower
effect for a higher spectral resolution. In addition, we expect that the
double scrambler improve the radial scrambling, i.e. decrease the RV effect.

###  3.2 Vignetting telescope

The pupil of the telescope, i.e. the entrance of the telescope or the far
field of the input light is known to be more stable than the telescope image.
We would like to test the effect in RV of variations of the far field. For
that, we vignette the telescope on day sky with the dome. We computed the RV
with the pipeline SOPHIE, estimating that the variation of Barycentric Earth
RV is not significant during our measurements. We made this test with the HE
mode in order that the variation of the far-field of the telescope are
projected on the grating (i.e. without double scrambler). We remarked that the
way of the RV variations depends on exterior or interior vignetting (Fig. 2).

Figure 2: Schema illustrating how the vignetting of the telescope is
translated at the output of the fiber HE in the far-field, i.e. at the
entrance of the spectrograph. For external occultation, the RV decrease
whereas, for internal occultation the RV increase.

###  3.3 Optical path simulations

We simulated the optical path in the SOPHIE spectrograph. We observed a
displacement of the spectrum in function of wavelength on the focal plane when
the input beam at the entrance of the spectrograph is center-illuminated or
center-darked, corresponding respectively when vignetting external and
internal part of the pupil in HE mode (cf. Sect.3.2). Variation of the slit or
the optical fiber illumination are directly translated on the spectrum in Fig.
3. We observed that the shift is more significant for an external occultation.
Because the effect is not symmetric along an order and not monitored by the
calibration lamp, the final computed RV vary. So, variations of the far-field
pattern projected onto the grating can introduce radial-velocity shifts at the
detector lowering the final precision in RV.

Figure 3: Displacement of the position of a nine wavelength as a function of a
internal (green) or an external (red) occultation of the entrance of the
spectrograph on the CCD detector.

Figure 4: When the seeing is good, the telescope image is less wide. With the
double scrambler in HR mode, near field becomes far-field and is projected on
the collimator at the entrance of the spectrograph. The pattern is comparable
to that observed in HE when vignetting telescope (Fig. 2)

###  3.4 RV effects due to seeing variations

Variations of the far-field of the input beam in HE mode is equivalent to a
variation of the telescope image in HR mode, due to the double scrambler.
Variations in seeing induce a variation of the input image as illustrate in
Fig. 4. The input beam at the entrance of the spectrograph is center-
illuminated (external occultation) when a target is observed with a good
seeing in HR mode. The previous tests and simulations explain a systematic
effect observed with SOPHIE named as ”seeing effect”. For a sample of stars
observed at high signal to noise ratio (SNR) in HR mode, we observed a
decrease in RV correlated with an estimation of seeing. The value of the
seeing is not monitored with SOPHIE. We estimated it with calculating the
relative flux by unit of exposure time :

$S=\frac{SNR^{2}}{T_{exp}10^{-M_{V}/2.5}}$ (1)

with SNR, the signal to noise ratio of the spectra, Texp the time exposure of
the measurement, MV the visual magnitude of the target. The seeing decrease
when the seeing estimation $S$ increase. With a lower seeing, the input image
is smaller than the fiber width, and as shown in the simulations, induced a
variation of the far field input in the spectrograph, due to the double
scrambler. We expect and observed a decrease of RV when the value of the
seeing decrease as shown in Fig. 5.

Figure 5: Radial-velocity measurements as a function of a seeing index (cf.
text). The seeing decrease when the seeing estimation $S$ increase. As the
seeing is lower, the RV decreases.

Moreover, when the input image is smaller than the diameter of the fiber, we
are more sensible to effect of guiding and centering system. The guiding and
centering system may induced variation of the position of the input image on
the slit or the entrance of the fiber, and so introduce RV variations. These
RV variation are quite random, and add some noise.

Whereas the seeing effect is directly related to the optical path in the
spectrograph, it may be quantified. We are modeling this variations with our
data in order to remove this noise with a software tool.

We note that the effect on HARPS is expected to be lower. The 1” width of the
fibers is smaller than the SOPHIE and roughly equivalent to the typical seeing
at La Silla. Furthemore the quality image provided by the 3.6-m telescope is
close to 0.7 arcsec. Hence, HARPS is less sensible to the variations of
seeing. Moreover, the resolution power of the instrument is better and then
the incomplete radial scrambling has a lower impact in RV as shown in Sect.
3.1. Furthermore the optical aberrations on HARPS are smaller than in SOPHIE.

##  4 Perspectives and conclusions

The CODEX experiment calls for a Doppler precision as low as 1 cms-1. This
work shows that the future instruments need for better scrambling to reach
this accuracy. New types of fibers for feeding the telescope or new double
scrambler are needed to improve the precision and to minimize the noise due to
variations of the illumination at the entrance of the spectrograph. To remove
the spherical symmetry of cylindrical fibers, octagonal and square section
optical fibers are then in study at Geneva, OHP-LAM, and ESO Garching. As
first results, very good scrambling properties are observed in the near field,
whereas strange patterns in far field are not well understood at the moment.
It needs future tests to improve the measurements, to study its best used, on
all the path or in a double scrambling mode. SOPHIE is then going to be a
bench test for the future instruments.

We note that additional solution is being installed on HARPS to reduce the
guiding and centering limitations. A tip-tilt mirror generate small-amplitude
and high frequencies variations in order to induce a spread of the light.

A new guiding camera is now in operation on SOPHIE and allows a better guiding
and centering and also allows to monitor the exact seeing.

## References

  * (1) Bouchy & Connes A&A, 1999, Volume136, 193
  * (2) Bouchy, F., Isambert, J., Lovis, C. Boisse, I. et al. EAS Publications Series, Volume37, 2009, pp.247-253
  * (3) Bouchy, F., Hébrard, G., Udry, S., Delfosse, X., Boisse, I. et al. A&A, Volume505, 2009, pp.853
  * (4) Brown, T. M. 1990, ASPC, 8, 335B
  * (5) Lovis, C. & Pepe, F. 2007, A&A, 468, 1115L
  * (6) Hunter, T.D. & Ramsey, L.W. 1992, PASP, 104, 1244
  * (7) Mayor, M., Udry, S., Lovis, C. et al. 2009, A&A, 493, 639
  * (8) Pasquini, L., Manescau, A., Avila, G. et al. 2009, svlt.conf, 411
  * (9) Pasquini, L., Avila, G., Dekker, H. et al. 2008, SPIE.7014E, 51P
  * (10) Pepe, F. & Lovis, C., Phys. Scr. T130, (2008) 014007
  * (11) Perruchot, S., Kohler, D., Bouchy, F. et al. 2008, SPIE.7014E, 17P
  * (12) Wildi, F., Pepe, F., Lovis, C., Chazelas, B. et al. 2009, SPIE.7440E, 19W