# Modulating Spin Current Induced Effective Damping in $\beta-W/Py$
Heterostructures by a Systematic Variation in Resistivity of the Sputtered
Deposited $\beta-W$ films

Soumik Aon  Sayani Pal, Subhadip Manna, Chiranjib Mitra  Partha Mitra
Department of Physical Sciences, Indian Institute of Science Education and
Research, Kolkata, Mohanpur 741246, India

###### Abstract

Utilizing the spin-induced pumping from a ferromagnet (FM) into a heavy metal
(HM) under the ferromagnetic resonance (FMR) condition, we report an
enhancement in effective damping in $\beta$\- W/Py bilayers by systematically
varying resistivity ($\rho_{W}$) of $\beta$-W films. Different resistivity
ranging from 100 $\mu\Omega$-cm to 1400 $\mu\Omega$-cm with a thickness of 8
nm can be achieved by varying the argon pressure ($P_{Ar}$) during the growth
by the method of sputtering. The coefficient of effective damping
$\alpha_{eff}$ is observed to increase from 0.010 to 0.025 with $\rho_{W}$,
which can be modulated by $P_{Ar}$. We observe a modest dependence of
$\alpha_{eff}$ on the sputtering power ($p_{S}$) while keeping the $P_{Ar}$
constant. $\alpha_{eff}$ dependence on both $P_{Ar}$ and $p_{S}$ suggests that
there exists a strong correlation between $\alpha_{eff}$ and $\rho_{W}$. It is
thus possible to utilize $\rho_{W}$ as a tuning parameter to regulate the
$\alpha_{eff}$, which can be advantageous for faster magnetization dynamics
switching. The thickness dependence study of Py in the aforementioned bilayers
manifests a higher spin mixing conductance ($g^{\uparrow\downarrow}_{eff}$)
which suggests a strong spin pumping from Py into the $\beta$-W layer. The
effective spin current ($J_{S(eff)}$) is also evaluated by considering the
spin-back flow in this process. Intrinsic spin mixing conductance
($g^{\uparrow\downarrow}_{W}$) and spin diffusion length ($\lambda_{SD}$) of
$\beta$-W are additionally investigated using thickness variations in
$\beta$-W. Furthermore, the low-temperature study in $\beta$-W/Py reveals an
intriguing temperature dependence in $\alpha_{eff}$ which is quite different
from $\alpha_{b}$ of single Py layer and the enhancement in $\alpha_{eff}$ at
low temperature can be attributed to the spin-induced pumping from Py layer
into $\beta$-W.

##  I Introduction

Spin transport in metallic heterostructures is a growing topic of interest
with the advent of new devices which utilize the phenomena like spin hall
effect (SHE) [1, 2, 3, 4, 5, 6], spin transfer torque (STT) [7], spin-orbit
torque (SOT) [8], spin pumping [9, 10, 11, 12, 13, 14, 15]. The spin-orbit
coupling [16] is the most significant phenomenon causing these effects as it
couples the charge $\&$ spin of an electron and controls the interconversion
between charge and spin current. In the context of metallic multilayered
devices, ferromagnetic resonance (FMR) induced spin pumping provides a
reliable technique to inject pure spin current into the non-magnetic (NM)
layer even without applying any charge current. Spin pumping is a phenomenon
in which the magnetization precession in the ferromagnetic metal (FM)
transfers the spin angular momentum into the NM layer, resulting in the
generation of a spin current. According to the law of conservation of angular
momentum, the spins ejected by spin current exert a torque on the FM layer
[17], leading to the enhancement of the coefficient of effective damping
($\alpha_{eff}$), which can be evaluated by studying and analyzing the FMR
absorption spectra.

Magnetization dynamics of the FM/NM bilayer can be understood using the
modified Landau-Lifsitz-Gilbert (LLG) equation as described by [18].

$\frac{d\vec{M}}{dt}=-\gamma(\vec{M}\times\vec{B}_{eff})+\frac{\alpha_{b}}{M_{s}}(\vec{M}\times\frac{d\vec{M}}{dt})+\frac{\gamma}{V}\vec{J}_{S}$
(1)

The conservative precessional term in a FM, where magnetization $\vec{M}$
precesses around the effective magnetic field $\vec{B}_{eff}$, is described by
the first term on the right-hand side of Eq. 1. However, the second term
corresponds to the Gilbert damping with a damping coefficient $\alpha_{b}$
which quantifies the spin relaxation mechanism in bulk FM. The third term
represents the spin pumping effect that results in a spin current injection
from a FM layer into a NM layer. The spin current density $\vec{J}_{S}$ can be
expressed as

$\vec{J}_{S}=\frac{\hbar A}{4\pi
M^{2}_{S}}g^{\uparrow\downarrow}_{eff}(\vec{M}\times\frac{d\vec{M}}{dt})$ (2)

which, leads to an additional damping ($\alpha_{SP}$), where the effective
damping is expressed as [9]: $\alpha_{eff}=\alpha_{b}+\alpha_{SP}$. Spin-orbit
coupling (SOC) is a key factor in the enhancement of damping caused by spin
pumping into the NM layer. The best candidates are the heavy metals (HM) and
topological insulators (TI) [19] as they have high SOC. Platinum has been
extensively explored as HM layer in FM/HM heterostructures for spin pumping
experiments [20, 21, 15, 22]. Among the other transition metals with higher
SOC, tungsten (W) in its $\beta$-phase ($\beta$-W) shows the largest spin hall
angle of $\approx$ 0.4 [23, 24, 25, 26] (much larger than Pt [21, 27] and
$\beta$-Ta [28]). $\beta$-W is characterized by high resistivity and has an
A-15 crystalline structure. On the other hand, $\alpha$-W is characterized by
its low resistivity and exhibits a small spin hall angle [23]. Recently, the
dependence of spin pumping in different structural phases of tungsten in
W/CoFeB bilayers has been studied at room temperature [29]. Lu et al. [30]
demonstrated an enhancement in spin mixing conductance by inserting a
$\alpha$-W layer in between CoFeB/$\beta$-W heterostructure through
interfacial phase engineering. There have not been many studies since then to
optimize the W thin film in its $\beta$ phase with higher resistivity and
investigate the spin pumping mechanism in HM/FM bilayers. This area of
research holds promise for further exploration and understanding of spin
transport properties in metallic heterostructures, potentially leading to the
development of more efficient spintronics devices.

In our study, we investigate the spin pumping efficiency in $\beta$-W/Py
bilayers by systematically varying the resistivity of $\beta$-W films by
tuning the argon pressure ($P_{Ar}$) during the deposition through the dc
sputtering technique, while maintaining the other parameters such as growth
rate and sputtering power ($p_{s}$) constant. All deposited W films are single
phase $\beta$-W with A15 crystal structure and resistivity increases with
increasing $P_{Ar}$. We employ short-circuited CPW-based broadband VNA-FMR
spectroscopy technique [31, 32] to measure the effective damping caused by
spin pumping in $\beta$-W/Py bilayers. It has been observed that the
resistivity of $\beta$-W ($\rho_{W}$) is strongly dependent on $P_{Ar}$
resulting in the enhancement in the effective damping $\alpha_{eff}$.
Sputtering power $p_{s}$ dependence of $\alpha_{eff}$ is also discussed which
is similar to fabrication kinematics of $P_{Ar}$. The other potential causes
for the enhancement in $\alpha_{eff}$ are discussed in detail. The interface
effect in $\beta$-W/Py is characterized by the effective spin mixing
conductance $g^{\uparrow\downarrow}_{eff}$ which is extracted using the
thickness variation of Py. The effective spin current $J_{S(eff)}$ is
calculated while taking spin back-flow during spin pumping into consideration.
Using the thickness dependence measurement of $\beta$-W, we are able to
calculate the intrinsic/interfacial spin mixing conductance
$g^{\uparrow\downarrow}_{W}$ and the spin diffusion length $\lambda_{SD}$. We
investigate the temperature dependence of spin pumping in order to gain a
deeper understanding of the damping mechanism in $\beta$-W. Our observation
reveals an intriguing trend: as temperature decreases there is an increase in
$\alpha_{eff}$ which can be explained by the torque-correlation model as
previously reported [33, 34, 35]. The device we employ in this paper is simple
yet effective, offering valuable insights into the underlying physical
mechanisms involved.

###  I.1 SAMPLE FABRICATION $\&$ EXPERIMENTAL DETAILS

A series of W thin films (8 nm) were fabricated on $Si/SiO_{2}$ (300 nm)
substrates at room temperature by dc magnetron sputtering technique equipped
with both scroll and turbo pump, reaching a base pressure of $1\times 10^{-6}$
Torr. The substrates of the dimension of 5 mm $\times$ 5 mm were placed in a
sample holder and kept at a constant distance of 15 cm from the sputtering
target. The dimension of the W target is 3 inches diameter $\times$ 3 mm thick
(99.95% pure). We used a straight deposition arrangement between the substrate
and target to achieve uniform films. The W thin films were deposited at
different argon pressure ($P_{Ar}$), varying systematically from 5.6 mTorr to
10 mTorr, with a constant sputtering power ($p_{S}$) = 150 watt. The
deposition rate of W thin films at different $P_{Ar}$ decreased from 0.6 Å/sec
for $P_{Ar}$ = 5.6 mTorr to 0.3 Å/sec for $P_{Ar}$ = 10 mTorr, recorded by a
crystal monitor. The crystal structure of deposited W films was characterized
using a Bruker x-ray diffractometer (XRD) with a Cu-$K_{\alpha}$ (1.54 Å)
source. The surface morphology and thickness profile of W films were studied
using an atomic force microscope (AFM). The resistivity of W films was
measured by the standard four-probe Van der Pauw technique. As no
microfabrication was needed, Py films were then deposited on top of the entire
$Si/SiO_{2}/W$ utilizing the thermal evaporation technique. The deposition
rate of Py was fixed at 1 Å/sec for all samples. Prior to each deposition, an
ion milling has been performed using dry argon plasma to clean the surface of
the substrates and to make the interface transparent. Py films were
characterized by XRD and in-plane anisotropic magnetoresistance (AMR)
measurement.

Figure 1: Schematic of spin pumping in a HM/FM bilayer device. The device is
placed on CPW upside down. Magnetization $\vec{M}$ in the FM layer precesses
around the effective magnetic field $\vec{B}_{eff}$, generating a spin current
that diffuses from the FM layer into the HM layer. For a realistic scenario,
the pumped spin current $J^{pump}_{S}$ generates a spin accumulation which
results in a back-flow of the spin current denoted as $J^{back}_{S}$.

For our experiment, we fabricated four different sets of samples: (i)
$Si/SiO_{2}/\beta$-W (8nm, $P_{Ar}$)/Py (15 nm), where, $P_{Ar}$ was varied
from 5.6 mTorr to 10 mTorr at constant sputtering power ($p_{s}$) of 150 watt.
These samples, labeled as $\beta$-W ($P_{Ar}$)/Py (set A) were used to
investigate the enhancement of effective damping at both room and low
temperatures, (ii) dependence of effective damping on $p_{S}$ was studied
using $\beta$-W(8nm, $p_{S}$)/Py(15 nm) (set B) bilayers with varying $p_{S}$
= 80, 150, 180, 250 and 330 watt, maintaining a constant $P_{Ar}$ = 6.7 mTorr,
(iii) $\beta$-W($P_{Ar}$ = 6.7 mTorr)/Py ($t_{Py}$) (set C) bilayers with
different Py thicknesses ($t_{Py}$ = 15, 20, 25, 30 nm) to evaluate
$g^{\uparrow\downarrow}_{eff}$ and $J_{S(eff)}$ injected from FM layer into HM
layer, (iv) $\beta$-W($P_{Ar}$ = 6.7 mTorr, $t_{W}$)/Py(15 nm) (set D)
bilayers with different W thickness ($t_{W}$ = 2, 5, 8, 10, 15 nm) to estimate
the $g^{\uparrow\downarrow}_{W}$ and $\lambda_{sd}$ of $\beta$-W.

Figure 2: (a) XRD of $\beta$-W thin films with various $P_{Ar}$. The peak
positions with their relative peak intensities corresponding to $\beta$ phase
of W are shown as vertical dotted lines, (b) Resistivity ($\rho_{W}$) as a
function of $P_{Ar}$ (inset: Grain size of W films at different $P_{Ar}$).

In our experimental setup, the samples were placed on top of the short-
circuited coplanar waveguide structure (CPW) as described in [31, 32] and an
in-plane external field (B) is applied, along with a radio frequency (rf)
microwave magnetic field ($B_{rf}$) in a transverse direction. Due to the
applied magnetic field, the magnetization starts to precess around the
effective magnetic field ($B_{eff}$) at a frequency known as Larmor precession
frequency which is shown in Fig. 1. Absorption of electromagnetic energy
occurs when the frequency of the $B_{rf}$ equals the Larmor frequency. There
are two techniques that are used to get FMR spectra: sweeping frequency while
maintaining a constant magnetic field or sweeping magnetic field while keeping
a constant frequency. To obtain the ferromagnetic resonance (FMR) spectra, we
employed the 2nd technique in our measurement where the magnetic field was
varied. During the measurements, we employed frequencies between 3.5 GHz to
5.5 GHz, and the magnetic field was swept from 0 Oe to 600 Oe. Throughout the
experiment, we used a microwave power of 1 mW to ensure consistent power
levels for accurate measurements.

Figure 3: The normalized absorption data in $\beta$-W ($P_{Ar}$ = 5.6
mTorr)/Py (set A) as a function of the applied field (B) at f = 3.8, 4.2, 4.6,
5.0, 5.3 and 5.5 GHz at room temperature.

###  I.2 Results and Discussion

Figure 4: (a) Normalized absorption spectra in $\beta$-W($P_{Ar}$)/Py (set A)
bilayers as a function of $B$ at a constant f = 5 GHz. $P_{Ar}$ varies from
5.6 mTorr to 10 mTorr, (b) Variation of frequency (f) with applied field (B)
which can be fitted with Kittel equation (Eq. 4). The Solid symbols are used
to depict the experimental data points, whereas the solid lines represent the
fitted data, (C) $M_{eff}$ vs $P_{Ar}$ (black dotted line serves as a
guideline), and (d) The curve $B_{k}$ vs $P_{Ar}$.

Crystal structure of deposited W films (8 nm) at different $P_{Ar}$ are
characterized by x-ray diffraction spectroscopy (XRD) with a resolution of
$2^{0}$/min illustrated in Fig. 2(a). All deposited W thin films are single-
phase $\beta$-W which is A15 type of crystal structure with peaks situated at
(200), (210), and (211) corresponding to 2$\theta$ = $35.5^{0},40^{0},44^{0}$
respectively [24, 36]. The W films grown at monotonically increasing $P_{Ar}$
show a systematic broadening in XRD peaks with lower intensities, which
indicates that W films are less crystalline in nature and contain smaller
crystallites as described in 2(a). XRD data provides a rough estimation of the
grain size of W films deposited at different $P_{Ar}$. Scherrer’s equation
[37] can be used to calculate the average grain size of W films,
$g=K\lambda/\delta cos(\theta)$, where $K$ is a shape factor ($\approx$ 0.9),
$\delta$ is the width of a diffraction peak at half maxima, $\lambda$ is the
x-ray wavelength, and $\theta$ is Bragg’s angle [38]. Using the XRD data, we
determine grain size as a function of $P_{Ar}$. As $P_{Ar}$ increases from 5.6
mTorr to 10 mTorr, grain size falls from 8.4 nm to 5.3 nm as shown in Fig.
2(b) inset. The Reduction in grain size as a function of $P_{Ar}$ indicates a
higher probability of electron scattering at grain boundaries [39]. Previous
studies have reported that $\beta$-W films do have remarkably high resistivity
due to the significant electron-phonon interaction presented in the A15
crystal structure [23]. According to the reports, the introduction of oxygen
inside the vacuum chamber during deposition stabilizes W films in its $\beta$
phase [40, 41]. The probability of oxygen being incorporated into the film is
dependent upon the deposition rate. Films grown at higher $P_{Ar}$ tend to
have lower deposition rates, and have a greater tendency to trap more oxygen
during deposition. Consequently, films deposited at higher $P_{Ar}$ exhibit
increased porosity and disorder resulting in a higher oxygen content which
leads to an increase in resistance. As illustrated in Fig. 2(b), we employ van
der Pauw technique for further characterization of resistivity ($\rho_{W}$) at
different $P_{Ar}$. A non-monotonic relation between $P_{Ar}$ and $\rho_{W}$
is obtained which can be separated into two segments. Initially, as $P_{Ar}$
increases, $\rho_{W}$ experiences a gradual and slow increase. However, beyond
$P_{Ar}$ = 7 mTorr, $\rho_{W}$ exhibits a rapid increase which follows a
linear trend until it reaches a saturation point at 10 mTorr with $\rho_{W}$
approaches $\approx$ 1400 $\mu\Omega$-cm. To assess the surface morphology of
films, we utilize semicontact topography mode in AFM with a minimum scanning
area of 2 $\mu$m $\times$ 2 $\mu$m. The analysis indicates that the films at
higher $P_{Ar}$ are more porous, which contributes to higher surface roughness
(Fig. S2). Conversely, when $P_{Ar}$ decreases, the films tend to become
smoother implying a compact structure that can be compared with the XRD graph
(Fig. 2(a)). The average surface roughness is observed to decrease from 0.8 nm
to 0.3 nm as $P_{Ar}$ decreases from 10 mTorr to 5.6 mTorr.

Fig. 3 represents the normalized FMR absorption spectra as a function of
external field B for $\beta$-W ($P_{Ar}$ = 5.6 mTorr)/Py(15 nm) bilayer over a
frequency (f) range from 3.5–5.5 GHz at room temperature. The experimental
results are fitted using the Lorentz equation [42].

Figure 5: (a) Variation of linewidth $\Delta B$ as a function of f in
$\beta$-W($P_{Ar}$/Py) (set A) bilayers. The solid symbols are used to
indicate the experimental data points, whereas the data points are fitted with
Eq. 5 described by the solid lines, (b) $\alpha_{eff}$ calculated from Eq. 5
as a function of $\rho_{W}$ [inset: variation of $\rho_{W}$ with $P_{Ar}$
(dark cyan symbols) and $\alpha_{eff}$ as a function of $P_{Ar}$ (red solid
symbols)], (C) Dependence of $\Delta B_{0}$ on $P_{Ar}$.

$S_{11}\propto S_{0}\frac{\Delta B}{[4(B-B_{r})^{2}+(\Delta B)^{2}]}$ (3)

where $S_{0}$ is the coefficient of absorptive microwave power, B is the in-
plane external magnetic field, $\Delta B$ is the absorption linewidth, and
$B_{r}$ is the resonance field. The observed increase in $B_{r}$ increases
with microwave frequency f which is consistent with the expected behavior
[43]. We investigate systematically the FMR spectra of $\beta$-W ($P_{Ar}$)/Py
bilayers (set A), with $P_{Ar}$ varying from 5.6 mTorr to 10 mTorr, which
corresponds to a range of $\rho_{W}$ from 127 $\mu\Omega$-cm to 1400
$\mu\Omega$-cm. This variation in resistivity permits the study of the
dependence of the $\alpha_{eff}$ on $\rho_{W}$ of $\beta$-W thin films. The
normalized FMR absorption signal of $\beta$-W ($P_{Ar}$)/Py(15 nm) observed at
f = 5 GHz is depicted in Fig. 4(a). A gradual increase in $B_{r}$ with
$P_{Ar}$ is observed, and the absorption curves become broadened, leading to
an increase in $\Delta B$. Fig. 4(b) shows the f vs B curves for $\beta$-W
films grown at different $P_{Ar}$. Using Kittel equation [44, 43], the
effective magnetization ($M_{eff}$) and the anisotropy field ($B_{k}$) are
extracted from f vs B curve as shown in Fig. 4(c) and Fig. 4(d) respectively
(set A).

$f=\frac{g\mu_{B}}{h}\sqrt{(B_{r}+B_{k})(B_{r}+B_{k}+4\pi M_{eff})}$ (4)

With, $g$ (=2.15), $\mu_{B}$, and $h$ are the Lande $g$ factor, Bohr magneton,
and Planck’s constant, respectively. Fig. 4(c) illustrates the variation in
$M_{eff}$ as a function of $P_{Ar}$, where a monotonous decrease in $M_{eff}$
with increasing $P_{Ar}$ is observed. The evaluated $M_{eff}$ in $\beta$-W
($P_{Ar}$)/Py bilayers is less than the $M_{eff}$ in single-layer Py with the
same thickness. The decrease in $M_{eff}$ could be the result of the d-d
hybridization at the interface between Py and $\beta$-W [45, 46]. Also, the
magnetic dead layer created by sp-d hybridization at the interface between Py
and $\beta$-W is a potential cause for the decrease in the $M_{eff}$ [47].
Fig. 4(d) shows the variation in $B_{k}$ with $P_{Ar}$, which does not have a
strong correlation with resistivity of $\beta$-W films and is nearly constant
even at higher $P_{Ar}$.

Figure 6: (a) Variation in resistivity ($\rho_{W}$) with $p_{S}$ in $\beta$-W
(8nm, $p_{S}$)/Py(15 nm) bilayers (set B) (inset: Grain size of $\beta$-W
films as a function of $p_{S}$. XRD of $\beta$-W thin films with various
$p_{S}$. The peak positions with their relative peak intensities corresponding
to the $\beta$ phase of W are shown as vertical dotted lines, (b)
$\alpha_{eff}$ is plotted as a function of $\rho_{W}$.

$\Delta B$ as shown in Fig. 5(a) as a function of f (set A), can be described
by a linear relationship [48]

$\Delta B=\frac{2h\alpha_{eff}}{g\mu_{B}}f+\Delta B_{0}$ (5)

where, 1st term is linearly dependent on f and the 2nd term $\Delta B_{0}$ is
independent of f known as inhomogeneous line broadening. As described in Fig.
5(a), the data are represented by solid symbols, and the curves are fitted
using Eq. 5, represented by the solid lines. All $\beta$-W ($P_{Ar}$)/Py
samples exhibit a linear response in $\Delta B$ vs f indicating that the
damping mechanism is dominated by both the intrinsic Gilbert damping and spin
pumping [49, 50, 51]. $\Delta B_{0}$ is the frequency-independent extrinsic
contribution of damping that reflects the sample’s quality during the
fabrication process and may be the result of structural imperfections,
impurities, or sample roughness [52]. Fig. 5(c) demonstrates that $\Delta
B_{0}$ varies from approximately 16 Oe to 1 Oe with $P_{Ar}$. Earlier it has
been shown that the roughness of $\beta$-W films increases with $P_{Ar}$ and
an opposite trend is observed in $\Delta B_{0}$ which suggests that $\Delta
B_{0}$ does not arise from sample roughness. $\alpha_{eff}$ can be evaluated
from the plot of $\Delta B$ vs f as shown in Fig. 5(b). $\alpha_{eff}$ has two
components: (a) the intrinsic Gilbert damping ($\alpha_{b}$) caused by the Py
layer and (b) damping ($\alpha_{SP}$) due to spin current, pumped into the
$\beta$-W films by the process of dissipation [53]. Here, the enhancement in
$\alpha_{eff}$ with $\rho_{W}$ is caused by the spin current-induced spin
pumping mechanism from Py into $\beta$-W films. Initially, $\alpha_{eff}$
remains constant with a magnitude $\approx$ 0.010 until $\rho_{W}$ reaches
$\approx$ 350 $\mu\Omega$-cm, as shown in Fig. 5(b). Beyond that,
$\alpha_{eff}$ begins to increase rapidly, reaching $\approx$ 0.024 at
$\rho_{W}$ = 1400 $\mu\Omega$-cm. The increased disorder states at higher
$P_{Ar}$ increase $\rho_{W}$, which aids in quicker relaxation and ultimately
enhances $\alpha_{eff}$. We conduct a similar study, as depicted in Fig. 6, in
which we vary the input power $p_{s}$ during sputtering while maintaining a
constant $P_{Ar}$ (set B). Fig. 6(a) presents $\rho_{W}$ as a function of
$p_{S}$ for $\beta$-W(8nm, $p_{s}$)/Py(15 nm) bilayers with $P_{Ar}$ = 6.7
mTorr. Both XRD data and grain size of $\beta$-W employed in these bilayers
are illustrated in the insets in Fig. 6(a). The relative increase in peak
sharpness in XRD indicates that the $\beta$-W films tend to become more
crystalline as $p_{s}$ increases. The grain size grows with $p_{s}$ as the
films become more smoother, while $P_{Ar}$ remains constant. As shown in Fig.
6(a), it can be observed that $\rho_{W}$ reduces with $p_{S}$, however, the
change is not as significant as what was previously observed when varying
$P_{Ar}$ [Fig. 2(b)]. Fig. 6(b) depicts the change in $\alpha_{eff}$ with
$\rho_{W}$ where $\rho_{W}$ is governed by $p_{S}$. Here, we observe a gradual
enhancement in $\alpha_{eff}$ as $\rho_{W}$ increases which can be compared
qualitatively to Fig. 5 (b) in the low $\rho_{W}$ range. Therefore, based on
the observation of $\alpha_{eff}$ dependence on both $P_{Ar}$ and $p_{S}$, we
may infer that there is a direct relationship between the $\rho_{W}$ of
$\beta$-W and the effective damping $\alpha_{eff}$ which defines the spin
pumping mechanism in $\beta$-W/Py bilayers.

Figure 7: (a) Py thickness dependence of $\alpha_{eff}$ (set C), fitted using
Eq. 6 with solid red symbols expressing the experimental data and black solid
lines are fitted data (inset: $M_{eff}$ vs $1/t_{Py}$), (b) $\alpha_{eff}$ as
a function of $t_{W}$ (set D). The curve is fitted using Eq. 8 with solid
symbols representing the experimental data, whereas the black solid line
describes the fitted data. Figure 8: (a) Normalized absorption spectra in
$\beta$-W($P_{Ar}$ = 5.6 mTorr)/Py (15nm) bilayer as a function of $B$ at T =
8, 30, 60, 100, 150, and 250 K (f = 5 GHz), (b) $B_{r}$ as a function of T at
f = 4 and 5 GHz, (c) $\Delta B$ as a function of T at f = 4 and 5 GHz, (d),
(e) Temperature dependence of $M_{eff}$ and $B_{k}$ respectively (inset:
resistance R vs T of $\beta$-W($P_{Ar}$ = 5.6 mTorr), (f) $\alpha_{eff}$ as a
function of temperature (inset: $\alpha_{b}$ vs T of single layer bulk Py).

In order to determine the interface contribution of $\beta$-W/Py bilayer on
spin pumping, we need to evaluate the $g^{\uparrow\downarrow}_{eff}$ by
studying the thickness dependence of Py layer as shown in Fig. 7(a). We use
$\beta$-W ($P_{Ar}$ = 6.7 mTorr)/Py ($t_{Py}$) bilayers labeled as set C for
our experiment. $\alpha_{eff}$ varies linearly with $1/t_{Py}$ and follows the
equation [50, 54, 55]

$\alpha_{eff}=\alpha_{b}+g\mu_{B}\frac{g^{\uparrow\downarrow}_{eff}}{4\pi
M_{S}}\frac{1}{t_{Py}}$ (6)

where, $M_{S}$ is saturation magnetization, which can be calculated using a
linear equation between $M_{eff}$ and $1/t_{Py}$

$\mu_{0}M_{eff}=\mu_{0}M_{S}-\frac{2K_{S}}{M_{S}d}$ (7)

Eq. 6 is a direct link between the interface and bulk regime, where, the first
term $\alpha_{b}$ is intrinsic Gilbert damping of bulk Py and the 2nd term is
spin pumping $\alpha_{SP}$ (=$\frac{\delta_{S}}{t_{Py}}$), where, $\delta_{S}$
= $g\mu_{B}\frac{g^{\uparrow\downarrow}_{eff}}{4\pi M_{S}}$ represents the
additional damping brought on by combined contribution of Py/vacuum and Py/W
interface. The enhanced damping in $\beta$-W/Py of thinner Py films indicates
the dominance of surface or interface contribution. The extracted parameters
are $\alpha_{b}$ = 0.0061, $\delta_{S}$ = 0.0625 nm in $\beta$-W ($P_{Ar}$ =
6.7 mTorr)/Py ($t_{Py}$) bilayers. We have calculated $M_{S}$ = 712 Oe [inset
of Fig. 7(a)] using Eq. 7, from which we obtain $g^{\uparrow\downarrow}_{eff}$
= 2.33 $nm^{-2}$ which is comparable with the reported value recently observed
experimentally in $\beta$-W [56]. The observed value of
$g^{\uparrow\downarrow}_{eff}$ is quite high and it confirms a substantial
spin transfer via pumping mechanism [57, 58, 59]. We need to determine the
$g^{\uparrow\downarrow}_{W}$ in order to comprehend the damping mechanism
through the $\beta$-W layer. In a $\beta$-W/Py bilayer, due to interfacial
non-equilibrium accumulation, spin back-flow ($J^{back}_{S}$) occurs which
further reduces the spin pumping mechanism. Effective spin current due back-
flow can be expressed as $J_{S(eff)}$ = $J_{S}(1-e^{-2t_{W}/\lambda_{SD}})$
[55, 60]. The dependence of $\alpha_{eff}$ on $t_{W}$ can be described by the
exponential function [55, 53, 61]

$\alpha_{eff}=\alpha_{b}+g\mu_{B}\frac{g^{\uparrow\downarrow}_{W}}{4\pi
M_{S}}\frac{1}{t_{Py}}(1-e^{-\frac{2t_{W}}{\lambda_{SD}}})$ (8)

where, $\alpha_{b}$ represents the damping of Py without $\beta$-W layer. Fig.
7(b) shows the fitted experimental data of $\alpha_{eff}$ on $t_{W}$ using Eq.
8. It shows that by adding the $\beta$-W layer, the effective damping
increases from the bulk Py damping and then saturates after $t_{W}$ $\approx$
5 nm. The extracted parameters are $g^{\uparrow\downarrow}_{W}$ = (1.57 $\pm$
0.07) $nm^{-2}$ and $\lambda_{SD}$ = (4.53 $\pm$ 1.68) nm [24][62]. The
calculated value of $g^{\uparrow\downarrow}_{W}$ is comparable to the value
found in W/Py bilayer recently [56]. Due to spin back-flow in $\beta$-W layer,
the evaluated $g^{\uparrow\downarrow}_{W}$ is one order of magnitude lower as
compared in Pt/Co bilayer reported in [59]. The evaluated $\lambda_{SD}$ is
consistent with the measured value in $\beta$-W in [25][63]. Using the
coefficient of effective damping, we evaluate the effective spin current
$J_{S(eff)}$ through the $\beta$-W layer from FM due to damping, which is
provided as follows [57]

$J_{S(eff)}=\frac{g^{\uparrow\downarrow}_{eff}\gamma^{2}B^{2}_{eff}\hbar[4\pi
M_{S}\gamma+\sqrt{(4\pi
M_{S}\gamma)^{2}+4\omega^{2}}]}{8\pi\alpha^{2}_{eff}[(4\pi
M_{S}\gamma)^{2}+4\omega^{2}]}$ (9)

where, $B_{eff}$ is microwave magnetic field and $\omega$ is frequency
respectively. Using the known parameters, the calculated $J_{S(eff)}$ is
$7.52\times 10^{-10}$ $J/m^{2}$, which is a factor of ten less than the
reported value [64]. A possible reason is that the microwave field strength
used in our experiment is much weaker than what has been published.

For a better understanding of the underlying mechanism, we now focus on the
temperature dependence of the spin pumping in the device
$\beta$-W($P_{Ar}$=5.6 mTorr/Py (15nm) (set A). Fig. 8(a) depicts the
normalized absorption data at T = 8, 30, 60, 100, 150, and 250 K (f = 5 GHz).
The curves tend to get broadened at low T. Fig. 8(b) illustrates the
temperature dependence of resonance field $B_{r}$ at $f$ = 4 and 5 GHz,
evaluated from the Kittel equation [44]. As temperature decreases, we observe
a shift in $B_{r}$ towards lower magnetic fields which follows a linear trend
across the entire temperature range. However, the temperature dependence can
be differentiated into two segments by lowering the temperature, with a
steeper slope between 290K and 150K than between 100K and 8K. This decrease in
$B_{r}$ can be explained by the increased $M_{eff}$ at low temperatures, as
depicted in Fig. 8(d). A similar trend is observed in $B_{K}$ as shown in
8(e). Temperature dependence of extracted $\Delta B$ at f = 4 and 5 GHz is
depicted in Fig. 8(c) and $\Delta B$ is expected to increase with f. $\Delta
B$ increases gradually at lowering T until it reaches 100K, below which it
begins to increase swiftly and continues to do so up to 8K. For greater
comprehension, we study $\alpha_{eff}$ vs T, where $\alpha_{eff}$ increases
slightly from 290K to 100K and begins to increase more rapidly below 100K.
This behavior can be explained using the theoretical torque correlation model
[33, 34, 35, 65] and our results are consistent with that. According to this
model, during magnetic precession, electron-hole pairs are created that relax
via lattice scattering with a characteristic relaxation time $\tau$. There are
two kinds of transitions involving electron-hole pairs. While the damping
brought on by intraband electron-hole pairs is proportional to $\tau$, the
damping brought on by interband transitions is inversely proportional to
$\tau$. As temperature decreases, the number of phonons begins to decrease,
which enhances the relaxation time $\tau$. If only an intraband transition
exists, $\alpha_{eff}$ should increase linearly with decreasing temperature.
However, non-monotonic increases suggest that there is a modest contribution
from interband transition, while intraband transition dominates the overall
damping. As illustrated in Fig. 8(f), $\alpha_{eff}$ rises gradually when the
temperature is lowered up to 150 K, below which it starts to increase more
rapidly until it reaches a magnitude $\approx$ 0.015 at T=8K. This result is
compared to the damping coefficient $\alpha_{b}$ of single layer Py as shown
in the inset of Fig. 8(f). The graph shows a decrease in $\alpha_{b}$ with
temperature and reaches a minimum at 100K, below which $\alpha_{b}$ starts to
increase, reaches a maximum at 45K, and decreases again with lowering the
temperature. As described in [51], this peak may be the result of spin
reorientation on the surface of Py at 45 K. In contrast,
$\beta$-W($P_{Ar}$=5.6 mTorr/Py (15nm) bilayer shows no such peak. Therefore,
comparing the $\beta$-W/Py bilayer and Py, the enhancement in $\alpha_{eff}$
at low-temperature concludes that there is a significant effect of spin
pumping from Py into the $\beta$-W layer.

###  I.3 Conclusion

In conclusion, we systematically study the Gilbert damping in $\beta$-W/Py
bilayers by modulating the $P_{Ar}$, which corresponds to different $\rho_{W}$
while maintaining a constant $p_{S}$ and observe that $\alpha_{eff}$ is
enhanced with $P_{Ar}$. We also perform a similar experiment to determine
$\alpha_{eff}$ as a function of $p_{S}$, while maintaining $P_{Ar}$. Since the
resistivity $\rho_{W}$ does not vary considerably with $p_{S}$, a comparably
insignificant change in $\alpha_{eff}$ is observed in those bilayers. Both
observations suggest a strong correlation between $\alpha_{eff}$ and
$\rho_{W}$, which is caused by the increased disorder accompanied by oxygen
incorporation into $\beta$-W films during deposition. These disorders modify
the relaxation mechanism in the system, which further enhances $\alpha_{eff}$.
The thickness dependence of Py indicates that the damping mechanism is
dominated by spin pumping in the aforementioned bilayer devices which is
supported by an effective spin mixing conductance
$g^{\uparrow\downarrow}_{eff}$ = 2.33 $nm^{-2}$. The role of $\beta$-W on spin
pumping in these devices can be explained by considering the back-flow of spin
current and the effective spin current is estimated to be $J_{S(eff)}$ =
$7.52\times 10^{-10}$ $J/m^{2}$ which can be further used to investigate the
inverse spin Hall effect (ISHE) in $\beta$-W/Py heterostructures. The
enhancement of $\alpha_{eff}$ with $t_{W}$ estimates the interfacial spin
mixing conductance $g^{\uparrow\downarrow}_{W}$ = 1.57 $nm^{-2}$ and
$\lambda_{SD}$ = 4.53 $nm$. Furthermore, temperature dependence in
$\beta$-W/Py clearly shows a substantial increase in $\alpha_{eff}$ at low
temperature that is explained by the torque-correlation model, and the
enhancement is attributed to the spin pumping mechanism from the Py layer into
the $\beta$-W. Therefore, we come to the conclusion that $\rho_{W}$ of
$\beta$-W can be used as a tuning parameter to regulate the $\alpha_{eff}$
which can be helpful in faster switching in spin dynamics in magnetic
heterostructures, opening up the possibilities for optimizing their
performances.

###  I.4 Acknowledgement

We acknowledge the Ministry of Human Resource Development (MHRD), the Science
and Engineering Research Board (SERB) (Grant No. EMR/2016/007950), the
Department of Science and Technology (Grant No. DST/ICPS/Quest/2019/22) for
providing the necessary funding. We also sincerely thank the Ministry of
Education of the Government of India, the Department of Science and Technology
(DST), and IISER Kolkata for funding the scholarship. Ritam Bannerjee, Kanav
Sharma, and Sambhu G Nath all contributed to this effort, for which the
authors are grateful.

## References

  * Hirsch [1999] J. Hirsch, Spin hall effect, Phys. Rev. Lett. 83, 1834 (1999).
  * Zhang [2000] S. Zhang, Spin hall effect in the presence of spin diffusion, Phys. Rev. Lett. 85, 393 (2000).
  * Valenzuela and Tinkham [2006] S. O. Valenzuela and M. Tinkham, Direct electronic measurement of the spin hall effect, Nature 442, 176 (2006).
  * Kimura  _et al._ [2007] T. Kimura, Y. Otani, T. Sato, S. Takahashi, and S. Maekawa, Room-temperature reversible spin hall effect, Phys. Rev. Lett. 98, 156601 (2007).
  * Brataas  _et al._ [2012] A. Brataas, A. D. Kent, and H. Ohno, Current-induced torques in magnetic materials, Nat. Mater. 11, 372 (2012).
  * Sinova  _et al._ [2015] J. Sinova, S. O. Valenzuela, J. Wunderlich, C. H. Back, and T. Jungwirth, Spin hall effects, Rev. Mod. Phys. 87, 1213 (2015).
  * Slonczewski [1996] J. Slonczewski, Current-driven excitation of magnetic multilayers, J. Magn. Magn. Mater. 159, L1 (1996).
  * Miron  _et al._ [2011] I. M. Miron, K. Garello, G. Gaudin, P.-J. Zermatten, M. V. Costache, S. Auffret, S. Bandiera, B. Rodmacq, A. Schuhl, and P. Gambardella, Perpendicular switching of a single ferromagnetic layer induced by in-plane current injection, Nature 476, 189 (2011).
  * Tserkovnyak  _et al._ [2002a] Y. Tserkovnyak, A. Brataas, and G. E. W. Bauer, Enhanced gilbert damping in thin ferromagnetic films, Phys. Rev. Lett. 88, 117601 (2002a).
  * Brataas  _et al._ [2002] A. Brataas, Y. Tserkovnyak, G. E. W. Bauer, and B. I. Halperin, Spin battery operated by ferromagnetic resonance, Phys. Rev. B 66, 060404 (2002).
  * Lenz  _et al._ [2004] K. Lenz, T. Toliński, J. Lindner, E. Kosubek, and K. Baberschke, Evidence of spin-pumping effect in the ferromagnetic resonance of coupled trilayers, Phys. Rev. B 69, 144422 (2004).
  * Woltersdorf  _et al._ [2005] G. Woltersdorf, M. Buess, B. Heinrich, and C. H. Back, Time resolved magnetization dynamics of ultrathin Fe (001) films: spin-pumping and two-magnon scattering, Phys. Rev. Lett. 95, 037401 (2005).
  * Saitoh  _et al._ [2006] E. Saitoh, M. Ueda, H. Miyajima, and G. Tatara, Conversion of spin current into charge current at room temperature: Inverse spin-hall effect, Appl. Phys. Lett. 88, 182509 (2006).
  * Brataas  _et al._ [2008] A. Brataas, Y. Tserkovnyak, and G. E. W. Bauer, Scattering theory of gilbert damping, Phys. Rev. Lett. 101, 037207 (2008).
  * Ando [2014] K. Ando, Dynamical generation of spin currents, Semicond. Sci. Technol. 29, 043002 (2014).
  * Vignale [2010] G. Vignale, Ten years of spin hall effect, J. Supercond. Nov. Magn. 23, 3 (2010).
  * Tserkovnyak  _et al._ [2005] Y. Tserkovnyak, A. Brataas, G. E. W. Bauer, and B. I. Halperin, Nonlocal magnetization dynamics in ferromagnetic heterostructures, Rev. Mod. Phys. 77, 1375 (2005).
  * Gilbert [2004] T. Gilbert, A phenomenological theory of damping in ferromagnetic materials, IEEE Trans. Magn. 40, 3443 (2004).
  * Rojas-Sánchez  _et al._ [2016] J.-C. Rojas-Sánchez, S. Oyarzún, Y. Fu, A. Marty, C. Vergnaud, S. Gambarelli, L. Vila, M. Jamet, Y. Ohtsubo, A. Taleb-Ibrahimi, P. Le Fèvre, F. Bertran, N. Reyren, J.-M. George, and A. Fert, Spin to charge conversion at room temperature by spin pumping into a new type of topological insulator: $\alpha$-Sn films, Phys. Rev. Lett. 116, 096602 (2016).
  * Ando  _et al._ [2009] K. Ando, T. Yoshino, and E. Saitoh, Optimum condition for spin-current generation from magnetization precession in thin film systems, Appl. Phys. Lett. 94, 152509 (2009).
  * Mosendz  _et al._ [2010] O. Mosendz, J. Pearson, F. Fradin, G. Bauer, S. Bader, and A. Hoffmann, Quantifying spin hall angles from spin pumping: Experiments and theory, Phys. Rev. Lett. 104, 046601 (2010).
  * Zhang  _et al._ [2015] W. Zhang, W. Han, X. Jiang, S.-H. Yang, and S. SP Parkin, Role of transparency of platinum–ferromagnet interfaces in determining the intrinsic magnitude of the spin hall effect, Nat. Phys. 11, 496 (2015).
  * Pai  _et al._ [2012] C.-F. Pai, L. Liu, Y. Li, H. Tseng, D. Ralph, and R. Buhrman, Spin transfer torque devices utilizing the giant spin hall effect of tungsten, Appl. Phys. Lett. 101, 122404 (2012).
  * Hao  _et al._ [2015] Q. Hao, W. Chen, and G. Xiao, Beta ($\beta$) tungsten thin films: Structure, electron transport, and giant spin hall effect, Appl. Phys. Lett. 106, 182403 (2015).
  * Hao and Xiao [2015] Q. Hao and G. Xiao, Giant spin hall effect and switching induced by spin-transfer torque in a W/Co40Fe40B20/MgO structure with perpendicular magnetic anisotropy, Phys. Rev. Appl. 3, 034009 (2015).
  * Demasius  _et al._ [2016] K.-U. Demasius, T. Phung, W. Zhang, B. P. Hughes, S.-H. Yang, A. Kellock, W. Han, A. Pushp, and S. S. Parkin, Enhanced spin–orbit torques by oxygen incorporation in tungsten films, Nat. Commun. 7, 1 (2016).
  * Feng  _et al._ [2012] Z. Feng, J. Hu, L. Sun, B. You, D. Wu, J. Du, W. Zhang, A. Hu, Y. Yang, D. M. Tang, B. S. Zhang, and H. F. Ding, Spin hall angle quantification from spin pumping and microwave photoresistance, Phys. Rev. B 85, 214423 (2012).
  * Liu  _et al._ [2012] L. Liu, C.-F. Pai, Y. Li, H. Tseng, D. Ralph, and R. Buhrman, Spin-torque switching with the giant spin hall effect of tantalum, Science 336, 555 (2012).
  * Jhajhria  _et al._ [2019] D. Jhajhria, N. Behera, D. K. Pandya, and S. Chaudhary, Dependence of spin pumping in W/CoFeB heterostructures on the structural phase of tungsten, Phys. Rev. B 99, 014430 (2019).
  * Lu  _et al._ [2019] Q. Lu, Y. Li, B. Peng, H. Tang, Y. Zhang, Z. He, L. Wang, C. Li, W. Su, Q. Yang, Z. Zhou, and M. Liu, Enhancement of the spin-mixing conductance in CoFeB/W bilayers by interface engineering, Phys. Rev. Appl. 12, 064035 (2019).
  * Pal  _et al._ [2022] S. Pal, S. Aon, S. Manna, and C. Mitra, A short-circuited coplanar waveguide for low-temperature single-port ferromagnetic resonance spectroscopy setup to probe the magnetic properties of ferromagnetic thin films, Rev. Sci. Instrum. 93, 083909 (2022).
  * Pal  _et al._ [2023] S. Pal, S. Aon, S. Manna, S. G. Nath, K. Sharma, and C. Mitra, Experimental investigation of the effect of topological insulator on the magnetization dynamics of ferromagnetic metal: BiSbTe1.5Se1.5 and Ni80Fe20 heterostructure (2023), arXiv:2303.07025 [cond-mat.mes-hall] .
  * Kamberskỳ [1976] V. Kamberskỳ, On ferromagnetic resonance damping in metals, Czechoslov. J. Phys. 26, 1366 (1976).
  * Gilmore  _et al._ [2007] K. Gilmore, Y. U. Idzerda, and M. D. Stiles, Identification of the dominant precession-damping mechanism in Fe, Co, and Ni by first-principles calculations, Phys. Rev. Lett. 99, 027204 (2007).
  * [35] M. Fähnle and C. Illg, Electron theory of fast and ultrafast dissipative magnetization dynamics, J. Phys. Condens. Matter 23, 493201.
  * Lee  _et al._ [2016] J.-S. Lee, J. Cho, and C.-Y. You, Growth and characterization of $\alpha$ and $\beta$-phase tungsten films on various substrates, J. Vac. Sci. Technol. A 34, 021502 (2016).
  * Patterson [1939] A. L. Patterson, The scherrer formula for x-ray particle size determination, Phys. Rev. 56, 978 (1939).
  * Maqbool and Khan [2005] M. Maqbool and T. Khan, Surface characterization and grain size calculation of silver films deposited by thermal evaporation, Surf. Rev. Lett. 12, 759 (2005).
  * Choi [2014] D. Choi, The electron scattering at grain boundaries in tungsten films, Microelectron. Eng. 122, 5 (2014).
  * Karabacak  _et al._ [2003] T. Karabacak, A. Mallikarjunan, J. P. Singh, D. Ye, G.-C. Wang, and T.-M. Lu, $\beta$-phase tungsten nanorod formation by oblique-angle sputter deposition, Appl. Phys. Lett. 83, 3096 (2003).
  * Salamon  _et al._ [2013] K. Salamon, O. Milat, N. Radić, P. Dubček, M. Jerčinović, and S. Bernstorff, Structure and morphology of magnetron sputtered w films studied by x-ray methods, J. Phys. D 46, 095304 (2013).
  * Celinski  _et al._ [1997] Z. Celinski, K. Urquhart, and B. Heinrich, Using ferromagnetic resonance to measure the magnetic moments of ultrathin films, J. Magn. Magn. Mater. 166, 6 (1997).
  * Jamali  _et al._ [2013] M. Jamali, A. Klemm, and J.-P. Wang, Precessional magnetization induced spin current from CoFeB into Ta, Appl. Phys. Lett. 103, 10.1063/1.4853195 (2013).
  * Kittel [1948] C. Kittel, On the theory of ferromagnetic resonance absorption, Phys. Rev. 73, 155 (1948).
  * Wilhelm  _et al._ [2000] F. Wilhelm, P. Poulopoulos, G. Ceballos, H. Wende, K. Baberschke, P. Srivastava, D. Benea, H. Ebert, M. Angelakeris, N. K. Flevaris, D. Niarchos, A. Rogalev, and N. B. Brookes, Layer-resolved magnetic moments in $\mathrm{Ni}/\mathrm{Pt}$ multilayers, Phys. Rev. Lett. 85, 413 (2000).
  * Poulopoulos  _et al._ [2002] P. Poulopoulos, A. Scherz, F. Wilhelm, H. Wende, and K. Baberschke, Direct probe of induced magnetic moments at interfaces via x-ray magnetic circular dichroism, Phys. Status Solidi 189, 293 (2002).
  * Shin  _et al._ [1998] S.-C. Shin, G. Srinivas, Y.-S. Kim, and M.-G. Kim, Observation of perpendicular magnetic anisotropy in Ni/Pt multilayers at room temperature, Appl. Phys. Lett. 73, 393 (1998).
  * Rossing [1963] T. D. Rossing, Resonance Linewidth and Anisotropy Variation in Thin Films, J. Appl. Phys. 34, 995 (1963).
  * Charilaou  _et al._ [2010] M. Charilaou, K. Lenz, and W. Kuch, Spin-pumping-enhanced magnetic damping in ultrathin Cu(001)/Co/Cu and Cu(001)/Ni/Cu films, J. Magn. Magn. Mater. 322, 2065 (2010).
  * Barati  _et al._ [2014] E. Barati, M. Cinal, D. Edwards, and A. Umerski, Gilbert damping in magnetic layered systems, Phys. Rev. B 90, 014420 (2014).
  * Zhao  _et al._ [2016] Y. Zhao, Q. Song, S.-H. Yang, T. Su, W. Yuan, S. S. Parkin, J. Shi, and W. Han, Experimental investigation of temperature-dependent gilbert damping in permalloy thin films, Sci. Rep. 6, 1 (2016).
  * Heinrich  _et al._ [1985] B. Heinrich, J. F. Cochran, and R. Hasegawa, FMR linebroadening in metals due to two‐magnon scattering, J. Appl. Phys. 57, 3690 (1985).
  * Foros  _et al._ [2005] J. Foros, G. Woltersdorf, B. Heinrich, and A. Brataas, Scattering of spin current injected in Pd(001), J. Appl. Phys. 97, 10A714 (2005).
  * Mizukami  _et al._ [2001] S. Mizukami, Y. Ando, and T. Miyazaki, Ferromagnetic resonance linewidth for NM/80NiFe/NM films (NM=Cu, Ta, Pd and Pt), J. Magn. Magn. Mater. 226-230, 1640 (2001).
  * Tserkovnyak  _et al._ [2002b] Y. Tserkovnyak, A. Brataas, and G. E. W. Bauer, Spin pumping and magnetization dynamics in metallic multilayers, Phys. Rev. B 66, 224403 (2002b).
  * Behera  _et al._ [2017] N. Behera, P. Guha, D. K. Pandya, and S. Chaudhary, Capping layer (CL) induced antidamping in CL/Py/$\beta$-W system (CL: Al, $\beta$-Ta, Cu, $\beta$-W), ACS Appl. Mater. Interfaces 9, 31005 (2017).
  * Deorani and Yang [2013] P. Deorani and H. Yang, Role of spin mixing conductance in spin pumping: Enhancement of spin pumping efficiency in Ta/Cu/Py structures, Appl. Phys. Lett. 103, 10.1063/1.4839475 (2013).
  * Tokaç  _et al._ [2015] M. Tokaç, S. A. Bunyaev, G. N. Kakazei, D. S. Schmool, D. Atkinson, and A. T. Hindmarch, Interfacial structure dependent spin mixing conductance in cobalt thin films, Phys. Rev. Lett. 115, 056601 (2015).
  * Azzawi  _et al._ [2016] S. Azzawi, A. Ganguly, M. Tokaç, R. M. Rowan-Robinson, J. Sinha, A. T. Hindmarch, A. Barman, and D. Atkinson, Evolution of damping in ferromagnetic/nonmagnetic thin film bilayers as a function of nonmagnetic layer thickness, Phys. Rev. B 93, 054402 (2016).
  * Jiao and Bauer [2013] H. Jiao and G. E. W. Bauer, Spin backflow and ac voltage generation by spin pumping and the inverse spin hall effect, Phys. Rev. Lett. 110, 217602 (2013).
  * Shaw  _et al._ [2012] J. M. Shaw, H. T. Nembach, and T. J. Silva, Determination of spin pumping as a source of linewidth in sputtered Co90Fe10/Pd multilayers by use of broadband ferromagnetic resonance spectroscopy, Phys. Rev. B 85, 054412 (2012).
  * Wang  _et al._ [2014] H. L. Wang, C. H. Du, Y. Pu, R. Adur, P. C. Hammel, and F. Y. Yang, Scaling of spin hall angle in 3d, 4d, and 5d metals from Y3Fe5O12/metal spin pumping, Phys. Rev. Lett. 112, 197201 (2014).
  * Cho  _et al._ [2015] S. Cho, S.-h. C. Baek, K.-D. Lee, Y. Jo, and B.-G. Park, Large spin hall magnetoresistance and its correlation to the spin-orbit torque in W/CoFeB/MgO structures, Sci. Rep. 5, 14668 (2015).
  * Nakayama  _et al._ [2012] H. Nakayama, K. Ando, K. Harii, T. Yoshino, R. Takahashi, Y. Kajiwara, K. Uchida, Y. Fujikawa, and E. Saitoh, Geometry dependence on inverse spin hall effect induced by spin pumping in Ni81Fe19/Pt films, Phys. Rev. B 85, 144408 (2012).
  * Martín-Rio  _et al._ [2020] S. Martín-Rio, A. Pomar, L. Balcells, B. Bozzo, C. Frontera, and B. Martínez, Temperature dependence of spin pumping and inverse spin hall effect in permalloy/Pt bilayers, J. Magn. Magn. Mater. 500, 166319 (2020).

Supplementary material for ‘Modulating Spin Current Induced Effective Damping
in $\beta-W/Py$ Heterostructures by a Systematic Variation in Resistivity of
the Sputtered Deposited $\beta-W$ films’

Figure S1: (a) XRD of obliquely deposited Py thin film of thickness 15 nm. The
peak position at $2\theta=44.52^{0}$ confirms the fcc crystal structure, (b)
AFM image (2 $\mu m$ $\times$ 2 $\mu m$) of 15 nm Py thin film with surface
roughness $\approx$ 0.3 nm Figure S2: (a)-(j) AFM images of $\beta$-W
deposited at different $P_{Ar}$ varying from 5.6 mTorr to 10 mTorr, while
maintaining a constant $p_{S}$. The surface morphology tends to become rough
and less crystalline as $P_{Ar}$ increases and the grain size decreases
accordingly. Average roughness is calculated that increases from 0.3 nm to 0.8
nm (5.6 mTorr to 10 mTorr). Figure S3: a)-(e) AFM images of $\beta$-W
deposited at different $p_{S}$ = 330, 250, 180, 150, and 80 watt, while
maintaining a constant $P_{Ar}$. Average roughness increases from 0.1 nm to
0.4 nm as $p_{S}$ is lowered from 330 watt to 80 watt.


# Hybrid MBlur: Using Ray Tracing to Solve the Partial Occlusion Artifacts in
Real-Time Rendering of Motion Blur Effect

Tan Yu Wei  National University of Singapore<EMAIL_ADDRESS>,  Cui Xiaohan
National University of Singapore<EMAIL_ADDRESS>and  Anand Bhojan
National University of Singapore<EMAIL_ADDRESS>
(2020)

###### Abstract.

For a foreground object in motion, details of its background which would
otherwise be hidden are uncovered through its inner blur. This paper presents
a novel hybrid motion blur rendering technique combining post-process image
filtering and hardware-accelerated ray tracing. In each frame, we advance rays
recursively into the scene to retrieve background information for inner blur
regions and apply a post-process filtering pass on the ray-traced background
and rasterized colour before compositing them together. Our approach achieves
more accurate partial occlusion semi-transparencies for moving objects while
maintaining interactive frame rates.

real-time, motion blur, ray tracing, post-processing, hybrid rendering, games

††copyright: rightsretained††journalyear: 2020††conference: SIGGRAPH ’20
Posters; August 17, 2020; Virtual Event, USA††booktitle: Special Interest
Group on Computer Graphics and Interactive Techniques Conference Posters
(SIGGRAPH ’20 Posters), August 17, 2020††doi: 10.1145/3388770.3407436††isbn:
978-1-4503-7973-1/20/08††submissionid: pos_203††ccs: Computing methodologies
Rendering††ccs: Computing methodologies Ray tracing††ccs: Applied computing
Computer games

Figure 1. From left to right: original scene, adapted post-process (McGuire et
al., 2012) (295 fps), UE4 post-process, hybrid (205 fps) and ray-traced MBlur
on The Modern Living Room (CC BY) with a GeForce RTX 2080 Ti

Close-up shot of foreground vase whose left edge covers left edge of cushion
in background

##  1\. Introduction

Blurred regions by nature uncover information of hidden background areas which
are otherwise excluded from the render, as an effect of partial occlusion.
Moving objects blur outwards and inwards at their silhouette, causing the
region surrounding their silhouette to appear semi-transparent (Jimenez,
2014). Outer blur represents an object’s blur into its background, while inner
blur refers to the blur produced within the silhouette of the object itself.

One key to Motion Blur (MBlur) rendering is hence the recovery of background
colour in inner blur regions which is inaccurate with screen space approaches.
Post-process techniques like McGuire et al. (2012) approximate the background
of the inner blur with neighbouring pixels when the background colour of the
target pixel cannot be retrieved from raster information. This approach not
only produces a mere approximation of the true background geometry of inner
blur regions, but also leads to inaccuracies between real and approximated
backgrounds for sharp and blurred regions respectively. Our technique
addresses these issues by obtaining the exact colour of occluded background
with ray tracing for a more accurate MBlur.

##  2\. Design

We first obtain per-pixel information such as camera space depth, world space
surface normal vector, screen space mesh ID and velocity as well as rasterized
colour under deferred shading. The same depth and colour information for
background geometry are retrieved by our novel ray reveal pass within a ray
mask for pixels in the inner blur of moving foreground objects. A tile-dilate
pass is then applied to these 2 sets of buffers to determine the sampling
range of our gathering filter in the subsequent post-process pass which is
adapted from McGuire et al. (2012). Both the ray-revealed result and
rasterized output are then blurred by the post-process pass, and lastly
composited together to produce our final image.

###  2.1. Post-Process

We gather samples from a heuristic range of nearby pixels and compute the
amount of contribution of each sample (McGuire et al., 2012) to produce a
motion-blurred effect separately for rasterized as well as ray-revealed
information.

For the sampling range, McGuire et al. centers the sampling area at the pixel
itself, creating a 2-directional blur effect towards both sides of the
geometry edge as shown in Figure 2. Although this produces more symmetric blur
for thin objects and the specular highlight of curved surfaces, it introduces
complexity in smoothening the transition between the inner and outer blur. Our
approach refrains from this problem by letting the target pixel be at the end
of the sampling area. In this way, inner and outer blur can be considered
separately without much change to the pipeline.

Figure 2. Range of samples for each pixel

Sampling range translated forward by half the magnitude of the velocity as
compared to McGuire et al.

For inner blur, McGuire et al. uses colour information of nearby samples based
on the reasoning that approximate information, though inaccurate, is more
desirable than the absence of any information whatsoever. However, this
creates an inconsistency of background information at the silhouette of moving
foreground objects.

###  2.2. Ray Mask

We obtain true background information by shooting rays within a ray mask,
where only inner blur regions corresponding to geometry edges are marked. For
every pixel with a nonzero speed, we first translate it in the direction of
its velocity for one magnitude of its estimated displacement within the
exposure time and compare the change in depth value and mesh ID. For a pixel
to be in the inner blur region of a foreground object, it would have to be
shallower than its displaced position by a certain amount, and also correspond
to a different mesh ID as part of a separate object. Pixels that do not
satisfy these conditions are hence filtered out.

The remaining pixels are passed into a Sobel convolution kernel which detects
edges based on the differences in surface normal and depth with surrounding
pixels. The result is then evaluated against a high edge threshold to
effectively eliminate non-edges from the edge mask. Lastly, a range check pass
is applied, where each pixel with a nonzero speed samples along its estimated
displacement. If any sample encountered is marked in the edge mask, the pixel
passes into the final ray mask.

###  2.3. Ray Reveal

We adapt recursive ray tracing and shoot rays within inner blur regions,
iteratively advancing them deeper into the scene until a different object is
found. When the recursion terminates, the background originally blocked at the
current view is revealed using information from the final hit point. Although
the accuracy of our motion-blurred background will increase when subsequent
deeper layers are revealed with rays, for efficiency, we limit the ray reveal
to one layer and apply post-process (i.e. approximate using neighbour
information) to achieve our motion-blurred background.

At the pixel level, a ray is dispatched for each pixel within the ray mask and
automatically advanced for recursion after the first hit. The advancing of a
ray is performed by shooting a new ray along the same direction with its
starting point at the latest hit. Currently, luminance is used as an indicator
for identifying different objects. Hence, our approach terminates the
recursive advancing process when the newest hit point reads a luminance
different from the original hit, or the maximum recursion level is met.
However, we hope to switch to using GeometryIndex in DirectX Raytracing Tier
1.1, which will enable the ray tracing shader to distinguish geometries. This
will be more suitable than luminance in scenes with multiple overlapping
objects of the same luminance value.

##  3\. Discussion

We evaluate our method against the state-of-the-art post-process MBlur from
UE4, which adopts a similar approach to McGuire et al.. UE4 also generates
MBlur by comparing the velocity of each pixel to the aggregate pixel velocity
in its neighbourhood.

As seen in Figure 1, post-process MBlur incorrectly reconstructs the
background by reusing neighbouring information available in the rasterized
image. Background colour is hardly visible within the inner blur of the
foreground vase for McGuire et al. as compared to UE4. However, it is clear
that the background for UE4 is mirrored from that outside the inner blur as
seen from the additional cushion edge annotated in yellow. For hybrid MBlur,
we can observe the accurate cushion edge marked in green that corresponds well
to ground truth distributed ray tracing. Here, we manage to sample what is
lost from depth testing in the rasterization pass while maintaining
interactive frame rates.

In future, we hope to better support nonlinear motion within the exposure time
by extending our technique with curve sampling. We are also exploring the
restriction of velocity computation to a pre-defined scene depth if geometry
movement is localized.

###### Acknowledgements.

This work is supported by the Singapore Ministry of Education Academic
Research grant T1 251RES1812, “Dynamic Hybrid Real-time Rendering with
Hardware Accelerated Ray-tracing and Rasterization for Interactive
Applications”.

## References

  * (1)
  * Jimenez (2014) Jorge Jimenez. 2014\.  Advances in Real-Time Rendering in Games, Part I: Next Generation Post Processing in Call of Duty: Advanced Warfare.  http://advances.realtimerendering.com/s2014/#_NEXT_GENERATION_POST
  * McGuire et al. (2012) Morgan McGuire, Padraic Hennessy, Michael Bukowski, and Brian Osman. 2012.  A Reconstruction Filter for Plausible Motion Blur. In _Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games_ (Costa Mesa, California) _(I3D ’12)_. ACM, New York, NY, USA, 135–142.  https://doi.org/10.1145/2159616.2159639


Testing Pushdown Systems In collaboration with Computing Institute - University of Campinas.

Adilson Luiz BonifacioComputing Department, University of Londrina, Londrina, Brazil. Arnaldo Vieira MouraComputing Institute, University of Campinas, Campinas, Brazil

§ INTRODUCTION

Reactive systems have become increasingly common among computer systems,  whether  in a usual technological solution or in a critical application of the industry.
We see everywhere real-world systems being ruled by reactive behaviors where the systems interact with an external environment by receiving input stimuli and producing outputs in response.
Usually the development of such systems requires a precise and an automatic support during the process, specially in the testing activity because high costs in terms of resources and maintenance time can be generated when the test step is inappropriately performed.

Model-based testing is an important approach that has been employed to test critical and reactive systems because it offers guarantees to its correctness and also because properties, such as completeness of test suites, can be formally proven [8, 11].
These aspects have been studied using appropriate formalisms that capture the behavior of reactive systems, where the exchange of input and output stimuli can occur asynchronously.
Prominent among such formalism are Input/Output Labeled Transition Systems (IOLTSs) [15, 16].

Usually, the testing process aims to verify whether an implementation conforms to a given specification, both described using a common chosen formalism [14].
This conformance checking process depends on the specification formalism, on the kind of fault model used, and on a conformance relation that is to be verified [2, 15, 16].
For IOLTS models, the classical Input/Output Conformance (ioco) is a well-studied relation [17, 12, 4].
A more recent work [3] proposed a more general approach, based on regular languages, to check ioco conformance for IOLTS models.

In this work we study aspects of conformance testing and test suite generation for a class of more powerful models, the so called Input/Output Visibly Pushdown Labeled Transition Systems (IOVPTSs), and their associated formalism, Visibly Pushdown Automata (VPAs).
Using an auxiliary pushdown stack, this formalism can capture the behavior of more complex reactive systems.
Accordingly, we use a more general  conformance relation, but one still in the same spirit of the classical ioco relation, in the sense that it prevents any observable implementation behavior that was not already present in the given specification.
We also develop and prove the correctness of an efficient algorithm to verify conformance in this testing scenario.
Further, we show that our algorithm runs in worst case asymptotic polynomial time in the size of both the given specification and the implementation that are put under test.

We organize this paper as follows.
Section <ref> establishes some notations, definitions and preliminary results over VPAs.
Section <ref> defines (IO)VPTSs and relates these models to the associated VPAs.
Section <ref> defines conformance relation based on IOVPTS models, and shows how to obtain complete test suites, of polynomial complexity, for this class of models.
Section <ref> gives an ioco-like conformance relation for IOVPTS models and the notion of test suite completeness, and then provides a  polynomial time algorithm to check ioco-like conformance for IOVPTS implementations.
Section <ref> offers some concluding remarks.

§ NOTATION AND PRELIMINARY RESULTS

In this section we establish some notation and define Visibly Pushdown Automata (VPA).
Some preliminary results that will be useful later are also indicated.

§.§ Basic Notation

Let $X$ and $Y$ be sets. We indicate by $\ypow{X}=\{Z\yst Z\ysse X\}$ the power set of $X$, and $X-Y=\{z\yst \text{$z \in X$ and $z \not\in Y$}\}$ indicates set difference.
We will let $X_Y=X\cup Y$. When $Y=\{y\}$ is a singleton we may also write $X_y$ for $X_{\{y\}}$.
If $X$ is a finite set, the size of $X$ will be indicated by $|X|$.

An alphabet is any non-empty set of symbols.
Let $A$ be an alphabet.
A word over $A$ is any finite sequence $\ysi=x_1\ldots x_n$ of symbols in $A$, that is, $n\geq 0$ and $x_i\in A$, for all $i=1,2,\ldots, n$.
When $n=0$, $\ysi$ is the empty sequence, also indicated by $\yeps$.
The set of all finite sequences, or words, over $A$ is denoted by $A^{\star}$, and the set of all nonempty finite words over $A$ is indicated by $A^+$.
When we write $x_1x_2\ldots x_n\in A^{\star}$, it is implicitly assumed that $n\geq 0$ and that $x_i\in A$, $1\leq i\leq n$, unless explicitly noted otherwise.
The length of a word $\alpha$ over $A$ is indicated by $|\alpha|$.
Hence, $|\yeps|=0$.
Let $\ysi=\ysi_1\ldots \ysi_n$ and $\rho=\rho_1\ldots \rho_m $ be words over $A$. The concatenation of $\ysi$ and $\rho$, indicated by $\ysi\rho$, is the word $\ysi_1\ldots\ysi_n\rho_1\ldots\rho_m$.
Clearly, $|\ysi\rho|=|\ysi|+|\rho|$.
A language $G$ over $A$ is any set $G\ysse A^\star$ of words over $A$.
Let $G_1$, $G_2\ysse A^\star$ be languages over $A$. Their product, indicated by  $G_1G_2$, is the language
$\{\ysi\rho\yst \ysi\in G_1, \rho\in G_2\}$.
If $G\ysse A^\star$ is a language over $A$, then its complement is the language $\ycomp{G}=A^\star-G$.

We will also need the notion of a morphism between alphabets.

Let $A$, $B$ be alphabets.
A homomorphism, or just a morphism, from $A$ to $B$ is any function $h:A\rightarrow B^\star$.

A morphism $h:A\rightarrow B^\star$ can be extended in a natural way to a function
$\widehat{h}:A^\star\rightarrow B^\star$, thus

\begin{equation*}
\widehat{h}(\ysi) =
\begin{cases}
\yeps \quad &\text{if $\ysi=\yeps$}\\
h(a)\widehat{h}(\rho) & \text{if $\ysi=a\rho$ with $a\in A$}.
\end{cases}
\end{equation*}

We can further lift $\widehat{h}$ to a function $\widetilde{h}: \ypow{A^\star}\rightarrow \ypow{B^\star}$ in a natural way, by letting $\widetilde{h}(G)=\bigcup\limits_{\ysi\in G}\widehat{h}(\ysi)$,
for all $G\ysse A^\star$.
In order to avoid cluttering the notation, we may write $h$ instead of $\widehat{h}$, or of $\widetilde{h}$, when no confusion can arise.
When $a\in A$, we define the simple morphism $h_a:A\rightarrow A-\{a\}$ by letting $h_a(a)=\yeps$, and $h_a(x)=x$ when $x\neq a$.
Hence, $h_a(\ysi)$ erases all occurrences of  $a$ in the word $\ysi$.

§ REACTIVE PUSHDOWN  MODELS

In this section we start with the Visibly Pushdown Labeled Transition System (VPTS) and state the relationship with its associated VPA.
Next, we discuss the notion of contracted VPTSs and then introduce the  variation of Input/Output VPTSs.

§.§ Visibly Pushdown Labeled Transition Systems

A Visibly Pushdown Labeled Transition System (VPTS) extends the classical notion of Labeled Transition System (LTS),  a formal model that is convenient to express asynchronous exchange of messages between participating entities, in the sense that outputs do not have to occur synchronously with inputs, but are generated as separated events.
Any LTS has only a finite memory, represented by its set of states.
A VPTS, on the other hand, has a stack memory associated to it, and thus can make use of a potentially infinite memory.

The definition of a VPTS is inspired by the close notion of a Visibly Pushdown Automaton [1].
As will be apparent,  any VPTS naturally induces a VPA.
In particular, internal transitions in the VPTS will correspond to $\yeps$-moves in the associated VPA.

A Visibly Pushdown Labeled Transition System (VPTS)  over an input alphabet $L$ is a tuple $\yS=\yvptsS$, where:

— $S$ is a finite set of states or locations;

— $S_{in}\ysse S$ is the set of initial states;

There  is a special symbol $\ytau\notin L$, the internal action symbol;

— $\Gamma$ is a  set of stack symbols.
There is a special symbol $\bot\not \in \Gamma$, the bottom-of-stack symbol;

$T=T_c \cup T_r \cup T_i$, where $T_c\ysse S\times L_c \times \yGa  \times S$, $T_r\ysse S\times L_r \times \yGa_\bot  \times S$, and $T_i\ysse S\times (L_i\cup\{\ytau\}) \times \{\yait\} \times S$,  where $\yait\not\in\yGa_\bot$ is a place-holder symbol.

Let $t=(p,x,Z,q)\in T$.
If $t\in T_c$ we say that it is a push-transition.
Its intended meaning is that $\yS$, in  state $p\in S$ and reading input $x$,  changes to state $q$ and pushes $Z$ onto the stack.
When $t\in T_r$ we have a pop-transition, with  the intended meaning that $\yS$, in  state $p\in S$ and reading input $x\in L_r$,  pops $Z$ from the top of the stack and changes to state $q$.
Further, when the stack is reduced to the bottom of stack symbol, $\bot$, then a pop move can be taken, leaving the stack unchanged.
We have a simple-transition when $t\in T_i$ and $x\in L_i$, and we have an internal-transition when $t\in T_i$ and $x=\ytau$.
The meaning of a simple-transition $t$ is to change from state $p$ to state $q$, while reading $x$ from the input and leaving the stack unchanged. An internal-transition also changes from state $p$ to state $q$ leaving the stack unchanged, but does not read any symbols from the input.

In order to make these notions precise, we define the set of configurations and the elementary moves of a VPTS.

Let $\yS=\yvptsS$ be a VPTS.
A configuration of $\yS$ is a pair $(p,\yal)\in S\times (\yGas\{\bot\})$.
When $p\in S_{in}$ and $\yal=\bot$, we say that  $(p,\yal)$ is an initial configuration of $\yS$.
The set of all configurations of $\yS$ is indicated by $\yltsconf{\yS}$.
Let $(q,\yal)\in\yltsconf{\yS}$, and let $\ell \in L_\ytau$.
Then we write $\ytr{(p,\yal)}{\ell}{(q,\ybe)}$ if there is a transition $(p,\ell,Z,q)\in T$, and either:

* $\ell \in L_c$, and $\ybe=Z\yal$;

* $\ell \in L_r$, and  either (i) $Z\neq \bot$ and $\yal=Z\ybe$, or (ii) $Z=\yal=\ybe=\bot$;

* $\ell \in L_i \cup \{\ytau\}$ and $\yal=\ybe$.

We call $\ytr{(p,\yal)}{\ell}{(q,\ybe)}$ an elementary move of $\yS$, and we say that $(p,\ell,Z,q)\in T$ is the transition used in the move  $\ytr{(p,\yal)}{\ell}{(q,\ybe)}$.

It is clear from the definition that after any elementary move $\ytr{(p,\yal)}{\ell}{(q,\ybe)}$ we have  $(q,\ybe)\in\yltsconf{\yS}$, that is, $(q,\ybe)$ is also a configuration of $\yS$.
Moreover, it also clear that we always have $\yal=\yal'\bot$ and $\ybe=\ybe'\bot$ with $\yal'$, $\ybe'\in \yGa^\star$,

In figures depicting VPTSs, a push-transition $(s,x,Z,q)$ will be graphically represented by $x/\ypush{Z}$ next to the corresponding arc from $s$ to $q$.
Similarly, the label $x/\ypop{Z}$ next to an arc from $s$ to $q$ will indicate a pop-transition $(s,x,Z,q)$.
A simple- or internal-transition over $(s,x,\yait,q)$ will be indicate by the label $x$ next to the corresponding arc.

Figure <ref> represents a VPTS $\yS$ where the set of states is $S=\{s_0,s_1\}$, $S_{in}=\{s_0\}$.
Also, we have $L_c=\{b\}$, $L_r=\{c,t\}$, and $L_i=\{\}$, and $\yGa=\{Z\}$.

We have a push-transition $(s_0,b,Z,s_0)$, the pop-transitions
$(s_0,c,Z,s_1)$, $(s_0,t,Z,s_1)$, $(s_1,c,Z,s_1)$, $(s_1,t,Z,s_1)$, and the internal-transition $(s_1,\ytau,\yait,s_0)$.

The semantics of a VPTS is given by its traces, or behaviors.
But first we need the notion of paths in VPTS models which are just chains of elementary moves.

Let $\yS=\yvptsS$ be a VPTS and let $(p,\yal),(q,\ybe)\in\yltsconf{\yS}$ .

* Let $\ysi=l_1,\ldots,l_n$ be a word in $L_\ytau^\star$. We say that $\ysi$ is a path from  $(p,\yal)$ to $(q,\ybe)$ if there are configurations  $(r_i, \yal_i)\in\yltsconf{\yS}$ , $0\leq i\leq n$, such that $\ytr{(r_{i-1},\yal_{i-1})}{l_i}{(r_i,\yal_i)}$, $1\leq i\leq n$,  with $(r_0,\yal_0)=(p,\yal)$ and $(r_n,\yal_n)=(q,\ybe)$.

* Let $\ysi\in L^\star$. We say that $\ysi$ is an observable path  from $(p,\yal)$ to $(q,\ybe)$ in $\yS$ if
there is a path $\mu$ from $(p,\yal)$ to $(q,\ybe)$ in $\yS$ such that $\ysi=h_\ytau(\mu)$.

In both cases we also say that the path starts at $(p,\yal)$ and ends at $(q,\ybe)$, and we say that the configuration $(q,\ybe)$ is reachable from $(p,\yal)$.
We also say that $(q,\ybe)$ is reachable in $\yS$ if it is reachable from an initial configuration of $\yS$.

Clearly, moves labeled by the internal symbol $\ytau$ can occur in a path.
An observable path is just a path from which $\ytau$-labels  were removed.
If $\ysi$ is a path from $(p,\yal)$ to $(q,\ybe)$, this can also be indicated  by writing $\ytr{(p,\yal)}{\ysi}{(q,\ybe)}$.
When $\vert\ysi\vert=1$ this has exactly the same meaning as indicated in Definition <ref>, so that no confusion can arise with this notation.
We may also write $\ytr{(p,\yal)}{\ysi}{}$ to indicate that there is some $(q,\ybe)\in \yltsconf{\yS}$ such that  $\ytr{(p,\yal)}{\ysi}{(q,\ybe)}$; likewise, $\ytr{(p,\yal)}{}{(q,\ybe)}$ means that there is some $\ysi\in L_\ytau^*$ such that $\ytr{(p,\yal)}{\ysi}{(q,\ybe)}$.
Also $\ytr{(p,\yal)}{}{}$ means $\ytr{(p,\yal)}{\ysi}{(q,\ybe)}$ for some $(q,\ybe)\in \yltsconf{\yS}$ and some $\ysi\in L_\ytau^*$.
When $\ysi$ is an observable path from $(p,\yal)$ to $(q,\ybe)$ we may write $\ytrt{(p,\yal)}{\ysi}{(q,\ybe)}$, with similar
shorthand notation also carrying over to the $\ytrt{}{}{}$ relation.
When we want to emphasize that the underlying VPTS is $\yS$, we write $\ytru{(p,\yal)}{\ysi}{\yS}{(q,\ybe)}$, or $\ytrut{(p,\yal)}{\ysi}{\yS}{(q,\ybe)}$.

Paths starting at a given configuration $(p,\yal)$ are also called the traces of $(p,\yal)$, or the traces starting at $(p,\yal)$.
The semantics of a VPTS is related to traces starting at an initial configuration.

Let $\yS=\yvptsS$ be a VPTS and let $(p,\yal)\in \yltsconf{\yS}$.

* The set of traces of $(p,\yal)$ is   $tr(p,\yal)=\{\ysi\yst \ytr{(p,\yal)}{\ysi\,\,}{}\}$.
The set of observable traces of $(p,\yal)$ is $otr(p,\yal)= \{\ysi\yst \ytrt{(p,\yal)}{\ysi\,\,}{}\}$.

* The semantics of $\yS$ is $\bigcup\limits_{q\in S_{in}}\!\!\!\!tr(q,\bot)$, and the observable semantics of $\yS$ is
$\bigcup\limits_{q\in S_{in}}\!\!\!\!otr(q,\bot)$.

We will also indicate the semantics and, respectively, the observable semantics, of $\yS$ by
$tr(\yS)$ and $otr(\yS)$.

In any VPTS $\yS=\yvptsS$, if $\ytrt{(s,\yal)}{}{(p,\ybe)}$ then we also have $\ytr{(s,\yal)}{}{(p,\ybe)}$ in $\yS$, for all $(s,\yal)$, $(p,\ybe)\in \yltsconf{\yS}$.
Moreover, $otr(\yS)=h_\ytau(tr(\yS))$.
When $\yS$ has no internal transitions we also have $otr(\yS)=tr(\yS)$.

We can also restrict the syntactic description of VPTS models somewhat,  without loosing any descriptive capability, by removing states that are not reachable from any initial state, since these states
will play no role when considering any system behaviors.
Moreover, we can also eliminate $\ytau$-labeled self-loops.
We formalize these observations in the following remark.

Let $\yS=\yvptsS$ be a VPTS.
For any $s\in S$ we postulate that  $\ytr{(s_0,\bot)}{\ysi}{(s,\yal\bot)}$, for some $\yal\in\yGas$,
$\ysi\in L_\ytau^\star$,  and $s_0\in S_{in}$.
Also, if $(s,\ytau,\yait,q)\in T$ then $s\neq q$.

The intended meaning for  $\ytau$-moves in VPTSs is similar to that given for LTS models [3], that is,
a VPTS can autonomously move along $\ytau$-transitions, without consuming any input symbol.
However, in some situations such moves may not be desirable, or  simply we might want no observable behavior leading to two distinct states.
This motivates the notion of determinism in VPTS models.

Let $\yS=\yvptsS$ be a VPTS.
We say that $\yS$ is deterministic if, for all   $s$, $p\in S_{in}$, $s_1$, $s_2\in S$, $\ybe_1,\ybe_2 \in \yGas$, and $\ysi\in L^\star$,
we have that 	$\ytrut{(s,\bot)}{\ysi}{}{(s_1,\ybe_1\bot)}$ and $\ytrut{(p,\bot)}{\ysi}{}{(s_2,\ybe_2\bot)}$ imply	$s_1=s_2$ and $\ybe_1=\ybe_2$.

As a consequence, deterministic VPTSs do not have internal moves.

Let $\yS=\yvptsS$ be a deterministic VPTS.
Then $\yS$ has no $\ytau$-labeled transitions.

By contradiction, assume that $(s,\ytau,\yait,q)\in T$.
From Remark <ref> we get $s\neq q$ and we also get $\yal\in\yGas$, $\ysi\in\ L^\star$ such that $\ytr{(s_0,\bot)}{\ysi}{(s,\yal\bot)}$, with $s_0\in S_{in}$.
Hence, $\ytr{(s_0,\bot)}{\ysi}{(s,\yal\bot)}\ytr{}{\ytau}{(q,\yal\bot)}$.
Using Definition <ref> we get $\ytrt{(s_0,\bot)}{\mu}{(s,\yal\bot)}$ and $\ytrt{(s_0,\bot)}{\mu}{(q,\yal\bot)}$, where $\mu=h_\ytau(\ysi)$.
Since $s\neq q$, this contradicts Definition <ref>.

§.§ Contracted VPTSs

It will also be useful, later on, to count on a guarantee that every transition in a VPTS can be exercised by some trace of the model.
Since every transition, except possibly for pop transitions, can always be taken, we concentrate on the pop transitions.

We say that a VPTS $\yS=\yvpts{S}{S_{in}}{L}{\yGa}{T}$ is contracted if for every transition $(p,b,Z,r) \in T$ with $b\in L_r$, there are some $s_0\in S_{in}$, $\yal\in\yGa^\star$ and $\ysi\in L ^\star$ such that $\ytrt{(s_0,\bot)}{\ysi}{(p,\yal\bot)}$, where either (i) $\yal=Z\ybe$ for some $\ybe\in\yGa^\star$, or (ii) $\yal=\yeps$ and $Z=\bot$.

We  can obtain contracted VPTSs using the next Proposition <ref>.
The idea is to construct a context free grammar (CFG) based on the given VPTS, in such a way that the CFG generates strings where terminals represent VPTS transitions.
The productions of the CFG will indicate the set of transitions that can be effectively used in a trace over the VPTS.

Let $\yS=\yvpts{S}{S_{in}}{L}{\yGa}{T}$ be a VPTS.
We can effectively construct a contracted VPTS $\yQ=\yvpts{Q}{Q_{in}}{L}{\yGa}{R}$ with $\vert Q\vert\leq \vert S\vert$,
and such that $tr(\yS)=tr(\yQ)$.
Moreover, if $\yS$ is deterministic, then $\yQ$ is also deterministic.

First we construct a context-free grammar $G$ whose terminals represent transitions of $\yS$.
Non-terminals are of the form $[s,Z,p]$ where $s, p\in S$ are states of $\yS$ and $Z\in\yGa_\bot$ is a stack symbol.
The main idea  can be grasped as follows.
Let $t_i=[s_i,a_i,Z_i,p_i]$, $1\leq i\leq n$ be transitions of $\yS$ and let $\ysi=a_1a_2\cdots a_n$ be an input string.
If  $G$ has a leftmost derivation

$$\ycfgtrtfl{[s_0,\bot,-]}{\star}{}{t_1\cdots t_n[r_1,W_1,r_2][r_2,W_2,r_3]\cdots[r_m,W_m,r_{m+1}][r_{m+1},\bot,-]}$$

it must be the case that $\yS$, starting at the initial configuration $(s_0,\bot)$, can move along the transitions $t_1, \ldots, t_n$., in that order, to reach the configuration $(r_1,W_1W_2\cdots W_m\bot)$.
That is, $\ytr{(s_0,\bot)}{\ysi}{(r_1,W_1W_2\cdots W_m\bot)}$, where $\ysi=a_1a_2\cdots a_n$.
And vice-versa.

We then show that leftmost derivations of $G$ faithfully simulate traces of $\yS$ and, conversely, that any trace of $\yS$ can be simulated by a leftmost derivation of $G$.
That done, we can easily extract from $G$ a contracted VPTS $\yQ$.
A simple argument then proves that $L(\yQ)=tr(\yS)$.

The complete construction and detailed proofs can be found in Appendix app:prop:contracted-vpts.

§.§ Relating VPTS and VPA models

Now we show that any VPTS $\yS$  gives rise to an associated VPA $\yS_\yA$ in a natural way.
We convert any $\ytau$-transition of $\yS$  into a $\yeps$-transition of $\yS_\yA$.
The set of final states of $\yS_\yA$ is just the set of all locations of $\yS$.
Conversely, we can associate a VPA to any given VPTS, provided that all states in the given VPA are final states.

We have the following two associations:

* Let $\yS=\yvptsS$ be a VPTS.
The VPA induced by $\yS$ is  $\yA_\yS=\yvpa{S}{S_{in}}{L}{\yGa}{\rho}{S}$ where, for all $p$, $q\in S$,  $Z\in \yGa$,  $\ell\in L$, we have:

* $(p,\ell,Z,q)\in \rho$ if and only if $(p,\ell,Z,q)\in T$;

* $(p,\yeps,\yait,q)\in \rho$ if and only if $(p,\ytau,\yait,q)\in T$.

* Let $\yA=\yvpa{S}{S_{in}}{L}{\yGa}{\rho}{S}$ be a VPA.
The VPTS induced by $\yA$ is $\yS_\yA=\yvpts{S}{S_{in}}{L}{\yGa}{T}$ where:

* $(p,\ell,Z,q)\in T$ if and only if $(p,\ell,Z,q)\in \rho$;

* $(p,\ytau,\yait,q)\in T$ if and only if $(p,\yeps,\yait,q)\in \rho$.

The relationship between the associated models is given by the following result.

$\yS=\yvptsS$ be a VPTS and  $\yA=\yvpa{S}{S_{in}}{L}{\yGa}{\rho}{S}$ a VPA.
Assume that either $\yA$ is the VPA induced $\yS$, or $\yS$ is the VPTS induced by $\yA$.
Then, the following are equivalent, where $\ysi\in L^\star$, $\mu\in (L_\ytau)^\star$,  $s,p\in S$, $\yal,\ybe \in\yGa^\star$, $n\geq 0$:

* $\ytrut{(s,\yal\bot)}{\ysi}{\yS}{(p,\ybe\bot)}$

* $\ytrtf{(s,\yal\bot)}{\mu}{\yS}{(p,\ybe\bot)}$, $h_\ytau(\mu)=\ysi$

* $\ypdatrtf{(s,\ysi,\yal\bot)}{n}{\yA}{(p,\yeps,\ybe\bot)}$,  $n=\vert\mu\vert$

From Definition <ref> we see that (1) and (2) are equivalent, for any VPTS $\yS$.

If $\yA$ is the VPA induced by $\yS$ then, using Definition <ref>(1), an easy induction on $\vert\mu\vert\geq 0$ shows that if (2) holds then (3) also holds with $n=\vert\mu\vert$.
Likewise, an easy induction on $n\geq 0$ shows that if (3) holds, then we get some $\mu$ satisfying (2) and with $\vert\mu\vert=n$.
If $\yS$ is the VPTS induced by the VPA $\yA$ then the reasoning is very similar, now using  Definition <ref>(2).

The observable semantics of $\mathcal{S}$ is just the language accepted by $A_\mathcal{S}$.
We note this as the next proposition.

Let $\yS$ be a VPTS and  $\yA_{\yS}$ the VPA induced by $\yS$.
Then $otr(\yS)=L(\yA_{\yS})$ and, further, if $\yS$ is deterministic and contracted
then $\yA_\yS$ is also deterministic.
Conversely, let $\yA$ be a VPA and $\yS_\yA$ the VPTS induced by $\yA$.
Then $L(\yA)=otr(\yS_\yA)$
and, also,
if $\yA$ is deterministic and has no $\yeps$-moves, then $\yS_\yA$ is deterministic.

Let $\yS=\yvptsS$ and  $\yA_\yS=\yvpa{S}{S_{in}}{L}{\yGa}{\rho}{S}$.
Then, $otr(\yS)=L(\yA_\yS)$ follows directly from Proposition <ref>.

Now assume that $\yS$ is deterministic and contracted.
We show that $\yA_\yS$  satisfies Definition <ref>.
First, take $p$, $q\in S_{in}$.
Then, we have $\ytrt{(p,\bot)}{\yeps}{(p,\bot)}$ and $\ytrt{(q,\bot)}{\yeps}{(q,\bot)}$ in $\yS$.
Since $\yS$ is deterministic, Definition <ref> gives $p=q$.
This shows that $\vert S_{in}\vert\leq 1$, as required by Definition <ref>.

Next, we look at the three assertions at Definition <ref>.
First, let $(p,\ell,Z_i,q_i)\in\rho_c$,  $i=1,2$.
Since $\ell\in L_c$, Definition <ref> gives $(p,\ell,Z_i,q_i)\in T$ for $i=1,2$. From Remark <ref> we obtain some $\ysi\in L^\star$ and $s_0\in S_{in}$ such that $\ytrut{(s_0,\bot)}{\ysi}{\yS}{(p,\yal\bot)}$ for some $\yal\in\yGa^\star$.
$\ytrut{(s_0,\bot)}{\ysi\ell}{\yS}{(q_i,Z_i\yal\bot)}$ for $i=1,2$.
Since $\yS$ is deterministic, Definition <ref> gives $q_1=q_2$ and $Z_1=Z_2$.
We conclude that $A_\yS$ satisfies condition 1 at Definition <ref>.
Now suppose we have $(p,\ell,Z,q_i)\in\rho_r\cup \rho_i$, $i=1,2$.
Since $\ell\in L_r\cup L_i$, Definition <ref> gives $(p,\ell,Z,q_i)\in T$, $i=1,2$.
When $\ell\in L_i$ we get $Z=\yait$, and proceed exactly as in the first case.

When $\ell\in L_r$, since $\yS$ is contracted, Proposition <ref>  gives  $s_0\in S_{in}$, $\ysi\in L^\star$ and $\yal\in\yGa^\star$ such that  $\ytrut{(s_0,\bot)}{\ysi}{\yS}{(p,\yal\bot)}$.
Further, $\yal= Z\ybe$ when $Z\neq \bot$, or $\yal=\yeps$ when $Z=\bot$.
In the first case, $\ytrut{(s_0,\bot)}{\ysi\ell}{\yS}{(q_i,\ybe\bot)}$ and, in the second case,  $\ytrut{(s_0,\bot)}{\ysi\ell}{\yS}{(q_i,\bot)}$, $i=1,2$.
Thus, because $\yS$ is deterministic, Definition <ref> forces
gives $q_1=q_2$.
We conclude that $A_\yS$ satisfies condition 2 at Definition <ref>.
Finally suppose we have $(p,x,Z,q_1)\in\rho$ and $(p,\yeps,Z,q_2)\in\rho$ with $x\neq \yeps$.
Then, Definition <ref> gives $(p,\ytau,\yait,q_2)\in T$
and $(p,x,Z,q_1)\in T$.
Since $\yS$ is deterministic, Proposition <ref> says that it has no $\ytau$-transitions, and we reached a contradiction.
Hence,  $A_\yS$ satisfies condition 3 at Definition <ref>, and the proof is complete.

For the converse, let $\yA=\yvpa{S}{S_{in}}{L}{\yGa}{\rho}{S}$ and $\yS_\yA=\yvptsS$.

Again, $otr(\yA)=otr(\yS_\yA)$ is immediate from Proposition <ref>.
Now assume that $\yA$ is deterministic and has no $\yeps$-moves.
Clearly, from the construction, we know that $\yS_\yA$ has no $\ytau$-moves.
Let $\ytrut{(s,\bot)}{\ysi}{\yS_\yA}{(s_1,\ybe_1\bot)}$ and
$\ytrut{(p,\bot)}{\ysi}{\yS_\yA}{(s_2,\ybe_2\bot)}$ with $p,s\in S_{in}$ and $\ysi\in L^\star$.
Since $\yA$ is deterministic, we get $\vert S_{in}\vert\leq 1$, so that $p=s$.
Using Definition <ref>, and since $\yS_\yA$ has no $\ytau$-moves, we get
$\ytrtf{(s,\bot)}{\ysi}{\yS_\yA}{(s_1,\ybe_1\bot)}$ and
From Proposition <ref> we get
$\ypdatrtf{(s,\ysi,\bot)}{n}{\yA}{(s_1,\yeps,\ybe_1\bot)}$ and
$\ypdatrtf{(s,\ysi,\bot)}{n}{\yA}{(s_2,\yeps,\ybe_2\bot)}$, where $n=\vert \ysi\vert$.
Now, since $\yA$ is deterministic, we can use Proposition <ref> and conclude that $s_1=s_2$ and $\ybe_1=\ybe_2$.
This shows that $\yS_\yA$ satisfies  Definition <ref>, completing the proof.

Lemma <ref> also says that $otr(\yS)$ is a visibly pushdown language, and that
for any given VPTS $\yS$, we can easily construct a VPA $\yA$ with $L(\yA)=otr(\yS)$.

§.§ Input Output Pushdown Transition Systems

The VPTS formalism can be used to model systems with a potentially infinite memory and with a capacity to interact asynchronously with an external environment.
In such situations, we may want to treat some action labels as symbols that the VPTS “receives” from the environment, and some other action labels as symbols that the VPTS “sends back” to the environment.
The next VPTS variation differentiates between input action symbols and output action symbols.

An Input/Output Visibly Pushdown Transition System (IOVPTS) over an alphabet $L$ is a tuple $\yI=\yiovptsS$, where

* $L_I$ is a finite set of input actions, or input labels;

* $L_U$ is a finite set of output actions, or output labels;

* $L_I\cap L_U=\emptyset$, and $L=L_I\cup L_U $ is the set of actions or labels; and

* $\yvptsS$ is an  underlying VPTS over $L$, which is associated to $\yI$.

denote the class of all IOVPTSs with input alphabet $L_I$ and output alphabet $L_U$ by $\yiovp{L_I}{L_U}$.

In order to keep the number of definitions under control, we agree that in any reference to a notion based on IOVPTSs, and  that has not been explicitly defined at some point, we substitute the IOVPTS model by its underlying VPTS.
As a case in point, if $\yS$ is any IOVPTS with $\yV$ as its underlying VPTS, then the VPA induced by $\yS$ is simply the VPA induced by $\yV$, according to Definition <ref>.
Likewise for any formal assertion involving IOVPTS models.
For example, using Proposition <ref> we can just say that $otr(\yS)=L(\yA_\yS)$ without any explicit mention to the underlying VPTS $\yV$.

The semantics of an IOVPTS is just the set of its observable traces, that is, observable traces of its underlying VPTS.

Let $\yI=\yiovptsS$ be an IOVPTS.
The semantics of $\yI$ is the set $otr(\yI)=otr(\yS_\yI)$,
where $\yS_\yI$ is the underlying VPTS associated to $\yI$.

Also, when referring an IOVPTS $\yI$, the notation $\underset{\yI}{\rightarrow}$ and $\underset{\yI}{\Rightarrow}$ are to be understood as $\underset{\yS}{\rightarrow}$ and $\underset{\yS}{\Rightarrow}$, respectively, where $\yS$ is the underlying VPTS associated to $\yI$.

Figure <ref> represents an IOVPTS that describes a machine that dispenses drinks.
Here we have $L_I=\{b\}$ and $L_U=\{c,t\}$. From the context we can see that $L_c=\{b\}$, $L_r=\{c,t\}$ and $L_i=\yemp$.

The start state is $s_0$.
Symbol $b$ stands for button an user can press when asking for a drink, namely a cup of coffee or a cup of tea, with corresponding buttons represented by the labels $c$ and $t$, respectively.
The user can hit the $b$ button while the machine stays at state $s_0$.
Each time the $b$ button is activated, the machine pushes the symbol $Z$ on the stack, so that the stack is used to count how many times the $b$ button was hit by the user.

At any instant, after the user has activated the $b$ button at least once, the machine moves to state $s_1$ and starts dispensing either coffee or tea, indicated by the $c$ and $t$ buttons.
It decrements the stack each time a drink is dispensed, so that it will never deliver more drinks than the user asked for.

A move back to state $s_0$, over the internal label $\ytau$, may interrupt the delivery of drinks, so that the user can, possibly, receive less drinks than originally asked for.
In this case, when the next user will operate  the machine with  residual number of $Z$ symbols in the stack he could, eventually collect more drinks than asked for.
But the machine will never dispense more drinks than the total number of solicitations.
An alternative could be to use one more state $s_2$ to interrupt the transition from $s_1$ to $s_0$ and install a self-loop at $s_2$ that empties the stack.
A more complex and complete version of a drink dispensing machine is illustrated in Subsection <ref>.

We register one more example which will be used later.

Figure <ref> depicts another IOVPTS, where $L_I=\{a,b\}$, $L_U=\{x\}$, $L_c=\{a\}$, $L_r=\{b,x\}$ and $L_i=\emptyset$.
Also, $S_{in}=\{s_0\}$ and $\yGa=\{A\}$.

§ CONFORMANCE CHECKING AND VISIBLY PUSHDOWN LANGUAGES

In this section we define a more general conformance relation based on  Visibly Pushdown Languages [1], a proper subset of the more general class of context-free languages [9], but a proper superset of the regular languages.
Next we study the notion of test suite completeness

and give a polynomial time complexity method to check conformance between an IUT and its specification, both based on VPTS models, and using the more general conformance relation over VPLs.

§ AN IOCO-LIKE CONFORMANCE CHECKING FOR IOVPTS MODELS

In this section we investigate whether IUTs, also described as IOVPTS models, conform to a given specification IOVPTS model.
Here we use a new notion of an ioco-like conformance relation for IOVPTSs.
That notion captures the same idea as the standard notion of conformance as studied by Tretmans [17], but using Labeled Transition Systems (LTSs) which do not have access to a pushdown stack memory.
The idea is that, given a specification $\yS$ and an IUT $\yI$, we say whether $\yI$ ioco-like conforms to $\yS$ when, for any valid observable behavior $\ysi$ of $\yS$, any output symbol that $\yI$ can emit after running over $\ysi$ is, necessarily, among the output symbols that $\yS$  can also emit after it runs over the same $\ysi$.

§ CONCLUDING REMARKS

Testing conformance of reactive systems implementations is usually a hard task, due to the intrinsic nature of reactive systems, which allows for the asynchronous interactions of messages with an external environment.
In such situations, rigorous approaches capable of generating test suites for these models, are indicated.
Several methods have been developed in order to generate test suites for reactive systems that can be modeled by formal systems which  have access only to a finite memory, or a finite number of states.

Here we study a more powerful class of reactive systems, those can make use of a potentially infinite memory, the form of a pushdown stack.

We defined a corresponding more general conformance relation for these systems.
We also showed the existence, and how to generate, test suites that can be used to verify whether this more general conformance relation holds between a given specification and a proposed implementation.
Further, we argued that these test suites can be generated in polynomial time, and that they are also complete, that is,
a given implementation does conform to a given specification if and only if the test suite verdict indicates that this is the case.

For such reactive systems with a pushdown stack, we also defined a conformance relation, called ioco-like, that embodies the same idea as the classic ioco conformance relation that is used for testing simpler systems, namely, those cannot make use of a potentially infinite memory.
Essentially, these conformance relations say that the implementation can only emit an output signal that is already present in the  specification, after a common exchange of symbols has taken place in both models.
We showed that  ioco-like conformance is a special case of the more general conformance relation we treat in this work.
We also developed, and proved correct, a polynomial time algorithm that can be used to test for ioco-like conformance between an implementation and a given specification.
In common practical situations the algorithm exhibits an asymptotic worst case time complexity that can be bounded by $\yoh{n^3+m^3}$ where $n$ and $m$
are proportional to the cube of the product of the number of states and transitions, respectively, present in the implementation and in the specification.

[1]
Rajeev Alur and P. Madhusudan.
Visibly pushdown languages.
In Proceedings of the Thirty-sixth Annual ACM Symposium on
Theory of Computing, STOC '04, pages 202–211, New York, NY, USA, 2004. ACM.

[2]
Saswat Anand, Edmund K. Burke, Tsong Yueh Chen, John Clark, Myra B. Cohen,
Wolfgang Grieskamp, Mark Harman, Mary Jean Harrold, Phil McMinn, and
An orchestrated survey of methodologies for automated software test
case generation.
Journal of Systems and Software, 86(8):1978–2001, 2013.

[3]
Adilson Luiz Bonifacio and Arnaldo Vieira Moura.
Testing asynchronous reactive systems: Beyond the ioco framework.
CLEI Electron. J., 24(10), 2021.

[4]
Adilson Luiz Bonifacio and Arnaldo Vieira Moura.
Complete Test Suites for Input/Output Systems.
arXiv e-prints, page arXiv:1902.10278, Feb 2019.

[5]
LUCA BREVEGLIERI, ALESSANDRA CHERUBINI, CLAUDIO CITRINI, and STEFANO CRESPI
Multi-push-down languages and grammars.
International Journal of Foundations of Computer Science,
07(03):253–291, 1996.

[6]
Dario Carotenuto, Aniello Murano, and Adriano Peron.
2-visibly pushdown automata.
In Tero Harju, Juhani Karhumäki, and Arto Lepistö, editors,
Developments in Language Theory, pages 132–144, Berlin, Heidelberg,
2007. Springer Berlin Heidelberg.

[7]
A. Finkel, B. Willems, and P. Wolper.
A direct symbolic approach to model checking pushdown systems.
In INFINITY, pages 27–37, 1997.

[8]
A. Gargantini.
Conformance testing.
In M. Broy, B. Jonsson, J.-P. Katoen, M. Leucker, and A. Pretschner,
editors, Model-Based Testing of Reactive Systems: Advanced Lectures,
volume 3472 of Lecture Notes in Computer Science, pages 87–111.
Springer-Verlag, 2005.

[9]
J. E. Hopcroft and J. D. Ullman.
Introduction to Automata Theory, Languages, and Comutation.
Addison Wesley, 1979.

[10]
Martin Lange.
P-hardness of the emptiness problem for visibly pushdown languages.
Inf. Process. Lett., 111(7):338–341, March 2011.

[11]
Deepinder P. Sidhu and Ting-kau Leung.
Formal methods for protocol testing: A detailed study.
IEEE Trans. Softw. Eng., 15(4):413–426, 1989.

[12]
Adenilso Simão and Alexandre Petrenko.
Generating complete and finite test suite for ioco is it possible?
In Ninth Workshop on Model-Based Testing (MBT 2014), pages
56–70, 2014.

[13]
Michael Sipser.
Introduction to the Theory of Computation.
International Thomson Publishing, 1996.

[14]
G. J. Tretmans.
Test generation with inputs, outputs and repetitive quiescence.
Technical Report TR-CTIT-96-26, Centre for Telematics and Information
Technology University of Twente, Enschede, 1996.

[15]
Gerrit Jan Tretmans.
A formal approach to conformance testing.
PhD thesis, University of Twente, Enschede, December 1992.

[16]
Jan Tretmans.
Testing concurrent systems: A formal approach.
In J.C.M Baeten and S. Mauw, editors, CONCUR '99: Proceedings of
the 10th International Conference on Concurrency Theory, volume 1664 of Lecture Notes in Computer Science, pages 46–65, London, UK, 1999.

[17]
Jan Tretmans.
Model based testing with labelled transition systems.
In Formal Methods and Testing, pages 1–38, 2008.

§ CONSTRUCTIONS AND PROOFS

In this appendix we present complete constructions and detailed proofs.