# Status and prospects of the NA64 experiment at the CERN SPS

P. Crivelli
ETH Zurich, Institute for Particle Physics and Astrophysics, Auguste-Piccard-
Hof 1, 8093 Zurich

###### Abstract

NA64 is a fixed target experiment at the CERN SPS designed as a hermetic
general purpose detector to search for Dark Sector physics in missing energy
events from electron/positron, hadrons, and muon scattering off nuclei. In
this contribution to the FIPs 2022 workshop, we review the current status and
prospects of NA64.

##  1 The NA64 experiment

Our proposal (P348) to search for Dark Sectors at the CERN Super Proton
Synchrotron (SPS) [1] was positively received by the SPS committee (SPSC) in
April 2014. We were granted a test beam run in 2015 for a feasibility study,
and we were finally approved as the 64th CERN experiment in the North Area
(NA64) in March 2016. NA64 is designed as a hermetic general-purpose detector
to search for Dark Sector (DS) physics in missing energy events from
electron/positron, hadron, and muon scattering off nuclei. The main focus of
the NA64 is Light thermal Dark Matter (LDM) interacting with the Standard
Model (SM) via vector (or other) portal, such e.g. as dark photons
($A^{\prime}$) and a variety of New Physics scenarios. The experiment, in
electron mode (NA64e), employs the optimized 100 GeV electron beam from the H4
beam-line at the North Area. The beam was designed to transport the electrons
with the maximal intensity up to a few $\simeq 10^{7}$ per SPS spill of 4.8 s
in the momentum range between 50 and 150 GeV/c. The hadron contamination in
the electron beam was measured to be at a level of $\pi/e^{-}\lesssim 2\%$ and
$K/e^{-}\lesssim 0.3\%$.
The NA64 experiment run from 2016 until 2018, and after the CERN long shutdown
(LS2) in 2021, it resumed data taking in a new permanent location at H4
beamline CERN prepared for us. Despite the experiment being quite new, very
interesting results were rapidly achieved [2, 3, 4]. In this contribution, we
review the main results accomplished so far subdividing those into the
$A^{\prime}$ decay modes being explored.

Invisible mode: NA64 pioneered the active beam dump technique combined with
the missing energy measurement to search for invisible decays of massive
$A^{\prime}$, produced in the ECAL target (the electromagnetic (em)
calorimeter) by the dark Bremsstrahlung reaction $e^{-}Z\rightarrow
e^{-}ZA^{\prime}$, where electrons scatter off a nucleus of charge $Z$. After
its production, the $A^{\prime}$ would promptly decay into a pair of LDM
candidate particles, $A^{\prime}\rightarrow\chi\chi$, which would escape the
setup undetected leaving missing energy as a signature. For this reason, we
call these searches invisible. The parameter space characterized by mixing
strengths 10${}^{-6}<\epsilon<$ 10-3 and masses $m_{A^{\prime}}$ in the sub-
GeV range is the NA64 physics scope: a region where the DM origin can be
explained as a thermal freeze-out relic. Missing energy experiments, such as
NA64, require precise knowledge of the incoming beam (momentum and particle
ID) and an accurate measurement of the deposited energy from the incoming
beam’s interaction.

A signal event is defined as a single electromagnetic shower in the ECAL with
an energy $E_{ECAL}$ below the given threshold111The value is chosen to
maximize the sensitivity of the experiment, in NA64 for 100 GeV incoming beam
energy this value is $E_{ECAL}<50$ GeV. accompanied by a significant missing
energy $E_{miss}=E_{A^{\prime}}=E_{initial}-E_{ECAL}$. The occurrence of the
$A^{\prime}$ production is inferred in case these events show an excess above
those expected from backgrounds. In Fig. 1, we present a sketch of the setup
and a summary of the NA64 working principle.

The signal yield for an active beam approach is proportional to
$\epsilon^{2}$, thus, enhancing the sensitivity for NA64 with respect to the
yield $\propto\alpha_{D}\epsilon^{4}$ in traditional beam-dump approach where
the $A^{\prime}$ decay is measured in a detector further away from its
production point in the dump.

Figure 1: NA64 setup and working principle for the search of dark photons
through missing energy in the active target (ECAL).

The main results achieved so far in the invisible electron mode are:

  1. 1.

2016 July run: $2.7\times 10^{9}$ electrons on target (EOT) have been
collected and the results published in Phys. Rev. Lett. (PRL) [2]. No event
compatible with signal was found, thus, excluding most of the favored region
of parameter space compatible with the muon $g-2$ anomaly depicted as a band
in the left plot of Fig.2. After our results were published, BABAR completely
closed the remaining region of parameter space which could provide an
explanation as the Dark photon contributing to the g-2 muon [5].

  2. 2.

2016 October run: the results corresponding to $4.3\times 10^{10}$ EOT have
been published in Phys. Rev. D. [3]. At this level, NA64 starts to become
sensitive to light-dark matter models. No event compatible with a signal was
found and so a new exclusion limit could be set.

  3. 3.

2017 run: $\simeq 5.5\cdot 10^{10}$ EOT were accumulated and the combined data
sample from 2016 and 2017 reaches the milestone of $\simeq 10^{11}$ EOT.

  4. 4.

2018 run: $2\cdot 10^{11}$ EOT were collected. No signal-like event was
detected. However, the results of the combined analysis from 2016-2018 data,
illustrated in Fig. 2, set the most stringent limit for LDM below 0.1 GeV for
the canonical benchmark parameters $\alpha_{D}=0.1$ and
$m_{A^{\prime}}=3m_{\chi}$, thus, NA64 became the leading beam-dump experiment
in this region. These results were selected as PRL editor’s suggestion [6].

In addition to the Bremsstrahlung reaction, the resonant $A^{\prime}$
production channel through the e- annihilation with the positrons present in
the electromagnetic shower has also been considered. The 90$\%$ C.L. exclusion
limits from the combined analysis are shown in Fig. 2. The inclusion of the
resonant process in the data analysis allows enhancing the NA64 sensitivity
for a given dark photon mass resulting in a peak around 200 MeV. The addition
of this process improves the NA64 sensitivity in the high mass region, where
the Dark photons yield is suppressed due to the $1/m^{2}_{A^{\prime}}$
dependency of the Bremsstrahlung cross-section (see [6]). Using positrons as a
primary beam instead of electrons would increase by another order of magnitude
the sensitivity of NA64 at a given mass depending on the beam energy. By
scanning the positron beam energy the mass range probed by this mode can be
further expanded. The drawback is that one has to deal with about an order of
magnitude more hadron contamination in the beam since the secondary particles
are created by the primary 400 GeV SPS protons and thus positively charged
hadrons are more abundant than their negative counterpart. To study the impact
of the increased hadron contamination and the possible resulting background, a
first test beam with 100 GeV positron was taken during the 2022 run (see
below).

Electron/positron beam-dump experiments allow exploring alternative scenarios
to the dark photon hypothesis. NA64 has already proven its potential to search
for light-scalar and pseudo-scalar axion-like particles (ALPs) produced
through the Primakoff reaction [7]. The current NA64 coverage in these
searches closes part of the gap between beam-dump and LEP bounds and it is
shown in the right plot of Fig. 3. A search for a generic X-boson coupling to
electrons could also be performed. We were positively surprised that the NA64
sensitivity was an order of magnitude more stringent than precision
experiments [8]. However, one should note that in NA64 we assume the X-boson
to decay invisibly while the electron g-2 [9] and the fine structure
measurements [10, 11] are model-independent.

Figure 2: Current status of NA64 experiment 90% C.L. exclusion limits on
$A^{\prime}$ invisible decays including both the Bremsstrahlung and the
resonant $A^{\prime}$ production channels (Left). LDM searches (Right) [6]

.

Visible mode: The method for the search of $A^{\prime}\to e^{+}e^{-}$ ($X\to
e^{+}e^{-}$) decays is described in [1, 12]. In this case, the setup is
slightly modified to include an additional compact calorimeter upstream with
respect to the ECAL. If the $A^{\prime}$ exists, due to the
$A^{\prime}(X)-e^{-}$ coupling it would occasionally be produced by a shower
electron (or positron) in its scattering off a nucleus in the dump:
$e^{-}+Z\to e^{-}+Z+A^{\prime}(X);~{}A^{\prime}(X)\to e^{+}e^{-}$. Since the
$A^{\prime}$ is penetrating, it would escape the beam dump and subsequently
decay into an $e^{+}e^{-}$ pair in a downstream set of detectors. The pair
energy would be equal to the energy missing from the target. Thus, the
signature of the $A^{\prime}(X)\to e^{+}e^{-}$ decay is an event with two em-
like showers in the detector: one shower in the dump, and another one in the
ECAL, located downstream in this case, with the sum energy being equal to the
beam energy.

  1. 1.

2017 run: $\simeq 5.5\cdot 10^{10}$ EOT were accumulated. No candidates were
found in the signal box. The combined 90% confidence level (C.L.) upper limits
for the mixing strength $\epsilon$ were obtained from the corresponding limit
for the expected number of signal events. These results set the first limits
on the $X-e^{-}$ coupling in the range $1.3\times
10^{-4}\lesssim\epsilon_{e}\lesssim 4.2\times 10^{-4}$ excluding part of the
parameter space suggested by the so called Beryllium anomaly [13] which could
be explained by a new X boson with a mass around 17 MeV (named X17)[14]. In
addition, new bounds are set on the mixing strength of photons with dark
photons ($A^{\prime}$) from non-observation of the decay $A^{\prime}\to$ e+e-
of the Bremsstrahlung $A^{\prime}$ with a mass $\lesssim 23$ MeV. The
corresponding paper was highlighted as an editor’s suggestion in Phys. Rev.
Lett. 5[4].

  2. 2.

2018 run: about $5\times 10^{10}$ EOT were collected at an energy of 150 GeV
to boost the putative X bosons outside the calorimeter before it decays in
order to improve the sensitivity to higher $X-e^{-}$ couplings. The results
extend the limits to $1.2\times 10^{-4}\leq\epsilon\leq 6.8\times 10^{-4}$ for
the vector-like benchmark model and leave only a small region open to fully
cover the parameter space compatible with the Beryllium anomaly (see the
central panel of Fig. 3). The paper was published in Phys. Rev. D Rapid[15].
Recently, these searches have been extended also to a pseudo-scalar particle
decaying visibly into a lepton pair and the result has been published in Phys.
Rev. D [16].

To completely cover the remaining region of parameter space a new shorter
optimized WCAL and a new spectrometer with the possibility to reconstruct the
X17 invariant mass should be used as proposed in [17]. Everything has been
prepared and is ready for installation. However, since it cannot run in
parallel with the invisible mode setup we decided to postpone this search.
About 30 days of beam-time would be required to solidly probe the remaining
X17 parameter space, therefore if the results from PADME currently taking data
[18], would confirm this anomaly we would be able to cross-check this in the
2024 run.

Semi-visible mode: Alternative extended scenarios envisioning two DM species
split in mass could result in a signature that is a combination of the two
signatures described above. A very intriguing feature of this channel is
related to the possibility to recover both the DM thermal freeze-out and the
$(g-2)_{\mu}$ anomaly explanations, by evading the existing experimental
constraints on pure visible and invisible modes [19]. These types of models
are known as inelastic DM and we refer to their signatures as a semi-visible
channel. An analysis based on a recast of the results from the combined
2016-2018 data [20] (see the left plot of Fig. 3) has already demonstrated the
potential of NA64 to study these models. The reach of NA64 to explore in a
model-independent way a broad class of parameter space is currently under
study (to appear soon on the arXiv).

Figure 3: Current status of the NA64 experiment 90% C.L. exclusion limits on
semi-visible $A^{\prime}$ decays [20] (Left), $A^{\prime}(X)$ visible decays
(center) [15] and NA64 coverage in ALPs searches [21] (Right).

##  2 Current status and prospects of NA64

The very dense NA64 program restarted after LS2 in August 2021 with the
installation of the setup in the new permanent experimental area in the H4 SPS
beam line. The setup was ready for the 6 weeks beam-time in 2021 and took data
during 10 weeks in 2022. The goal is to continue our DS exploration until LS3
and collect around $5\cdot 10^{12}$ EOT in order to probe the parameter space
for light DM models suggested by the observed relic density and other
interesting New Physics scenarios. Depending on the results of PADME, in 2024
the upgraded visible setup could be installed to probe the full parameter
space of the hypothetical X17 boson.

Combining the 2021 data with the one collected before LS2 (total statistic of
$3.2\times 10^{11}$ electrons on target), we performed a search for a new
$Z^{\prime}$ gauge boson associated with (un)broken B-L symmetry [22]. No
signal events were found, thus, new constraints on the $Z^{\prime}$-e coupling
strength were set. For the mass range $0.3<m_{Z^{\prime}}<100$ MeV, these
limits are more stringent than those obtained from the neutrino-electron
scattering data (see Fig. 4. The data also indicate that NA64 is background
free at a level of $1\times 10^{12}$. Another possibility that is currently
under investigation is based on the existence of a light $Z^{\prime}$ boson
resulting from gauging the difference of the lepton number between the muon
and tau flavor. This hypothetical boson can couple via QED vertex corrections
to the electron and its existence could explain both the muon g-2 anomaly and
the DM relic composition. Moreover, this $Z^{\prime}$ can be produced again
through the dark Bremsstrahlung process, $e^{-}N\rightarrow e^{-}NZ^{\prime}$,
but also via the resonant annihilation with secondary positrons from the
shower. With the 2016-2018 statistics, NA64 was able to probe in this scenario
the region suggested by the $(g-2)_{\mu}$ anomaly up to $m_{Z^{\prime}}\sim 1$
MeV [23]. Such a light $Z^{\prime}$ can additionally couple directly to muons
and its search is therefore also one of the physics goals of NA64μ, the NA64
extension using a high energetic muon beam [24, 25].

Figure 4: Left: NA64 limits for a generic X boson, for the scalar (S), vector
(V), pseudo-scalar (P), and axial vector (A) cases [8]. Middle: NA64e
exclusion limit for the Lμ-Lτ (red line) obtained with the 2016-2018
statistics for models where $Z^{\prime}$ can decay to DM particles [23]. The
red (orange) dashed curves represent the sensitivity projections for a future
high-statistics NA64e run with an electron (positron) beam, for a total a of
$10^{13}$ EOT, while the green dashed curve is the sensitivity projection of
NA64μ. Right: NA64 exclusion limits for a new B-L Z’ boson [22].

The NA64μ program started in 2021 with two pilot runs at the M2 beam-line
using the unique CERN 160 GeV/c muon beam. This will probe DS in a
complementary way to the H4 measurements with electrons and will address the
g-2 muon anomaly [25]. The main difference between the experimental technique
used in NA64μ compared to NA64e is that in this case one has to rely solely on
momentum reconstruction to measure the missing energy carried away from a
possible $Z^{\prime}$ or $A^{\prime}$ decay. This makes NA64μ much more
challenging than NA64e where one employs calorimeters for this purpose. During
the pilot runs in 2021 and 2022, a total of $4\times 10^{10}$ MOT were
collected. The analysis is still ongoing but the preliminary results already
hint to the fact that an additional spectrometer should be added upstream the
ECAL since an accurate determination of the incoming momentum is crucial for
the experiment. This will be tested in 2023 and the first physics runs are
expected for 2024-2025.

It is worth mentioning, that for the new-physics process simulations and for
detailed comparison between data and Monte Carlo, a new GEANT4 based package
called DMG4 [26] was developed by NA64 members, which has been well accepted
by the community, see, e.g [27].

##  3 Outlook and conclusions

NA64 just reached a major milestone of accumulating $\sim 10^{12}$ EOT which
allows one to start probing very interesting LDM benchmark models. The
analysis is ongoing and with the increased statistics we expect to improve the
sensitivity also of our searches for ALPs, Lμ-Lτ and B-L $Z^{\prime}$ bosons,
inelastic DM and generic X bosons. The plan until LS3 is to accumulate as many
as possible electrons on target and if the background will be under control
also use the positron mode to enhance the sensitivity in the higher
$A^{\prime}$ mass region. To study the impact of the larger hadron
contamination when running with positrons compared to electrons, in the 2022
run 2 days were used to collect $\sim 10^{10}$ positrons on target (the
analysis is ongoing).

NA64 also started its program at the M2 beam-line providing unique high
intensity 160 GeV muons to explore dark sectors weakly coupled to muons. The
results of the pilot runs show that with an optimized setup, one could collect
$>10^{11}$ MOT before LS3 in order to check if an Lμ-Lτ $Z^{\prime}$ boson is
the explanation of the g-2 muon anomaly and complement the searches with
electrons (see [28]). After LS3 the experiment would then continue data taking
to accumulate $\sim 10^{13}$ MOT to explore the $A^{\prime}$ higher mass
region and $\mu\to\tau$ and $\mu\to e$ LFV processes [29].

In the 2022 beam-time, we also dedicated 1 day of data taking to accumulate
$\sim 2\times 10^{9}$ pions on target in order to understand the potential of
NA64 to explore dark sectors coupled predominantly to quarks using the missing
energy technique [30, 31]. This will be further investigated and, if the
feasibility would be demonstrated, a dedicated search will be performed after
LS3.

To conclude the exploration of the NA64 physics potential has just begun. Our
proposed searches with leptonic and hadronic beams provide unique
sensitivities highly complementary to similar projects.

## Acknowledgments

I would like to acknowledge the NA64 collaboration and in particular S.
Gninenko, L. Molina-Bueno and V. Poliakov. Special thanks also to the past and
current ETHZ members, notably E. Depero, H. Sieber, B. Banto-Oberhauser, M.
Mongillo, A. Ponten. A big thank you also to the CERN beam department: D.
Banerjee, J. Bernhard, N. Charitonidis, M. Brugger for their continuous
support. My gratitude to the CERN SPSC members and NA64 referees who were
fundamental for the success of NA64: particularly C. Vallé, G. Lanfranchi, G.
Salam, L. Gatignon, M. Wing and G. Schnell. My work is supported by ETHZ and
the Swiss National Science Foundation (SNSF) under the Grants No. 169133 and
186158.

## References

  * [1] S. Andreas, P. Crivelli, et al.  Proposal for an Experiment to Search for Light Dark Matter at the SPS.  2013\.
  * [2] D. Banerjee, P. Crivelli, et al.  Search for invisible decays of sub-GeV dark photons in missing-energy events at the CERN SPS.  Phys. Rev. Lett., 118(1):011802, 2017.
  * [3] D. Banerjee, P. Crivelli, et al.  Search for vector mediator of Dark Matter production in invisible decay mode.  Phys. Rev., D97(7):072002, 2018.
  * [4] D. Banerjee, P. Crivelli, et al.  Search for a Hypothetical 16.7 MeV Gauge Boson and Dark Photons in the NA64 Experiment at CERN.  Phys. Rev. Lett., 120(23):231802, 2018.
  * [5] J. P. Lees et al.  Search for Invisible Decays of a Dark Photon Produced in ${e}^{+}{e}^{-}$ Collisions at BaBar.  Phys. Rev. Lett., 119(13):131804, 2017.
  * [6] D. Banerjee et al.  Dark matter search in missing energy events with NA64.  Phys. Rev. Lett., 123(12):121801, 2019.
  * [7] D. Banerjee et al.  Search for Axionlike and Scalar Particles with the NA64 Experiment.  Phys. Rev. Lett., 125(8):081801, 2020.
  * [8] Yu. M. Andreev et al.  Constraints on New Physics in Electron $g-2$ from a Search for Invisible Decays of a Scalar, Pseudoscalar, Vector, and Axial Vector.  Phys. Rev. Lett., 126(21):211802, 2021.
  * [9] X. Fan, T. G. Myers, B. A. D. Sukra, and G. Gabrielse.  Measurement of the Electron Magnetic Moment.  9 2022.
  * [10] Richard H. Parker, Chenghui Yu, Weicheng Zhong, Brian Estey, and Holger Müller.  Measurement of the fine-structure constant as a test of the Standard Model.  Science, 360:191, 2018.
  * [11] Léo Morel, Zhibin Yao, Pierre Cladé, and Saïda Guellati-Khélifa.  Determination of the fine-structure constant with an accuracy of 81 parts per trillion.  Nature, 588(7836):61–65, 2020.
  * [12] S. N. Gninenko.  Search for MeV dark photons in a light-shining-through-walls experiment at CERN.  Phys. Rev., D89(7):075008, 2014.
  * [13] A. J. Krasznahorkay et al.  Observation of Anomalous Internal Pair Creation in Be8 : A Possible Indication of a Light, Neutral Boson.  Phys. Rev. Lett., 116(4):042501, 2016.
  * [14] Jonathan L. Feng, Bartosz Fornal, Iftah Galon, Susan Gardner, Jordan Smolinsky, Tim M. P. Tait, and Philip Tanedo.  Particle physics models for the 17 MeV anomaly in beryllium nuclear decays.  Phys. Rev., D95(3):035017, 2017.
  * [15] D. Banerjee et al.  Improved limits on a hypothetical X(16.7) boson and a dark photon decaying into $e^{+}e^{-}$ pairs.  2019\.
  * [16] Yu. M. Andreev et al.  Search for pseudoscalar bosons decaying into $e^{+}e^{-}$ pairs in the NA64 experiment at the CERN SPS.  Phys. Rev. D, 104(11):L111102, 2021.
  * [17] E. Depero et al.  Hunting down the X17 boson at the CERN SPS.  Eur. Phys. J. C, 80(12):1159, 2020.
  * [18] Luc Darmé, Marco Mancini, Enrico Nardi, and Mauro Raggi.  Resonant search for the X17 boson at PADME.  9 2022.
  * [19] Gopolang Mohlabeng.  Revisiting the dark photon explanation of the muon anomalous magnetic moment.  Phys. Rev. D, 99:115001, Jun 2019.
  * [20] C. Cazzaniga et al.  Probing the explanation of the muon (g-2) anomaly and thermal light dark matter with the semi-visible dark photon channel.  Eur. Phys. J. C, 81(10):959, 2021.
  * [21] Sergei Gninenko.  NA64 Status Report 2018.  Technical Report CERN-SPSC-2018-015. SPSC-SR-231, CERN, Geneva, May 2018\.
  * [22] Yu. M. Andreev et al.  Search for a New B-L Z’ Gauge Boson with the NA64 Experiment at CERN.  Phys. Rev. Lett., 129(16):161801, 2022.
  * [23] Yu. M. Andreev et al.  Search for a light Z’ in the L$\mu$-L$\tau$ scenario with the NA64-e experiment at CERN.  Phys. Rev. D, 106(3):032015, 2022.
  * [24] S. N. Gninenko, N. V. Krasnikov, and V. A. Matveev.  Muon g-2 and searches for a new leptophobic sub-GeV dark boson in a missing-energy experiment at CERN.  Phys. Rev. D, 91:095015, 2015.
  * [25] H. Sieber, D. Banerjee, P. Crivelli, E. Depero, S. N. Gninenko, D. V. Kirpichnikov, M. M. Kirsanov, V. Poliakov, and L. Molina Bueno.  Prospects in the search for a new light Z’ boson with the NA64$\mu$ experiment at the CERN SPS.  Phys. Rev. D, 105(5):052006, 2022.
  * [26] M. Bondi, A. Celentano, R. R. Dusaev, D. V. Kirpichnikov, M. M. Kirsanov, N. V. Krasnikov, L. Marsicano, and D. Shchukin.  Fully Geant4 compatible package for the simulation of Dark Matter in fixed target experiments.  Comput. Phys. Commun., 269:108129, 2021.
  * [27] Tom Eichlersmith, Jeremiah Mans, Omar Moreno, Joseph Muse, Michael Revering, and Natalia Toro.  Simulation of Dark Bremsstrahlung in GEANT4.  11 2022.
  * [28] S. N. Gninenko, D. V. Kirpichnikov, M. M. Kirsanov, and N. V. Krasnikov.  Combined search for light dark matter with electron and muon beams at NA64.  Phys. Lett. B, 796:117–122, 2019.
  * [29] S. N. Gninenko and N. V. Krasnikov.  Leptonic scalar portal: Origin of muon g-2 anomaly and dark matter?  Phys. Rev. D, 106(1):015003, 2022.
  * [30] S. N. Gninenko.  Search for invisible decays of $\pi^{0},\eta,\eta^{\prime},K_{S}$ and $K_{L}$: A probe of new physics and tests using the Bell-Steinberger relation.  Phys. Rev. D, 91(1):015004, 2015.
  * [31] S. N. Gninenko and N. V. Krasnikov.  Invisible $K_{L}$ decays as a probe of new physics.  Phys. Rev. D, 92(3):034009, 2015.


# Thermal Equilibrium Solutions of Black Hole Accretion Flows: Outflows VS
Advection

Wen-Biao Wu  Wei-Min Gu  Mouyuan Sun  Department of Astronomy, Xiamen
University, Xiamen, Fujian 361005, P. R. China<EMAIL_ADDRESS>
###### Abstract

Observations and numerical simulations have shown that outflows generally
exist in the accretion process. We revisit the thermal equilibrium solutions
of black hole accretion flows by including the role of outflows. Our study
focuses on the comparison of the cooling rate of outflows with that of
advection. Our results show that, except for the inner region, outflows can
dominate over advection in a wide range of the flow, which is in good
agreement with previous numerical simulations. We argue that an advection-
dominated inner region together with an outflow-dominated outer region should
be a general radial distribution for both super-Eddington accretion flows and
optically thin flows with low accretion rates.

High energy astrophysics (739) — accretion (14) — black hole (162) —
hydrodynamics (1963)

##  1 Introduction

Three well-known models have been widely investigated in black-hole accretion
systems, namely, the standard thin disk (Shakura & Sunyaev, 1973, hereafter
SSD), the slim disk (Abramowicz et al., 1988), and the optically thin
advection- dominated accretion flow (Narayan & Yi, 1994, 1995, hereafter
ADAF). The SSD is optically thick, geometrically thin, and radiative cooling
dominated. This model has been proposed to be central engines of luminous
active galactic nuclei (AGNs) and black hole X-ray binaries (BHXBs) in the
high/soft state (e.g., Kato et al., 2008). For the slim disk, it has a high
mass accretion rate (super-Eddington), thus the radiation diffusion timescale
is larger than the viscous timescale. This disk is optically thick and
geometrically slim, which may work for ultraluminous X-ray sources, bright
microquasars, and narrow-line Seyfert 1 galaxies (e.g., Wang & Zhou, 1999;
Mineshige et al., 2000; Done et al., 2007; Kaaret et al., 2017; Kosec et al.,
2018). The ADAF is radiatively inefficient, where the viscous heating is
mainly balanced by the advective cooling. The flow is geometrically thick and
its gas temperature is close to the virial temperature. This model has been
applied to describe sources such as the supermassive black hole in our
Galactic center, Sagittarius ${\rm A}^{\ast}$ (Sgr ${\rm A}^{\ast}$), low-
luminosity AGNs, and BHXBs in the low/hard and quiescent states (e.g., Narayan
& McClintock, 2008; Yuan & Narayan, 2014). The above models assume that the
accretion rate remains constant during the accretion process.

Recent observations showed that outflows exist in the geometrically thin disks
(e.g., King & Pounds, 2015; Díaz Trigo & Boirin, 2016; Homan et al., 2016),
the super-Eddington accretion disks (e.g., Gladstone et al., 2009; Middleton
et al., 2011; Du et al., 2015), and the radiatively inefficient accretion
flows (e.g., Wang et al., 2013; Cheung et al., 2016; Homan et al., 2016; Ma et
al., 2019; Muñoz-Darias et al., 2019). This means that the accretion rate is
no longer a constant. Apart from observations, outflows were also found in the
hydrodynamical (HD) and magnetohydrodynamical (MHD) numerical simulations of
the geometrically thin disks (e.g., Ohsuga & Mineshige, 2011; Nomura et al.,
2016, 2020), the super-Eddington accretion disks (e.g., Ohsuga et al., 2005;
Ohsuga & Mineshige, 2011; Jiang et al., 2014; Sadowski et al., 2014; Sadowski
& Narayan, 2015; Kitaki et al., 2017, 2018; Zahra Zeraatgari et al., 2020),
and the radiatively inefficient accretion flows (e.g., Stone et al., 1999;
Yuan et al., 2012; Narayan et al., 2012; Yuan et al., 2012, 2015).

Outflows as a signature of the super-Eddington accretion were discussed by
Shakura & Sunyaev (1973). In this pioneering paper, they supposed that
outflows are inevitable when the luminosity of the disk exceeds the Eddington
limit, since the radiation force is greater than the gravity. More
importantly, Piran (1978) investigated the stability of accretion disks and
proposed that wind escaping from the disk surface can have a stabilizing
effect. Later, Abramowicz (1981) showed that the innermost parts of accretion
disks are thermally and secularly stable owing to the general relativistic
effect, where the physical picture is analogous to the case of Roche-lobe
overflow in close binaries. On the other hand, Narayan & Yi (1994, 1995)
argued that outflows are likely to occur because the Bernoulli parameter is
positive in some regions. Blandford & Begelman (1999) constructed the
adiabatic inflow-outflow solutions to describe outflows. They assumed that the
accretion rate is a function of radius $\dot{M}\propto r^{p}$, where $p$ is in
the range $[0,1]$. Xie & Yuan (2008) also used a global method to show the
influence of the outflows on the disk structure by this relationship. Further
numerical simulations showed the power-law index $p$ in a range of [0.5, 1]
(e.g., Stone et al., 1999; Ohsuga et al., 2005; Narayan et al., 2012; Yuan et
al., 2012; Bu & Gan, 2018). In the case of Sgr $\rm{A}^{\ast}$, however, a
relatively low value for the index $p$ is preferred, such as $p=0.25$
(Quataert & Narayan, 1999), 0.27 (Yuan et al., 2003), and 0.37 (Ma et al.,
2019). Dotan & Shaviv (2011) proposed a model for super-Eddington accretion
flows that the disk remains slim and a significant wind is accelerated. Some
works also demonstrated that the super-Eddington accretion (Gu & Lu, 2007; Gu,
2015; Cao & Gu, 2015; Feng et al., 2019) and the optically thin ADAF (Gu,
2015) ought to have outflows.

In this work, we revisit the thermal equilibrium solutions of black hole
accretion flows by including the role of outflows. Our study focuses on the
comparison of the cooling rate of outflows with that of advection. The paper
is organized as follows. The basic equations for our model are described in
Section 2. Numerical results and analyses are shown in Section 3. Conclusions
and discussion are presented in Section 4.

##  2 Basic Equations

In this section, we describe the basic equations of our model. We consider a
steady state axisymmetric accretion flow, and use the pseudo-Newtonian
potential $\Phi=-GM_{\rm{BH}}/(R-R_{\rm{g}})$, where $M_{\rm{BH}}$ is the mass
of the black hole and $R_{\rm{g}}$ is the Schwarzschild radius. The vertical
scale height of the flow is $H=c_{\rm{s}}/\Omega_{\rm{K}}$, where
$\Omega_{\rm{K}}$ is Keplerian angular velocity, and
$c_{\rm{s}}=(P/\rho)^{1/2}$ is the isothermal sound speed, with $P$ and $\rho$
being the pressure and mass density, respectively. The kinematic viscosity
coefficient is expressed as $\nu=\alpha c_{\rm{s}}H$, where $\alpha$ is the
constant viscosity parameter.

The basic equations describing the flow contain the continuity, radial
momentum, azimuthal momentum, and energy equations. The continuity equation is

$\frac{1}{R}\frac{d}{dR}\left(R\Sigma V_{\rm{R}}\right)+\frac{1}{2\pi
R}\frac{d\dot{M}_{\rm w}}{dR}=0\ ,$ (1)

where $\Sigma$ is the surface density defined as $\Sigma\equiv 2\rho H$, and
$V_{\rm{R}}$ is the radial velocity, which is defined to be negative when the
flow is inward. The outflow mass-loss rate $\dot{M}_{\rm{w}}$ is (Knigge,
1999)

$\dot{M}_{\rm w}(R)=\int_{R_{\rm{in}}}^{R}4\pi R^{\prime}\dot{m}_{\rm
w}(R^{\prime})dR^{\prime}\ ,$ (2)

where $R_{\rm{in}}$ denotes the radius at the inner edge of the disk and
$\dot{m}_{\rm w}$ is mass-loss rate per unit area from each disk face.

Due to the influence of outflows, we assume that the accretion rate $\dot{M}$
varies with radius as follows (Blandford & Begelman, 1999):

$\dot{M}=-2\pi R\Sigma
V_{\rm{R}}=\dot{M}_{\rm{outer}}\left(\frac{R}{R_{\rm{outer}}}\right)^{p}\ ,$
(3)

where $\dot{M}_{\rm{outer}}$ is the mass accretion rate at the outer boundary
$R_{\rm{outer}}$.

Some numerical simulations showed that outflows in super-Eddington accretion
cases and ADAFs are stronger than that in SSDs (e.g., Ohsuga & Mineshige,
2011, 2014), which can be physically understood as follows. The effective
cooling of radiation in SSDs leads to a low temperature of the disk, i.e., a
negative Bernoulli parameter of the flow. Thus, only relatively weak outflows
may be produced by SSDs. On the contrary, for super-Eddington accretion cases,
even though the temperature of the disk is only slightly higher than that of
SSDs, a large amount of photons trapped in the disk result in high radiation
pressure, which can contribute to strong outflows. In addition, for ADAFs, the
extremely high temperature of the disk due to energy advection cause positive
Bernoulli parameter (e.g., Narayan & Yi, 1994; Narayan et al., 1997), which
can also contribute to strong outflows. In summary, energy advection is
helpful to produce strong outflows, no matter the physics of advection is
related to photons or gas. It is known that the dimensionless thickness $H/R$
of the disk well describes the strength of advection, i.e., $H/R\ll 1$ for
SSDs and $H/R\lesssim 1$ for slim disks and ADAFs. We therefore assume that
the power-law index $p$ is proportional to $H/R$ of the disk, i.e.,
$p=\lambda(H/R)$, where $\lambda$ is a constant. In our opinion, such an
assumption is more appropriate than a fixed value of $p$ for different
accretion models.

Using Equations (1)-(3), we obtain this relation,

$\dot{m}_{\rm{w}}=\frac{\dot{M}p}{4\pi R^{2}}\ .$ (4)

The integrated radial momentum equation and the azimuthal equation of motions
can be respectively written as

$V_{\rm R}\frac{dV_{\rm R}}{dR}+\left(\Omega_{\rm
K}^{2}-\Omega^{2}\right)R+\frac{1}{\rho}\frac{dP}{dR}=0\ ,$ (5)
$-\frac{1}{R}\frac{d}{dR}\left(R^{3}\Sigma V_{\rm
R}\Omega\right)+\frac{1}{R}\frac{d}{dR}\left(R^{3}\nu\Sigma\frac{d\Omega}{dR}\right)-\frac{\left(lR\right)^{2}\Omega}{2\pi
R}\frac{d\dot{M_{\rm w}}}{dR}=0\ ,$ (6)

where the last term on the left-hand side of Equation (6) represents angular
momentum carried by the outflowing materials. Here, $l=0$ corresponds to a
non-rotating outflow, and $l=1$ corresponds to the outflowing materials
carrying away the specific angular momentum at the point of ejection. The
cases with $l>1$ correspond to centrifugally driven magnetic disk winds that
extract more angular momentum from the disk (Knigge, 1999).

The pressure $P$ is the sum of gas and radiation pressure:

$P=\frac{\rho k_{\rm{B}}}{\mu m_{\rm{p}}}\left(T_{\rm i}+T_{\rm
e}\right)+\frac{Q_{\rm{rad}}}{4c}\left(\tau+\frac{2}{\sqrt{3}}\right)\ ,$ (7)

where $T_{\rm{i}}$ and $T_{\rm{e}}$ are the ion temperature and the electron
temperature, respectively, and $T_{\rm{e}}=\min\ (T_{\rm{i}},6\times
10^{9}~{}{\rm K})$. $\mu=0.617$ is the mean molecular weight, and
$\tau=(\kappa_{\rm{es}}+\kappa_{\rm{abs}})\rho H$ is the total optical depth,
where $\kappa_{\rm{es}}=0.34\rm{\ cm^{2}\ g^{-1}}$ and
$\kappa_{\rm{abs}}=0.27\times 10^{25}\rho T_{\rm{e}}^{-3.5}\ \rm{cm^{2}\
g^{-1}}$ (e.g., Abramowicz et al., 1996).

The energy equation is written as

$Q_{\rm{vis}}=Q_{\rm adv}+Q_{\rm rad}+Q_{\rm w}\ ,$ (8)

where $Q_{\rm{vis}}$, $Q_{\rm adv}$, and $Q_{\rm rad}$ are the viscous heating
rate, the advective cooling rate, and the radiative cooling rate,
respectively. Their expressions are as follows,

$Q_{\rm{vis}}=\nu\Sigma\left(R\frac{d\Omega}{dR}\right)^{2}\ ,$ (9) $Q_{\rm
adv}=\Sigma V_{\rm R}T\frac{ds}{dR}=\Sigma V_{\rm
R}\left(\frac{1}{\gamma-1}\frac{dc_{\rm s}^{2}}{dR}-\frac{c_{\rm
s}^{2}}{\rho}\frac{d\rho}{dR}\right)\ ,$ (10) $Q_{\rm rad}=8\sigma T_{\rm
e}^{4}\left(\frac{3\tau}{2}+\sqrt{3}+\frac{8\sigma
T_{\rm{e}}^{4}}{Q_{\rm{br}}^{-}}\right)^{-1}\ .$ (11)

Equation (11) is valid in both optically thin and optically thick regimes
(Narayan & Yi, 1995). The bremsstrahlung cooling is given by (e.g., Abramowicz
et al., 1995)

$Q_{\rm{br}}^{-}=1.24\times 10^{21}H\rho^{2}T_{\rm e}^{1/2}~{}{\rm
erg~{}s^{-1}cm^{-2}}\ .$ (12)

The quantity $Q_{\rm w}$ in Equation (8) represents the energy taken away by
outflows, which is expressed as

$Q_{\rm w}=2f\eta\dot{m}_{\rm w}V_{\rm K}^{2}\ ,$ (13)

where a factor of 2 represent the outflow energy is emitted from both sides of
the accretion disk. $\eta$ is an outflow energy parameter and $V_{\rm K}$ is
the Keplerian velocity. By using Equation (1) and integrating Equation (6), we
have

$\nu\Sigma=\frac{\dot{M}fg^{-1}}{3\pi}\left(1-\frac{l^{2}p}{p+\frac{1}{2}}\right)\
,$ (14)

where $g=-\left(2/3\right)\left(d\ln\Omega_{\rm{K}}/d\ln R\right)$ and the
factor
$f=1-[\Omega\left(3R_{\rm{g}}\right)/\Omega(R)]\left(3R_{\rm{g}}/R\right)^{p+2}$.
For $p=0$, Equation (14) returns to Equation (2.1) of Chen et al. (1995).

Following some previous works (e.g., Narayan & Yi, 1994; Gu & Lu, 2000), we
adopt the self-similar assumptions and set $\gamma=1.5$. Then Equations
(9)-(11) are reduced to the following algebraic forms:

$\frac{1}{2}V_{\rm{R}}^{2}+\frac{5}{2}c_{\rm
s}^{2}+\left(\Omega^{2}-\Omega_{\rm K}^{2}\right)R^{2}=0\ ,$ (15)
$Q_{\rm{vis}}=\frac{3\dot{M}\Omega^{2}fg}{4\pi}\left(1-\frac{l^{2}p}{p+\frac{1}{2}}\right)\
,$ (16) $Q_{\rm adv}=\frac{1}{4\pi}\frac{\dot{M}c_{\rm s}^{2}}{R^{2}}\ .$ (17)

Finally, substituting Equation (4) into Equation (13), we have

$Q_{\rm w}=\frac{f\eta p\dot{M}\Omega_{\rm{K}}^{2}}{2\pi}\ .$ (18)

By solving the five equations, Equations (3), (7-8), and (14-15), for the five
variables $\rho$, $T$, $c_{\rm s}$, $\Omega$, and $V_{\rm R}$ with given
parameters $M_{\rm BH}$, $\alpha$, $\dot{M}$, and $l$, we obtain the thermal
equilibrium solutions of accretion flows. In the following calculations, we
fix $M_{\rm{BH}}=10M_{\sun}$, $\alpha=0.1$, and $l=1$.

##  3 Numerical Results

Figure 1: Thermal equilibria of accretion disks at $R=10R_{\rm g}$ for various
$\lambda$ and $\eta$. The color lines correspond to the cases for
($\lambda=0$, black), ($\lambda=0.5,\eta=1$, red), ($\lambda=0.5,\eta=2$,
blue), and ($\lambda=1,\eta=1$, green).

In this section, we describe the numerical results of the accretion flows with
outflows. Figure 1 shows thermal equilibrium solutions at $R=10\ R_{\rm{g}}$
in the $\log\dot{m}-\log\Sigma$ plane, where $\dot{m}$ is the accretion rate
normalized by the Eddington accretion rate $\dot{M}_{\rm{Edd}}=64\pi
GM_{\rm{BH}}/c\kappa_{\rm{es}}$. The black line represents the solutions under
the no-outflow assumptions (e.g., Abramowicz et al., 1995; Chen et al., 1995;
Takeuchi & Mineshige, 1998; Gu & Lu, 2000). The curve on the left is composed
of two branches, of which the upper one is for ADAFs and the lower one is for
SLE disks (Shapiro et al., 1976). The right S-shaped curve is composed of
three branches, of which the upper one is for slim disk, the middle one for
radiation pressure-supported SSDs, and the lower one for gas pressure-
supported SSDs. The red, blue and green lines represent the results with
($\lambda=0.5,\eta=1$), ($\lambda=0.5,\eta=2$), and ($\lambda=1,\eta=1$),
respectively. It is seen from the figure that the maximal accretion rate of
the left curve decreases with increasing cooling effects of outflows. However,
the change of the right S-shaped curve is quite slight. The obtained values of
$p$ of ADAFs and slim branches are $p\sim 0.23$ for $\lambda=0.5$ and $p\sim
0.39$ for $\lambda=1$. For comparison, we have $p\sim 0.003$ for gas-pressure-
supported SSDs. For the ADAF branch, the values of $p$ are in good consistent
with the fitting results of the Sgr $\rm{A}^{\ast}$ observations under
radiatively inefficient accretion model (e.g., Quataert & Narayan, 1999; Yuan
et al., 2003; Ma et al., 2019).

Figure 2: Variations of $f_{\rm{adv}}$ (red line), $f_{\rm{rad}}$ (blue line),
$f_{\rm{w}}$ (black line) with $R$ for $\dot{m}=100,\eta=1,\lambda=0.5$. The
green dashed line denotes the outflow-cooling-dominated region
($f_{\rm{w}}>f_{\rm{adv}}$, $f_{\rm{w}}>f_{\rm{rad}}$).

In order to quantitatively understand the influence of outflows at different
radius, we fix $\dot{m}=100$, $\eta=1$, $\lambda=0.5$, and $R_{\rm
outer}=10^{4}R_{\rm g}$. We then obtain variations of $f_{\rm{adv}}(\equiv
Q_{\rm{adv}}/Q_{\rm{vis}})$, $f_{\rm{rad}}(\equiv Q_{\rm{rad}}/Q_{\rm{vis}})$
and $f_{\rm{w}}(\equiv Q_{\rm{w}}/Q_{\rm{vis}})$ with radius. It is seen from
Figure 2 that, in the inner regions cooling is dominated by advection
($f_{\rm{adv}}$, the red line), and in the middle regions cooling is dominated
by outflows ($f_{\rm{w}}$, the black line). Since the gravitational force in
the inner regions is greater than the radiation force, and the radial velocity
is large (i.e., the viscous timescale is short), only a weak outflow can form.
In the middle regions (denoted by the green dashed line), however, the
situation is reversed as outflow dominance. Such an outflow-dominated region
varies significantly with varying accretion rates, which is presented in
Figure 3.

Figure 3: Distribution of thermal equilibrium solutions for $\eta=1$ and
$\lambda=0.5$. In panel (a), the parameter space is divided into three regions
by two curves. The upper region, denoted as “advection”
($f_{\rm{adv}}>f_{\rm{rad}}$), corresponds to the super-Eddington accretion
flows, and the lower “advection” region represents the ADAFs. The solutions of
panel (a) are under the no-outflow assumptions. On the contrary, panel (b)
takes outflows into account. The “advection” region corresponds to
($f_{\rm{adv}}>f_{\rm{rad}}$, $f_{\rm{adv}}>f_{\rm{w}}$), the “outflow” region
corresponds to ($f_{\rm{w}}>f_{\rm{adv}}$, $f_{\rm{w}}>f_{\rm{rad}}$), and the
“radiation” region corresponds to ($f_{\rm{rad}}>f_{\rm{adv}}$,
$f_{\rm{rad}}>f_{\rm{w}}$). The two red lines ($R_{\rm b}$) represent the
boundary between outflow-dominated and advection-dominated cases. The green
dashed line corresponds to the example solution for $\dot{m}=100$ in Figure 2.

A main purpose of this work is to compare the cooling effects of outflows with
that of advection. Figure 3 is a description of thermal equilibrium solutions
of accretion flows with outflows in the $\dot{m}-R$ plane. For a comparison,
Figure 3(a) is under the no-outflow assumptions. The $\dot{m}-R$ plane is
divided into three regions by two curves. The region above the upper curve
($f_{\rm adv}=1/2$) represents advective-cooling-dominated solutions ($f_{\rm
adv}>f_{\rm rad}$) owing to the photon trapping, which corresponds to the
super-Eddington accretion cases. The middle region represents solutions with
cooling dominated by radiation ($f_{\rm rad}>f_{\rm adv}$). The region below
the lower curve also represents advective-cooling-dominated solutions ($f_{\rm
adv}>f_{\rm rad}$), but the physics of advection is related to the internal
energy of accreted gas, which corresponds to the ADAF cases. Here, the maximal
critical mass accretion rate $\dot{m}_{\rm crit}$ of ADAF is assumed to be
around $0.01\dot{M}_{\rm Edd}$ ($\dot{m}_{\rm
crit}\sim\alpha^{2}\dot{M}_{\rm{Edd}}$) for the inner part with $R\lesssim
R_{\rm tr}$, where $R_{\rm tr}$ is around $10^{2}-10^{3}R_{\rm g}$ for
$\alpha=0.1$. For $R>R_{\rm tr}$, $\dot{m}_{\rm crit}$ decreases with
increasing $R$ (see, e.g., Figure 8 of Narayan et al., 1998).

Similar to Figure 2, Figure 3(b) is also for $\eta=1$ and $\lambda=0.5$, which
shows that there exists a boundary radius $R_{\rm b}$ (red lines) which
separates an inner “advection” region and an outer “outflow” region. By
comparing Figures 3(a) and 3(b), it is seen that for $R>R_{\rm b}$, the
original region with cooling dominated by advection is replaced by a region
with cooling dominated by outflows. The green dashed line denotes the outflow-
dominated region of the example solution with $\dot{m}=100$ in Figure 2. It is
seen from Figure 3(b) that the outflow-dominated region increases with
increasing accretion rates for the super-Eddington accretion cases. In
addition, for the optically thin cases, Figure 3(b) shows that a relatively
wide outflow-dominated region exists for ADAFs, and this region increases with
decreasing accretion rates. Thus, we argue that an advection-dominated inner
region together with an outflow-dominated outer region should be a general
radial distribution for both super-Eddington accretion flows and optically
thin flows with low accretion rates.

Figure 4: Variations of the boundary radius $R_{\rm b}$ with $\eta$ for a
typical ADAF with $\dot{m}=0.001$ and a typical slim disk with $\dot{m}=100$.
The solid and dashed curves correspond to the cases with $\lambda=1$ and
$\lambda=0.5$, respectively.

Figure 4 shows the variation of $R_{\rm{b}}$ with the parameter $\eta$. The
red solid (dashed) line represents solutions with $\dot{m}=0.001$ and
$\lambda=1$ ($\lambda=0.5$), where $p$ is less than 0.4 (0.25). The blue solid
(dashed) line represents solutions with $\dot{m}=100$ and $\lambda=1$
($\lambda=0.5$), where $p$ is less than 0.33 (0.22). Since the temperature of
ADAFs is close to the virial value, the outflows are stronger and therefore
the boundary $R_{\rm b}$ has a larger span in the radial direction. In
addition, the figure shows that, for a certain $\lambda$, when $\eta\gtrsim
1$, the boundary $R_{\rm b}$ is located between the inner stable circular
orbit ($3R_{\rm g}$) and $\sim 10R_{\rm g}$. The physical reason is that the
gravitational force in the inner region of is very strong and therefore the
outflows are restrained. In other words, outflows from inside $\sim 10R_{\rm
g}$ are quite weak, which is consistent with previous numerical simulations
(e.g., Yuan et al., 2012).

##  4 Conclusions and Discussion

In this work, we have revisited the thermal equilibrium solutions of black-
hole accretion flows by including the role of outflows. By comparing the
cooling rate of outflows with that of advection, we have found that advection
is important only in the inner regions and outflows play a key role in
balancing the viscous heating in the outer regions (Figure 3). We argue that
an advection-dominated inner region together with an outflow-dominated outer
region should be a general radial distribution for both super-Eddington
accretion flows and optically thin flows with low accretion rates. In
addition, we have also obtained the boundary $R_{\rm b}$ as a function of
$\dot{m}$ and $\eta$. Our results are well physically understood, and well
agree with observations and numerical simulations.

The present work is based on $\alpha=0.1$ and $l=1$. However, there exists a
critical viscosity parameter $\alpha_{\rm{crit}}$ for the structure of thermal
equilibrium solutions (Chen et al., 1995). For $\alpha>\alpha_{\rm{crit}}$, a
new topological type of equilibria appears where the ADAF branch can smoothly
connect the slim disk branch. Similarly, critical viscosity parameters should
also exist if the effects of outflows are taken into account. Thus, a new
topological type of equilibria may also exist for large values of $\alpha$. In
addition, the present study is based on $l=1$. In fact, outflows can extract
more angular momentum from the disk, which corresponds to $l>1$, such as the
centrifugally driven magnetohydrodynamic winds (Blandford & Payne, 1982). This
means more energy carried away by the outflows, which may have significant
effects on the disk structure.

A fundamental difference between neutron stars and black holes is that the
former has a hard surface whereas the latter has an event horizon. For the
ADAF case, most of the energy due to viscous heating process in the flow is
finally absorbed by the central black hole. However, if the central object is
a neutron star, the main energy generated by the viscous process will be
finally released around the hard surface. Following this spirit, the
observational evidence of event horizon was previously proposed by comparing
the radiation of quiescent state of BHXBs and neutron star X-ray binaries
(see, e.g., Figure 1 of Narayan et al., 1997). Lasota & Hameury (1998)
proposed to compare quiescent neutron star and black hole transients at
similar mass accretion rates, and the best way is to plot luminosities as a
function of the binary orbital period. By comparable orbital periods, the
luminosities of black hole systems are 2-3 orders of magnitude fainter than
neutron star systems (see, e.g., Figures 4 and 5 of McClintock et al., 2004).
We would point out that outflows may have effects on this issue, which was not
taken into account. It is known that the inner region of a disk has essential
contribution to the total radiation. According to our results, since the
outflows in the inner region is quite weak, in our opinion, the effects of
outflows on this issue may not be significant.

This work was supported by the National Key R&D Program of China under grant
2021YFA1600401, and the National Natural Science Foundation of China under
grants 11925301, 12033006, and 11973002.

## References

  * Abramowicz (1981) Abramowicz, M. A. 1981, Nature, 294, 235. doi:10.1038/294235a0
  * Abramowicz et al. (1988) Abramowicz, M. A., Czerny, B., Lasota, J. P., et al. 1988, ApJ, 332, 646. doi:10.1086/166683
  * Abramowicz et al. (1995) Abramowicz, M. A., Chen, X., Kato, S., et al. 1995, ApJ, 438, L37. doi:10.1086/187709
  * Abramowicz et al. (1996) Abramowicz, M. A., Chen, X.-M., Granath, M., et al. 1996, ApJ, 471, 762. doi:10.1086/178004
  * Blandford & Payne (1982) Blandford, R. D. & Payne, D. G. 1982, MNRAS, 199, 883. doi:10.1093/mnras/199.4.883
  * Blandford & Begelman (1999) Blandford, R. D. & Begelman, M. C. 1999, MNRAS, 303, L1. doi:10.1046/j.1365-8711.1999.02358.x
  * Bu & Gan (2018) Bu, D.-F. & Gan, Z.-M. 2018, MNRAS, 474, 1206. doi:10.1093/mnras/stx2894
  * Cao & Gu (2015) Cao, X. & Gu, W.-M. 2015, MNRAS, 448, 3514. doi:10.1093/mnras/stv269
  * Chen et al. (1995) Chen, X., Abramowicz, M. A., Lasota, J.-P., et al. 1995, ApJ, 443, L61. doi:10.1086/187836
  * Cheung et al. (2016) Cheung, E., Bundy, K., Cappellari, M., et al. 2016, Nature, 533, 504. doi:10.1038/nature18006
  * Díaz Trigo & Boirin (2016) Díaz Trigo, M. & Boirin, L. 2016, Astronomische Nachrichten, 337, 368. doi:10.1002/asna.201612315
  * Done et al. (2007) Done, C., Gierliński, M., & Kubota, A. 2007, A&A Rev., 15, 1. doi:10.1007/s00159-007-0006-1
  * Dotan & Shaviv (2011) Dotan, C. & Shaviv, N. J. 2011, MNRAS, 413, 1623. doi:10.1111/j.1365-2966.2011.18235.x
  * Du et al. (2015) Du, P., Hu, C., Lu, K.-X., et al. 2015, ApJ, 806, 22. doi:10.1088/0004-637X/806/1/22
  * Feng et al. (2019) Feng, J., Cao, X., Gu, W.-M., et al. 2019, ApJ, 885, 93. doi:10.3847/1538-4357/ab4592
  * Gladstone et al. (2009) Gladstone, J. C., Roberts, T. P., & Done, C. 2009, MNRAS, 397, 1836. doi:10.1111/j.1365-2966.2009.15123.x
  * Gu & Lu (2000) Gu, W.-M. & Lu, J.-F. 2000, ApJ, 540, L33. doi:10.1086/312864
  * Gu & Lu (2007) Gu, W.-M. & Lu, J.-F. 2007, ApJ, 660, 541. doi:10.1086/512967
  * Gu (2015) Gu, W.-M. 2015, ApJ, 799, 71. doi:10.1088/0004-637X/799/1/71
  * Homan et al. (2016) Homan, J., Neilsen, J., Allen, J. L., et al. 2016, ApJ, 830, L5. doi:10.3847/2041-8205/830/1/L5
  * Jiang et al. (2014) Jiang, Y.-F., Stone, J. M., & Davis, S. W. 2014, ApJ, 796, 106. doi:10.1088/0004-637X/796/2/106
  * Kaaret et al. (2017) Kaaret, P., Feng, H., & Roberts, T. P. 2017, ARA&A, 55, 303. doi:10.1146/annurev-astro-091916-055259
  * Kato et al. (2008) Kato, S., Fukue, J., & Mineshige, S. 2008, Black-Hole Accretion Disks — Towards a New Paradigm —, 549 pages, including 12 Chapters, 9 Appendices, ISBN 978-4-87698-740-5, Kyoto University Press (Kyoto, Japan), 2008.
  * King & Pounds (2015) King, A. & Pounds, K. 2015, ARA&A, 53, 115. doi:10.1146/annurev-astro-082214-122316
  * Kitaki et al. (2017) Kitaki, T., Mineshige, S., Ohsuga, K., et al. 2017, PASJ, 69, 92. doi:10.1093/pasj/psx101
  * Kitaki et al. (2018) Kitaki, T., Mineshige, S., Ohsuga, K., et al. 2018, PASJ, 70, 108. doi:10.1093/pasj/psy110
  * Knigge (1999) Knigge, C. 1999, MNRAS, 309, 409. doi:10.1046/j.1365-8711.1999.02839.x
  * Kosec et al. (2018) Kosec, P., Pinto, C., Walton, D. J., et al. 2018, MNRAS, 479, 3978. doi:10.1093/mnras/sty1626
  * Lasota & Hameury (1998) Lasota, J.-P. & Hameury, J.-M. 1998, Accretion processes in Astrophysical Systems: Some like it hot! - eigth AstroPhysics Conference, 431, 351. doi:10.1063/1.55920
  * Ma et al. (2019) Ma, R.-Y., Roberts, S. R., Li, Y.-P., et al. 2019, MNRAS, 483, 5614. doi:10.1093/mnras/sty3039
  * McClintock et al. (2004) McClintock, J. E., Narayan, R., & Rybicki, G. B. 2004, ApJ, 615, 402. doi:10.1086/424474
  * Middleton et al. (2011) Middleton, M. J., Sutton, A. D., & Roberts, T. P. 2011, MNRAS, 417, 464. doi:10.1111/j.1365-2966.2011.19285.x
  * Mineshige et al. (2000) Mineshige, S., Kawaguchi, T., Takeuchi, M., et al. 2000, PASJ, 52, 499. doi:10.1093/pasj/52.3.499
  * Muñoz-Darias et al. (2019) Muñoz-Darias, T., Jiménez-Ibarra, F., Panizo-Espinar, G., et al. 2019, ApJ, 879, L4. doi:10.3847/2041-8213/ab2768
  * Narayan & Yi (1994) Narayan, R. & Yi, I. 1994, ApJ, 428, L13. doi:10.1086/187381
  * Narayan & Yi (1995) Narayan, R. & Yi, I. 1995, ApJ, 444, 231. doi:10.1086/175599
  * Narayan & Yi (1995) Narayan, R. & Yi, I. 1995, ApJ, 452, 710. doi:10.1086/176343
  * Narayan et al. (1997) Narayan, R., Garcia, M. R., & McClintock, J. E. 1997, ApJ, 478, L79. doi:10.1086/310554
  * Narayan et al. (1997) Narayan, R., Kato, S., & Honma, F. 1997, ApJ, 476, 49. doi:10.1086/303591
  * Narayan et al. (1998) Narayan, R., Mahadevan, R., & Quataert, E. 1998, Theory of Black Hole Accretion Disks, 148
  * Narayan & McClintock (2008) Narayan, R. & McClintock, J. E. 2008, New A Rev., 51, 733. doi:10.1016/j.newar.2008.03.002
  * Narayan et al. (2012) Narayan, R., SÄ dowski, A., Penna, R. F., et al. 2012, MNRAS, 426, 3241. doi:10.1111/j.1365-2966.2012.22002.x
  * Nomura et al. (2020) Nomura, M., Ohsuga, K., & Done, C. 2020, MNRAS, 494, 3616. doi:10.1093/mnras/staa948
  * Nomura et al. (2016) Nomura, M., Ohsuga, K., Takahashi, H. R., et al. 2016, PASJ, 68, 16. doi:10.1093/pasj/psv124
  * Ohsuga et al. (2005) Ohsuga, K., Mori, M., Nakamoto, T., et al. 2005, ApJ, 628, 368. doi:10.1086/430728
  * Ohsuga & Mineshige (2011) Ohsuga, K. & Mineshige, S. 2011, ApJ, 736, 2. doi:10.1088/0004-637X/736/1/2
  * Ohsuga & Mineshige (2014) Ohsuga, K. & Mineshige, S. 2014, Space Sci. Rev., 183, 353. doi:10.1007/s11214-013-0017-3
  * Piran (1978) Piran, T. 1978, ApJ, 221, 652. doi:10.1086/156069
  * Quataert & Narayan (1999) Quataert, E. & Narayan, R. 1999, ApJ, 520, 298. doi:10.1086/307439
  * Sadowski et al. (2014) Sadowski, A., Narayan, R., McKinney, J. C., et al. 2014, MNRAS, 439, 503. doi:10.1093/mnras/stt2479
  * Sadowski & Narayan (2015) Sadowski, A. & Narayan, R. 2015, MNRAS, 453, 3213. doi:10.1093/mnras/stv1802
  * Shakura & Sunyaev (1973) Shakura, N. I. & Sunyaev, R. A. 1973, A&A, 24, 337
  * Shapiro et al. (1976) Shapiro, S. L., Lightman, A. P., & Eardley, D. M. 1976, ApJ, 204, 187. doi:10.1086/154162
  * Stone et al. (1999) Stone, J. M., Pringle, J. E., & Begelman, M. C. 1999, MNRAS, 310, 1002. doi:10.1046/j.1365-8711.1999.03024.x
  * Takeuchi & Mineshige (1998) Takeuchi, M. & Mineshige, S. 1998, ApJ, 505, L19. doi:10.1086/311590
  * Wang & Zhou (1999) Wang, J.-M. & Zhou, Y.-Y. 1999, ApJ, 516, 420. doi:10.1086/307080
  * Wang et al. (2013) Wang, Q. D., Nowak, M. A., Markoff, S. B., et al. 2013, Science, 341, 981. doi:10.1126/science.1240755
  * Xie & Yuan (2008) Xie, F.-G. & Yuan, F. 2008, ApJ, 681, 499. doi:10.1086/588522
  * Yuan et al. (2003) Yuan, F., Quataert, E., & Narayan, R. 2003, ApJ, 598, 301. doi:10.1086/378716
  * Yuan et al. (2012) Yuan, F., Bu, D., & Wu, M. 2012, ApJ, 761, 130. doi:10.1088/0004-637X/761/2/130
  * Yuan et al. (2012) Yuan, F., Wu, M., & Bu, D. 2012, ApJ, 761, 129. doi:10.1088/0004-637X/761/2/129
  * Yuan & Narayan (2014) Yuan, F. & Narayan, R. 2014, ARA&A, 52, 529. doi:10.1146/annurev-astro-082812-141003
  * Yuan et al. (2015) Yuan, F., Gan, Z., Narayan, R., et al. 2015, ApJ, 804, 101. doi:10.1088/0004-637X/804/2/101
  * Zahra Zeraatgari et al. (2020) Zahra Zeraatgari, F., Mosallanezhad, A., Yuan, Y.-F., et al. 2020, ApJ, 888, 86. doi:10.3847/1538-4357/ab594f


11institutetext: Bar-Ilan University, Dep. of Math. and CS, 52900,Ramat Gan,
Israel<EMAIL_ADDRESS>
# Some new Features and Algorithms for the Study of DFA

A.N. Trahtman

###### Abstract

The work presents some new algorithms realized recently in the package TESTAS.
They decide whether or not deterministic finite automaton ($DFA$) is
synchronizing, several procedures find relatively short synchronizing words
and a synchronizing word of the minimal length. We check the existence of a
coloring of directed graph that turns the graph into a synchronizing $DFA$.
The algorithm finds the coloring (better known as the road coloring) if it
exists. Otherwise, the $k$-synchronizing road coloring can be found. We use a
linear visualization of the graph of an automaton based on its structural
properties.

Open Journal of Discrete Mathematics, 2012, 2, 45-50

Keywords: finite automaton, synchronizing word, algorithm, visualization.

## Introduction

The problem of synchronization of a DFA is natural and various aspects of this
problem were touched upon the literature. Synchronization makes the behavior
of an automaton resistant against input errors since, after detection of an
error, synchronizing word resets the automaton back to its original state, as
if no error had occurred [4]. Synchronizing word stops propagation of errors
in prefix code.

The early version of the package TESTAS was described in [18] in 2003. There
exists some interest in the original algorithms of the package, sometimes even
quite exotic [6]. The features of the package are considered also favorably
for educational purposes: ”The Road Coloring Conjecture makes a nice
supplement to any discrete mathematics course” [15].

A problem with a long story is the estimation of the minimal length of a
synchronizing word, (Černy’s conjecture). Jan Černy found in 1964 [8]
$n$-state complete DFA with shortest synchronizing word of length $(n-1)^{2}$
for alphabet size $q=2$. The problem can be reduced to automata with strongly
connected graph. Černy’s conjecture together with the road coloring problem
belong to the most fascinating problems in the theory of finite automata [9],
[11], [13].

The package decides whether or not $DFA$ is synchronizing, several procedures
find relatively short synchronizing words ($O(n^{3}d)$ time complexity in the
worst case) and a synchronizing word of the minimal length (non-polynomial
algorithm) [23]. The space complexity is quadratic. These procedures were
successfully checked, in particular, in the program that has studied all
transition graphs of automata with 10 states or less in a search of long
synchronizing words. The size of the set of studied objects was about
$10^{20}$.

Imagine a map with roads which are colored in such a way that fixed sequence
of colors, called a synchronizing sequence, leads to fixed place whatever is
the starting point. Finding such a coloring is called road coloring problem.
The roads of the map are considered as edges of a directed graph.

The road coloring conjecture [1], [2], [14] was stated over forty yeas ago for
a complete strongly connected directed finite graph with constant outdegree of
all its vertices where the greatest common divisor (gcd) of lengths of all its
cycles is one. The edges of the graph being unlabelled, the task is to find a
labelling that turns the graph into a deterministic finite automaton
possessing a synchronizing word.

The problem was mentioned in ”Wikipedia” on the list of the interesting
unsolved problems in mathematics many years ago. The positive solution of the
road coloring problem [20], [21] is a basis of a polynomial-time implemented
algorithm of $O(n^{3})$ complexity in the worst case. The space complexity is
quadratic.

For arbitrary complete graph the program finds $k$-synchronizing (or
generalized [7]) road coloring [23].

The visualization of the transition graph of an automaton is an important tool
for the study of automata. A tool for the visualization of the inner structure
of a digraph is without any doubt an interesting matter, not only for the road
coloring problem but also for a wide range of applications on directed graphs
with labels on edges. For these reasons, the visual perception of the
structural properties of an automata is important.

The visualization algorithm is linear in the size of the automaton [22]. This
feature of the package is handy.

##  1 Preliminary

As usual, we regard a directed graph (digraph) with letters assigned to its
edges as a finite automaton, whose input alphabet $\Sigma$ consists of these
letters. The graph is called a transition graph of the automaton. The letters
from $\Sigma$ can be considered as colors and the assigning of colors to edges
will be called coloring.

A path in a digraph $G$ is a sequence of edges $e_{1},...,e_{k}$ such that the
end vertex of $e_{i}$ is the start vertex of $e_{i+1}$ for $i=1,2,...,k-1$.
The path is called a cycle if $e_{1}=e_{k}$.

A digraph is strongly connected if for every pair of vertices ${\bf q}$, ${\bf
p}$ there exists a path from ${\bf q}$ to ${\bf p}$. An arbitrary digraph
consists of some strongly connected components ($SCC$). An $SCC$ is sink if
from every vertex of digraph there exists a path to vertex of the $SCC$.

A finite directed strongly connected graph with constant outdegree of all its
vertices where the gcd of lengths of all its cycles is one will be called an
$AGW$ graph (as introduced by Adler, Goodwyn and Weiss).

An automaton is deterministic if no state has two outgoing edges of the same
color. In complete automaton each state has outgoing edges of any color.

If there exists a path in an automaton from the state $\bf p$ to the state
$\bf q$ and the edges of the path are consecutively labelled by
$\sigma_{1},...,\sigma_{k}$, then for $s=\sigma_{1}...\sigma_{k}\in\Sigma^{+}$
we shall write ${\bf q}={\bf p}s$.

Let $Ps$ be the set of states ${\bf p}s$ for ${\bf p}\in P$ $s\in\Sigma^{+}$.
For the transition graph $\Gamma$ of an automaton let $\Gamma s$ denote the
map of the set of states of the automaton.

A word $s\in\Sigma^{+}$ is called a synchronizing word of the automaton with
transition graph $\Gamma$ if $|\Gamma s|=1$.

A coloring of a directed finite graph is synchronizing if the coloring turns
the graph into a deterministic finite automaton possessing a synchronizing
word.

Let the integer $q$ denote the size of alphabet and let $n$ be the number of
nodes.

##  2 Algorithms for finding synchronizing word

The package TESTAS presents three distinct versions of polynomial time
algorithm for synchronizing word based on different approaches [19], [23]. The
algorithms have $O(n^{3}d)$ time complexity in the worst case.

All synchronizing words obtained in a lot of experiments have lengths near
minimal. In particular, no synchronizing word of length greater than $n^{2}$
was found.

###  2.1 The algorithm for synchronizing word of minimal length

The algorithm is a revision of an algorithm for finding the syntactic
semigroup of an automaton on the base of its transition graph [24]. Let us
notice that the size of the semigroup is not polynomial in the graph size and
the problem to find synchronizing word of minimal length is NP-hard [11].

We find first some synchronizing word $s$ of length $L$ using mention above
algorithms. Foe every left subword $s_{i}$ of $s$ of length $i$ let us keep
the set $\Gamma s_{i}$ with its size $|\Gamma s_{i}|$. The subsets of states
of $\Gamma$ are presented by vectors of units and zeroes, the units correspond
to the subset states.

The let us consider the mappings of the graph of the automaton induced by the
letters of the alphabet of the labels are considered. They correspond to
semigroup elements. For every letter $\alpha$ (and a word $t$ $\Gamma\alpha$
(and $\Gamma t$) is a subset of states can be presented by vector of units and
zeroes where the units correspond to the states of subset.

Let us consider the sequence of these mappings (or vectors). First vector
$v_{0}$ of the sequence consists of units and presents all states of $\Gamma$.
For every vector $v_{i}$ of the set of states $S_{v_{i}}$ from the sequence we
consider the set $S_{v_{i}}\alpha$ for every letter $\alpha$ of the alphabet
and the corresponding vector $v_{i}\alpha$.

With every vector $v_{i}$ we connect the former vector, the letter that has
created it, size of $S_{v_{i}}$ and the length $l(v_{i})$ of the word $u$ such
that $\Gamma u=S_{v_{i}}$. So for $v_{i}\alpha$ the former vector is $v_{i}$,
the letter is $\alpha$ and $l(v_{i}\alpha)=l(v_{i})+1$.

The vector $v_{i}\alpha$ is excluded from the study if $l(v_{i}\alpha)>L$
because the corresponding word could not be a part of a minimal synchronizing
word.

We compare the vector $v_{i}\alpha$ with every vector $w$ of the sequence if
$l(v_{i}\alpha)\leq L$. If $S_{w}\subseteq S_{v_{i}}\alpha$ the vector
$v_{i}\alpha$ also is excluded from the study. We compare the vector
$v_{i}\alpha$ with every vector of the set $s_{j}$ for $j<i$ if
$l(v_{i}\alpha)\leq L$. If $S_{s_{j}}\subseteq S_{v_{i}}\alpha$ for some $j$
then the vector $v_{i}\alpha$ also is excluded from the study.

Otherwise, $v_{i}\alpha$ is added to the sequence. Thus for vector $v_{i}$ we
need $(i-1)d+|s|d$ operations and together with former vectors one has
$i(i-1+|s|)d$ operations. Every vector of the sequence is studied once.

The size of the syntactic semigroup of the automaton is in general not
polynomial in the size of the transition graph. Therefore the time and space
complexity of the algorithm is not polynomial in the size of the graph in the
worst case.

With any vector let us connect the previous vector and its letter. On this
way, the path on the graph of the automaton can be constructed. Any
synchronizing mapping of the set of vertices presents a synchronizing word.
The word can be restored from letters connected with vectors.

The algorithm founds a list of all words (elements of syntactic semigroup) of
length $k$ where $k$ is growing. The first synchronizing word of the list is a
synchronizing word of the minimal length.

The algorithm is valid for both complete and non-complete graphs. The time
complexity of the considered procedure is $O(|\Gamma|d|N|^{2})$ with
$O(|\Gamma||N|)$ space complexity. $N$ is here syntactic semigroup of the
graph $\Gamma$ over alphabet of size $d$.

##  3 The algorithm for synchronizing coloring

The positive solution of the road coloring problem [20], [21] is a basis of a
polynomial-time implemented algorithm of $O(n^{3})$ complexity in the worst
case. The study uses the following theorems.

###### Theorem 1

_[20]_ Let every vertex of a strongly connected directed graph $\Gamma$ have
the same number of outgoing edges. Then $\Gamma$ has synchronizing coloring if
and only if the greatest common divisor of lengths of all its cycles is one.

###### Theorem 2

_[9]_ _[20]_ Let us consider a coloring of an $AGW$ graph $\Gamma$. Let $\rho$
be the transitive and reflexive closure of the stability relation on the
obtained automaton. Then $\rho$ is a congruence relation, $\Gamma/\rho$ is
also an $AGW$ graph and a synchronizing coloring of $\Gamma/\rho$ implies a
synchronizing recoloring of $\Gamma$.

The input of the algorithm is a graph with an arbitrary coloring. The
algorithm changes some colors of edges of the graph. At the end of the work of
the implemented version, on the screen appears the layout of the graph without
coloring and then in few seconds of artificial delay the desired coloring
appears.

The work [5] presented an algorithm of $O(n^{2})d$ time complexity. We still
have no information about its implementation.

###  3.1 The algorithm for $k$-synchronizing coloring

A $k$-synchronizing word of a deterministic automaton is a word in the
alphabet of colors at its edges that maps the state set of the automaton at
least on $k$-element subset. A coloring of edges of a directed strongly
connected finite graph of a uniform outdegree (constant outdegree of any
vertex) is $k$-synchronizing if the coloring turns the graph into a
deterministic finite automaton possessing a $k$-synchronizing word.

The solution of the problem of $k$-synchronizing coloring based on the method
from [20] appeared first in [5] and repeated later independently in [7].

Some consequences for coloring of an arbitrary finite digraph as well as for
coloring of such a graph of uniform outdegree are a matter of the algorithm.
The minimal value of $k$ for $k$-synchronizing coloring is found by the
algorithm for any finite digraph. The value of $k$ is equal to the great
common divisor of lengths of cycles of the digraph. So we obtain a partially
synchronizing coloring.

The polynomial-time algorithm for $k$-synchronizing coloring has also
$O(n^{3})d$ time complexity at worst and quadratic space complexity [23].

##  4 The approach to the visualization of digraph

The visualization of the transition graph of the automaton is an important
help tool of the study of automata. The visibility of inner structure of a
digraph without doubt is a matter of interest not only for the road coloring,
the range of the application may be significantly wider and includes all
directed graphs with labels on edges.

Crucial role in the visualization plays the correspondence of the layout to
the human intuition, the perception of the structure properties of the graph
and the rapidity of the appearance of the image. The automatically drawn
graphical image must resemble the last one of a human being and present the
structure of the graph. We use and develop for this goal some known approaches
[17], [25].

Our main objective is a visual representation of a directed graph with labels
on its edges and, in particular, of the transition graph of a deterministic
finite automaton based on the structure properties of the graph. Among the
important visual objects of a digraph one can mention paths, cycles, strongly
connected components, cliques, bunches etc. These properties reflect the inner
structure of the digraph. The pictorial diagram demonstrates the graph
structure highlighting strongly connected components, paths and cycles. So
this kind of visualization can be considered as a structure visualization.
This algorithm successfully solves a whole series of tasks of the disposal of
the objects.

We choose here a cyclic layout [17], [25]. According to this approach the
vertices are placed at the periphery of a circle. Our modification of the
approach considered two levels of circles, the first level consists of
strongly connected components, the second level corresponds to the whole graph
with $SCC$ at the periphery of the circle. The visual placement is based on
the structure of the graph considered as a union of the set of strongly
connected components.

Clearly, the curve edges (used, for instance, in the package GraphViz [10],
[16]) hinder to recognize the cycles and paths. Therefore, we use only direct
and, hopefully, short edges. We have changed some priorities of the layout
and, in particular, eliminate the goal of reducing the number of intersections
of the edges as it was an important aim in some algorithms [16]. The
intersections of the edges are even not considered in our algorithm. This
approach gives us an opportunity to simplify essentially the procedure and to
reduce its complexity. Our main intent is only not to stir by the
intersections of the edges to conceive the structure of the graph. The
intersections are placed in our algorithm far from the vertices due to the
cyclic layout [25], [17] we use. The area of vertices differs of the area of
the majority of intersections.

The algorithm for the visualization is linear in the size of the automaton.
Thus the linearity of the algorithm is comfortably and important.

###  4.1 Visualization algorithm

The layout of the deterministic graph is demonstrated by a high-speed linear
program.

The strongly connected components (SCC) are of special significance in the
algorithm. Thus our first step is the eduction and selection of the $SCC$. The
quick linear algorithm for finding $SCC$ [3] is implemented in the program.

According to the cyclic approach, all $SCC$ are placed on the periphery of a
big circle and are ordered according to the size [22]. The vertices of $SCC$
are arranged in a circle of $SCC$ in the graph layout. So strongly connected
components can be easily recognized by the observer.

The periphery of a circle of $SCC$ is the most desirable area for placing the
edges because the edges in this case are relatively short. We choose the order
of the vertices of the $SCC$ on the circle according to this purpose. The
length of some edges can be reduced in a such way. It also helps to recognize
paths and cycles on the screen.

From the other hand, the edges between distinct $SCC$ are relatively longer
than the inner edges of strongly connected components.

The problem of the placing of the labels near corresponding edges is sometimes
very complicated and frequently the connection between the edge and its label
is not clear. Our solution is to use colors on the edges instead of labels and
exclude the placing of labels.

The set of loops of arbitrary vertex is placed around the vertex with some
shift that depends on the size of the set. The problem of parallel edges is
solved analogously, the origins of the edges must belong to the vertex. The
complexity of the algorithm shows the following

###### Lemma 4.1

The time and space complexity of the visualization algorithm described above
is linear in the sum of states and edges of the transition graph of the
automaton.

The transition graph of any deterministic finite automaton is accepted by the
visualization algorithm. The transitions graphs of non-complete automata also
can be reproduced.

##  5 Input of data in the package

The input file is an ordinary txt file for all algorithms used in the package
TESTAS. We open the source file and then check different properties from menu
bar. The graph is shown on the display by help of a rectangular table. More
precisely, transition graph of an automaton as well as an arbitrary directed
graph with distinct labels on outgoing edges of every vertex is presented by
the matrix (Cayley graph):

vertices X labels

First two numbers in input file are the size of alphabet of labels and the
number of vertices. The integers from 0 to n-1 denote the vertices. i-th row
is a list of successors of i-th vertex according to the label in the column
(number of the vertex from the end of edge with label from the j-th column and
beginning in i-th state is placed in the (i,j) cell).

The User defines the data: the number of nodes, size of the alphabet of edge
labels and the values in the matrix. For example, the input 2 6 1 0 2 1 0 3 5
2 3 2 4 5 presents the Cayley graph with 2 labels and 6 vertices and the next
input 2 5 1 0 2 1 ; 3 5 ; 3 ; presents the Cayley graph with 2 labels and 5
vertices. The values are divided by a gap. The semicolon corresponds to empty
cell of the table.

| letter $a$ | letter $b$
---|---|---
$vertex$ 0 | 1 | 0
$vertex$ 1 | 2 | 1
$vertex$ 2 | 0 | 3
$vertex$ 3 | 5 | 2
$vertex$ 4 | 3 | 2
$vertex$ 5 | 4 | 5

$and$ letter $a$ letter $b$ $vertex$ 0 1 0 $vertex$ 1 2 1 $vertex$ 2 3
$vertex$ 3 $vertex$ 4 3 2

\begin{picture}(50.0,78.0)\end{picture}

021534

aaaa

aa

b

b

bbb

\begin{picture}(45.0,78.0)\end{picture} aaa

02134

b

b

b

b

An important verification tool of the package is the possibility to study the
semigroup of an automaton. The program finds syntactic semigroup of the
automaton, its size and generators. The semigroup is presented by a quadratic
table of the form elements X generators (letters). In the cell $(i,j)$ is a
product of element $i$ and generator $j$. The first line of the table presents
the size of the semigroup and the number of generators.

## References

  * [1] R.L. Adler, L.W. Goodwyn, B. Weiss. 1977, Equivalence of topological Markov shifts, Israel J. of Math. 27, 49-63.
  * [2] R.L. Adler, B. Weiss. 1970, Similarity of automorphisms of the torus, Memoirs of the Amer. Math. Soc. 98, Providence, RI.
  * [3] A. Aho, J. Hopcroft, J. Ulman. The Design and Analisys of Computer Algorithms, Addison-Wesley, 1974.
  * [4] Béal M.P., Czeizler E., Kari J., Perrin D. 2008, Unambiguous automata. Math. Comput. Sci., 1, 625-638.
  * [5] M.P. Béal, and D. Perrin, A quadratic algorithm for road coloring, arXiv: 0803.0726v2 [cs.DM], 2008.
  * [6] Robert C. Berwick, Kazuo Okanoya3, Gabriel J.L. Beckers and Johan J. Bolhuis. 2011, Songs to syntax: the linguistics of birdsong .Trends in Cognitive Science, V15, I.3, 113-121
  * [7] G. Budzban and Ph. Feinsilver, 2011, The generalized road coloring problem and periodic digraphs. Appl. Alg. in Eng., Comm. and Comput., V 22, N 1, 21-35.
  * [8] J. Černy. 1964, Poznamka k homogenym eksperimentom s konechnymi automatami, _Math.-Fyz. Čas._ , 14(1964), 208-215.
  * [9] K. Culik II, J. Karhumaki, J. Kari. A note on synchronized automata and Road Coloring Problem. Developments in Language Theory (5th Int. Conf., Vienna, 2001), J. of Found. Comput. Sci., 13(2002), 459-471.
  * [10] J. Ellson, E. Gansner, L. Koutsofios, et al..2002, GraphViz - open source graph drawing tools, Graph Drawing, 2265, 483-484.
  * [11] A. Mateescu, A. Salomaa, 1999, Many-Valued Truth Functions, Černy’s Conjecture and Road Coloring. Bull. of European Ass. for TCS, 68, 134-148.
  * [12] D. Perrin, M.P. Schǔtzenberger. 1992,Synchronizing prefix codes and automata, and the road coloring problem, In Symbolic Dynamics and Appl., Contemp. Math., 135, 295-318.
  * [13] Pin J.E. On two combinatorial problems arising from automata theory, Annals of Discrete Mathematics, 1983, 17: 535-548.
  * [14] B.A. Rubshtein. 1974, Generating partitions of Markov endomorphisms. Func. Anal. Appl., vol. 8, 84-85.
  * [15] J. V. Rauff, 2009, Way back from anywhere: exploring the road coloring conjecture. Math. and Comput. Education. 01.
  * [16] M.Simonato, 2004, An Introduction to GraphViz.
  * [17] JM. Six, IG. Tollis, 1999, A framework for user-grouped circular drawings Lect. Notes in Comp. Sci., 1731, 107-116.
  * [18] A.N. Trahtman, 2003, A package TESTAS for checking some kinds of testability. Lect. Notes in Comput. Sci., 2608, 228-232.
  * [19] A.N. Trahtman, 2006, An eficient algorithm finds noticeable trends and examples concerning the Cerny conjecture. Lect. Notes in Comp. Sci, Springer, MFCS 4162(2006), 789-800.
  * [20] A.N. Trahtman. 2008, Synchronizing Road Coloring. 5-th IFIP WCC-TCS, Springer, 273, 43-53.
  * [21] A.N. Trahtman The road coloring problem. 2009, Israel Journal of Math., 172(1), 51-60.
  * [22] A.N. Trahtman, Bauer T., Cohen N. 2010, Linear visualization of a Road Coloring. Proc of 9 Cologne Twente workshop on graphs and Comb. Optim., 13-16.
  * [23] Trahtman A. N. A Partially Synchronizing Coloring. CSR-2010, LNCS 6072, Springer, 2010, 362-370
  * [24] A.N. Trahtman, 2003, Verification of algorithms for checking some kinds of testability. In Algebraic Methods in Language Processing, TWLT 21, eds. F.Spoto, G. Scollo, A. Nijholt. 253-263.
  * [25] R. Wiese, M. Eiglsperger, M. Kaufmann. 2002, A framework for circular drawings of networks. Lect. Notes in Comp. Sci., 2265, 453-454.


sources have been observed multiple times. Here we show quantitatively the
number of spectra for the AGN in the SOUX sample. We use astroquery (Ginsburg
et al. 2019) to search for all optical spectra of our 696 AGN in SDSS DR14.
The query performs a 2′′-radius search around the input coordinates (taken
from the Pâris et al. 2018 and R17 catalogues) for sources with spectroscopy.
We checked that all spectra returned by the query relate to the same object
(i.e. they have the same ObjID) and that the specific spectrum analysed in
this work is one of those. No results were returned by astroquery for seven
AGN; for these we manually checked for all spectra in the SDSS Science Archive
Server777https://dr14.sdss.org/optical/spectrum/search. We show the
distribution of the number of spectra in Fig. 24. Whilst 83 per cent of the
AGN in our sample have only one optical spectrum, 17 have many ($>49$). The
wealth of optical data for these AGN may be explored further in future
studies.

Figure 24: The number of SDSS optical spectra ($N_{\mathrm{spec}}$) available
for the 696 AGN in our sample, up to and including DR14. The majority of our
sample (83 per cent) have only one spectrum, but a small number have $\approx
50$ spectra.

##  Appendix C Quality flags

We assess the quality of measurements determined from the spectral fits by
assigning a quality flag. If no issues are raised the quality flag value is 0
and the measurement may be considered to be reliable. The quality flags are
integer numbers which are the sum
$2^{\mathrm{Bit~{}0}}+2^{\mathrm{Bit~{}1}}...+2^{\mathrm{Bit}~{}n}$ for set
bits. The bit numbers and the conditions for setting them are listed in Tables
8 and 9. For example, if the fractional uncertainty of the FWHM of a measured
broad H $\upbeta$ line is greater than 2 and the uncertainty on the velocity
offset of the line is greater than 1000 km s-1 then bits 5 and 8 are set and
the H $\upbeta$ quality flag has the value $2^{5}+2^{8}=32+256=288$.

Table 8: Quality flags for the fitted continuum

Bit | Condition
---|---
- | no quality flags raised
0 | the luminosity or its uncertainty are zero, NaN or infinite
1 | fractional uncertainty of the luminosity > 1.5
2 | the continuum slope or its uncertainty are zero, NaN or infinite
3 | the continuum slope has reached the lower or upper limit in the fit
4 | the uncertainty on the continuum slope > 0.3
5 | the continuum fit $\chi^{2}_{\nu}>50$

Table 9: Quality flags for the fitted emission lines

Bit | Condition
---|---
- | no quality flags raised
0 | S/N in the continuum around the line < 3
1 | the luminosity or its uncertainty are zero, NaN or infinite
2 | fractional uncertainty of the luminosity > 1.5
3 | the FWHM or its uncertainty are zero, NaN or infinite
4 | the $\mathrm{FWHM}\leqslant 910$ km s-1
5 | the fractional uncertainty of the FWHM > 2
6 | the velocity offset or its uncertainty are zero, NaN or infinite
7 | the velocity offset has reached the lower or upper limit in the fit
8 | the uncertainty on the velocity offset > 1000 km s-1

##  Appendix D Table information

We have made available online a table containing the details (RA, Dec., $z$,
etc.), measurements (emission line widths, optical and X-ray continuum
luminosities etc.) and derived quantities (black hole masses,
$\alpha_{\mathrm{ox}}$ etc.) of the 696 AGN in the SOUX sample. Table 10 gives
an overview of the columns of that table.

Table 10: The SOUX AGN Sample - Column information for the table containing
the details, measurements and derived quantities for the 696 AGN

# | Column name | Units |  Description
---|---|---|---
Source and SDSS optical spectrum details:
1 | SDSS_ID |  |  Unique SDSS spectrum identifier (PLATE-MJD-FIBER)
2 | RA | Degrees |  Right Ascension (J2000)
3 | DEC | Degrees |  Declination (J2000)
4 | Z |  |  Spectroscopic redshift
5 | DR14Q |  |  0: source is not in the SDSS DR14 quasar catalog; 1: source is in the SDSS DR14 quasar catalog
6 | R17 |  |  0: source is not in the R17 NLS1 catalog; 1: source is in the R17 NLS1 catalog
7 | SN_RATIO_CONT |  |  Median S/N sampled in emission-line free windows of the spectrum
8 | MIN_WAVE | Å |  Shortest rest-frame wavelength covered in the optical spectrum
9 | MAX_WAVE | Å |  Longest rest-frame wavelength covered in the optical spectrum
UV-optical continuum measurements:
10 | LOG_L1350 | erg s-1 |  Logarithm of the continuum luminosity at 1350 Å (rest-frame) from the SDSS spectrum
11 | LOG_L1350_ERR | erg s-1 |  Uncertainty on LOG_L1350_ERR
12 | QUALITY_L1350 |  |  Quality flag on LOG_L1350 (see Table 8)
13 | LOG_L2500_SPEC | erg s-1 |  Logarithm of the continuum luminosity at 2500 Å (rest-frame) from the SDSS spectrum
14 | LOG_L2500_SPEC_ERR | erg s-1 |  Uncertainty on LOG_L2500_SPEC
15 | LOG_L2500_PHOT_OM | erg s-1 |  Logarithm of the continuum luminosity at 2500 Å (rest-frame) from XMM-Newton OM photometry
16 | LOG_L2500_PHOT_OM_ERR | erg s-1 |  Uncertainty on LOG_L2500_PHOT_OM
17 | LOG_L2500_PHOT_SDSS | erg s-1 |  Logarithm of the continuum luminosity at 2500 Å (rest-frame) from SDSS photometry
18 | LOG_L2500_PHOT_SDSS_ERR | erg s-1 |  Uncertainty on LOG_L2500_PHOT_SDSS
19 | LOG_L2500_ALPHA_OX |  |  Which $L_{2500}$ measurement was used to calculate ALPHA_OX (#86)
20 | LOG_L3000 | erg s-1 |  Logarithm of the continuum luminosity at 3000 Å (rest-frame) from the SDSS spectrum
21 | LOG_L3000_ERR | erg s-1 |  Uncertainty on LOG_L3000_ERR
22 | QUALITY_L3000 |  |  Quality flag on LOG_L3000 (see Table 8)
23 | LOG_L4400_SPEC | erg s-1 |  Logarithm of the continuum luminosity at 4400 Å (rest-frame) from the SDSS spectrum
24 | LOG_L4400_SPEC_ERR | erg s-1 |  Uncertainty on LOG_L4400_SPEC
25 | LOG_L4400_PHOT_OM | erg s-1 |  Logarithm of the continuum luminosity at 4400 Å (rest-frame) from XMM-Newton OM photometry
26 | LOG_L4400_PHOT_OM_ERR | erg s-1 |  Uncertainty on LOG_L4400_PHOT_OM
27 | LOG_L4400_PHOT_SDSS | erg s-1 |  Logarithm of the continuum luminosity at 4400 Å (rest-frame) from SDSS photometry
28 | LOG_L4400_PHOT_SDSS_ERR | erg s-1 |  Uncertainty on LOG_L4400_PHOT_SDSS
29 | LOG_L4400_R_LOUD |  |  Which $L_{4400}$ measurement was used to calculate R_LOUD (#90)
30 | LOG_L5100 | erg s-1 |  Logarithm of the continuum luminosity at 5100 Å (rest-frame) from the SDSS spectrum
31 | LOG_L5100_ERR | erg s-1 |  Uncertainty on LOG_L5100_ERR
32 | QUALITY_L5100 |  |  Quality flag on LOG_L5100 (see Table 8)
Broad emission line measurements:
33 | FWHM_HA_BR | km s-1 |  Full width at half maximum of the broad H $\upalpha$ emission line
34 | FWHM_HA_BR_ERR | km s-1 |  Uncertainty on FWHM_HA_BR
35 | PEAK_HA_BR | Å |  Peak wavelength of the broad H $\upalpha$ emission line
36 | PEAK_HA_BR_ERR | Å |  Uncertainty on PEAK_HA_BR
37 | EW_HA_BR | Å |  Equivalent width of the broad H $\upalpha$ emission line
38 | EW_HA_BR_ERR | Å |  Uncertainty on EW_HA_BR
39 | LOGL_HA_BR | erg s-1 |  Logarithm of the luminosity of the broad H $\upalpha$ emission line
40 | LOGL_HA_BR_ERR | erg s-1 |  Uncertainty on LOGL_HA_BR
41 | QUALITY_HA |  |  Quality flag on the broad H $\upalpha$ emission line (see Table 9)
42 | FWHM_HB_BR | km s-1 |  Full width at half maximum of the broad H $\upbeta$ emission line
43 | FWHM_HB_BR_ERR | km s-1 |  Uncertainty on FWHM_HB_BR
44 | PEAK_HB_BR | Å |  Peak wavelength of the broad H $\upbeta$ emission line
45 | PEAK_HB_BR_ERR | Å |  Uncertainty on PEAK_HB_BR
46 | EW_HB_BR | Å |  Equivalent width of the broad H $\upbeta$ emission line
47 | EW_HB_BR_ERR | Å |  Uncertainty on EW_HB_BR
48 | LOGL_HB_BR | erg s-1 |  Logarithm of the luminosity of the broad H $\upbeta$ emission line
49 | LOGL_HB_BR_ERR | erg s-1 |  Uncertainty on LOGL_HB_BR
50 | QUALITY_HB |  |  Quality flag on the broad H $\upbeta$ emission line (see Table 9)
51 | BALMER_SOURCE |  |  K23: Balmer lines measurements from this work; R20: Balmer lines measured by R20

Table 10: Table 10 continued

# | Column name | Units |  Description
---|---|---|---
52 | FWHM_MGII_BR | km s-1 |  Full width at half maximum of the broad Mg ii emission line
53 | FWHM_MGII_BR_ERR | km s-1 |  Uncertainty on FWHM_MGII_BR
54 | PEAK_MGII_BR | Å |  Peak wavelength of the broad Mg ii emission line
55 | PEAK_MGII_BR_ERR | Å |  Uncertainty on PEAK_MGII_BR
56 | EW_MGII_BR | Å |  Equivalent width of the broad Mg ii emission line
57 | EW_MGII_BR_ERR | Å |  Uncertainty on EW_MGII_BR
58 | LOGL_MGII_BR | erg s-1 |  Logarithm of the luminosity of the broad Mg ii emission line
59 | LOGL_MGII_BR_ERR | erg s-1 |  Uncertainty on LOGL_MGII_BR
60 | QUALITY_MGII |  |  Quality flag on the broad Mg ii emission line (see Table 9)
61 | MGII_SOURCE |  |  K23: Mg ii measurements from this work; R20: Mg ii measured by R20
62 | MGII_SEP |  |  0: Mg ii region modelled in global fit to full spectrum; 1: Mg ii region modelled separately to Balmer line regions (see Section 2.3)
63 | LINEWIDTH |  |  N: narrow-line type 1 AGN; B: broad-line type 1 AGN (see Section 2.3.1)
Black hole mass estimates:
64 | MASS_HA_5100_MR16 | M⊙ |  BH mass estimate from FWHM_HA_BR and LOG_L5100 using the relation of MR16
65 | MASS_HA_HA_MR16 | M⊙ |  BH mass estimate from FWHM_HA_BR and LOGL_HA_BR using the relation of MR16
66 | MASS_HB_5100_MR16 | M⊙ |  BH mass estimate from FWHM_HB_BR and LOG_L5100 using the relation of MR16
67 | MASS_HB_HB_G10 | M⊙ |  BH mass estimate from FWHM_HB_BR and LOGL_HB_BR using the relation of Greene et al. (2010)
68 | MASS_MGII_3000_MR16 | M⊙ |  BH mass estimate from FWHM_MGII_BR and LOG_L3000 using the relation of MR16
69 | MASS_MGII_MGII_W18 | M⊙ |  BH mass estimate from FWHM_MGII_BR and LOGL_MGII_BR using the relation of Woo et al. (2018)
70 | MASS_HA_5100_K23 | M⊙ |  BH mass estimate from FWHM_HA_BR and LOG_L5100 using the relation found in this work
71 | MASS_HA_HA_K23 | M⊙ |  BH mass estimate from FWHM_HA_BR and LOGL_HA_BR using the relation found in this work
72 | MASS_HB_HB_K23 | M⊙ |  BH mass estimate from FWHM_HB_BR and LOGL_HB_BR using the relation found in this work
73 | MASS_MGII_3000_K23 | M⊙ |  BH mass estimate from FWHM_MGII_BR and LOG_L3000 using the relation found in this work
74 | MASS_MGII_MGII_K23 | M⊙ |  BH mass estimate from FWHM_MGII_BR and LOGL_MGII_BR using the relation found in this work
75 | Q_MASS_HA_5100 |  |  Quality flag on H $\upalpha$-5100 $\mathrm{\SIUnitSymbolAngstrom}$ mass: $=1$ unless QUALITY_HA and QUALITY_L5100 are both 0
76 | Q_MASS_HB_5100 |  |  Quality flag on H $\upbeta$-5100 $\mathrm{\SIUnitSymbolAngstrom}$ mass: $=1$ unless QUALITY_HB and QUALITY_L5100 are both 0
77 | Q_MASS_MGII_3000 |  |  Quality flag on Mg ii-3000 $\mathrm{\SIUnitSymbolAngstrom}$ mass: $=1$ unless QUALITY_MGII and QUALITY_L3000 are both 0
78 | LOG_MASS_PREF_VALUE | M⊙ |  Logarithm of our preferred BH mass estimate
79 | LOG_MASS_PREF_SOURCE |  |  Which BH mass estimate is the preferred one
Multiwavelength measurements:
80 | XMM_OBSID |  |  The XMM-Newton Observation ID for the X-ray and OM photometric data
81 | XMM_SRCID |  |  The unique X-ray source number taken from the XMM-Newton catalog
82 | LOG_L2KEV | erg s-1 Hz-1 |  Logarithm of $L_{\nu}(2~{}\mathrm{keV~{}\mbox{rest-frame}})$ estimated from the XMM-Newton band fluxes (see Section 3.2)
83 | LOG_L2KEV_ERR | erg s-1 Hz-1 |  Uncertainty on LOG_L2KEV
84 | GAMMA_X |  |  Estimated X-ray photon index (see Section 3.2)
85 | GAMMA_X_ERR |  |  Uncertainty on GAMMA_X
86 | ALPHA_OX |  |  Optical-X-ray energy index $\alpha_{\mathrm{ox}}$ calculated from LOG_L2500_ALPHA_OX and LOG_L2KEV
87 | ALPHA_OX_ERR |  |  Uncertainty on ALPHA_OX
88 | LOG_L5GHZ | W Hz-1 |  Logarithm of $L_{\nu}(5~{}\mathrm{GHz~{}\mbox{rest-frame}})$ estimated from the FIRST radio flux (see Section 3.3)
89 | LOG_L5GHZ_ERR | W Hz-1 |  Uncertainty on L5GHZ
90 | R_LOUD |  |  Radio loudness calculated from LOG_L4400_R_LOUD and LOG_L5GHZ
91 | R_LOUD_FLAG |  |  RL: radio-loud; RQ: radio-detected and radio-quiet; RQu: radio-undetected and radio-quiet; RU: radio-undetected and undetermined radio-loudness; $-$999: outside FIRST footprint or no $L_{4400}$