11institutetext: Grupo de Astrofísica Molecular, Instituto de Física
Fundamental (IFF-CSIC), C/ Serrano 121, 28006 Madrid, Spain. 11email:
<EMAIL_ADDRESS>22institutetext: Centro de Desarrollos Tecnológicos,
Observatorio de Yebes (IGN), 19141 Yebes, Guadalajara, Spain. 33institutetext:
Observatorio Astronómico Nacional (IGN), C/ Alfonso XII, 3, 28014, Madrid,
Spain.

# Discovery of CH2CHCCH and detection of HCCN, HC4N, CH3CH2CN, and,
tentatively, CH3CH2CCH in TMC-1 ††thanks: Based on observations carried out
with the Yebes 40m telescope (projects 19A003, 19A010, 20A014, 20D023). The
40m radio telescope at Yebes Observatory is operated by the Spanish Geographic
Institute (IGN, Ministerio de Transportes, Movilidad y Agenda Urbana).

J. Cernicharo 11 M. Agúndez 11 C. Cabezas 11 N. Marcelino 11 B. Tercero 2233
J. R. Pardo 11 J. D. Gallego 22 F. Tercero 22 J. A. López-Pérez 22 and P. de
Vicente 22

(Received; accepted)

We present the discovery in TMC-1 of vinyl acetylene, CH2CHCCH, and the
detection, for the first time in a cold dark cloud, of HCCN, HC4N, and
CH3CH2CN. A tentative detection of CH3CH2CCH is also reported. The column
density of vinyl acetylene is (1.2$\pm$0.2)$\times$1013 cm-2, which makes it
one of the most abundant closed-shell hydrocarbons detected in TMC-1. Its
abundance is only three times lower than that of propylene, CH3CHCH2. The
column densities derived for HCCN and HC4N are (4.4$\pm$0.4)$\times$1011 cm-2
and (3.7$\pm$0.4)$\times$1011 cm-2, respectively. Hence, the HCCN/HC4N
abundance ratio is 1.2$\pm$0.3. For ethyl cyanide we derive a column density
of (1.1$\pm$0.3)$\times$1011 cm-2. These results are compared with a state-of-
the-art chemical model of TMC-1, which is able to account for the observed
abundances of these molecules through gas-phase chemical routes.

###### Key Words.:

molecular data — line: identification — ISM: molecules — ISM: individual
(TMC-1) — — astrochemistry

##  1 Introduction

The chemical complexity of the interstellar medium has been demonstrated by
the detection of more than 200 different chemical species. In this context,
the cold dark core TMC-1 presents an interesting carbon-rich chemistry that
led to the formation of long neutral carbon-chain radicals and their anions
(see Cernicharo et al. 2020a, and references therein). Cyanopolyynes, which
are stable molecules, are also particularly abundant in TMC-1 (see Cernicharo
et al. 2020b, c, and references therein). The chemistry of this peculiar
object produces a large abundance of the nearly saturated species CH3CHCH2,
which could mostly be a typical molecule of hot cores (Marcelino et al. 2007).
The polar benzenic ring C6H5CN has also been detected for the first time in
space in this object (McGuire et al. 2018), while benzene itself has only so
far been been detected toward post-asymptotic giant branch objects (Cernicharo
et al. 2001).

Sensitive line surveys are the best tools for unveiling the molecular content
of astronomical sources and searching for new molecules. A key element for
carrying out a detailed analysis of line surveys is the availability of
exhaustive spectroscopic information of the already-known species, their
isotopologues, and their vibrationally excited states. The ability to identify
the maximum possible number of spectral features leaves the cleanest possible
forest of unidentified ones, therefore opening up a chance to discover new
molecules and get insights into the chemistry and chemical evolution of the
observed objects. In this context we have recently succeeded in discovering,
prior to any spectroscopic information from the laboratory, several new
molecular species (see, e.g., Cernicharo et al. 2020a, b, c, 2021a, 2021b;
Marcelino et al. 2020). Consequently, the astronomical object under study has
become a real spectroscopic laboratory. Experience shows that, if the
sensitivity of a line survey is sufficiently high, many unknown species will
be discovered, providing key information on the ongoing chemical processes in
the cloud.

In this letter we report on the discovery of vinyl acetylene, CH2CHCCH, a
species that has been spectroscopically characterized but never detected in
space. We also present the detection, for the first time in a cold dark cloud,
of HCCN, HC4N, and CH3CH2CN. Ethyl acetylene, CH3CH2CCH, has also been
tentatively detected.

##  2 Observations

New receivers, built within the Nanocosmos
project111https://nanocosmos.iff.csic.es/ and installed at the Yebes 40m radio
telescope, were used for the observations of TMC-1. The Q-band receiver
consists of two high electron mobility transistor cold amplifiers covering the
31.0-50.3 GHz range with horizontal and vertical polarizations. Receiver
temperatures vary from 17 K at 32 GHz to 25 K at 50 GHz. Eight 2.5 GHz wide
fast Fourier transform spectrometers, with a spectral resolution of 38.15 kHz,
provide the whole coverage of the Q-band in each polarization. The main beam
efficiency varies from 0.6 at 32 GHz to 0.47 at 50 GHz. A detailed description
of the system is given in Tercero et al. (2021).

The line survey of TMC-1 ($\alpha_{J2000}=4^{\rm h}41^{\rm m}41.9^{\rm s}$ and
$\delta_{J2000}=+25^{\circ}41^{\prime}27.0^{\prime\prime}$) in the Q-band was
performed over several sessions. Previous results obtained from the line
survey were based on two observing runs, one performed in November 2019 and
one in February 2020. They concerned the detection of C3N- and C5N-
(Cernicharo et al. 2020b), HC5NH+ (Marcelino et al. 2020), HC4NC (Cernicharo
et al. 2020c), and HC3O+ (Cernicharo et al. 2020a). Additional data were taken
in October 2020, December 2020, and January 2021 to improve the line survey
and to further check the consistency of all observed spectral features. These
new data allowed the detection of HC3S+ (Cernicharo et al. 2021a) along with
the acetyl cation, CH3CO+ (Cernicharo et al. 2021b), the isomers of C4H3N
(Marcelino et al. 2021), and HDCCN (Cabezas et al.  2021).

Two different frequency coverages were used in the line survey, 31.08-49.52
GHz and 31.98-50.42 GHz, to ensure that no spurious spectral ghosts were
produced in the down-conversion chain, which down-converts the signal from the
receiver to 1-19.5 GHz and then splits it into eight 2.5 GHz bands, which are
finally analyzed by the FFTs. The observing procedure was frequency switching
with a frequency throw of 10 MHz for the first two runs and 8 MHz for the
later ones. The intensity scale (i.e., the antenna temperature, $T_{A}^{*}$)
was calibrated using two absorbers at different temperatures and the
atmospheric transmission model (ATM; Cernicharo 1985; Pardo et al. 2001).
Calibration uncertainties were adopted to be 10 %. The nominal spectral
resolution of 38.15 kHz was kept for the final spectra. The sensitivity varied
across the Q-band from 0.5 to 2.0 mK. All data were analyzed using the GILDAS
package222http://www.iram.fr/IRAMFR/GILDAS.

##  3 Results and discussion

The sensitivity of our observations toward TMC-1 (see Sect. 2) is a factor of
10-20 better than previously published line surveys of this source at the same
frequencies (Kaifu et al. 2004). This large improvement allowed us to detect a
forest of weak lines, most of which arise from the isotopologues of abundant
species such as HC3N, HC5N, and HC7N (Cernicharo et al. 2020c). In fact, it
was possible to detect many individual lines (Marcelino et al. 2021) from
molecular species that had previously only been reported using stacking
techniques. Taking into account, on one hand, the large abundances found in
TMC-1 for cyanide derivatives of abundant species and, on the other, the
presence of nearly saturated hydrocarbons such as CH3CHCH2 (Marcelino et al.
2007), we searched for species such as CH2CHCCH and CH3CH2CCH, as well as for
cyanides found previously only in carbon-rich stars (HCCN and HC4N) or in warm
molecular clouds (CH3CH2CN). Line identifications in this TMC-1 survey were
performed using the MADEX catalogue (Cernicharo 2012), the Cologne Database of
Molecular Spectroscopy (CDMS) catalogue (Müller et al. 2005), and the JPL.

Figure 1: Observed transitions of CH2CHCCH toward TMC-1. The abscissa
corresponds to the rest frequency of the lines assuming a vLSR for the source
of 5.83 km s-1. Frequencies and intensities for the observed lines are given
in Table LABEL:tab_line_parameters. The ordinate is the antenna temperature,
corrected for atmospheric and telescope losses, in millikelvins (mK). The
purple line shows the synthetic spectrum obtained for this species.  Figure 2:
Line profile for CH3CH2CCH toward TMC-1 from stacking the signal from the
transitions of this species in the 31-50 GHz frequency range. The abscissa
corresponds to the local standard of rest velocity. The ordinate is the
antenna temperature, corrected for atmospheric and telescope losses, in mK.
The observed spectra from the individual lines are shown in Fig. 6.

###  3.1 Vinyl acetylene, CH2CHCCH

Spectroscopic constants for CH2CHCCH were derived from a fit to the lines
reported by Thorwirth et al.  (2004) and implemented in the MADEX code
(Cernicharo 2012). We detected six lines with $K_{a}$=0 and 1 (see Fig. 1).
Although the observed line intensities (see Table LABEL:tab_line_parameters)
are low ($\sim$2-3 mK), the column density for this molecule should be
particularly large as its dipole moment, $\mu_{a}$, is only 0.43 D (Sobolev et
al.  1962; Thorwirth & Lichau  2003). Only a $K_{a}$=2 line was marginally
detected, corresponding to the $4_{22}-3_{21}$ rotational transition. Assuming
a uniform source with a radius of 40′′ (Fossé et al. 2001) and through a
standard rotational diagram, we derived a rotational temperature of
5.0$\pm$0.5 K and a column density for vinyl acetylene of
(1.2$\pm$0.2)$\times$1013 cm-2. Figure 1 shows the synthetic spectrum of
CH2CHCCH computed for the derived rotational temperature and column density
(see Appendix A). The comparison with the data shows a very good agreement for
all lines, with the exception of the 505-404 transition, for which the
predicted intensity is nearly a factor of two larger than what is observed.
This line is probably affected by a negative spectral feature resulting from
the folding of the frequency switching data.

Using the column density of H2 derived by Cernicharo & Guélin  (1987), the
abundance of CH2CHCCH relative to H2 toward TMC-1 is 1.2$\times$10-9. This
abundance is only three times lower than that of propylene (Marcelino et al.
2007), and ten times lower than that of methyl acetylene (Cabezas et al.
2021). Hence, vinyl acetylene is one of the most abundant hydrocarbons in
TMC-1 and probably the most abundant compound containing four carbon atoms. It
is interesting to compare the abundance of vinyl acetylene with that of vinyl
cyanide. We analyzed the lines of CH2CHCN covered by our Q-band data. We
derived a rotational temperature of 4.5$\pm$0.3 K, and
$N$(CH2CHCN)=(6.5$\pm$0.5)$\times$1012 cm-2 (see Appendix C). Hence, the
abundance ratio between the acetylenic and cyanide derivatives of ethylene
(CH2CH2) is 1.8$\pm$0.4, which suggests that ethylene could be a likely
precursor of CH2CHCCH and CH2CHCN through reactions with CCH and CN,
respectively (see Sect. 3.4 for more details).

Figure 3: Observed lines of HCCN in our Q-band survey toward TMC-1. The
abscissa corresponds to the rest frequency assuming a vLSR of the source of
5.83 km s-1. The ordinate is the antenna temperature, corrected for
atmospheric and telescope losses, in mK. The violet line shows the synthetic
spectrum computed for Tr=4.5 K and N(HCCN)=4.4$\times$1011 cm-2. For the sake
of clarity, only the upper quantum numbers F1 and F are provided in panel (c).

We searched for CH3CH2CCH in our survey. Figure 2 shows the resulting spectrum
from stacking the lines of this species covered in our data (see details in
Appendix B). The whole set of individual lines is shown in Fig. 6. We consider
this molecule to be tentatively detected with a column density of
9$\times$1011 cm-2. We also detected ethyl cyanide, CH3CH2CN, in TMC-1 (see
Sect. 3.3) with a column density of 1011 cm-2. Hence, assuming that CH3CH2CCH
in TMC-1 is detected, the abundance ratio CH3CH2CCH/CH3CH2CN is $\sim$9.

###  3.2 HCCN and HC4N

The cyano methylene radical, HCCN, was detected toward the carbon-rich star
IRC+10216 by Guélin & Cernicharo  (1991). The molecule has been observed in
the laboratory by several authors (Saito et al.  1984; Endo & Ohshima  1993;
McCarthy et al.  1995; Allen et al.  2001). Its dipole moment is 3.04 D
(Inostroza et al.  2012). Given the large abundance of cyanopolyynes in TMC-1
(e.g., Cernicharo et al. 2020c), HCCN could be expected in this source,
although it was searched for by McGonagle & Irvine  (1996) with no success.
Several of its rotational transitions, which show significant hyperfine
splitting, are within the frequency range of our TMC-1 survey. All of them
were detected, as shown in Fig. 3 (see Table LABEL:tab_line_parameters). This
is the first time HCCN has been detected in cold interstellar clouds. The
range of level energies covered by the observed transitions, 1.6-3.7 K, did
not allow us to build a reliable rotational diagram. We adopted the rotational
temperature derived for CH2CHCN (4.5$\pm$0.5 K; see Sect. 3.1) and computed a
synthetic spectrum with the column density as a free parameter. The best fit
was obtained for a column density of (4.4$\pm$0.4)$\times$1011 cm-2. As shown
in Fig. 3, the match between the model and the observations is very good.

Figure 4: Selected lines of HC4N in the 31-50 GHz frequency range toward
TMC-1. The abscissa corresponds to the rest frequency assuming a vLSR for
TMC-1 of 5.83 km s-1. The ordinate is the antenna temperature, corrected for
atmospheric and telescope losses, in mK. The violet line shows the synthetic
spectrum computed for Tr=4.0 K and N(HC4N)=3.7$\times$1011 cm-2.

In addition to HCCN, the linear cyano ethynyl-methylene radical, HC4N, was
also detected in IRC+10216 (Cernicharo et al.  2004). Spectroscopic
information on this molecule (Tang et al.  1999) was implemented in MADEX. Its
dipole moment is 4.33 D (Ikuta et al.  2000). The observed lines toward TMC-1
are shown in Fig. 4. From those lines and the model fitting procedure, it is
possible to derive a rotational temperature of 4$\pm$1 K and a column density
of (3.7$\pm$0.4)$\times$1011 cm-2. Figure 4 shows the synthetic spectrum
corresponding to these parameters. The agreement with the observations is very
good. This is the first time that this species has been detected in a cold
dark cloud.

We searched for the bent and cyclic isomers of HC4N (McCarthy et al.  1999a,
b) without success. We derived 3$\sigma$ upper limits to their column
densities of 1.5$\times$1011 cm-2 and 1.0$\times$1011 cm-2, respectively. It
is interesting to note that these two isomers have a very different molecular
structure relative to linear HC4N (Cernicharo et al.  2004). Hence, they are
probably not formed in the reaction between CH and HC3N, which is the main
pathway to the linear isomer. Finally, we searched for the related radicals
CCN (Kakimoto & kasuya  1982; Ohshima & Endo  1995) and C4N (McCarthy et al.
2003). However, due to their low permanent dipole moment (Pd et al. 2001;
Fiser & Polák  2013), we obtained very conservative 3$\sigma$ upper limits to
their abundances of 1.8$\times$1012 cm-2 and 4.0$\times$1013 cm-2 ,
respectively.

The abundance ratio HCCN/HC4N derived in TMC-1 is 1.2$\pm$0.3, which is very
different than that derived in the carbon-star envelope IRC +10216 ($\sim$ 9;
Cernicharo et al.  2004). In IRC +10216, this abundance ratio is a factor of
two larger than the HC2n+1N/HC2n+3N decrement observed for cyanopolyynes
(Cernicharo et al.  2004), while in TMC-1 the HCCN/HC4N ratio is two to three
times lower than that of the cyanopolyyne decrement. The different behavior in
TMC-1 compared to IRC +10216 is probably caused by differences in the
abundances of the precursors of HCCN and HC4N (see Sect. 3.4).

###  3.3 CH3CH2CN

This molecule is typical of warm molecular clouds, where it produces a forest
of lines arising from all its isotopologues and low-energy vibrational excited
states (Demyk et al.  2007; Daly et al.  2013). It was searched for in TMC-1
by Minh & Irvine  (1991) without success. More recently, Lee et al.  (2021)
used stacking techniques, providing an upper limit to its column density in
TMC-1 of 4$\times$1011 cm-2. We searched for the lines of this molecule in our
TMC-1 Q-band survey. Figure 7 shows the six lines with $K_{a}$=0 and 1
detected. All of them appear at 4-5$\sigma$ levels. The $K_{a}$=2 lines are
too weak to be detected with the sensitivity of our survey.

We computed a synthetic spectrum using the rotational temperature derived for
CH2CHCN (4.5 K; see Appendix C) and a column density of
$N$(CH3CH2CN)=1.1$\times$1011 cm-2 (with an estimated error of 30%). The match
between the observations and the model is very reasonable. We derived
abundance ratios CH2CHCN/CH3CH2CN=65$\pm$20 and
CH2CHCCH/CH3CH2CCH=120$\pm$40\. It is interesting to compare the abundance
ratio between vinyl cyanide and ethyl cyanide in TMC-1 and that in Orion KL.
In the latter source it is 0.06 (López et al.  2014), which is a factor of
$\sim$1100 smaller than in TMC-1. The spatial distribution of both molecules
in Orion KL has been analyzed by Cernicharo et al.  (2016). Both species arise
in regions with temperatures of 100 and 350 K. The huge difference in this
abundance ratio tells us about the different chemical processes prevailing in
cold and warm molecular clouds. While the chemistry is dominated by the
contribution of the evaporating ices covering dust grains in objects such as
Orion KL, reactions between radicals and neutrals in cold dark clouds play a
key role in producing these molecules.

###  3.4 Chemistry of detected molecules

After the discovery of abundant propylene in TMC-1 (Marcelino et al. 2007),
the detection of an even larger, partially saturated, and abundant
hydrocarbon, such as vinyl acetylene, in the same cloud brings to light the
existence of a rich organic chemistry in cold dark clouds, going beyond the
long-known presence of unsaturated carbon chains. Moreover, just as the
hydrocarbons CH3CCH and CH2CCH2 act as precursors of the various nitriles
C4H3N found in TMC-1 (Marcelino et al. 2021), CH2CHCCH emerges as a very
likely candidate precursor of the large nitriles with molecular formula C5H3N
that have recently been claimed in TMC-1 (Lee et al.  2021).

To get insight into the formation mechanism of CH2CHCCH and the other
molecules covered in this study, we ran a pseudo-time-dependent gas-phase
chemical model that adopts typical parameters of cold dark clouds (see, e.g.,
Agúndez & Wakelam 2013). We used the chemical network RATE12 from the UMIST
database (McElroy et al. 2013), augmented with reactions relevant for the
molecules of interest in this work, which are discussed below.

Vinyl acetylene is formed in the model through the neutral-neutral gas-phase
reactions C2 \+ C2H6, CH + C3H4 (where C3H4 stands for the two isomers CH3CCH
and CH2CCH2), and C2H + C2H4. These reactions have been found to be rapid at
low temperatures (Canosa et al. 2007; Daugey et al. 2005; Bowman et al. 2012),
and branching ratios have been measured for some of them (Loison & Bergeat
2009; Goulay et al. 2009; Bowman et al. 2012). Vinyl acetylene is predicted to
form with a peak abundance of $\sim 10^{-9}$ relative to H2 (see Fig. 5), in
good agreement with the value derived from observations. We also investigated
whether cyanide derivatives of CH2CHCCH can be formed through the reaction CN
+ CH2CHCCH, which has been found to be rapid for temperatures down to 174 K
(Yang et al. 1992). The peak abundance calculated for the generic species
C5H3N, which accounts for different possible isomers, is a few times 10-10
relative to H2, somewhat above the observed abundance, which means that the
reaction between CN and vinyl acetylene is a viable route to the C5H3N isomers
found in TMC-1 (Lee et al.  2021). Information on the kinetics of this
reaction down to very low temperatures would be highly valuable to validate
this mechanism.

Figure 5: Calculated fractional abundances of assorted molecules relevant to
this study as a function of time. Horizontal dashed lines correspond to
observed values.

Ethyl cyanide can also be formed efficiently in the gas phase in cold dark
cloud conditions. In our chemical model the main route involves the radiative
association between CH${}_{3}^{+}$ and CH3CN and the dissociative
recombination of the ion C2H5CNH+ with electrons, both of which have measured
rate constants (Anicich 1993; Vigren et al. 2010). The calculated peak
abundance is $\sim 10^{-10}$ relative to H2 (see Fig. 5), which is around ten
times higher than the observed value. The chemical network probably misses
some important reactions of destruction of CH3CH2CN (e.g., with neutral atoms
or ions) which could explain the abundance overestimation.

We finally discuss the formation of the allenic molecules HCCN and HC4N in
TMC-1. The chemical network that involves HCCN is mostly taken from Loison et
al. (2015), while that for HC4N is assumed to be similar. The chemical model
predicts HCCN to be around ten times more abundant than HC4N (see Fig. 5), in
contrast with observations that find both molecules to have similar
abundances. The reason for this is that the main routes to HCCN and HC4N are
the reactions CH + HCN/HNC and CH + HC3N, respectively (with rate constants
based on Zabarnick et al. 1991), and the chemical model predicts that HCN and
HNC together are around ten times more abundant than HC3N. However,
observations indicate that HC3N is as abundant as HCN and HNC in TMC-1 (e.g.,
Agúndez & Wakelam 2013), and therefore if the reactions CH + HCN/HNC and CH +
HC3N are the main pathways to HCCN and HC4N, respectively, one would expect
similar abundances for HCCN and HC4N, in agreement with observations. The
higher HCCN/HC4N observed in IRC +10216 is probably explained by the higher
abundance of HCN compared to HC3N in this source.

###### Acknowledgements.

We thank Ministerio de Ciencia e Innovación of Spain (MICIU) for funding
support through projects AYA2016-75066-C2-1-P, PID2019-106110GB-I00,
PID2019-107115GB-C21 / AEI / 10.13039/501100011033, and PID2019-106235GB-I00.
We also thank ERC for funding through grant ERC-2013-Syg-610256-NANOCOSMOS.
M.A. thanks MICIU for grant RyC-2014-16277.

## References

  * Agúndez & Wakelam (2013) Agúndez, M. & Wakelam, V. 2013, Chem. Rev. 113, 8710
  * Allen et al. (2001) Allen, M.D., Evenson, K.M., & Brown, J.M., 2001, J. Mol. Spectrosc., 209, 143
  * Anicich (1993) Anicich, V. G. 1993, J. Phys. Chem. Ref. Data, 22, 1469
  * Bestmann & Dreizler (1985) Bestmann, G., & Dreizler, H., 1985, Z. Naturforsch, 40a, 263
  * Bowman et al. (2012) Bowman, J., Goulay, F., Leone, S. R., & Wilson, K. R. 2012, J. Phys. Chem. A, 116, 3907
  * Cabezas et al. (2021) Cabezas, C., Endo, Y., Roueff, E., et al. 2021, A&A, 646, L1
  * Canosa et al. (2007) Canosa, A., Páramo, A., Le Picard, S. D., & I. R. Sims 2007, Icarus, 187, 558
  * Cernicharo (1985) Cernicharo, J. 1985, Internal IRAM report (Granada: IRAM)
  * Cernicharo & Guélin (1987) Cernicharo, J., & Guélin, M. 1987, A&A, 176, 299
  * Cernicharo et al. (2001) Cernicharo, J., Heras, A.M, Tielens, A.G.G.M., et al., 2001, ApJ, 546, L123
  * Cernicharo et al. (2004) Cernicharo, J., Guélin, M., & Pardo, J.R., 2004, ApJ, 615, L145
  * Cernicharo (2012) Cernicharo, J., 2012, in ECLA 2011: Proc. of the European Conference on Laboratory Astrophysics, EAS Publications Series, 2012, Ed.: C. Stehl, C. Joblin, & L. d’Hendecourt (Cambridge Univ. Press), 251; https://nanocosmos.iff.csic.es/?page$\\_$id=1619
  * Cernicharo et al. (2016) Cernicharo, J., Kisiel, Z., Tercero, B., et al. 2016, A&A, 587, L4
  * Cernicharo et al. (2020a) Cernicharo, J., Marcelino, N, Agúndez, M., et al. 2020a, A&A, 642, L17
  * Cernicharo et al. (2020b) Cernicharo, J., Marcelino, N., Pardo, J.R., et al. 2020b, A&A, 641, L9
  * Cernicharo et al. (2020c) Cernicharo, J., Marcelino, N., Agúndez, et al. 2020c, A&A, 642, L8
  * Cernicharo et al. (2021a) Cernicharo, J., Cabezas, C., Endo, Y., et al. 2021a, A&A, 646, L3
  * Cernicharo et al. (2021b) Cernicharo, J., Cabezas, C., Bailleux, S., et al. 2021b, A&A, in press
  * Daly et al. (2013) Daly, A.M., Bermúdez, C., López, A., et al. 2013, ApJ, 768, 81
  * Daugey et al. (2005) Daugey, N., Caubet, P., Retail, B., et al. 2005, PCCP, 7, 2921
  * Demaison et al., (1983) Demaison, J., Boucher, D., Burie, J., & Dubrulle, A. 1983, Z. Naturforsch, 38a, 447
  * Demyk et al. (2007) Demyk, K., Mäder, H., Tercero, B., et al. 2007, A&A, 466, 255
  * Endo & Ohshima (1993) Endo, Y., & Ohshima, Y. 1993, J. Chem. Phys., 98, 6618
  * Fossé et al. (2001) Fossé, D., Cernicharo, J., Gerin, M., Cox, P. 2001, ApJ, 552, 168
  * Fiser & Polák (2013) Fiser, J., & Polák, R. 2013, Chem. Phys., 425,126
  * Goulay et al. (2009) Goulay, F., Trevitt, A. J., Meloni, G., et al. 2009, J. Am. Chem. soc., 131, 993
  * Guélin & Cernicharo (1991) Guélin, M., & Cernicharo, J. 1991, A&A, 244, L21
  * Ikuta et al. (2000) Ikuta, S., Tsuboi, T., Aoki, K. 2000, J. Mol. Struct., 528, 297
  * Inostroza et al. (2012) Inostroza, N., Huang, X., & Lee, T.J. 2012, J. Chem. Phys., 135, 244310
  * Kaifu et al. (2004) Kaifu, N., Ohishi, M., Kawaguchi, K., et al. 2004, PASJ, 56, 69
  * Kakimoto & kasuya (1982) Kakimoto, M., & Kasuya, T. 1982, J. Mol. Spectrosc.. 94, 380
  * Landsberg & Suenram (1983) Landsberg, B.M., & Suenram, R.D. 1983, J. Mol. Spectrosc., 98, 210
  * Lee et al. (2021) Lee, K.L.K., Loomis, R.A., Burkhardt, A.M., et al. 2021, ApJ, arXiv:2101.05858v1
  * Loison & Bergeat (2009) Loison, J.-C. & Bergeat, A. 2009, PCCP, 11, 655
  * Loison et al. (2015) Loison, J.-C., Hébrard, E., Dobrijevic, M., et al. 2015, Icarus, 247, 218
  * López et al. (2014) López, A., Tercero, B., Kisiel, Z., et al. 2014, A&A, 572, A44
  * Marcelino et al. (2007) Marcelino, N., Cernicharo, J., & Agúndez, M.,et al. 2007, ApJ, 665, L127
  * Marcelino et al. (2020) Marcelino, N., Agúndez, M., Tercero, B., et al. 2020, A&A, 643, L6
  * Marcelino et al. (2021) Marcelino, N., Tercero, B., Agúndez, M., & Cernicharo, J. 2021, A&A, in press, arxiv.org/abs/2101.08516
  * McCarthy et al. (1995) McCarthy, M.C., Gottlieb, C.A., Cooksy, A.L., & Thaddeus, P. 1995, J. Chem. Phys., 103, 7779
  * McCarthy et al. (1999a) McCarthy, M.C., Apponi, A.J., Gordon, V.D., et al. 1999a, J. Chem. Phys., 111, 6750
  * McCarthy et al. (1999b) McCarthy, M.C., Grabow, J.-U., Travers, M.J., et al. 1999b, ApJ, 513, 305
  * McCarthy et al. (2003) McCarthy, M.C., Fuchs, G.W., Kucera, J., et al. 2003, J. Chem. Phys., 118, 3549
  * McElroy et al. (2013) McElroy, D., Walsh, C., Markwick, A. J., et al. 2013, A&A, 550, A36
  * McGonagle & Irvine (1996) McGonagle, D., & Irivine, W.M. 1996, A&A, 310, 970
  * McGuire et al. (2018) McGuire, B.A., Burkhardt, M., Kalenskii, S., et al., 2018, Science, 359, 202
  * Minh & Irvine (1991) Minh, Y.C., & Irvine, W.M. 1991, Astrophysics and Space Science, 175, 165
  * Müller et al. (2005) Müller, H.S.P., Schlöder, F., Stutzki, et al. 2005, J. Mol. Struct., 742, 215
  * Ohshima & Endo (1995) Ohshima, Y., & Endo, Y. 1995, J. Mol. Spectrosc., 172, 225
  * Pardo et al. (2001) Pardo, J. R., Cernicharo, J., Serabyn, E. 2001, IEEE Trans. Antennas and Propagation, 49, 12
  * Pd et al. (2001) Pd., R., & Chandra, P. 2001, J. Chem. Phys., 114, 1589
  * Pickett et al. (1998) Pickett, H.M., Poynter, R. L., Cohen, E. A., et al. 1998, J. Quant. Spectrosc. Radiat. Transfer, 60, 883
  * Saito et al. (1984) Saito, S., Endo, Y., & Hirota, E. 1984, J. Chem. Phys., 80, 1427
  * Sobolev et al. (1962) Sobolev, G.A., Shcherbakov, A.M., & Akishin, P.A. 1962, Opt. Spectrosc., 12, 78
  * Steber et al. (2012) Steber, A.L., Harris, B.J., Neill, J.L., et al. 2012, J. Mol. Spectrosc., 280, 3
  * Tang et al. (1999) Tang, J., Sumiyoshi, Y., & Endo, Y. 1999, Chem. Phys. Lett., 315, 69
  * Tercero et al. (2021) Tercero, F., López-Pérez, J. A., Gallego, J. D., et al. 2021, A&A, 645, A37
  * Thorwirth & Lichau (2003) Thorwirth, S., & Lichau, H. 2003, A&A, 398, L11
  * Thorwirth et al. (2004) Thorwirth, S., Müller, H.S.P., Lichau, H., et al. 2004, J. Mol. Struct., 695, 263
  * Vigren et al. (2010) Vigren, E., Hamberg, M., Zhaunerchyk, V., et al. 2010, ApJ, 722, 847
  * Yang et al. (1992) Yang, D. L., Yu, T., Wang, N. S., & Lin, M. C. 1992, Chem. Phys. 160, 317
  * Zabarnick et al. (1991) Zabarnick, S., Fleming, J. W., & Lin, M. C. 1991, Chem. Phys. 150, 109

##  Appendix A Line parameters for CH2CHCCH and model fitting procedure

Line parameters were derived for CH2CHCCH by fitting a Gaussian line profile
to the observed lines. A velocity range of $\pm$20 km s-1around each feature
was considered for the fit after a polynomial baseline was removed. The
derived line parameters are given in Table LABEL:tab_line_parameters.

For the other species we show the synthetic spectrum resulting from the best
fit model to all the lines computed using the MADEX code (Cernicharo 2012). We
assumed a homogeneous rotational temperature for all rotational levels, a
source of uniform brightness with a radius of 40′′ (Fossé et al. 2001), and a
full linewidth at half power intensity of 0.6 km s-1 , which represents a good
averaged value to the linewidth of all observed lines. A fit to the observed
line profiles and intensities provide the rotational temperature and the
column density for the observed species. The final parameters derived in this
way should be very similar to those derived from a standard rotational
diagram. However, this model fit allows us to compare the modeled line
profiles with those of the observations, which is particularly interesting
when the rotational transitions exhibit hyperfine structure, as is the case
for HCCN, HC4N, and, to a lesser extent, CH3CH2CN.

Table 1: Observed line parameters for CH2CHCCH, HCCN, HC4N, and CH3CH2CN.  Transition | $\nu$ |  $\int$T${}_{A}^{*}$dv |  vLSR |  $\Delta$v |  TA∗ | Notes
---|---|---|---|---|---|---
| (MHz) |  (mk km s-1) |  (km s-1) |  (km s-1) | (mK) |
CH2CHCCH |  |  |  |  |  |
$4_{04}-3_{03}$ |  35463.2066$\pm$0.0003 |  2.1$\pm$0.4 |  5.84$\pm$0.04 |  0.79$\pm$0.09 |  2.5$\pm$0.3 |
$4_{14}-3_{13}$ |  36270.1555$\pm$0.0003 |  3.2$\pm$0.5 |  5.81$\pm$0.04 |  0.87$\pm$0.09 |  3.5$\pm$0.4 |
$4_{23}-3_{22}$ |  36298.8671$\pm$0.0003 |  |  |  | ….. | A
$4_{22}-3_{21}$ |  36327.0963$\pm$0.0003 |  1.1$\pm$0.4 |  5.81$\pm$0.15 |  1.22$\pm$0.30 |  0.8$\pm$0.3 |
$4_{13}-3_{12}$ |  37123.6151$\pm$0.0003 |  1.0$\pm$0.3 |  5.75$\pm$0.04 |  0.35$\pm$0.15 |  2.7$\pm$0.4 |
$5_{15}-4_{14}$ |  44323.5327$\pm$0.0004 |  1.8$\pm$0.3 |  5.71$\pm$0.05 |  0.59$\pm$0.11 |  2.8$\pm$0.5 |
$5_{05}-4_{04}$ |  45316.5327$\pm$0.0003 |  1.7$\pm$0.4 |  5.87$\pm$0.06 |  0.58$\pm$0.15 |  2.7$\pm$0.6 |
$5_{24}-4_{23}$ |  45369.7261$\pm$0.0003 |  |  |  |  $\leq$1.5 | B
$5_{23}-4_{22}$ |  45426.1532$\pm$0.0003 |  |  |  |  $\leq$1.5 | B
$5_{14}-4_{13}$ |  46398.7422$\pm$0.0005 |  2.0$\pm$0.5 |  5.76$\pm$0.06 |  0.66$\pm$0.15 |  2.8$\pm$0.6 |
CH3CH2CN |  |  |  |  |  |
$4_{1,4}-3_{1,3}$ 4-3 |  34823.953$\pm$0.001 |  0.9$\pm$0.3 |  5.61$\pm$0.13 |  0.71$\pm$0.15 |  1.2$\pm$0.3 |
$4_{1,4}-3_{1,3}$ 5-4 |  34824.089$\pm$0.001 |  1.1$\pm$0.3 |  5.74$\pm$0.15 |  0.80$\pm$0.15 |  1.3$\pm$0.3 |
$4_{0,4}-3_{0,3}$ 3-2 |  35722.143$\pm$0.001 |  1.2$\pm$0.4 |  5.83$\pm$0.12 |  1.15$\pm$0.30 |  1.0$\pm$0.3 |
$4_{0,4}-3_{0,3}$ 4-3 |  35722.208$\pm$0.001 |  1.8$\pm$0.4 |  5.70$\pm$0.06 |  0.66$\pm$0.12 |  2.5$\pm$0.3 |
$4_{0,4}-3_{0,3}$ 5-4 |  35722.238$\pm$0.001 |  |  |  |  | NR
$4_{1,3}-3_{1,2}$ 5-4 |  36739.711$\pm$0.001 |  1.3$\pm$0.4 |  5.56$\pm$0.08 |  0.83$\pm$0.16 |  1.5$\pm$0.3 | BBR
$5_{1,5}-4_{1,4}$ 6-5 |  43516.229$\pm$0.001 |  1.8$\pm$0.4 |  6.00$\pm$0.09 |  0.89$\pm$0.20 |  1.9$\pm$0.4 | NR
$5_{1,5}-4_{1,4}$ 5-4 |  43516.153$\pm$0.001 |  |  |  |  | NR
$5_{1,5}-4_{1,4}$ 4-3 |  43516.186$\pm$0.001 |  |  |  |  | NR
$5_{0,5}-4_{0,4}$ 6-5 |  44597.010$\pm$0.001 |  2.3$\pm$0.4 |  5.79$\pm$0.09 |  1.09$\pm$0.18 |  1.9$\pm$0.5 | NR
$5_{0,5}-4_{0,4}$ 4-3 |  44596.954$\pm$0.001 |  |  |  |  | NR
$5_{0,5}-4_{0,4}$ 5-4 |  44596.986$\pm$0.001 |  |  |  |  | NR
$5_{1,4}-4_{1,3}$ 6-5 |  45908.544$\pm$0.001 |  1.4$\pm$0.4 |  6.09$\pm$0.06 |  0.49$\pm$0.14 |  2.5$\pm$0.6 | NR
$5_{1,4}-4_{1,3}$ 5-4 |  45909.472$\pm$0.001 |  |  |  |  | NR
$5_{1,4}-4_{1,3}$ 4-3 |  45908.514$\pm$0.001 |  |  |  |  | NR
HCCN |  |  |  |  |  |
$1_{0}-0_{1}$ 2-1 5/2-5/2 |  33681.972$\pm$0.014 |  0.8$\pm$0.3 |  5.53$\pm$0.07 |  0.49$\pm$0.12 |  1.4$\pm$0.3 |
$1_{1}-0_{1}$ 1-1 3/2-3/2 |  33711.125$\pm$0.009 |  0.6$\pm$0.3 |  5.74$\pm$0.10 |  0.60$\pm$0.15 |  0.9$\pm$0.3 |
$2_{3}-1_{2}$ 3-3 5/2-5/2 |  43599.379$\pm$0.004 |  0.9$\pm$0.3 |  5.75$\pm$0.12 |  0.70$\pm$0.25 |  1.2$\pm$0.3 |
$2_{3}-1_{2}$ 2-2 3/2-3/2 |  43609.127$\pm$0.003 |  1.1$\pm$0.4 |  5.65$\pm$0.13 |  0.96$\pm$0.40 |  1.0$\pm$0.4 |
$2_{3}-1_{2}$ 2-1 3/2-1/2 |  43622.442$\pm$0.002 |  1.2$\pm$0.3 |  5.60$\pm$0.07 |  0.62$\pm$0.12 |  1.9$\pm$0.4 |
$2_{3}-1_{2}$ 2-1 5/2-3/2 |  43613.513$\pm$0.002 |  |  |  |  | NR
$2_{3}-1_{2}$ 4-3 7/2-5/2 |  43613.571$\pm$0.002 |  5.0$\pm$0.5 |  5.86$\pm$0.02 |  0.77$\pm$0.04 |  6.2$\pm$0.4 |
$2_{3}-1_{2}$ 3-2 5/2-3/2 |  43624.295$\pm$0.002 |  2.8$\pm$0.4 |  5.72$\pm$0.04 |  0.70$\pm$0.08 |  3.7$\pm$0.4 |
$2_{3}-1_{2}$ 4-3 9/2-7/2 |  43624.662$\pm$0.003 |  2.7$\pm$0.4 |  5.74$\pm$0.02 |  0.53$\pm$0.06 |  4.7$\pm$0.4 |
$2_{3}-1_{2}$ 3-2 7/2-5/2 |  43624.800$\pm$0.002 |  1.6$\pm$0.3 |  5.73$\pm$0.03 |  0.40$\pm$0.05 |  3.8$\pm$0.4 |
$2_{2}-1_{1}$ 2-1 3/2-1/2 |  43936.844$\pm$0.009 |  |  |  |  $\leq$1.2 | B
$2_{2}-1_{1}$ 1-1 1/2-1/2 |  43939.743$\pm$0.007 |  |  |  |  $\leq$1.2 | B
$2_{2}-1_{1}$ 3-2 5/2-3/2 |  43940.214$\pm$0.006 |  2.2$\pm$0.5 |  5.65$\pm$0.09 |  1.05$\pm$0.25 |  1.9$\pm$0.4 |
$2_{2}-1_{1}$ 2-2 3/2-3/2 |  43943.474$\pm$0.007 |  |  |  |  $\leq$1.2 | B
$2_{2}-1_{1}$ 1-0 3/2-1/2 |  43945.275$\pm$0.006 |  1.2$\pm$0.4 |  5.45$\pm$0.13 |  0.96$\pm$0.30 |  1.1$\pm$0.4 |
$2_{2}-1_{1}$ 2-1 5/2-3/2 |  43945.594$\pm$0.003 |  1.0$\pm$0.4 |  5.80$\pm$0.11 |  0.72$\pm$0.20 |  1.3$\pm$0.4 |
$2_{2}-1_{1}$ 3-2 7/2-5/2 |  43948.624$\pm$0.004 |  2.6$\pm$0.4 |  5.80$\pm$0.03 |  0.66$\pm$0.09 |  3.7$\pm$0.4 |
HC4N |  |  |  |  |  |
$7_{7}-6_{6}$ 6- 5 11/2- 9/2 |  32233.047$\pm$0.010 |  0.5$\pm$0.3 |  5.78$\pm$0.20 |  0.62$\pm$0.15 |  0.8$\pm$0.3 |
$7_{7}-6_{6}$ 7- 6 13/2-11/2 |  32233.149$\pm$0.010 |  1.5$\pm$0.4 |  5.75$\pm$0.10 |  0.98$\pm$0.05 |  1.4$\pm$0.3 |
$7_{7}-6_{6}$ 8- 7 15/2-13/2 |  32233.290$\pm$0.003 |  1.0$\pm$0.3 |  5.80$\pm$0.14 |  0.95$\pm$0.09 |  1.0$\pm$0.3 |
$7_{7}-6_{6}$ 6- 5 13/2-11/2 |  32233.472$\pm$0.010 |  1.6$\pm$0.5 |  5.89$\pm$0.08 |  1.04$\pm$0.10 |  1.4$\pm$0.3 |
$7_{7}-6_{6}$ 7- 6 15/2-13/2 |  32233.545$\pm$0.003 |  |  |  |  | NR
$7_{7}-6_{6}$ 8- 7 17/2-15/2 |  32233.694$\pm$0.003 |  0.9$\pm$0.3 |  5.83$\pm$0.09 |  0.74$\pm$0.18 |  1.2$\pm$0.3 |
$7_{8}-6_{7}$ 7- 6 15/2-13/2 |  32365.728$\pm$0.010 |  0.9$\pm$0.4 |  5.93$\pm$0.11 |  0.84$\pm$0.21 |  0.9$\pm$0.3 |
$7_{8}-6_{7}$ 8- 7 17/2-15/2 |  32365.938$\pm$0.003 |  |  |  |  | NR,BN
$7_{8}-6_{7}$ 7- 6 13/2-11/2 |  32365.972$\pm$0.003 |  2.7$\pm$0.5 |  5.83$\pm$0.04 |  0.87$\pm$0.07 |  2.9$\pm$0.3 |
$7_{8}-6_{7}$ 9- 8 19/2-17/2 |  32365.994$\pm$0.003 |  |  |  |  | NR,BN
$7_{8}-6_{7}$ 8- 7 15/2-13/2 |  32366.230$\pm$0.010 |  1.9$\pm$0.4 |  5.51$\pm$0.06 |  0.95$\pm$0.13 |  1.9$\pm$0.3 |
$7_{8}-6_{7}$ 9- 8 17/2-15/2 |  32366.230$\pm$0.010 |  |  |  |  | NR,BN
$8_{7}-7_{6}$ 7- 6 13/2-11/2 |  36665.590$\pm$0.004 |  1.1$\pm$0.3 |  5.98$\pm$0.15 |  1.00$\pm$0.30 |  1.1$\pm$0.3 |
$8_{7}-7_{6}$ 8- 7 15/2-13/2 |  36665.694$\pm$0.004 |  0.8$\pm$0.3 |  5.74$\pm$0.10 |  0.57$\pm$0.17 |  1.3$\pm$0.3 |
$8_{7}-7_{6}$ 6- 5 11/2- 9/2 |  36665.831$\pm$0.004 |  0.7$\pm$0.3 |  5.76$\pm$0.06 |  0.32$\pm$0.30 |  1.9$\pm$0.3 |
$8_{7}-7_{6}$ 7- 6 15/2-13/2 |  36666.427$\pm$0.004 |  2.2$\pm$0.4 |  5.64$\pm$0.06 |  1.07$\pm$0.14 |  2.0$\pm$0.3 |
$8_{7}-7_{6}$ 8- 7 17/2-15/2 |  36666.497$\pm$0.004 |  |  |  |  | NR
$8_{7}-7_{6}$ 6- 5 13/2-11/2 |  36666.641$\pm$0.004 |  0.8$\pm$0.4 |  5.42$\pm$0.09 |  0.68$\pm$0.18 |  1.1$\pm$0.3 |
$8_{8}-7_{7}$ 7- 6 13/2-11/2 |  36837.871$\pm$0.005 |  2.5$\pm$0.6 |  5.65$\pm$0.09 |  1.48$\pm$0.25 |  1.6$\pm$0.3 |
$8_{8}-7_{7}$ 8- 7 15/2-13/2 |  36837.939$\pm$0.005 |  |  |  |  | NR
$8_{8}-7_{7}$ 9- 8 17/2-15/2 |  36838.043$\pm$0.005 |  |  |  |  | NR
$8_{8}-7_{7}$ 7- 6 15/2-13/2 |  36838.172$\pm$0.005 |  1.3$\pm$0.4 |  5.66$\pm$0.09 |  0.90$\pm$0.22 |  1.4$\pm$0.3 |
$8_{8}-7_{7}$ 8- 7 17/2-15/2 |  36838.240$\pm$0.005 |  1.3$\pm$0.4 |  6.15$\pm$0.05 |  0.71$\pm$0.11 |  1.7$\pm$0.3 |
$8_{8}-7_{7}$ 9- 8 19/2-17/2 |  36838.350$\pm$0.005 |  |  |  |  | NR
$8_{9}-7_{8}$ 8- 7 17/2-15/2 |  36942.973$\pm$0.004 |  |  |  |  $\leq$0.9 | B
$8_{9}-7_{8}$ 8- 7 15/2-13/2 |  36943.144$\pm$0.004 |  3.2$\pm$0.5 |  5.66$\pm$0.03 |  0.82$\pm$0.07 |  3.7$\pm$0.3 |
$8_{9}-7_{8}$ 9- 8 19/2-17/2 |  36943.144$\pm$0.004 |  |  |  |  | NR
$8_{9}-7_{8}$ 10- 9 21/2-19/2 |  36943.179$\pm$0.004 |  |  |  |  | NR
$8_{9}-7_{8}$ 9- 8 17/2-15/2 |  36943.330$\pm$0.004 |  1.5$\pm$0.4 |  5.67$\pm$0.04 |  0.60$\pm$0.08 |  2.4$\pm$0.3 |
$8_{9}-7_{8}$ 10- 9 19/2-17/2 |  36943.352$\pm$0.004 |  |  |  |  | NR
$9_{8}-8_{7}$ 8- 7 15/2-13/2 |  41309.798$\pm$0.007 |  1.3$\pm$0.3 |  5.94$\pm$0.15 |  1.19$\pm$0.12 |  1.0$\pm$0.3 |
$9_{8}-8_{7}$ 9- 8 17/2-15/2 |  41309.886$\pm$0.007 |  |  |  |  | NR
$9_{8}-8_{7}$ 7- 6 13/2-11/2 |  41309.971$\pm$0.007 |  2.4$\pm$0.5 |  5.67$\pm$0.10 |  0.33$\pm$0.04 |  0.7$\pm$0.3 |
$9_{8}-8_{7}$ 8- 7 17/2-15/2 |  41310.387$\pm$0.007 |  |  |  |  | NR
$9_{8}-8_{7}$ 9- 8 19/2-17/2 |  41310.452$\pm$0.007 |  1.3$\pm$0.4 |  5.85$\pm$0.06 |  0.64$\pm$0.09 |  1.9$\pm$0.3 |
$9_{8}-8_{7}$ 7- 6 15/2-13/2 |  41310.540$\pm$0.007 |  |  |  |  | NR
$9_{9}-8_{8}$ 8- 7 15/2-13/2 |  41442.624$\pm$0.007 |  |  |  |  | NR
$9_{9}-8_{8}$ 9- 8 17/2-15/2 |  41442.703$\pm$0.007 |  |  |  |  | NR
$9_{9}-8_{8}$ 10- 9 19/2-17/2 |  41442.760$\pm$0.007 |  |  |  |  | NR
$9_{9}-8_{8}$ 8- 7 17/2-15/2 |  41442.839$\pm$0.007 |  2.4$\pm$0.6 |  5.54$\pm$0.30 |  2.44$\pm$0.50 |  0.9$\pm$0.3 |
$9_{9}-8_{8}$ 9- 8 19/2-17/2 |  41442.917$\pm$0.007 |  |  |  |  | NR
$9_{9}-8_{8}$ 10- 9 21/2-19/2 |  41443.002$\pm$0.007 |  |  |  |  | NR
$9_{10}-8_{9}$ 9- 8 19/2-17/2 |  41527.729$\pm$0.007 |  1.0$\pm$0.3 |  5.68$\pm$0.06 |  0.51$\pm$0.12 |  1.8$\pm$0.4 |
$9_{10}-8_{9}$ 9- 8 17/2-15/2 |  41527.847$\pm$0.007 |  |  |  |  | NR
$9_{10}-8_{9}$ 10- 9 21/2-19/2 |  41527.865$\pm$0.007 |  |  |  |  | NR
$9_{10}-8_{9}$ 11-10 23/2-21/2 |  41527.887$\pm$0.007 |  2.7$\pm$0.6 |  5.90$\pm$0.04 |  0.70$\pm$0.11 |  3.6$\pm$0.4 |
$9_{10}-8_{9}$ 10- 9 19/2-17/2 |  41527.994$\pm$0.007 |  0.6$\pm$0.3 |  6.86$\pm$0.12 |  0.53$\pm$0.29 |  1.0$\pm$0.4 |
$9_{10}-8_{9}$ 11-10 21/2-19/2 |  41528.006$\pm$0.007 |  |  |  |  | NR
$10_{10}-9_{9}$ 9- 8 17/2-15/2 |  46047.335$\pm$0.010 |  |  |  |  | NR
$10_{10}-9_{9}$ 9- 9 19/2-17/2 |  46047.440$\pm$0.010 |  |  |  |  | NR
$10_{10}-9_{9}$ 11-10 21/2-19/2 |  46047.445$\pm$0.010 |  2.5$\pm$0.4 |  5.86$\pm$0.08 |  0.84$\pm$0.17 |  2.8$\pm$0.6 |
$10_{10}-9_{9}$ 10- 8 19/2-17/2 |  46047.469$\pm$0.010 |  |  |  |  | NR
$10_{10}-9_{9}$ 10- 9 21/2-19/2 |  46047.573$\pm$0.010 |  |  |  |  | NR
$10_{10}-9_{9}$ 11-10 23/2-21/2 |  46047.641$\pm$0.010 |  2.0$\pm$0.4 |  6.01$\pm$0.06 |  0.57$\pm$0.13 |  3.2$\pm$0.6 |
$10_{11}-9_{10}$ 10- 9 21/2-19/2 |  46117.484$\pm$0.010 |  |  |  |  | NR
$10_{11}-9_{10}$ 10- 9 19/2-17/2 |  46117.567$\pm$0.010 |  |  |  |  | NR
$10_{11}-9_{10}$ 11-10 23/2-21/2 |  46117.594$\pm$0.010 |  1.6$\pm$0.5 |  5.74$\pm$0.06 |  0.51$\pm$0.12 |  3.3$\pm$0.6 |
$10_{11}-9_{10}$ 12-11 25/2-23/2 |  46117.608$\pm$0.010 |  |  |  |  | NR
$10_{11}-9_{10}$ 11-10 21/2-19/2 |  46117.685$\pm$0.010 |  1.3$\pm$0.5 |  5.70$\pm$0.11 |  0.62$\pm$0.17 |  2.0$\pm$0.6 |
$10_{11}-9_{10}$ 12-11 23/2-21/2 |  46117.692$\pm$0.010 |  |  |  |  | NR
CH2CHCN |  |  |  |  |  |
$4_{1,4}-3_{1,3}$ 4-4 |  37017.816$\pm$0.001 |  1.7$\pm$0.3 |  5.87$\pm$0.05 |  0.68$\pm$0.11 |  2.4$\pm$0.4 |
$4_{1,4}-3_{1,3}$ 4-3 |  37018.829$\pm$0.001 |  26.8$\pm$0.8 |  5.77$\pm$0.01 |  0.69$\pm$0.02 |  36.3$\pm$0.4 |
$4_{1,4}-3_{1,3}$ 3-2 |  37018.926$\pm$0.001 |  22.8$\pm$0.7 |  5.73$\pm$0.02 |  0.68$\pm$0.05 |  31.4$\pm$0.4 |
$4_{1,4}-3_{1,3}$ 5-4 |  37018.981$\pm$0.001 |  29.3$\pm$0.8 |  5.74$\pm$0.01 |  0.64$\pm$0.02 |  42.9$\pm$0.4 |
$4_{1,4}-3_{1,3}$ 3-3 |  37020.293$\pm$0.001 |  0.9$\pm$0.3 |  5.72$\pm$0.15 |  0.51$\pm$0.34 |  1.6$\pm$0.4 |
$4_{0,4}-3_{0,3}$ 4-4 |  37903.587$\pm$0.001 |  3.0$\pm$0.4 |  5.81$\pm$0.03 |  0.66$\pm$0.08 |  4.3$\pm$0.4 |
$4_{0,4}-3_{0,3}$ 3-2 |  37904.770$\pm$0.001 |  31.7$\pm$0.8 |  5.87$\pm$0.01 |  0.69$\pm$0.02 |  42.8$\pm$0.4 |
$4_{0,4}-3_{0,3}$ 4-3 |  37904.850$\pm$0.001 |  87.2$\pm$1.5 |  5.75$\pm$0.02 |  0.72$\pm$0.01 |  113.8$\pm$0.4 |
$4_{0,4}-3_{0,3}$ 5-4 |  37904.880$\pm$0.001 |  |  |  |  | NR
$4_{0,4}-3_{0,3}$ 3-3 |  37906.474$\pm$0.001 |  1.5$\pm$0.4 |  5.72$\pm$0.03 |  0.49$\pm$0.12 |  2.9$\pm$0.4 |
$4_{2,3}-3_{2,2}$ 4-3 |  37939.248$\pm$0.001 |  4.2$\pm$0.5 |  5.90$\pm$0.01 |  0.62$\pm$0.03 |  6.3$\pm$0.4 |
$4_{2,3}-3_{2,2}$ 5-4 |  37939.763$\pm$0.001 |  6.2$\pm$0.5 |  5.78$\pm$0.01 |  0.74$\pm$0.04 |  7.8$\pm$0.4 |
$4_{2,3}-3_{2,2}$ 3-2 |  37939.896$\pm$0.001 |  2.6$\pm$0.4 |  5.79$\pm$0.02 |  0.59$\pm$0.05 |  4.1$\pm$0.4 |
$4_{2,2}-3_{2,1}$ 4-3 |  37973.989$\pm$0.001 |  4.7$\pm$0.4 |  5.83$\pm$0.02 |  0.74$\pm$0.04 |  6.0$\pm$0.4 |
$4_{2,2}-3_{2,1}$ 5-4 |  37974.504$\pm$0.001 |  5.5$\pm$0.5 |  5.80$\pm$0.01 |  0.68$\pm$0.03 |  7.6$\pm$0.4 |
$4_{2,2}-3_{2,1}$ 3-2 |  37974.636$\pm$0.001 |  3.1$\pm$0.4 |  5.82$\pm$0.02 |  0.65$\pm$0.05 |  4.4$\pm$0.4 |
$4_{1,3}-3_{1,2}$ 4-4 |  38846.762$\pm$0.001 |  1.5$\pm$0.4 |  5.88$\pm$0.06 |  0.89$\pm$0.13 |  1.6$\pm$0.4 |
$4_{1,3}-3_{1,2}$ 4-3 |  38847.641$\pm$0.001 |  27.4$\pm$0.8 |  5.75$\pm$0.00 |  0.66$\pm$0.01 |  38.9$\pm$0.4 |
$4_{1,3}-3_{1,2}$ 3-2 |  38847.747$\pm$0.001 |  55.4$\pm$1.1 |  5.88$\pm$0.00 |  0.79$\pm$0.01 |  66.3$\pm$0.4 |
$4_{1,3}-3_{1,2}$ 5-4 |  38847.790$\pm$0.001 |  |  |  |  | NR
$4_{1,3}-3_{1,2}$ 3-3 |  38848.933$\pm$0.001 |  2.5$\pm$0.4 |  5.81$\pm$0.02 |  0.63$\pm$0.06 |  3.4$\pm$0.6 |
$5_{1,5}-4_{1,4}$ 5-4 |  46266.887$\pm$0.001 |  |  |  |  | NR
$5_{1,5}-4_{1,4}$ 4-3 |  46266.926$\pm$0.001 |  70.2$\pm$1.2 |  5.76$\pm$0.01 |  0.87$\pm$0.01 |  76.0$\pm$0.6 |
$5_{1,5}-4_{1,4}$ 6-5 |  46266.971$\pm$0.001 |  |  |  |  | NR
$5_{0,5}-4_{0,4}$ 5-5 |  47353.356$\pm$0.001 |  1.9$\pm$0.4 |  5.80$\pm$0.05 |  0.56$\pm$0.11 |  3.2$\pm$0.6 |
$5_{0,5}-4_{0,4}$ 4-3 |  47354.605$\pm$0.001 |  |  |  |  | NR
$5_{0,5}-4_{0,4}$ 5-4 |  47354.648$\pm$0.001 |  104.0$\pm$1.5 |  5.80$\pm$0.01 |  0.74$\pm$0.01 |  132.9$\pm$0.6 |
$5_{0,5}-4_{0,4}$ 6-5 |  47354.670$\pm$0.001 |  |  |  |  | NR
$5_{0,5}-4_{0,4}$ 4-4 |  47356.230$\pm$0.001 |  2.5$\pm$0.4 |  6.00$\pm$0.06 |  0.75$\pm$0.09 |  3.1$\pm$0.6 |
$5_{2,4}-4_{2,3}$ 5-4 |  47419.606$\pm$0.001 |  5.5$\pm$0.6 |  5.77$\pm$0.02 |  0.69$\pm$0.05 |  7.6$\pm$0.6 |
$5_{2,4}-4_{2,3}$ 6-5 |  47419.876$\pm$0.001 |  8.6$\pm$0.8 |  5.75$\pm$0.02 |  0.70$\pm$0.05 |  11.5$\pm$0.6 |
$5_{2,4}-4_{2,3}$ 4-3 |  47419.904$\pm$0.001 |  |  |  |  | NR
$5_{1,4}-4_{1,3}$ 5-4 |  48552.516$\pm$0.001 |  |  |  |  | NR
$5_{1,4}-4_{1,3}$ 4-3 |  48552.559$\pm$0.001 |  73.8$\pm$1.9 |  5.77$\pm$0.01 |  0.86$\pm$0.02 |  80.3$\pm$0.9 |
$5_{1,4}-4_{1,3}$ 6-5 |  48552.598$\pm$0.001 |  |  |  |  | NR
Table 1: continued. 333
$A$$A$footnotetext: Blended with a strong feature.
$B$$B$footnotetext: Three sigma upper limit.
$NR$$NR$footnotetext: Hyperfine structure line blended with other components
of the same rotational transition. The line has been included in the fit to
the previous or next entry in the table.

##  Appendix B Ethyl acetylene and ethyl cyanide

We searched for the lines of ethyl acetylene, CH3CH2CCH, a molecule for which
accurate laboratory data are available up to 317.7 GHz (Demaison et al.,
1983; Landsberg & Suenram  1983; Bestmann & Dreizler  1985; Steber et al.
2012) and which has moderate dipole moments of $\mu_{a}$=0.763 D and
$\mu_{b}$=0.17 D (Landsberg & Suenram  1983). The barrier to internal rotation
is very high (Bestmann & Dreizler  1985), and therefore the ground state does
not show significant splitting between the $A$ and $E$ species. Of the ten
lines expected for this molecule in the Q-band, five are detected at a
3$\sigma$ level, two are blended with other weak features slightly shifted in
frequency, and three are too weak. Using stacking techniques (see below) and
removing the blended lines, which could introduce a significant bias in the
final spectrum, we detected a signal at 5$\sigma$ at the correct velocity, as
shown in Fig. 2. However, we have no explanation for the lack of emission at
the frequency of the $5_{05}-4_{04}$ transition other than that the data are
too noisy at its frequency (see Fig. 6). It is expected to be the strongest
feature for the parameters we used for the synthetic spectrum (Tr=5 K,
N(CH3CH2CCH)=9 1011 cm-2).

For CH3CH2CCH, all the expected strongest lines in the Q-band are shown in
Fig. 6, and Fig. 2 shows the resulting stacked profile. The stacking procedure
we used is rather simple: A velocity range of $\pm$20 km s-1 was selected for
each line and the noise, $\sigma$, outside 5.83$\pm$0.5 km s-1 was computed
(with known and unknown lines in each individual spectrum blanked). The data
were normalized to the expected intensity of each transition computed under
local thermodynamic equilibrium for a rotational temperature of 5 K, the same
as the value derived for CH2CHCCH. Finally, all the data were multiplied by
the expected intensity of the strongest transition in the sample. The lines
are optically thin, and hence the intensity of all lines scale in the same way
with the assumed column density. Each individual spectrum was weighted as
1/$\sigma_{N}^{2}$, where $\sigma_{N}$ now contains the normalization
intensity factor. All rotational transitions falling in the frequency ranges
where our data have the highest sensitivity were detected (transitions
$4_{14}-3_{13},4_{04}-3_{03},4_{13}-3_{12},5_{15}-4_{14}$, and
$5_{24}-5_{23}$). Two of the observed transitions are heavily blended
($4_{22}-3_{21}$ and $5_{14}-4_{13}$) and were excluded from the stacked
spectrum. Two $K_{a}$=2 transitions, which are expected to be weak, were not
detected ($4_{23}-3_{22}$ and $5_{23}-4_{22}$) but were included in the data
stacking with the corresponding weights, as explained above. The data for the
strongest rotational transition, the $5_{05}-4_{04}$, have a sensitivity of
0.6 mK. The expected intensity is 1.3 mK. This rotational transition was
included in the stacked spectrum, although it is clearly not detected at the
noise level of the data. Figure 2 shows the resulting spectrum from this
procedure. A feature, at exactly the velocity of the cloud, appears at a
5$\sigma$ level ($\sigma$=0.16 mK). Although a positive detection of ethyl
acetylene is highly possible, we consider it as tentative. Longer integration
times are needed to confirm the detection of this species.

In our survey we observed a large number of unidentified lines at the level of
1-5 mK (see Figs. 1, 3, 4, and 6). Moreover, the isotopologues of abundant
species contribute with several hundred lines. Consequently, stacking
techniques that could compete in sensitivity with our survey may provide false
positive or negative results for low abundant molecular species. An example is
the case of CH3CH2CN, which was detected in our work (see Sect. 3.3 and Fig.
7), while only upper limits were obtained by Lee et al.  (2021). The observed
lines of CH3CH2CN, together with the best model fit to the observed emission,
are shown in Fig. 7.

Figure 6: Observed lines of CH3CH2CCH in the Q-band toward TMC-1. The abscissa
corresponds to the rest frequency assuming a local standard of rest velocity
of 5.83 km s-1. The ordinate is the antenna temperature, corrected for
atmospheric and telescope losses, in mK. The red line shows the synthetic
spectrum obtained using the parameters derived from a rotational diagram of
the observed lines (Tr=5 K and N(CH3CH2CCH)=9.0$\times$1011 cm-2). The
rotational quantum numbers are provided in the upper right corners of each
panel.  Figure 7: Observed lines of CH3CH2CN in the 31-50 GHz frequency range
toward TMC-1. The abscissa corresponds to the rest frequency assuming a local
standard of rest velocity of 5.83 km s-1. The ordinate is the antenna
temperature, corrected for atmospheric and telescope losses, in mK. The violet
line shows the synthetic spectrum computed for Tr=4.5 K and
N(CH3CH2CN)=1.1$\times$1011 cm-2.

##  Appendix C Vinyl cyanide, CH2CHCN

Vinyl cyanide produces a very rich spectrum in the 31-50 GHz range, with most
of its lines exhibiting the hyperfine structure due to the nitrogen nucleus.
All the observed lines are shown in Fig. 8. The model fitting procedure
provides a rotational temperature of 4.5$\pm$0.5 K and a column density of
(6.5$\pm$0.5)$\times$1012 cm-2. Its abundance relative to vinyl acetylene and
ethyl cyanide is discussed in Sects. 3.1, 3.3, and 3.4.

Figure 8: Observed lines of CH2CHCN in the 31-50 GHz frequency range toward
TMC-1. The abscissa corresponds to the rest frequency assuming a local
standard of rest velocity of 5.83 km s-1. The ordinate is the antenna
temperature, corrected for atmospheric and telescope losses, in mK. The violet
line shows the synthetic spectrum obtained using the parameters derived from a
rotational diagram of the observed lines (Tr=4.5$\pm$0.3 K and
N(CH2CHCN)=(6.5$\pm$0.5)$\times$1012 cm-2). Numbers in the upper left corners
of the panels indicate the multiplicative factor applied to the synthetic
spectrum to match the data. The rotational quantum numbers are provided in the
upper right corners of each panel. The hyperfine structure of each rotational
transition has been taken into account in the calculation of the synthetic
spectra. Line parameters are given in Table LABEL:tab_line_parameters.


Université Paris Cité, CNRS, IRIF, F-75013, Paris,
Francecarton@irif.frhttps://orcid.org/0000-0002-2728-6534 Université Paris
Cité, CNRS, IRIF, F-75013, Paris, France and Direction générale de l’armement
- Ingénierie des projets, Paris, France<EMAIL_ADDRESS>Olivier Carton and
Gaëtan Douéneau-Tabot[100]Theory of computation Formal languages and automata
theory Automata extensions Transducers This work was supported by the DeLTA
ANR project (ANR-16-CE40-0007). Full Versionhttps://arxiv.org/abs/2204.11235

###### Acknowledgements.

0 MFCS 2022

# Continuous rational functions
are deterministic regular

Olivier Carton  Gaëtan Douéneau-Tabot

###### Abstract

A word-to-word function is rational if it can be realized by a non-
deterministic one-way transducer. Over finite words, it is a classical result
that any rational function is regular, i.e. it can be computed by a
deterministic two-way transducer, or equivalently, by a deterministic
streaming string transducer (a one-way automaton which manipulates string
registers).

This result no longer holds for infinite words, since a non-deterministic one-
way transducer can guess, and check along its run, properties such as
infinitely many occurrences of some pattern, which is impossible for a
deterministic machine. In this paper, we identify the class of rational
functions over infinite words which are also computable by a deterministic
two-way transducer. It coincides with the class of rational functions which
are continuous, and this property can thus be decided. This solves an open
question raised in a previous paper of Dave et al.

###### keywords:

infinite words, rational functions, determinization, continuity, streaming
string transducers, two-way transducers

###### category:

##  1 Introduction

Transducers are finite-state machines obtained by adding outputs to finite
automata. They are very useful in a lot of areas like coding, computer
arithmetic, language processing or program analysis, and more generally in
data stream processing. In this paper, we study transducers which compute
partial functions. They are either deterministic, or non-deterministic but
unambiguous (they have at most one accepting run on a given input).

Over finite words, a deterministic two-way transducer
($2$-$\operatorname{\textsf{dT}}$) consists of a deterministic two-way
automaton which can produce outputs. Such machines realize the class of
_regular functions_ , which is often considered as one of the functional
counterparts of regular languages. It coincides with the class of functions
definable by monadic second-order transductions [engelfriet2001mso], or
copyless deterministic streaming string transducers
($\operatorname{\textsf{dSST}}$), which is a model of one-way automata
manipulating string registers [alur2010expressiveness]. On the other hand, the
model of non-deterministic one-way transducers
($1$-$\operatorname{\textsf{nT}}$) describe the well-known class of _rational
functions_. It is well known that any rational function is regular, but the
converse does not hold.

#### Infinite words.

The class of _regular functions over infinite words_ was defined in
[alur2012regular] using monadic second-order transductions. It coincides with
the class of functions realized by $2$-$\operatorname{\textsf{dT}}$ with
$\omega$-regular lookahead, or by copyless $\operatorname{\textsf{dSST}}$ with
some Müller conditions. However, the use of $\omega$-regular lookaheads (or
Müller conditions for $\operatorname{\textsf{dSST}}$) is necessary to capture
the expressive power of monadic second-order logic on infinite words, in order
to check properties such as infinitely many occurrences of some pattern.
Similarly, the model of $1$-$\operatorname{\textsf{nT}}$ with Büchi acceptance
conditions defines the subclass of _rational functions over infinite words_.

Even if regular and rational functions give very natural frameworks for
specification (due to their connections with logic), not all these functions
can effectively be computed by a deterministic machine without lookaheads. It
turns out that the regular functions which can be computed by a deterministic
Turing machine (doing an infinite computation on its infinite input) are
exactly those which are continuous for the Cantor topology
[dave2020synthesis]. Furthermore continuity can be decided, which has been
known for rational functions since [prieur2001decide].

The authors of [dave2020synthesis] conjecture that any continuous rational (or
even regular) function can in fact be computed by a
$2$-$\operatorname{\textsf{dT}}$ (without lookahead), instead of a Turing
machine. A partial answer was obtained in [filiot2021synthesizing], whose
results imply that $2$-$\operatorname{\textsf{dT}}$ can be built for a
subclass of rational functions defined by $1$-$\operatorname{\textsf{nT}}$
where some forms of non-determinism are prohibited. Their proof is based on
game-theoretic techniques.

#### Contributions.

This paper shows that any continuous rational function over infinite words can
be extended to a function which is computable by a
$2$-$\operatorname{\textsf{dT}}$ (without lookaheads). Since the converse also
holds, this result completely characterizes rational functions which can be
computed by $2$-$\operatorname{\textsf{dT}}$s, up to an extension of the
domain. Furthermore, this property is decidable and our construction of a
$2$-$\operatorname{\textsf{dT}}$ is effective.

This result is tight, in the sense that two-way moves cannot be avoided.
Indeed, one-way deterministic transducers (describing the class of _sequential
functions_) cannot realize all continuous rational functions, even when only
considering total functions (contrary to what happens for the subclass of
rational functions studied in [filiot2021synthesizing]).

In order to establish this theorem, we first study the expressive power of
$2$-$\operatorname{\textsf{dT}}$ over infinite words. We introduce the class
of _deterministic regular functions_ as the class of functions computed by
$2$-$\operatorname{\textsf{dT}}$ (as opposed to the regular functions, which
are not entirely deterministic since they use lookaheads to guess the future).
Following the aforementioned equivalences between two-way and register
transducers, we prove that deterministic rational functions are exactly the
functions which are realized by copyless $\operatorname{\textsf{dSST}}$
(without Müller conditions). Hence our problem is reduced to showing that any
continuous rational function can be realized by a copyless
$\operatorname{\textsf{dSST}}$. Building a copyless
$\operatorname{\textsf{dSST}}$ is also relevant for practical applications,
since it corresponds to a streaming algorithm over infinite strings.

$\begin{subarray}{c}\textsf{REGULAR}\end{subarray}$

$\begin{subarray}{c}\textsf{SEQUENTIAL}\end{subarray}$

$\begin{subarray}{c}\textsf{DETERMINISTIC}\\\ \textsf{REGULAR}\end{subarray}$

$\begin{subarray}{c}\textsf{RATIONAL}\end{subarray}$

$\begin{subarray}{c}\textsf{RATIONAL}\\\ \textsf{\& CONTINUOUS}\end{subarray}$

$\begin{subarray}{c}\text{{Normalization in base}}\leavevmode\nobreak\
2\text{{.}}\\\ x\in\\{0,1\\}^{\omega}\leavevmode\nobreak\
\mapsto\leavevmode\nobreak\ x\text{{ if }}|x|_{0}=\infty\\\
u01^{\omega}\leavevmode\nobreak\ \mapsto\leavevmode\nobreak\
u10^{\omega}\text{{ for
}}u\in\\{0,1\\}^{*}\end{subarray}$$\begin{subarray}{c}0^{n_{1}}{a_{1}}0^{n_{2}}{a_{2}}\cdots\leavevmode\nobreak\
\mapsto\leavevmode\nobreak\ ({a_{1}})^{n_{1}}({a_{2}})^{n_{2}}\cdots\\\
\text{{with }}n_{i}\in\mathbb{N}\leavevmode\nobreak\ \text{ and
}\leavevmode\nobreak\
a_{i}\in\\{1,2\\}\end{subarray}$$\begin{subarray}{c}\text{{Division by
}}3\text{{ in base }}2\end{subarray}$ Figure 1:  Classes of partial functions
over infinite words studied in this paper

Then we introduce various new concepts in order to transform a
$1$-$\operatorname{\textsf{nT}}$ computing a continuous function into a
$\operatorname{\textsf{dSST}}$. This determinization procedure is rather
involved. The main difficulty is that even if the
$1$-$\operatorname{\textsf{nT}}$ is unambiguous, it might not check its
guesses after reading only a finite number of letters. In other words, a given
input can label several infinite runs, even if only one of them is accepting.
However, a deterministic machine can never determine which run is the
accepting one, since it requires to check whether a property occurs infinitely
often. This intuition motivates our key definition of _compatible sets_ among
the states of a $1$-$\operatorname{\textsf{nT}}$. Such sets are the sets of
states which have a “common infinite future”. The restriction of
$1$-$\operatorname{\textsf{nT}}$ considered in [filiot2021synthesizing] leads
to compatible sets which are always singletons (hence their condition defines
a natural special case). We show that when the function computed by the
$1$-$\operatorname{\textsf{nT}}$ is continuous, the outputs produced along
finite runs which end in a compatible set enjoy several combinatorial
properties.

We finally describe how to build a $\operatorname{\textsf{dSST}}$ which
realizes the continuous function given by a $1$-$\operatorname{\textsf{nT}}$.
Its construction is is rather complex, and it crucially relies on the
aforementioned properties of compatible sets. These sets are manipulated by
the $\operatorname{\textsf{dSST}}$ in an original tree-like fashion. To the
knowledge of the authors, this construction of this
$\operatorname{\textsf{dSST}}$ is completely new (in particular, it is not
based on the constructions of [dave2020synthesis] nor of
[filiot2021synthesizing]).

#### Outline.

We recall in Section 2 the definitions of rational functions and one-way
transducers. In Section 3, we present the new class of deterministic regular
functions and give the various transducer models which capture it. Our main
result which relates continuous rational and deterministic regular functions
is given in Section 4. The proof is sketched in sections 4 and 5.

##  2 Rational functions

Letters $A,B$ denote alphabets, i.e. finite sets of letters. The set $A^{*}$
(resp. $A^{+}$, $A^{\omega}$) denotes the set of finite words (resp. non-empty
finite words, infinite words) over the alphabet $A$. If $u\in A^{*}\cup
A^{\omega}$, we let $|u|\in\mathbb{N}\cup\\{\infty\\}$ be its length. For
$a\in A$, $|u|_{a}$ denotes the number of $a$ in $u$. For $1\leqslant
i\leqslant|u|$, $u[i]\in A$ is the $i$-th letter of $u$. If $1\leqslant
i\leqslant j\leqslant|u|$, $u[i{:}j]$ stands for $u[i]u[i{+}1]\cdots$ until
$j$. We write $u[i{:}]$ for $u[i{:}|u|]$. If $j>|u|$ we let $u[i{:}j]\coloneqq
u[i{:}|u|]$. If $j<i$ we let $u[i{:}j]\coloneqq\varepsilon$ . We write
$u\sqsubseteq v$ (resp. $u\sqsubset v$) when $u$ is a (resp. strict) prefix of
$v$. Given two words $u,v$, we let $u\land v$ be their longest common prefix.
We say that $u,v$ are _mutual prefixes_ if $u\sqsubseteq v$ or $v\sqsubseteq
u$. In this case we let $u\lor v$ be the longest of them. A function $f$
between two sets $S,T$ is denoted by $f:S\rightarrow T$. If $f$ is a _partial
function_ (i.e. possibly with non-total domain), it is denoted
$f:S\rightharpoonup T$. Its domain is denoted
$\operatorname{\textsf{Dom}}(f)$.

######  Definition 2.1.

A _one-way non-deterministic transducer_ _( $1$-$\operatorname{\textsf{nT}}$)_
$\mathcal{T}=(A,B,Q,I,F,\Delta,\lambda)$ is:

  * •

a finite input (respectively output) alphabet $A$ (respectively $B$);

  * •

a finite set of states $Q$ with $I\subseteq Q$ initial and $F\subseteq Q$
final;

  * •

a transition relation $\Delta\subseteq Q\times A\times Q$;

  * •

an output function $\lambda:\Delta\rightarrow B^{*}$ (defined for each
transition).

We write $q\mathchoice{\xrightarrow{a|\alpha}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle
a|\alpha$}}}}{\xrightarrow{a|\alpha}}{\xrightarrow{a|\alpha}}q^{\prime}$
whenever $(q,a,q^{\prime})\in\Delta$ and $\lambda(q,a,q^{\prime})=\alpha$. A
_run_ labelled by some $x\in A^{*}\cup A^{\omega}$ is a sequence of
consecutive transitions $\rho\coloneqq
q_{0}\mathchoice{\xrightarrow{x[1]|\alpha_{1}}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle
x[1]|\alpha_{1}$}}}}{\xrightarrow{x[1]|\alpha_{1}}}{\xrightarrow{x[1]|\alpha_{1}}}q_{1}\mathchoice{\xrightarrow{x[2]|\alpha_{2}}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle
x[2]|\alpha_{2}$}}}}{\xrightarrow{x[2]|\alpha_{2}}}{\xrightarrow{x[2]|\alpha_{2}}}q_{2}\cdots$.
The _output_ of $\rho$ is the word $\alpha_{1}\alpha_{2}\cdots\in A^{*}\cup
A^{\omega}$. If $x\in A^{\omega}$, we also write
$q_{0}\mathchoice{\xrightarrow{x|\alpha_{1}\alpha_{2}\cdots}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle
x|\alpha_{1}\alpha_{2}\cdots$}}}}{\xrightarrow{x|\alpha_{1}\alpha_{2}\cdots}}{\xrightarrow{x|\alpha_{1}\alpha_{2}\cdots}}\infty$
to denote an infinite run starting in $q_{0}$. The run $\rho$ is _initial_ if
$q_{0}\in I$, _final_ if $x\in A^{\omega}$ and $q_{i}\in F$ infinitely often
(Büchi condition), and _accepting_ if both initial and final. $\mathcal{T}$
computes the _relation_ $\\{(x,y):y\in B^{\omega}\text{ is output along an
accepting run on }x\\}$. It is _functional_ if this relation is a (partial)
function. In this case, $\mathcal{T}$ can be transformed in an equivalent
_unambiguous_ $1$-$\operatorname{\textsf{nT}}$ (a transducer which has at most
one accepting run on each $x\in A^{\omega}$) [choffrut1999uniformization,
Corollary 3]. A function $f:A^{\omega}\rightharpoonup B^{\omega}$ is said to
be _rational_ if it can be computed by a (unambiguous)
$1$-$\operatorname{\textsf{nT}}$.

######  Example 2.2.

In Figure 2, we describe $1$-$\operatorname{\textsf{nT}}$s which compute the
following functions:

  * •

$\operatorname{\textsf{normalize}}:\\{0,1\\}^{\omega}\rightharpoonup\\{0,1\\}^{\omega}$
mapping $x\mapsto x$ if $|x|_{0}=\infty$ and $u01^{\omega}\mapsto
u10^{\omega}$ if $u\in\\{0,1\\}^{*}$;

  * •

$\operatorname{\textsf{replace}}:\\{0,1,2\\}^{\omega}\rightharpoonup\\{1,2\\}^{\omega}$
with
$\operatorname{\textsf{Dom}}(\operatorname{\textsf{replace}})=\\{x:|x|_{1}=\infty\text{{
or }}|x|_{2}=\infty\\}$ and mapping
$0^{n_{1}}{a_{1}}0^{n_{2}}{a_{2}}\cdots\mapsto{a_{1}}^{n_{1}+1}{a_{2}}^{n_{2}+1}\cdots$
if $a_{i}\in\\{1,2\\}$, $n_{i}\in\mathbb{N}$;

  * •

$\operatorname{\textsf{double}}:\\{0,1,2\\}^{\omega}\rightarrow\\{0,1,2\\}^{\omega}$
mapping $0^{n_{1}}{a_{1}}0^{n_{2}}{a_{2}}\cdots\mapsto
0^{a_{1}n_{1}}{a_{1}}0^{a_{2}n_{2}}a_{2}\cdots$ and $0^{n_{1}}{a_{1}}\cdots
0^{n_{m}}{a_{m}}0^{\omega}\mapsto 0^{a_{1}n_{1}}{a_{1}}\cdots
0^{a_{m}n_{m}}{a_{m}}0^{\omega}$ (if finitely many $1$ or $2$).

$\begin{subarray}{c}q_{0}\end{subarray}$$\begin{subarray}{c}q_{1}\end{subarray}$$\begin{subarray}{c}q_{2}\end{subarray}$$\begin{subarray}{c}0|1\end{subarray}$$\begin{subarray}{c}0|0\end{subarray}$$\begin{subarray}{c}1|1\end{subarray}$$\begin{subarray}{c}1|0\end{subarray}$$\begin{subarray}{c}1|1\end{subarray}$$\begin{subarray}{c}0|0\end{subarray}$
(a) $1$-$\operatorname{\textsf{nT}}$ computing
$\operatorname{\textsf{normalize}}$

$\begin{subarray}{c}q_{0}\end{subarray}$$\begin{subarray}{c}q_{1}\end{subarray}$$\begin{subarray}{c}q_{2}\end{subarray}$$\begin{subarray}{c}0|1\end{subarray}$$\begin{subarray}{c}1|1\end{subarray}$$\begin{subarray}{c}0|2\end{subarray}$$\begin{subarray}{c}2|2\end{subarray}$$\begin{subarray}{c}0|1\end{subarray}$$\begin{subarray}{c}0|2\end{subarray}$$\begin{subarray}{c}1|1\\\
2|2\end{subarray}$ (b) $1$-$\operatorname{\textsf{nT}}$ computing
$\operatorname{\textsf{replace}}$

$\begin{subarray}{c}q_{0}\end{subarray}$$\begin{subarray}{c}q_{1}\end{subarray}$$\begin{subarray}{c}q_{2}\end{subarray}$$\begin{subarray}{c}0|0\end{subarray}$$\begin{subarray}{c}1|1\end{subarray}$$\begin{subarray}{c}0|00\end{subarray}$$\begin{subarray}{c}2|2\end{subarray}$$\begin{subarray}{c}0|0\end{subarray}$$\begin{subarray}{c}0|00\end{subarray}$$\begin{subarray}{c}1|1\\\
2|2\end{subarray}$ (c) $1$-$\operatorname{\textsf{nT}}$ computing
$\operatorname{\textsf{double}}$

Figure 2:  Unambiguous, clean and trim $1$-$\operatorname{\textsf{nT}}$s
computing the functions of Example 2.2.

######  Remark 2.3.

The functions mentioned in Example 2.2 are not _sequential_ , i.e. they cannot
be computed by deterministic one-way transducers (i.e. deterministic
$1$-$\operatorname{\textsf{nT}}$s).

A $1$-$\operatorname{\textsf{nT}}$ is _trim_ if any state is both accessible
and co-accessible, or equivalently if it occurs in some accepting run. It is
_clean_ if the production along any accepting run is infinite.

######  Lemma 2.4.

A trim $1$-$\operatorname{\textsf{nT}}$ is clean if and only if for all $q\in
F$, the existence of a cycle
$q\mathchoice{\xrightarrow{u|\alpha}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle
u|\alpha$}}}}{\xrightarrow{u|\alpha}}{\xrightarrow{u|\alpha}}q$ for $u\in
A^{+}$ implies $\alpha\neq\varepsilon$. Given an unambiguous
$1$-$\operatorname{\textsf{nT}}$, one can build an equivalent unambiguous,
clean and trim $1$-$\operatorname{\textsf{nT}}$.

##  3 Deterministic regular functions

We now introduce the new class of _deterministic regular_ functions, which are
computed by _deterministic two-way transducers_. Contrary to
$1$-$\operatorname{\textsf{nT}}$s, such machines cannot test $\omega$-regular
properties of their input. Hence they describe continuous (and computable)
functions.

######  Definition 3.1.

A _deterministic two-way transducer_ _( $2$-$\operatorname{\textsf{dT}}$)_
$\mathcal{T}=(A,B,Q,q_{0},\delta,\lambda)$ is:

  * •

an input alphabet $A$ and an output alphabet $B$;

  * •

a finite set of states $Q$ with an initial state $q_{0}\in Q$;

  * •

a transition function $\delta:Q\times(A\uplus\\{{\vdash}\\})\rightharpoonup
Q\times\\{\triangleleft,\triangleright\\}$;

  * •

an output function $\lambda:Q\times(A\uplus\\{{\vdash}\\})\rightharpoonup
B^{*}$ with same domain as $\delta$.

If the input is $x\in A^{\omega}$, then $\mathcal{T}$ is given as input the
word ${\vdash}x$. The symbol ${\vdash}$ is used to mark the beginning of the
input. We denote by $x[0]\coloneqq{}\vdash$. A _configuration_ over
${\vdash}x$ is a tuple $(q,i)$ where $q\in Q$ is the current state and
$i\geqslant 0$ is the current position of the reading head. The _transition
relation_ $\rightarrow$ is defined as follows. Given a configuration $(q,i)$,
let $(q^{\prime},\star):=\delta(q,w[i])$. Then
$(q,i)\rightarrow(q^{\prime},i^{\prime})$ whenever either
$\star=\triangleleft$ and $i^{\prime}=i-1$ (move left), or
$\star=\triangleright$ and $i^{\prime}=i+1$ (move right). A _run_ is a (finite
or infinite) sequence of configurations
$(q_{1},i_{1})\rightarrow(q_{2},i_{2})\rightarrow\cdots$. An _accepting_ run
is an infinite run which starts in $(q_{0},0)$ and such that
$i_{n}\rightarrow\infty$ when $n\rightarrow\infty$ (otherwise the transducer
repeats the same loop).

The partial function $f:A^{\omega}\rightharpoonup B^{\omega}$ computed by
$\mathcal{T}$ is defined as follows. Let $x\in A^{\omega}$ be such that there
exists a (unique) accepting run
$(q^{x}_{0},i^{x}_{0})\rightarrow(q^{x}_{1},i^{x}_{1})\rightarrow\cdots$
labelled by $x$. Let
$y\coloneqq\prod_{j=1}^{\infty}\lambda(q^{x}_{j},w[i^{x}_{j}])\in B^{*}\cup
B^{\omega}$ be the concatenation of the outputs produced along this run. If
$y\in B^{\omega}$, we define $f(x)\coloneqq y$. Otherwise $f(x)$ is undefined.

######  Example 3.2.

The function $\operatorname{\textsf{replace}}$ from Example 2.2 can be
computed by $2$-$\operatorname{\textsf{dT}}$. For each $i\geqslant 1$, this
$2$-$\operatorname{\textsf{dT}}$ crosses the block $0^{n_{i}}$ to determines
${a_{i}}$, and then crosses the block once more and outputs
${a_{i}}^{n_{i}+1}$. The function $\operatorname{\textsf{double}}$ can be
computed using similar ideas. However, an important difference is that the
$2$-$\operatorname{\textsf{dT}}$ must output the block $0^{n_{i}}$ when it
crosses it for the first time, in order to ensure that the production over
$0^{\omega}$ is $0^{\omega}$.

There exists deterministic regular functions which are not rational, for
instance the function which reverses (mirror image) a prefix of its input.

Over finite words, it is known that two-way transducers are equivalent to
copyless streaming string transducers [alur2010expressiveness]. Over infinite
words, a similar equivalence holds between two-way transducers with lookahead
and copyless streaming string transducers with Müller output conditions
[alur2012regular]. These models define the class of _regular functions_ over
infinite words. However, lookaheads enable two-way transducers to check
$\omega$-regular properties of their input (and thus non-computable
behaviors). Hence our deterministic regular functions form a strict subclass
of these regular functions over infinite words.

We now introduce a model of streaming string transducer to describe
deterministic regular functions, in the spirit of the aforementioned results.
In our setting, it consists of a one-way deterministic automaton with a finite
set $\mathfrak{R}$ of registers that store words from $B^{*}$. We use a
distinguished register $\operatorname{\mathfrak{out}}$ to store the output
produced when reading an infinite word. The registers are modified using
_substitutions_ , i.e. mappings
$\mathfrak{R}\rightarrow(B\uplus\mathfrak{R})^{*}$. We denote by
$\mathcal{S}_{\mathfrak{R}}^{B}$ the set of these substitutions. They can be
extended morphically from $(B\uplus\mathfrak{R})^{*}$ to
$(B\uplus\mathfrak{R})^{*}$ by preserving the elements of $B$. They can be
composed (see Example 3.3).

######  Example 3.3.

Let $\mathfrak{R}=\\{\mathfrak{r},\mathfrak{s}\\}$ and $B=\\{b\\}$. Consider
$\sigma_{1}:=\mathfrak{r}\mapsto b,\mathfrak{s}\mapsto
b\mathfrak{r}\mathfrak{s}b$ and
$s_{2}:=\mathfrak{r}\mapsto\mathfrak{r}b,\mathfrak{s}\mapsto\mathfrak{r}\mathfrak{s}$,
then $\sigma_{1}\circ\sigma_{2}(\mathfrak{r})=s_{1}(\mathfrak{r}b)=bb$ and
$\sigma_{1}\circ\sigma_{2}(\mathfrak{s})=\sigma_{1}(\mathfrak{r}\mathfrak{s})=bb\mathfrak{r}\mathfrak{s}b$.

######  Definition 3.4.

A _deterministic streaming string transducer_ _(
$\operatorname{\textsf{dSST}}$)_ is:

  * •

a finite input (resp. output) alphabet $A$ (resp. $B$);

  * •

a finite set of states $Q$ with $q_{0}\in Q$ initial;

  * •

a transition function $\delta:Q\times A\rightharpoonup Q$;

  * •

a finite set of registers $\mathfrak{R}$ with a distinguished output register
$\operatorname{\mathfrak{out}}\in\mathfrak{R}$;

  * •

an update function $\lambda:Q\times
A\rightharpoonup\mathcal{S}_{\mathfrak{R}}^{B}$ such that for all
$(q,a)\in\operatorname{\textsf{Dom}}(\lambda)=\operatorname{\textsf{Dom}}(\delta)$:

    * –

$\lambda(q,a)(\operatorname{\mathfrak{out}})=\operatorname{\mathfrak{out}}\cdots$;

    * –

there is no other occurence of $\operatorname{\mathfrak{out}}$ in
$\\{\lambda(q,a)(\mathfrak{r}):\mathfrak{r}\in\mathfrak{R}\\}$.

We denote it
$\mathcal{T}=(A,B,Q,q_{0},\delta,\mathfrak{R},\operatorname{\mathfrak{out}},\lambda)$.

This machine defines a function $f:A^{*}\rightharpoonup B^{*}$ as follows. For
$i\geqslant 0$ let $q^{x}_{i}:=\delta(q_{0},x[1{:}i])$ (when defined). For
$i\geqslant 1$, we let $\lambda^{x}_{i}\coloneqq\lambda(q^{x}_{i-1},x[i])$
(when defined) and $\lambda^{x}_{0}(\mathfrak{r})=\varepsilon$ for all
$\mathfrak{r}\in\mathfrak{R}$. For $i\geqslant 0$, define the substitution
${\color[rgb]{0.1,0.1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,1}\bm{\llbracket}\cdot\bm{\rrbracket}}^{x}_{i}\coloneqq\lambda^{x}_{0}\circ\cdots\circ\lambda^{x}_{i}$.
By construction we get
${\color[rgb]{0.1,0.1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,1}\bm{\llbracket}\operatorname{\mathfrak{out}}\bm{\rrbracket}}^{x}_{i}\sqsubseteq{\color[rgb]{0.1,0.1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,1}\bm{\llbracket}\operatorname{\mathfrak{out}}\bm{\rrbracket}}^{x}_{i+1}$
(when defined). If
${\color[rgb]{0.1,0.1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,1}\bm{\llbracket}\operatorname{\mathfrak{out}}\bm{\rrbracket}}^{x}_{i}$
is defined for all $i\geqslant 0$ and
$|{\color[rgb]{0.1,0.1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,1}\bm{\llbracket}\operatorname{\mathfrak{out}}\bm{\rrbracket}}^{x}_{i}|\rightarrow+\infty$,
we let
$f(x)\coloneqq\bigvee_{i}{\color[rgb]{0.1,0.1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,1}\bm{\llbracket}\operatorname{\mathfrak{out}}\bm{\rrbracket}}^{x}_{i}$
(it denotes the unique infinite word $y$ such that
${\color[rgb]{0.1,0.1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,1}\bm{\llbracket}\operatorname{\mathfrak{out}}\bm{\rrbracket}}^{x}_{i}\sqsubseteq
y$ for all $i\geqslant 0$). Otherwise $f(x)$ is undefined.

We say that a substitution $\sigma\in\mathcal{S}_{\mathfrak{R}}^{B}$ is
_copyless_ (resp. $K$-bounded) if for all $\mathfrak{r}\in\mathfrak{R}$,
$\mathfrak{r}$ occurs at most once in
$\\{\sigma(\mathfrak{s}):\mathfrak{s}\in\mathfrak{R}\\}$ (resp. for all
$\mathfrak{r},\mathfrak{s}\in\mathfrak{R}$, $\mathfrak{r}$ occurs at most $K$
times in $\sigma(\mathfrak{s})$).

######  Definition 3.5 (Copy restrictions).

We say that a $\operatorname{\textsf{dSST}}$
$\mathcal{T}=(A,B,Q,q_{0},\delta,\mathfrak{R},\operatorname{\mathfrak{out}},\lambda)$
is _copyless_ (resp. _$K$ -bounded_) if for all $x\in A^{\omega}$ and
$i\leqslant j$ such that $\lambda^{x}_{i}\circ\cdots\circ\lambda^{x}_{j}$ is
defined, this substitution is copyless (resp. $K$-bounded).

######  Example 3.6.

The function $\operatorname{\textsf{replace}}$ from Example 2.2 can be
computed by a copyless $\operatorname{\textsf{dSST}}$. For all $i\geqslant 1$,
it crosses the block $0^{n_{i}}$ and computes $1^{n_{i}}$ and $2^{n_{i}}$ in
two registers. Once it sees ${a_{i}}$ it adds in
$\operatorname{\mathfrak{out}}$ the register storing ${a_{i}}^{n_{i}}$. The
function $\operatorname{\textsf{double}}$ can be computed using similar ideas.
However, an important difference is that the $\operatorname{\textsf{dSST}}$
must directly output the block $0^{n_{i}}$ while crossing it, in order to
ensure that the production over $0^{\omega}$ is $0^{\omega}$.

The proof of the next result is quite involved, but it is largely inspired by
the techniques used for regular functions over finite or infinite words (see
e.g. [dartois2016aperiodic, doueneau2020register]).

######  Theorem 3.7.

The following machines compute the same class of functions
$A^{\omega}\rightharpoonup B^{\omega}$:

  1. 1.

deterministic two-way transducers _( $2$-$\operatorname{\textsf{dT}}$)_;

  2. 2.

$K$-bounded deterministic streaming string transducers _(_ $K$-bounded
$\operatorname{\textsf{dSST}}$_)_ ;

  3. 3.

copyless deterministic streaming string transducers _(_ copyless
$\operatorname{\textsf{dSST}}$_)_.

Furthermore, all the conversions are effective.

######  Remark 3.8.

Even if this result is a variant of existing results over finite or infinite
words, it requires a proof on its own. Indeed, the authors are not aware of a
direct proof which would enable to deduce it from the existing similar
results.

Let us now describe the domains of deterministic regular functions. We say
that a language is _Büchi deterministic_ if it is accepted by a deterministic
Büchi automaton [perrin2004].

######  Proposition 3.9.

If $f$ is deterministic regular, then $\operatorname{\textsf{Dom}}(f)$ is
Büchi deterministic.

We finally give a closure property of deterministic regular functions under
pre-composition.

######  Definition 3.10.

A _restricted_ $1$-$\operatorname{\textsf{nT}}$ is a
$1$-$\operatorname{\textsf{nT}}$ whose states all are final.

The semantics of a restricted $1$-$\operatorname{\textsf{nT}}$
$\mathcal{N}=(A,B,Q,I,\Delta,\lambda)$ is defined so that it _always_ computes
a function $f:A^{\omega}\rightharpoonup B^{\omega}$. The domain
$\operatorname{\textsf{Dom}}(f)$ is the set of $x\in A^{\omega}$ such that
$\mathcal{N}$ has a unique accepting run labelled by $x$, and such that the
output along this unique run is infinite. In this case, we let $f(x)$ be the
output of along this run. Intuitively, such a transducer expresses the ability
to make non-deterministic guesses, as long as these guesses can be verified
after reading a finite number of letters (i.e. there are no two possible
infinite runs).

######  Theorem 3.11.

Given a restricted $1$-$\operatorname{\textsf{nT}}$ computing a function
$f:A^{\omega}\rightharpoonup B^{\omega}$ and a deterministic regular function
$g:B^{\omega}\rightharpoonup C^{\omega}$, $g\circ f$ is (effectively)
deterministic regular.

##  4 Continuous rational functions are deterministic regular

We now state the main result of this paper, which shows that a rational
function can be extended to a deterministic regular function. Using an
extension of the original function is necessary since not all $\omega$-regular
languages are Büchi deterministic (see Proposition 3.9). Note that Theorem 4.2
is in fact an equivalence, in the sense that a rational function which can be
extended to a deterministic regular function is obviously continuous.

We recall that a function $f:A^{\omega}\rightharpoonup B^{\omega}$ is
_continuous_ if and only if for all $x\in\operatorname{\textsf{Dom}}(f)$ and
$n\geqslant 0$, there exists $p\geqslant 0$ such that $\forall
y\in\operatorname{\textsf{Dom}}(f)$, $|x\wedge y|\geqslant
p\Rightarrow|f(x)\wedge f(y)|\geqslant n$.

######  Example 4.1.

The functions $\operatorname{\textsf{replace}}$ and
$\operatorname{\textsf{double}}$ are continuous, but
$\operatorname{\textsf{normalize}}$ is not.

######  Theorem 4.2.

Given a continuous rational function $f:A^{\omega}\rightharpoonup B^{\omega}$,
one can build a deterministic regular function $f^{\prime}$ which extends $f$
(i.e. for all $x\in\operatorname{\textsf{Dom}}(f)$, $f(x)=f^{\prime}(x)$).

To prove Theorem 4.2, it is enough by theorems 3.7 and 3.11 to show that
$f^{\prime}$ can be computed as a composition of a restricted
$1$-$\operatorname{\textsf{nT}}$ and a $K$-bounded
$\operatorname{\textsf{dSST}}$ (see Subsection 4.2, the construction will in
fact give a $1$-bounded transducer).

###  4.1 Properties of continuous rational functions

We first describe some structural properties of
$1$-$\operatorname{\textsf{nT}}$ computing continuous functions. In this
subsection, we let $\mathcal{T}=(A,B,Q,I,F,\Delta,\lambda)$ be an unambiguous,
clean and trim $1$-$\operatorname{\textsf{nT}}$ computing a continuous
function $f:A^{\omega}\rightharpoonup B^{\omega}$. It is well known that
$\mathcal{T}$ verifies Lemma 4.3. This property is in fact equivalent to the
continuity of $f$ (see e.g. [prieur2001decide] or [dave2020synthesis]).

######  Lemma 4.3.

For all $q_{1},q_{2}\in I$, $q^{\prime}_{1}\in F$, $q^{\prime}_{2}\in Q$,
$u\in A^{*}$, $u^{\prime}\in A^{+}$,
$\alpha_{1},\alpha^{\prime}_{1},\alpha_{2},\alpha^{\prime}_{2}\in B^{*}$ such
that $q_{i}\mathchoice{\xrightarrow{u|\alpha_{i}}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle
u|\alpha_{i}$}}}}{\xrightarrow{u|\alpha_{i}}}{\xrightarrow{u|\alpha_{i}}}q^{\prime}_{i}\mathchoice{\xrightarrow{u^{\prime}|\alpha^{\prime}_{i}}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle
u^{\prime}|\alpha^{\prime}_{i}$}}}}{\xrightarrow{u^{\prime}|\alpha^{\prime}_{i}}}{\xrightarrow{u^{\prime}|\alpha^{\prime}_{i}}}q^{\prime}_{i}$
for $i\in\\{1,2\\}$ we have (note that $\alpha^{\prime}_{1}\neq\varepsilon$
since $\mathcal{T}$ is clean):

  * •

if $\alpha_{2}^{\prime}\neq\varepsilon$, then
$\alpha_{1}{\alpha^{\prime}_{1}}^{\omega}=\alpha_{2}{\alpha^{\prime}_{2}}^{\omega}$;

  * •

if $\alpha^{\prime}_{2}=\varepsilon$, $x\in A^{\omega}$, $\beta\in B^{\omega}$
and
$q^{\prime}_{2}\mathchoice{\xrightarrow{x|\beta}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle
x|\beta$}}}}{\xrightarrow{x|\beta}}{\xrightarrow{x|\beta}}\infty$ is final,
then $\alpha_{1}{\alpha^{\prime}_{1}}^{\omega}=\alpha_{2}\beta$.

Empty cycles
$q\mathchoice{\xrightarrow{u|\varepsilon}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle
u|\varepsilon$}}}}{\xrightarrow{u|\varepsilon}}{\xrightarrow{u|\varepsilon}}q$
for $q\not\in F$ cannot be avoided in a $1$-$\operatorname{\textsf{nT}}$.
However, we shall see in Lemma 4.4 that such cycles can be avoided if the
function is continuous. Formally, we say that the clean $\mathcal{T}$ is
_productive_ if the hypotheses of Lemma 4.3 imply
$\alpha^{\prime}_{2}\neq\varepsilon$.

######  Lemma 4.4.

Given $\mathcal{T}$, one can build an equivalent unambiguous, trim and
productive $1$-$\operatorname{\textsf{nT}}$.

#### Compatible sets and steps.

We now introduce the key notion of a _compatible set_ which is a set of states
having a “common future” and such that one of the future runs is accepting.

######  Definition 4.5 (Compatible set).

We say that a set of states $C\subseteq Q$ is _compatible_ whenever there
exists $x\in A^{\omega}$ and infinite runs $\rho_{q}$ for each $q\in C$
labelled by $x$ such that:

  * •

$\forall q\in C$, $\rho_{q}$ starts from $q$;

  * •

$\exists q\in C$ such that $\rho_{q}$ is final.

Let $\operatorname{\textsf{Comp}}$ be the set of compatible sets. If
$S\subseteq Q$, let $\operatorname{\textsf{Comp}}(S)$ be the set
$2^{S}\cap\operatorname{\textsf{Comp}}$.

######  Definition 4.6 (Pre-step).

We say that $C,u,D$ is a _pre-step_ if $C,D\in\operatorname{\textsf{Comp}}$,
$u\in A^{*}$ and for all $q\in D$, there exists a unique state ${\rm
Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ E}{C,D}{u}(q)\in C$ such
that ${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\
E}{C,D}{u}(q)\mathchoice{\xrightarrow{u}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle u$}}}}{\xrightarrow{u}}{\xrightarrow{u}}q$.

Note that for all $D^{\prime}\in\operatorname{\textsf{Comp}}(D)$, we have
${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\
E}{C,D}{u}(D^{\prime})\in\operatorname{\textsf{Comp}}$.

######  Definition 4.7 (Step).

We say that a pre-step $C,u,D$ is a _step_ if ${\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\ E}{C,D}{u}$ is surjective.

Given $q\in D$, let $\operatorname{\textsf{prod}}_{C,D}^{u}(q)$ be the output
$\alpha\in B^{*}$ produced along the run ${\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\
E}{C,D}{u}(q)\mathchoice{\xrightarrow{u|\alpha}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle
u|\alpha$}}}}{\xrightarrow{u|\alpha}}{\xrightarrow{u|\alpha}}q$. We say that a
(pre-)step is _initial_ whenever $C\subseteq I$. We first claim that the
productions along the runs of an initial step are mutual prefixes. Lemma 4.3
is crucial here.

######  Lemma 4.8.

Let $J,u,C$ be an initial step. Then
$\operatorname{\textsf{prod}}_{J,C}^{u}(q)$ for $q\in C$ are mutual prefixes.

######  Example 4.9.

In Figure 2(b), if a step is initial, it is of the form
$\\{q_{0}\\},u,\\{q_{i}\\}$ for some $i\in\\{0,1,2\\}$. In Figure 2(c),
$\\{q_{0}\\},0^{n},\\{q_{1},q_{2}\\}$ is an initial step for all $n\geqslant
0$.

######  Definition 4.10 (Common, advance).

Let $J,u,C$ be an initial step. We define:

  * •

the _common_ $\operatorname{\textsf{com}}_{J,C}^{u}\in B^{*}$ as the longest
common prefix $\bigwedge_{q\in C}\operatorname{\textsf{prod}}_{J,C}^{u}(q)$;

  * •

for all $q\in C$, its _advance_ $\operatorname{\textsf{adv}}_{J,C}^{u}(q)\in
B^{*}$ as
$(\operatorname{\textsf{com}}_{J,C}^{u})^{-1}\operatorname{\textsf{prod}}_{J,C}^{u}(q)$;

  * •

the _maximal advance_ $\operatorname{\textsf{max-adv}}_{J,C}^{u}$ as the
longest advance, i.e. $\bigvee_{q\in
C}\operatorname{\textsf{adv}}_{J,C}^{u}(q)$.

Definition 4.10 makes sense by Lemma 4.8, and furthermore
$\operatorname{\textsf{prod}}_{J,C}^{u}(q)=\operatorname{\textsf{com}}_{J,C}^{u}\operatorname{\textsf{adv}}_{J,C}^{u}(q)$
for all $q\in C$. Now let $M\coloneqq\max(10,\max_{q,q^{\prime}\in Q,a\in
A}|\lambda(q,a,q^{\prime})|)$ and $\Omega\coloneqq M|Q|^{|Q|}$. We say that a
compatible set $C$ is _separable_ if there exists an initial step which ends
in $C$, and such that the lengths of the productions along two of its runs
differ of at least $\Omega$.

######  Definition 4.11 (Separable set).

Let $C\in\operatorname{\textsf{Comp}}$, we say that $C$ is _separable_ if
there exists an initial step $J,u,C$ and $p,q\in C$ such that
$\left||\operatorname{\textsf{adv}}_{J,C}^{u}(p)|-|\operatorname{\textsf{adv}}_{J,C}^{u}(q)|\right|>\Omega$.

######  Remark 4.12.

In other words, it means that $|\operatorname{\textsf{max-
adv}}_{J,C}^{u}|>\Omega$.

It is easy to see (by a pumping argument) that one can decide if a set is
separable. We now show that the productions along the initial steps which end
in a separable set are forced to “iterate” some value $\theta$ if the step is
pursued. The following lemma is the key ingredient for showing that a rational
function is deterministic regular (see Section 4).

######  Corollary 1.

######  Lemma 4.13 (Looping futures).

Let $C\in\operatorname{\textsf{Comp}}$ be separable and $J,u,C$ be an initial
step (not necessarily the one which makes $C$ separable). There exists
$\tau,\theta\in B^{*}$ with $|\tau|\leqslant\Omega!$, and $|\theta|=\Omega!$
which can be uniquely determined from $C$ and
$\operatorname{\textsf{adv}}_{J,C}^{u}(q)$ for $q\in C$, such that:

  * •

$\operatorname{\textsf{max-adv}}_{J,C}^{u}\sqsubseteq\tau\theta^{\omega}$;

  * •

for all step $C,v,D$ and $q\in D$,
$\operatorname{\textsf{prod}}_{C,D}^{v}(q)\sqsubseteq(\operatorname{\textsf{adv}}_{J,C}^{u}(p))^{-1}\tau\theta^{\omega}$
with $p\coloneqq{\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\
E}{C,D}{v}(q)$.

######  Remark 4.14.

Since
$\operatorname{\textsf{adv}}_{J,C}^{u}(p)\sqsubseteq\operatorname{\textsf{max-
adv}}_{J,C}^{u}\sqsubseteq\tau\theta^{\omega}$, the second item makes sense.

######  Example 4.15.

In Figure 2(c), the compatible set $C\coloneqq\\{q_{1},q_{2}\\}$ is separable.
For all step $C,v,D$ we have $D=C$ thus $v=0^{n}$,
$\operatorname{\textsf{prod}}_{C,D}^{0^{n}}(q_{1})=0^{n}$ and
$\operatorname{\textsf{prod}}_{C,D}^{0^{n}}(q_{2})=0^{2n}$.

###  4.2 Composition of a restricted $1$-$\operatorname{\textsf{nT}}$ and a
$1$-bounded $\operatorname{\textsf{dSST}}$

In the rest of this paper, we let $\mathcal{T}=(A,B,Q,I,F,\Delta,\lambda)$ be
an unambiguous, productive and trim $1$-$\operatorname{\textsf{nT}}$ computing
a continuous $f:A^{\omega}\rightharpoonup B^{\omega}$. Our goal is to rewrite
$f$ as the composition of a restricted $1$-$\operatorname{\textsf{nT}}$ and a
$1$-bounded $\operatorname{\textsf{dSST}}$. We first build the restricted
$1$-$\operatorname{\textsf{nT}}$, which computes an over-approximation of the
accepting run of $\mathcal{T}$ in terms of compatible sets.

######  Lemma 4.16.

One can build a restricted $1$-$\operatorname{\textsf{nT}}$ $\mathcal{N}$
computing $g:A^{\omega}\rightharpoonup(\operatorname{\textsf{Comp}}\uplus
A)^{\omega}$ such that
$\operatorname{\textsf{Dom}}(f)\subseteq\operatorname{\textsf{Dom}}(g)$, and
for all $x\in\operatorname{\textsf{Dom}}(g)$,
$g(x)=C_{0}x[1]C_{1}x[2]C_{2}\cdots$ where:

  * •

$C_{0}\subseteq I$ and for all $i\geqslant 0$, $C_{i},x[i{+}1],C_{i+1}$ is a
pre-step;

  * •

if $x\in\operatorname{\textsf{Dom}}(f)$ then $\forall i\geqslant 0$,
$q^{x}_{i}\in C_{i}$, where
$q^{x}_{0}\mathchoice{\xrightarrow{x[1]}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle
x[1]$}}}}{\xrightarrow{x[1]}}{\xrightarrow{x[1]}}q^{x}_{1}\mathchoice{\xrightarrow{x[2]}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle
x[2]$}}}}{\xrightarrow{x[2]}}{\xrightarrow{x[2]}}\cdots$ is the accepting run
of $\mathcal{T}$.

Given $x\in\operatorname{\textsf{Dom}}(f)$, we denote by
$C^{x}_{0},C^{x}_{1},\dots$ the sequence of compatible sets produced by
$\mathcal{N}$ in Lemma 4.16. We now describe a $1$-bounded
$\operatorname{\textsf{dSST}}$ $\mathcal{S}$ which, when given as input
$g(x)\in(\operatorname{\textsf{Comp}}\uplus A)^{\omega}$ for
$x\in\operatorname{\textsf{Dom}}(f)$, outputs $f(x)$ (this description is
continued in Section 5).

#### Tree of compatibles.

Given $C\in\operatorname{\textsf{Comp}}$, we define
$\operatorname{\textsf{tree}}(C)$ as a finite set of words over
$\operatorname{\textsf{Comp}}(C)$, which describes the decreasing chains for
$\subset$. It can be identified with the set of all root-to-node paths of a
tree labelled by elements of $\operatorname{\textsf{Comp}}(C)$, as shown in
Example 4.18.

######  Definition 4.17 (Tree of compatibles).

Given $C\in\operatorname{\textsf{Comp}}$, we denote by
$\operatorname{\textsf{tree}}(C)$ the set of words $\pi=C_{1}\cdots
C_{n}\in(\operatorname{\textsf{Comp}}(C))^{+}$ such that $C_{1}=C$ and for all
$1\leqslant i\leqslant n{-}1$, $C_{i}\supset C_{i+1}$.

######  Example 4.18.

If $C=\\{1,2,3\\}$ and
$\operatorname{\textsf{Comp}}(C)=\\{\\{1,2,3\\},\\{1,2\\},\\{2,3\\},\\{1\\},\\{2\\},\\{3\\}\\}$,
then we have
$\operatorname{\textsf{tree}}(C)=\\{\\{1,2,3\\}\\{1,2\\}\\{1\\},\\{1,2,3\\}\\{1,2\\}\\{2\\},\\{1,2,3\\}\\{2,3\\}\\{2\\},\\{1,2,3\\}\\{2,3\\}\\{3\\},$
$\\{1,2,3\\}\\{1\\},\\{1,2,3\\}\\{2\\},\\{1,2,3\\}\\{3\\}\\}$. Its view as a
tree is depicted in Figure 3.

$\\{1,2,3\\}$$\\{1,2\\}$$\\{1\\}$$\\{2\\}$$\\{2,3\\}$$\\{2\\}$$\\{3\\}$$\\{1\\}$$\\{2\\}$$\\{3\\}$
Figure 3:  The tree of compatibles obtained from Example 4.18.

#### Information stored.

The states of the $\operatorname{\textsf{dSST}}$ $\mathcal{S}$ are partitioned
in two categories: the sets of the _separable mode_ and the sets of of the
_non-separable mode_. A configuration of the $\operatorname{\textsf{dSST}}$
$\mathcal{S}$ will always keep track of the following information:

  * •

the content of a register $\operatorname{\mathfrak{out}}$;

  * •

two sets
$\operatorname{\textsf{J}},\operatorname{\textsf{C}}\in\operatorname{\textsf{Comp}}$
and a function ${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\
E}{}{}:\operatorname{\textsf{C}}\rightarrow\operatorname{\textsf{J}}$ (stored
in the state);

Furthermore, when $\mathcal{S}$ is in a state of the separable mode, it will
additionally store:

  * •

a value $\theta\in B^{*}$ with $|\theta|=\Omega!$ (stored in the state);

  * •

for all $\pi=C_{1}\cdots
C_{n}\in\operatorname{\textsf{tree}}(\operatorname{\textsf{C}})$ (note that
$C_{1}=\operatorname{\textsf{C}}$ by definition of
$\operatorname{\textsf{tree}}(\operatorname{\textsf{C}})$):

    * –

  * •

a function $\operatorname{\textsf{last}}:\operatorname{\textsf{C}}\rightarrow
B^{*}$ such that $|\operatorname{\textsf{last}}(q)|<\Omega!$ forall
$q\in\operatorname{\textsf{C}}$ (stored in the state).

If a configuration of $\mathcal{S}$ is clearly fixed, we abuse notations and
denote by $\operatorname{{\mathfrak{out}}}_{\pi}$ (resp.
$\operatorname{\textsf{nb}}_{\pi}$, $\operatorname{\textsf{lag}}$, etc.) the
value contained in register $\operatorname{\mathfrak{out}}_{\pi}$ (resp.
stored in the state) in this configuration. In a given configuration of
$\mathcal{S}$, we say that
$\pi\in\operatorname{\textsf{tree}}(\operatorname{\textsf{C}})$ is _close_ if
for all
$\pi\sqsubset\pi^{\prime}\in\operatorname{\textsf{tree}}(\operatorname{\textsf{C}})$,
we have $\operatorname{\textsf{nb}}_{\pi^{\prime}}=0$ and
$\operatorname{{\mathfrak{out}}}_{\pi^{\prime}}=\varepsilon$ (intuitively, the
subtree rooted in $\pi$ stores empty informations).

#### Invariants.

The main idea for building $\mathcal{S}$ it the following. If $C^{x}_{i}$ is a
non-separable set, then the productions along the initial runs which end in
$C^{x}_{i}$ are mutual prefixes (by Lemma 4.8) which only differ from a
bounded information. Hence the common part $\operatorname{\textsf{com}}$ of
these runs is stored to $\operatorname{\mathfrak{out}}$, and the
$\operatorname{\textsf{adv}}$ are stored in the $\operatorname{\textsf{lag}}$.
If $C^{x}_{i}$ becomes separable, then these runs still produce mutual
prefixes, but two of them can differ by a large information. However by Lemma
4.13, they iterate some value $\theta$. Hence the only relevant information is
the number of $\theta$ which were produced along these runs. Formally, our
construction ensures that the following invariants hold when $\mathcal{S}$ has
just read $C^{x}_{0}x[1]C^{x}_{1}\cdots x[i]C^{x}_{i}$ for $i\geqslant 0$:

  1. 1.

$\operatorname{\textsf{C}}=C^{x}_{i}$;

  2. 2.

$\operatorname{\textsf{J}},x[1{:}i],\operatorname{\textsf{C}}$ is an initial
step and ${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ E}{}{}={\rm
Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\
E}{\operatorname{\textsf{J}},\operatorname{\textsf{C}}}{}$

  3. 3.

if $\operatorname{\textsf{C}}$ is not separable, then $\mathcal{S}$ is in non-
separable mode and:

    1. (a)

$\operatorname{\mathfrak{out}}=\operatorname{\textsf{com}}_{\operatorname{\textsf{J}},\operatorname{\textsf{C}}}^{x[1{:}i]}$;

    2. (b)

$\operatorname{\textsf{lag}}(q)=\operatorname{\textsf{adv}}_{\operatorname{\textsf{J}},\operatorname{\textsf{C}}}^{x[1{:}i]}(q)$
for all $q\in\operatorname{\textsf{C}}$.

  4. 4.

if $\operatorname{\textsf{C}}$ is separable, then $\mathcal{S}$ is in
separable mode and:

    1. (a)

##  5 Description of the $1$-bounded $\operatorname{\textsf{dSST}}$ for
Subsection 4.2

In this section, we finally describe how the $\operatorname{\textsf{dSST}}$
$\mathcal{S}$ can preserve the invariants of Subsection 4.2, while being
$1$-bounded and outputting $f(x)$ when $x\in\operatorname{\textsf{Dom}}(f)$.

Let us first deal with the initialization of $\mathcal{S}$. When reading the
first letter $C^{x}_{0}$ of $g(x)$, $\mathcal{S}$ stores
$\operatorname{\textsf{J}}\leftarrow C^{x}_{0}$,
$\operatorname{\textsf{C}}\leftarrow C^{x}_{0}$ and
$\operatorname{\textsf{lag}}(q)\leftarrow\varepsilon$ for all $q\in
C^{x}_{0}$.