# Periodic strings: a mechanical analogy to photonic and phononic crystals

R. S. Pitombo<EMAIL_ADDRESS>Instituto de Física Teórica, UNESP - Univ.
Estadual Paulista, ICTP South American Institute for Fundamental Research, Rua
Dr. Bento Teobaldo Ferraz 271, 01140-070, São Paulo, SP, Brazil  M.
Vasconcellos<EMAIL_ADDRESS>Instituto de Física, Universidade
Federal Fluminense, 24210-346, RJ, Brazil  P. P. Abrantes
<EMAIL_ADDRESS>Departamento de Física, Universidade Federal de São
Carlos, Rodovia Washington Luís, km 235 - SP-310, 13565-905, São Carlos, SP,
Brazil  Reinaldo de Melo e Souza<EMAIL_ADDRESS>Instituto de Física,
Universidade Federal Fluminense, 24210-346, RJ, Brazil  G. M. Penello
<EMAIL_ADDRESS>Instituto de Física, Universidade Federal do Rio de
Janeiro, 21941-972, RJ, Brazil  C. Farina<EMAIL_ADDRESS>Instituto de
Física, Universidade Federal do Rio de Janeiro, 21941-972, RJ, Brazil

###### Abstract

We study a periodic vibrating string composed of a finite sequence of string
segments connected periodically, with each segment characterized by a constant
linear mass density. The main purpose is to provide a configuration that can
mimic the properties of photonic or phononic crystals and could be implemented
in undergraduate physics laboratories. We demonstrate that this configuration
displays frequency intervals for which wave propagation is not allowed
(frequency bandgaps), in close analogy to photonic and phononic crystals. We
discuss the behavior of these bandgaps when varying physical parameters, such
as the values of the linear mass densities, the oscillation frequency, and the
number of strings constituting the entire system. Some analogies with the
propagation of electronic waves through a crystal lattice in condensed matter
physics are also explored.

##  I Introduction

First proposed in 1987 by Yablonovitch [1] and John [2], a photonic crystal is
an arrangement of different material media so that its effective optical
properties are periodic. This configuration can be achieved by a sequence of
periodic structures of equally spaced materials with alternating dielectric
constants. Historically, however, the study of one-dimensional periodic
structures dates back to 1887 with Lord Rayleigh [3], who analyzed an
experiment performed by Stokes and showed the existence of high reflectivity
of light over a narrow well-defined frequency range.

When the period of the spatial modulation is comparable to the wavelength of
the light propagating through the material, photonic bandgaps appear –
frequency ranges in which light propagation is forbidden in certain directions
[4, 5, 6, 7, 8, 9]. These are the photonic crystals, electromagnetic analogs
to crystalline solids in which forbidden energy bandgaps appear [10]. An
essential aspect is that these bandgaps heavily depend on the spatial pattern,
leading to several strategies for manufacturing photonic crystals [11, 12].
For further study concerning other properties and numerical modeling of these
materials, as well as experimental details on their fabrication and
characterization, see Refs. [4, 8] and references therein.

Since their discovery, photonic crystals have offered a remarkable chance for
light manipulation, attracting much research interest. Because of their
capacity to confine and control light of an arbitrary wavelength, such
materials have allowed for a variety of technological applications beyond the
field of optical physics, such as in optoelectronics [13], displays [14],
sensors [15], solar cells [16], light-emitting diodes [17], optical fibers
[18], and in the construction of high-efficiency reflectors [19]. In nature,
photonic crystals are also present from inorganic opals [20] to different
organic structures in butterfly wing scales, beetle scales, and bird feathers
[21].

Similarly, the propagation of elastic or acoustic waves in periodic composite
media also produces bandgaps, which gave rise to the concept of phononic
crystals, initially proposed in 1992 by Sigalas and Economou [22] and later in
1993 by Kushwaha and collaborators [23]. Since then, such systems have been
extensively studied, presenting different applications in engineering and
applied physics, such as in vibration reduction [24] and noise control [25].
Recent reviews covering these periodic structures can be found in [26, 27,
28]. Similar phenomenology can be found in semiconductors heterostructures, as
can be appreciated in Ref. [29] and references therein.

Therefore, the investigation of optical and acoustic responses of periodic
structures plays a key role in current research topics. This study involves
techniques and concepts rarely discussed in standard undergraduate textbooks.
An alternative that has been widely used to emulate one-dimensional photonic
crystals, both theoretically and experimentally, involves coaxial cables [30,
31, 32, 33, 34, 35]. However, the essential aspect for the appearance of
bandgaps is the interference of waves, thereby appearing in any wave
phenomena. In this regard, we propose the study of a conceptually simpler
configuration: the periodic string, which requires only an introductory
classical mechanics background. Such a configuration consists of a finite
sequence of string segments connected, presenting periodically alternating
linear mass densities, which play the role of dielectric permittivities
(densities) in photonic (phononic) crystals. This analogy is possible because
the light (sound) velocity in a given material is a function of its
permittivity (density), while the wave velocity in a string depends on its
linear mass density. As in the context of photonic crystals, the bandgaps
appear because periodicity implies a destructive interference for waves with
frequencies in ranges denominated frequency bandgaps. Pedagogically, it is
enlightening to see these bandgaps originating from the interference of waves
in a string instead of the more abstract electromagnetic waves in material
media. Formally, periodicity would require an infinite set of strings, but we
show that, for realistic values of linear mass densities for the strings, only
a few are enough to observe the bandgaps. In this way, this setup offers an
experimental appeal since the properties of waves in a vibrating string can be
observed in an undergraduate physics laboratory. Throughout this paper, we
will refer more to photonic crystals, but the analogies can be applied to
phononic crystals as well.

##  II Methodology

In this section, we introduce the methodology of the transfer matrix to study
the periodic strings. In addition to being easy to implement numerically, this
method is powerful to study one-dimensional wave propagation and is a
convenient tool to deal with stratified media. It allows for the exact
computation of transmittance and reflectance in non-trivial configurations
[36, 37, 38, 39], including in the description of photonic crystals [40, 31].
For an introduction to the transfer matrix formalism in the contexts of
photonics, plasmonics, and condensed matter systems, see Refs. [41, 42, 43].

Figure 1: Two semi-infinite strings with different linear mass densities
$\mu_{1}$ and $\mu_{2}$.

The starting point is to understand how waves behave at the interface of two
different media. Consider the system depicted in Fig. 1, consisting of two
semi-infinite strings attached at the origin, whose linear mass densities are
$\mu_{1}$ and $\mu_{2}$. Denoting the vertical displacement of a generic point
of the string at instant $t$ by $u(x,t)$, and assuming small slopes
($|\partial u/\partial x|\ll 1$), $u(x,t)$ obeys the wave equation

$\frac{\partial^{2}u(x,t)}{\partial
x^{2}}-\frac{\mu(x)}{T}\frac{\partial^{2}u(x,t)}{\partial t^{2}}=0\,,$ (1)

where the tension $T$ will be considered as uniform throughout the string, and
$\mu(x)$ is the linear mass density. We first assume that $\mu(x)=\mu_{1}$ for
$x<0$, and $\mu(x)=\mu_{2}$ for $x>0$. Physical solutions must satisfy the
boundary conditions [44]

$\displaystyle u_{1}(0^{-},t)$ $\displaystyle=u_{2}(0^{+},t)\,,$ (2)
$\displaystyle\frac{\partial u_{1}}{\partial x}(0^{-},t)$
$\displaystyle=\frac{\partial u_{2}}{\partial x}(0^{+},t)\,,$ (3)

where the index $1$ ($2$) refers to $x<0$ ($x>0$).

In this work, we are mainly interested in transmittance and reflectance. To
compute them, we search for harmonic solutions of frequency $\omega$ for Eq.
(1) submitted to the boundary conditions (2) and (3). We propose the ansatz

$\displaystyle u_{1}(x,t)=A_{1}e^{i(k_{1}x-\omega t)}+B_{1}e^{-i(k_{1}x+\omega
t)}\;\;\;\;(x<0)\,,$ (4) $\displaystyle u_{2}(x,t)=A_{2}e^{i(k_{2}x-\omega
t)}+B_{2}e^{-i(k_{2}x+\omega t)}\;\;\;\;(x>0)\,,$ (5)

where $A_{i}$ and $B_{i}$ ($i=1,2$) are coefficients to be determined. The
wave equation requires that

$k_{j}=\omega\sqrt{\frac{\mu_{j}}{T}}\,,\;\;\;\;\textrm{with }j=1,2\,,$ (6)

and the boundary conditions give the relations

$\displaystyle A_{1}+B_{1}=A_{2}+B_{2}\,,$ (7) $\displaystyle
k_{1}(A_{1}-B_{1})=k_{2}(A_{2}-B_{2})\,.$ (8)

Defining $\eta=k_{2}/k_{1}$, this linear system of equations can be cast into
the matrix form

$\displaystyle\begin{pmatrix}A_{1}\\\ B_{1}\end{pmatrix}$
$\displaystyle=\frac{1}{2}\begin{pmatrix}1+\eta&1-\eta\\\
1-\eta&1+\eta\end{pmatrix}\begin{pmatrix}A_{2}\\\
B_{2}\end{pmatrix}=\mathds{T}_{1\rightarrow 2}\begin{pmatrix}A_{2}\\\
B_{2}\end{pmatrix}.$ (9)

$\mathds{T}_{1\rightarrow 2}$ is called the transfer matrix [42], and it
relates the coefficients of the solutions at the interface that connects the
waves traveling in the left and right sides of the origin. Thus, we can obtain
the reflectance and transmittance directly from the transfer matrix elements,
enforcing that no waves are coming from the right and setting $B_{2}=0$. Since
the transmittance (reflectance) is the ratio between the power carried by the
transmitted (reflected) and incident waves, we can write

$\displaystyle\mathcal{T}=\frac{k_{2}}{k_{1}}\frac{|A_{2}|^{2}}{|A_{1}|^{2}}\;\;\;\textrm{and}\;\;\;\mathcal{R}=\frac{|B_{1}|^{2}}{|A_{1}|^{2}}\,.$
(10)

From Eq. (9), we obtain $2A_{1}=(1+\eta)A_{2}$, implying

$\displaystyle\mathcal{T}=\frac{4k_{2}/k_{1}}{\left(1+k_{2}/k_{1}\right)^{2}}=\frac{4\sqrt{\mu_{2}/\mu_{1}}}{\left(1+\sqrt{\mu_{2}/\mu_{1}}\right)^{2}}\,.$
(11)

Analogously, the reflectance reads

$\mathcal{R}=\bigg{(}\frac{1-k_{2}/k_{1}}{1+k_{2}/k_{1}}\bigg{)}^{2}=\bigg{(}\frac{1-\sqrt{\mu_{2}/\mu_{1}}}{1+\sqrt{\mu_{2}/\mu_{1}}}\bigg{)}^{2}\,.$
(12)

Let us now analyze the case where a finite string segment of length $d$ and
linear mass density $\mu_{2}$ is inserted between two semi-infinite strings of
equal linear mass densities $\mu_{1}$, as in Fig. 2. The transmittance and
reflectance can be obtained through the total transfer matrix, relating the
amplitudes of the solutions in the intervals $x<0$ and $x>d$. The additional
phase acquired by the propagation of the waves along the finite string segment
can be taken into account by the propagation matrix

$\mathds{P}_{2}=\begin{pmatrix}e^{ik_{2}d}&0\\\ 0&e^{-ik_{2}d}\end{pmatrix}$
(13)

so that the total transfer matrix is

$\displaystyle\mathds{T}_{\mathrm{tot}}$
$\displaystyle=\mathds{T}_{1\rightarrow
2}\mathds{P}_{2}\mathds{T}_{2\rightarrow 1}\,,$ (14)

with $\mathds{T}_{2\rightarrow 1}=\mathds{T}^{-1}_{1\rightarrow 2}$ by
definition. From the total transfer matrix, the transmittance and reflectance
are obtained in the same way as in the previous example, yielding

$\displaystyle\mathcal{T}$
$\displaystyle=\frac{k_{f}}{k_{i}}\frac{1}{|T_{11}^{\mathrm{tot}}|^{2}}\,,$
(15) $\displaystyle\mathcal{R}$
$\displaystyle=\bigg{|}\frac{T_{21}^{\mathrm{tot}}}{T_{11}^{\mathrm{tot}}}\bigg{|}^{2}\,,$
(16)

Figure 2: Finite string segment with length $d$ and linear mass density
$\mu_{2}$ placed between two semi-infinite strings of equal linear mass
density $\mu_{1}$.

where $k_{i}$ ($k_{f}$) stands for the wavenumber in the semi-infinite segment
in the range $x<0$ ($x>d$) and $T_{ij}^{\rm tot}$ ($i,j=1,2$) are the matrix
elements of $\mathds{T}_{\mathrm{tot}}$. In the particular configuration of
Fig. 2, the linear mass densities of these segments were chosen to be the
same, and, consequently, $k_{f}/k_{i}=1$. Explicit calculation (see Appendix
A) results in

$\mathcal{T}=\frac{1}{1+\dfrac{(\mu_{1}^{2}-\mu_{2}^{2})^{2}}{\mu_{1}^{2}\mu_{2}^{2}}\sin^{2}\left({\omega
d\sqrt{\dfrac{\mu_{2}}{T}}}\right)}\,.$ (17)

Figure 3: Transmittance $\mathcal{T}$ as a function of frequency $\omega$ for
scattering by a single finite segment. Here, $\mu_{1}=2$ g/m,
$\mu_{2}=4\mu_{1}$, $d=10$ cm, and $T=1$ N.

This expression is plotted in Fig. 3, in which we show the transmittance as a
function of frequency, with $\mu_{1}=2$ g/m, $\mu_{2}=4\mu_{1}$, $d=10$ cm,
and $T=1$ N. Note that the transmittance never vanishes and presents a
periodic behavior with a period satisfying $\Delta\omega
d\sqrt{\mu_{2}/T}=\pi$. From Eq. (6), we obtain $\Delta k_{2}d=\pi$. Equations
(13) and (14) show that, when this condition is satisfied, $T_{11}^{\rm tot}$
just changes sign, keeping $\mathcal{T}$ unaltered. Also, whenever
$k_{2}d=n\pi$ with integer $n$, we have full transmittance. This was also
expected from Eqs. (13) and (14) since, in this case, $\mathds{P}_{2}$ and,
consequently, $\mathds{T}_{\rm tot}$ are $\pm 1$ times the identity matrix. We
invite the reader to explain these features from the interference of multiple
reflections and check from themselves how time-saving the transfer matrix
method is. Note that, in the limit $\mu_{1}\rightarrow\infty$ for a fixed
$\mu_{2}$, we have $\mathcal{T}\rightarrow 0$, except at the frequencies for
which we have full transmittance. There is a close analogy between this case
and the transmission of electromagnetic waves propagating normally through a
finite dielectric layer. The functional dependence is the same, with the only
differences being the relevant physical parameters. As a matter of fact, the
role played by linear mass densities in our cases is analogous to the one
played by the refraction indexes in the electromagnetic one.

Now, we return to the central purpose of this work: a periodic string
containing $N$ segments of linear mass density $\mu_{2}$ interspersed with
segments characterized by linear mass density $\mu_{1}$, as sketched in Fig.
4. By a straightforward generalization of the previous examples, the transfer
matrix is now given by

$\mathds{T}_{\mathrm{tot}}=\mathds{T}_{1\rightarrow
2}\left(\mathds{P}_{2}\mathds{T}_{1\rightarrow
2}^{-1}\mathds{P}_{1}\mathds{T}_{1\rightarrow
2}\right)^{N-1}\mathds{P}_{2}\mathds{T}_{1\rightarrow 2}^{-1}\,,$ (18)

where $\mathds{P}_{1}$ accounts for the propagation along segments of linear
mass density $\mu_{1}$ and is obtained from Eq. (13) by exchanging $k_{2}$ by
$k_{1}$ (we shall assume all segments with length $d$). In the next section,
we study Eq. (18) analytically, but it is instructive for the students to gain
some intuition by first analyzing some concrete examples. For the results of
Sec. III, we used the computational environment Mathematica, but no specific
calculation techniques or any numerical approximations were needed.
Additionally, an experimental proposal is discussed in Appendix B.

Figure 4: The periodic string: a set of $N$ segments with linear mass density
$\mu_{2}$ and size $d$ alternated with segments of linear mass density
$\mu_{1}$ and the same size.

##  III Results and discussions

Throughout this section, we chose $d=10$ cm and $T=1$ N. In Fig. 5, we show
the transmittance against the frequency of the propagating wave along the
string. In all panels, we used $\mu_{1}=2$ g/m and $\mu_{2}=4\mu_{1}$, and
each curve refers to a configuration with a different value of $N$, the number
of unit cells contained in the string. A striking feature in Figs. 5(b) and
5(c) is the presence of periodic frequency regions in which the transmittance
goes to zero, revealing the presence of bandgaps. Note that we still do not
have bandgaps for $N=2$ [panel (a)], although the transmittance is already
much lower for some frequencies. As $N$ increases, the valleys become more
prominent, and bandgaps can be identified even for a modest value of $N=7$
[panel (b)]. In addition, between these bandgaps, there is an oscillatory
behavior, and the frequency of such oscillations increases with $N$.

Figure 5: Transmittance $\mathcal{T}$ as a function of the frequency $\omega$
for (a) $N=2$, (b) $N=7$, and (c) $N=25$. In all plots, we set $\mu_{1}=2$ g/m
and $\mu_{2}=4\mu_{1}$.  Figure 6: Transmittance $\mathcal{T}$ as a function
of the strings’ density ratio $\mu_{2}/\mu_{1}$ for (a) $N=2$, (b) $N=7$, and
(c) $N=25$. The oscillation frequency was fixed at $\omega=500$ Hz and we used
$\mu_{1}=2$ g/m.

Figure 6 displays the transmittance against the density ratio
$\mu_{2}/\mu_{1}$ of the strings segments, with $\mu_{1}=2$ g/m and exploiting
the same values of $N$ shown in Fig. 5. The dashed gray lines in each panel
stress that the outcome is full transmittance for $\mu_{2}/\mu_{1}=1$, as
expected for a homogeneous medium. These plots indicate that, for a given
frequency, we can always choose a density ratio value for which that frequency
is contained in a bandgap.

Figure 7:  Transmittance $\mathcal{T}$ as a function of (a) $k_{1}$ and
$k_{2}$, (b) $k_{2}$, for the slope $k_{2}\gg k_{1}$, (c) $k_{1}$, for the
slope $k_{2}\ll k_{1}$, (d) $k_{1}$, with $k_{2}=\pi/d$ and fixed frequency,
and (e) $k_{2}$, with $k_{1}=\pi/d$ and fixed frequency. In all plots, we set
$N=10$ and the axes with $k_{1}$ and $k_{2}$ are normalized by $\pi/2d$ for
convenience.

In Fig. 7(a), we display the transmittance as a function of the wavenumbers of
each string for $N=10$. Consider straight lines passing through the origin,
with a constant slope given by the ratio $k_{2}/k_{1}=\sqrt{\mu_{2}/\mu_{1}}$,
according to Eq. (6). For convenience, but without loss of generality, suppose
that both $\mu_{1}$ and $\mu_{2}$ are fixed. In this case, the wavenumber of
each string can only change through the frequency of the harmonic wave
propagating along the string. Thus, starting at the origin and moving along
any of these lines, we continuously increase the frequency of the wave. As it
is evident from Fig. 7(a), the transmittance is always equal to $1$ for
$k_{2}/k_{1}=1$, as expected, since it implies $\mu_{2}=\mu_{1}$. However,
even for slight deviations of $k_{2}/k_{1}=1$, we necessarily pass through
bandgaps when moving from the origin along a straight line. Note that the
crossed bandgaps are very narrow for small deviations of $k_{2}/k_{1}=1$, but
wider bandgaps appear as we deviate from unity. We can understand this result
if we remember that there is no reflection of the incident wave for a
homogeneous string. Consequently, there is nothing to scatter this wave: nor
any discontinuity in the linear mass density of the string and not even any
continuous change in density. Nevertheless, as the ratio $\mu_{2}/\mu_{1}$
deviates from $1$, the existence of the “lattice” (periodic string) starts to
be noticed, and the bandgaps start to show up. In this sense, this ratio
measures the presence of the lattice and, consequently, how much scattering
occurs in the system. It is worth noting that, even for slopes very different
from the unity, besides wide bandgaps, we still have narrow ones, as shown in
Fig. 5, which can be understood as similar cuts in Fig. 7 with constant slopes
containing the origin.

Naively, one could think that Fig. 7(a) is symmetric concerning the straight
line containing the origin with slope $k_{2}/k_{1}=1$. However, this is not
true since our physical system is not symmetric under the exchange
$k_{2}\leftrightarrow k_{1}$ (recall that the incident wave starts propagating
through a semi-infinite string with linear mass density $\mu_{1}$ and, after
crossing the “periodic string”, is transmitted to another semi-infinite string
with the same density $\mu_{1}$). This asymmetry becomes less evident as the
number $N$ of unit cells composing the periodic string increases.

There are two interesting limiting cases. The first one is
$k_{2}/k_{1}\rightarrow\infty$, which can be thought as taking
$\mu_{2}\rightarrow\infty$ and a finite value for $\mu_{1}$. This situation is
similar to an incident wave reaching a piece of string with infinite mass,
which means an incident wave that reaches a fixed extreme (Dirichlet boundary
condition). Consequently, we expect total reflection or, equivalently, zero
transmittance. Indeed, Fig. 7(b) shows the transmittance as a function of
$k_{2}$ for the vertical axis containing the origin ($k_{2}\gg k_{1}$), and
the outcome is zero transmittance. One could think that at $2k_{2}d/\pi$ equal
to an even positive integer, implying $d=n\lambda_{2}/2$ ($n=1,2,3,...$), the
transmittance would not vanish. Nevertheless, even for these values, the
transmittance tends to zero as the slope tends to infinite, though more
slowly, as the condition $d=n\lambda_{2}/2$ favors constructive interference
[the same kind of constructive interference that we discussed with Eq. (17)].
The second limiting case consists of $k_{2}\ll k_{1}$, and it corresponds to
select in Fig. 7(a) the horizontal straight line containing the origin,
resulting in Fig. 7(c).

A last interesting analysis comes from considering horizontal and vertical
cuts in Fig. 7(a) that do not include the origin, which means considering
constant values of $k_{2}$ and $k_{1}$, respectively. Since
$k_{2}=\omega\sqrt{\mu_{2}/T}$, a constant $k_{2}$ means a constant value of
$\omega\sqrt{\mu_{2}}$ (the string tension $T$ is held constant along all this
work). As we seek to quantify the influence of a change in the parameters on a
given propagating mode, we may consider a fixed frequency, such that constant
$k_{2}$ implies constant $\mu_{2}$. Consequently, starting at a point in a
vertical axis of Fig. 7(a) and moving along a horizontal straight line is
equivalent to increasing the value of $\mu_{1}$. The first important feature
to be noted is that there are no bandgaps for the horizontal lines given by
$2k_{2}d/\pi$ equal to an even positive integer (or $d=n\lambda_{2}/2$, with
$n=1,2,3,...$), as highlighted in Fig. 7(d). In other words, no bandgap will
take place, regardless of the choice of propagation mode frequency and also
the value of $\mu_{1}$. Moreover, $\mathcal{T}=1$ for these values, which can
be understood in terms of the constructive interference condition already
mentioned. Analogous reasoning can be employed to the vertical cuts: moving
along a straight vertical line means increasing $\mu_{2}$. For values of
$2k_{1}d/\pi$ equal to an even positive integer (or $d=n\lambda_{1}/2$, with
$n=1,2,3,...$), there is an oscillatory behavior, so that the transmittance is
not always equal to one, but again there are no bandgaps, as shown in Fig.
7(e).

##  IV Analytical origin of bandgaps

At this point, one might wonder why the frequency gaps appear and if it is
possible to determine their position analytically. The periodicity allows for
a positive answer. An analytical evaluation of Eq. (18) requires the
$(N-1)$-th power of the matrix
$\mathds{M}=\mathds{P}_{2}\mathds{T}_{1\rightarrow
2}^{-1}\mathds{P}_{1}\mathds{T}_{1\rightarrow 2}$. Since $\det\mathds{M}=1$,
we have [45]

$(\mathds{M})^{n}=\begin{pmatrix}m_{11}U_{n-1}(a)-U_{n-2}(a)&m_{12}U_{n-1}(a)\\\
m_{21}U_{n-1}(a)&m_{22}U_{n-1}(a)-U_{n-2}(a)\\\ \end{pmatrix}\,,$ (19)

where $m_{ij}$ denotes the matrix elements of $\mathds{M}$,
$a=(m_{11}+m_{22})/2$, and $U_{n}(x)$ are the Chebyshev polynomials of the
second kind, given by

$U_{n}(x)=\frac{\sin[(n+1)\cos^{-1}(x)]}{\sqrt{1-x^{2}}}\,.$ (20)

Since $\cos^{-1}(x)$ is a purely imaginary number for $|x|>1$, and recalling
that $\sin(i\alpha)=-i\sinh(\alpha)$, we conclude that, for $|x|>1$,
$U_{n}(x)$ diverges exponentially for large $n$, leading to a divergence in
all elements of $\mathds{T}_{\rm tot}$ and, from Eq. (15), to a zero
transmittance. From Eq. (19), we see that $U_{n}$ must be evaluated at the
semi-trace $a$ of the matrix $\mathds{M}$, which is a function of $k_{1}$,
$k_{2}$ and $d$. Hence, the explicit calculation of $a$ shows that the
frequency bandgaps appear whenever the following condition is satisfied:

$\frac{\Bigg{|}2\cos(k_{1}d)\cos(k_{2}d)-\left(\dfrac{k_{1}}{k_{2}}+\dfrac{k_{2}}{k_{1}}\right)\sin(k_{1}d)\sin(k_{2}d)\Bigg{|}}{2}>1\,.$
(21)

Outside this range, $U_{n}(x)$ is an oscillating function, explaining the
oscillations in the transmittance observed in the previous section. In Fig. 8,
we observe that the gaps appear exactly in the regions where $a>1$.

Although we do not have an explicit solution of Eq. (21), its main properties
can be readily grasped. First, note that, if $k_{1}=k_{2}$ (homogeneous
string), $a$ will become $\cos^{2}(2kd)$ and the condition (21) is never
satisfied. Indeed, we have obtained full transmittance for all frequencies.
Furthermore, when $k_{2}$ and $k_{1}$ are commensurable, $a$ is a periodic
function, and the bandgaps’ locations and width will obey the same
periodicity. When $|k_{1}-k_{2}|/k_{1}=|\mu_{1}-\mu_{2}|/\mu_{1}\sim 1$, we
have $U_{n}\sim e^{n}$ and thus, from Eq. (16), $\mathcal{R}\sim e^{-n}$. This
explains why the bandgaps are perceptible even for small values of $N$ in the
previous section.

Figure 8: Transmittance $\mathcal{T}$ and the parameter $a$ as a function of
the frequency $\omega$ for $\mu_{1}=2$ g/m, $\mu_{2}=4\mu_{1}$, and $N=25$.

##  V Final remarks and conclusions

In this work, we employed the transfer matrix formalism to investigate the
periodic string and explore its analogies with photonic crystals and condensed
matter systems. We determined the transmittance and discussed its dependence
on the relevant physical parameters. The most remarkable result was the
emergence of prohibited frequency bandgaps, even for a low number of strings
segments. The choice of the physical parameters was made to be compatible with
materials and equipment that may be available in undergraduate physics
laboratories as discussed in appendix B.

Useful analogies may also be drawn from our results to the behavior of band
theory in crystalline systems. The interfaces in our string system are
analogous to the atoms that scatter the electronic wavefunction, and the
frequencies in our classical system play the role of energy, as expected by
the de Broglie relation applied to the electronic wavefunction. Also, the
expression $|1-\eta|=|1-\sqrt{\mu_{2}/\mu_{1}}|$ can be related to the
potential generated by each atom. For instance, when $\eta=1$, we have
$\mu_{1}=\mu_{2}$, and there is no scattering, which would be analogous to the
free electron model. In fact, as expected, we obtain in Fig. 7 (d) full
transmission in this case, tantamount to state that a free electron gas
presents no energy gap. In addition, for $|1-\eta|\ll 1$, we have weak
scattering, analogously to the nearly free electron approximation, leading to
the appearance of small bandgaps. The small reflectances, given in Eq. (12),
are akin to the small matrix element of the potential connecting states with
different wave vectors in the condensed matter case. The opposite situations
of $\eta\gg 1$ and $\eta\ll 1$ are analogous to the tight-binding limit. In
these limits, we may think of Fig. 2 as the analog of a single atom. As we
discussed in Sec. II, in the limit $\eta\rightarrow 0$ or $1/\eta\rightarrow$
0, the result is transmission only on a discrete set of frequencies, which
plays the role here of the discrete atomic energy levels in crystals. Once we
couple many string segments as in Fig. 4 (or “atoms”in this analogy), the
small individual transmittance acts as the hopping parameter, which enlarges
the discrete transmitted frequencies into a small band of allowed frequencies.
Despite these similarities, the periodic string also has some important
differences from Bloch waves in crystals. To begin with, we do not have de
Broglie relations so that frequency band does not imply energy bands. In our
classical system, any energy is possible. Furthermore, in our classical
system, we have an inhomogeneous medium, and thus the wave has different
wavelengths depending on which medium it is vibrating. Therefore, our analogy
is stronger with the envelope approximation in heterostructures than
homogeneous crystals.

Ultimately, this system offers a variety of interesting aspects to explore,
providing much physical intuition for being described purely within the
framework of classical mechanics. Therefore, it is an excellent route to get
beginner undergraduate students in touch with physical concepts rarely covered
in standard textbooks. It can also arouse the student’s interest in other
topics and motivate further studies, as the techniques we used have found
applications in different physical situations and can be generalized for more
complex problems, as discussed throughout the text.

## Acknowledgements

R.S.P. and C.F. thank L. O. A. Azevedo for useful discussions. R.S.P. and
P.P.A. acknowledges São Paulo Research Foundation (FAPESP) (Grant numbers
#2020/14489-5 and #2021/04861-7) for financial support. M.V.S acknowledges
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) (Grant
number 88887.635842/2021-00) for financial support. G.P.M acknowledges
Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro (FAPERJ). C.F.
acknowledges Conselho Nacional de Desenvolvimento Científico e Tecnológico
(CNPq) (Grant number 310365/2018-0). R.M.S. also thanks the funding agencies.

##  Appendix A Explicit derivation of Eq. (17)

In this appendix, we discuss two strategies to derive the transmittance of the
system depicted in Fig. 2, given by Eq. (17). First, we impose the boundary
conditions on the harmonic solutions and solve the system of linear equations
that arises from these steps. In the second method, we re-obtain this result,
employing the transfer matrix formalism and illustrating its convenience.

###  A.1 By imposing the boundary conditions at the interfaces

Supposing that there is an incoming wave in the region $x<0$, the harmonic
solutions in each of the segments are

$\displaystyle u_{1}(x,t)$ $\displaystyle=Ae^{i(k_{1}x-\omega
t)}+Be^{-i(k_{1}x+\omega t)}\;\;(x<0)\,,$ (22) $\displaystyle u_{2}(x,t)$
$\displaystyle=Ce^{i(k_{2}x-\omega t)}+De^{-i(k_{2}x+\omega t)}\;\,(0<x<d)\,,$
(23) $\displaystyle u_{3}(x,t)$ $\displaystyle=Ee^{i(k_{1}x-\omega
t)}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,\,\;\;\>(x>d)\,.$ (24)

Imposing the boundary conditions at the interfaces $x=0$ and $x=d$, we obtain
set of the equations

$\displaystyle A+B=C+D\,,$ (25) $\displaystyle k_{1}(A-B)=k_{2}(C-D)\,,$ (26)
$\displaystyle Ee^{ik_{1}d}=Ce^{ik_{2}d}+De^{-ik_{2}d}\,,$ (27) $\displaystyle
Ek_{1}e^{ik_{1}d}=k_{2}\left(Ce^{ik_{2}d}-De^{-ik_{2}d}\right)\,.$ (28)

After some simple mathematical manipulations, one can obtain

$\displaystyle\frac{A}{E}=$
$\displaystyle\frac{1}{4k_{1}k_{2}}\left[(k_{1}+k_{2})^{2}e^{i(k_{1}-k_{2})d}-(k_{1}-k_{2})^{2}e^{i(k_{1}+k_{2})d}\right].$
(29)

Recalling that

$\displaystyle\frac{1}{\mathcal{T}}=\frac{|A|^{2}}{|E|^{2}}=\frac{AA^{*}}{EE^{*}}\,,$
(30)

then

$\displaystyle\frac{1}{\mathcal{T}}$
$\displaystyle=\frac{1}{16k_{1}^{2}k_{2}^{2}}\left[(k_{1}+k_{2})^{2}e^{-ik_{2}d}-(k_{1}-k_{2})^{2}e^{ik_{2}d}\right]$
$\displaystyle\times\left[(k_{1}+k_{2})^{2}e^{ik_{2}d}-(k_{1}-k_{2})^{2}e^{-ik_{2}d}\right]\,.$
(31)

After lengthy but straightforward manipulations, we arrive at Eq. (17).

###  A.2 By transfer matrix approach

In this case, it is only necessary to calculate the matrix element
$T_{11}^{\mathrm{tot}}$ of the transfer matrix $\mathds{T}_{\mathrm{tot}}$,
given by Eq. (14). We can write

$\displaystyle\mathds{T}_{\mathrm{tot}}$
$\displaystyle=\frac{1}{2}\begin{bmatrix}1+\eta&1-\eta\\\
1-\eta&1+\eta\end{bmatrix}\begin{bmatrix}e^{ik_{2}d}&0\\\
0&e^{-ik_{2}d}\end{bmatrix}\mathds{T}_{1\rightarrow 2}^{-1}$ (32)

Using that $\mathds{T}_{1\rightarrow 2}^{-1}=\mathds{T}_{2\rightarrow 1}$, the
previous equation yields

$\displaystyle T_{11}^{\mathrm{tot}}$
$\displaystyle=\frac{1}{4}\left[e^{ik_{2}d}(1+\eta)(1+\eta^{-1})+e^{-ik_{2}d}(1-\eta)(1-\eta^{-1})\right]$
(33)
$\displaystyle=\frac{1}{4k_{1}k_{2}}\left[e^{ik_{2}d}(k_{1}+k_{2})^{2}-e^{-ik_{2}d}(k_{1}-k_{2})^{2}\right]\,.$
(35)

In going to the second line, we used the definition $\eta=k_{2}/k_{1}$ given
in the main text. Consequently, using Eq. (15), the transmittance is obtained
from

$\displaystyle\frac{1}{\mathcal{T}}$
$\displaystyle=\frac{1}{16k_{1}^{2}k_{2}^{2}}\left[(k_{1}+k_{2})^{2}e^{-ik_{2}d}-(k_{1}-k_{2})^{2}e^{ik_{2}d}\right]$
$\displaystyle\times\left[(k_{1}+k_{2})^{2}e^{ik_{2}d}-(k_{1}-k_{2})^{2}e^{-ik_{2}d}\right]\,.$
(36)

This is precisely the same result given in Eq. (31) that leads to Eq. (17).

##  Appendix B Experimental setup proposal

To show the frequency intervals for which wave propagations are not allowed
(the frequency bandgaps), an adaptation of Melde’s original experiment[46] can
be employed. Modern versions of this experiment can be set up with an electric
vibrator, string, pulley, and hanging masses to control the string tension.
Also, low-cost experiments are readily available in the literature [47]. The
basis of our proposed experiment is similar to Melde’s apparatus, with the
main difference being that the string will be replaced by two others with
different linear mass densities interspersed. Since we want to observe the
forbidden propagation for certain frequencies, the lack of oscillations in the
last segment (the one away from the oscillator) will demonstrate that no wave
has been transmitted through the stratified medium. In other words, unlike
Melde’s original experiment that looks for stationary waves, we will focus our
attention on whether the wave propagation reaches the end of the string.

To assemble the experiment, we suggest using an electric vibrator, a signal
generator to drive the vibrator, two strings with different linear mass
densities (paracord type IA and paracord type II, for example), and hanging
masses to control the tension. The values for frequencies and linear mass
densities in the main text were chosen based on typical values obtained with
available materials. There are three different alternatives to observe the
lack of oscillations on the last segment of the string: the use of a high-
speed camera, the use of stroboscopic light, or the use of opto-switch sensors
to measure the motion [48].

The choice of paracords (or any nylon-based cord) is due to their ability to
melt when exposed to heat. By cutting two segments of different paracords, one
can join them seamlessly, making the interface abrupt and respecting the
boundary conditions used in the theoretical modeling. This joining procedure
must be repeated for each segment, obtaining, in the end, the desired
stratified medium with a specific number of segments. A hanging object of mass
100g suspended can be used to create a tension of $1$ N. Considering seven
repetitions to generate the situation of Fig. 5(b), the total length of the
interspersed ropes is $1.4$ m. A $1.0$ m paracord can be used as the semi-
infinite string. Longer semi-infinite segment could also be employed, but, in
this case, it would be better to change the orientation of the rope from
horizontal to vertical to avoid sagging.

As mentioned before, frequency bandgaps will be shown up as no oscillations in
the last segment. After setting up the experiment, the frequency of the
electric vibrator is varied, and measurements on the oscillations of the last
segment will be performed, by using a high-speed camera (in a more expensive
experimental setup) or by using stroboscopic light or opto-switch sensors (a
less expensive one). The use of a high-speed camera is straightforward, and
analysis can be conducted by using the freeware Tracker(for an introduction to
video analysis of experimental results using this freeware, we refer the
reader to Ref. [49]). For low-cost alternatives, a stroboscopic light can be
employed only for visual observation since it does not measure the
oscillations on the last segment. On the other side, by calibrating an opto-
switch sensor [48], the oscillations can be measured, and quantitative
analysis can be performed. This allows creating a plot that relates the
oscillation amplitude with frequency, showing a bandgap for specific frequency
ranges.

## References

  * [1] E. Yablonovitch, Inhibited spontaneous emission in solid-state physics and electronics, Phys. Rev. Lett. 58, 2059 (1987).
  * [2] S. John, Strong localization of photons in certain disordered dielectric superlattices, Phys. Rev. Lett. 58, 2486 (1987).
  * [3] L. Rayleigh, XXVI. On the remarkable phenomenon of crystalline reflexion described by Prof. Stokes, The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 26, 256 (1888).
  * [4] J. D. Joannopoulos, R. D. Meade, and J. N. Winn, Photonic Crystals: Molding the Flow of Light (Princeton University Press, Princeton, 1995).
  * [5] B. Schulkin, L. Sztancsik, and J. F. Federici, Analytical solution for photonic band-gap crystals using Drude conductivity, Am. J. Phys. 72, 1051 (2004).
  * [6] F. Szmulowicz, Analytic, graphical, and geometric solutions for photonic bandgaps, Am. J. Phys. 72, 1392 (2004).
  * [7] W. Guo, Optical bandgaps as a result of destructive superposition of scattered waves, Am. J. Phys. 74, 595 (2006).
  * [8] G. von Freymann, V. Kitaev, B. V. Lotsch, and G. A. Ozin, Bottom-up assembly of photonic crystals, Chem. Soc. Rev. 42, 2528 (2013).
  * [9] A. Cerjan and S. Fan, Complete photonic bandgaps in supercell photonic crystals, Phys. Rev. A 96, 051802(R) (2017).
  * [10] N. W. Ashcroft and N. D. Mermin, Solid State Physics (Harcourt College Publishers, Orlando, 1976).
  * [11] S. H. Ryu, M. J. Gim, W. Lee, S. W. Choi, and D. K. Yoon, Switchable photonic crystals using one-dimensional confined liquid crystals for photonic device application, ACS Appl. Mater. Interfaces 9, 3186 (2017).
  * [12] H. Wang, S. K. Gupta, B. Xie, and M. Lu, Topological photonic crystals: a review, Front. Optoelectron. 13, 50 (2020).
  * [13] J. Joannopoulos, P. Villeneuve, and S. Fan, Photonic crystals: putting a new twist on light, Nature 386, 143 (1997).
  * [14] A. C. Arsenault, D. P. Puzzo, I. Manners, and G. A. Ozin, Photonic-crystal full-colour displays, Nature Photon. 1, 468 (2007).
  * [15] H. Xu, P. Wu, C. Zhu, A. Elbaz, and Z. Z. Gu, Photonic crystal for gas sensing, J. Mater. Chem. C 1, 6087 (2013).
  * [16] P. Bermel, C. Luo, L. Zeng, L. C. Kimerling, and J. D. Joannopoulos, Improving thin-film crystalline silicon solar cell efficiencies with photonic crystals, Opt. Express 15, 16986 (2007).
  * [17] E. Matioli, E. Rangel, M. Iza, B. Fleury, N. Pfaff, J. Speck, E. Hu, and C. Weisbuch, High extraction efficiency light-emitting diodes based on embedded air-gap photonic-crystals, Appl. Phys. Lett. 96, 031108 (2010).
  * [18] S. A. Cerqueira Jr, Recent progress and novel applications of photonic crystal fibers, Rep. Progr. Phys. 73, 024401 (2010).
  * [19] A. Bruyant, G. Lérondel, P. J. Reece, and M. Gal, All-silicon omnidirectional mirrors based on one-dimensional photonic crystals, Appl. Phys. Lett. 82, 3227 (2003).
  * [20] C. I. Aguirre, E. Reguera, and A. Stein, Tunable colors in opals and inverse opal photonic crystals, Adv. Funct. Mater. 20, 2565 (2010).
  * [21] K. L. Yu, T. X. Fan, S. Lou, and D. Zhang, Biomimetic optical materials: Integration of nature’s design for manipulation of light, Prog. Mater. Sci. 58, 825 (2013).
  * [22] M. M. Sigalas and E. N. Economou, Elastic and Acoustic Wave Band Structure, J. Sound Vib. 158, 377 (1992).
  * [23] M. S. Kushwaha, P. Halevi, L. Dobrzynski, and B. Djafari-Rouhani, Acoustic band structure of periodic elastic composites, Phys. Rev. Lett. 71, 2022 (1993).
  * [24] D. Richards and D. J. Pines, Passive reduction of gear mesh vibration using a periodic drive shaft, J. Sound Vib. 264, 317 (2003).
  * [25] J. Sanchez-Dehesa, V. M. Garcia-Chocano, D. Torrent, F. Cervera, and S. Cabrera, Noise control by sonic crystal barriers made of recycled materials, J. Acoust. Soc. Am. 129, 1173 (2011).
  * [26] M. I. Hussein, M. J. Leamy, and M. Ruzzene, Dynamics of phononic materials and structures: Historical origins, recent progress, and future outlook, Appl. Mech. Rev. 66, 040802 (2014).
  * [27] Y. F. Wang, Y. Z. Wang, B. Wu, W. Chen, and Y. S. Wang, Tunable and active phononic crystals and metamaterials, Appl. Mech. Rev. 72, 040801 (2020).
  * [28] J. Liu, H. Guo, and T. Wang, A review of acoustic metamaterials and phononic crystals, Crystals 10, 305 (2020).
  * [29] Germano M. Penello et al., Progress in Symmetric and Asymmetric Superlattice Quantum Well Infrared Photodetectors, Ann. der Phys. 531, 1800462 (2019).
  * [30] A. Haché and L. Poirier, Anomalous dispersion and superluminal group velocity in a coaxial photonic crystal: Theory and experiment, Phys. Rev. E 65, 036608 (2002).
  * [31] M. M. Sánchez-López, J. A. Davis, and K. Crabtree, Coaxial cable analogs of multilayer dielectric optical coatings, Am. J. Phys. 71, 1314 (2003).
  * [32] A. Haché and A. Slimani, A model coaxial photonic crystal for studying band structures, dispersion, field localization, and superluminal effects, Am. J. Phys. 72, 916 (2004).
  * [33] E. H. El Boudouti, Y. El Hassouani, B. Djafari-Rouhani, and H. Aynaou, Two types of modes in finite size one-dimensional coaxial photonic crystals: General rules, and experimental evidence, Phys. Rev. E 76, 026607 (2007).
  * [34] E. H. El Boudouti, Y. El Hassouani, H. Aynaou, B. Djafari-Rouhani, A. Akjouj, and V. R. Velasco, Electromagnetic wave propagation in quasi-periodic photonic circuits, J. Phys.: Condens. Matter 19, 246217 (2007).
  * [35] A. Perrier, Y. Guilloit, É. L. Cren, and Y. Dumeige, A simple model system to study coupled photonic crystal microcavities, Am. J. Phys. 89, 538 (2021).
  * [36] J. S. Walker and J. Gathright, Exploring one-dimensional quantum mechanics with transfer matrices, Am. J. Phys. 62, 408 (1994).
  * [37] R. B. Balili, Transfer matrix method in nanophotonics, Int. J. Modern Phys.: Conf. Series 17, 159 (2012).
  * [38] T. Zhan, X. Shi, Y. Dai, X. Liu, and J. Zi, Transfer matrix method for optics in graphene layers, J. Phys.: Condens. Matter 25, 215301 (2013).
  * [39] I. Haddouche and L. Cherbi, Comparison of finite element and transfer matrix methods for numerical investigation of surface plasmon waveguides, Opt. Commun. 382, 132 (2017).
  * [40] J. Zi, J. Wan, and C. Zhang, Large frequency range of negligible transmission in one-dimensional photonic quantum well structures, Appl. Phys. Lett. 73, 2084 (1998).
  * [41] P. Markoš and C. M. Soukoulis, Wave propagation: from electrons to photonic crystals and left-handed materials (Princeton University Press, Princeton, 2008).
  * [42] P. A. D. Gonçalves and N. M. R. Peres, An Introduction to Graphene Plasmonics (World Scientific, Singapore, 2016).
  * [43] P. Pereyra, Fundamentals of Quantum Physics: Textbook for Students of Science and Engineering (Springer, 2012).
  * [44] A. P. French, Vibrations and waves (CRC press, 2017).
  * [45] M. Born and E. Wolf, Principles of Optics: Electromagnetic Theory of Propagation, Interference, and Diffraction of Light (New York: Pergamon Press, 1999).
  * [46] F. Melde, Ueber die Erregung stehender Wellen eines fadenförmigen Körpers, Ann. Phys.185, pp. 193-215 (1860).
  * [47] G. Bozzo, F. de Sabata, S. Pistori, and F. Monti, Imaging and studying standing waves with a homemade Melde-type apparatus and information and communication technology (ICT), Phys. Teach. 57, 612 (2019).
  * [48] J. L. Le Carrou, D. Chadefaux, L. Seydoux, and B. Fabre, A low-cost high-precision measurement method of string motion, J. Sound Vib. 333, 3881 (2014).
  * [49] V. L. B. de Jesus, Experiments and Video Analysis in Classical Mechanics (Springer, 2017).


# MultiWOZ-DF - A Dataflow implementation of the MultiWOZ dataset

###### Abstract

In this paper we introduce MultiWOZ-DF, a dataflow implementation of the well
known MultiWOZ dataset. The implementation demonstrates how to both convert
and execute MultiWOZ dialogues as dataflow dialogues. Our goal is to encourage
the research community to further investigate the dataflow dialogue paradigm.

Keywords: Dialogue systems, dataflow

MultiWOZ-DF - A Dataflow implementation of the MultiWOZ dataset

Joram Meron, Victor Guimarães
---
Telepathy Labs GmbH
36 Militärstrasse, Zurich, Switzerland
{joram.meron<EMAIL_ADDRESS>

Abstract content

## 1\. Introduction

Semantic Machines (SM) have introduced the use of the dataflow (DF) paradigm
to dialogue modelling, using computational graphs to hierarchically represent
user requests, data, and the dialogue history [Semantic Machines et al.,
2020].

Although the main focus of that paper was the SMCalFlow dataset (to date, the
only dataset with ”native” DF annotations), they also reported some results of
an experiment using a transformed version of the commonly used MultiWOZ
dataset [Budzianowski et al., 2018] into a DF format.

In this paper, we expand the experiments using DF for the MultiWOZ dataset,
exploring some additional experimental set-ups. The code and instructions to
reproduce the experiments reported here have been
released111https://github.com/telepathylabsai/OpenDF.

The contributions of this paper are:

  1. 1.

A DF implementation capable of executing MultiWOZ dialogues;

  2. 2.

Several versions of conversion of MultiWOZ into a DF format are presented;

  3. 3.

Experimental results on state match and translation accuracy.

## 2\. The MultiWOZ dataset

The MultiWOZ dataset [Budzianowski et al., 2018] consists of 10K annotated
dialogues in 7 domains (hotels, restaurants, trains, attractions, hospitals,
police, taxi). The collection of the dataset was done using a Wizard-Of-Oz
set-up, where both the user and the system (agent) are played by human
participants. The user is presented with a set of goals they need to achieve
(e.g. book a hotel, restaurant, etc.) as well as a set of constraints for the
goals (e.g. the hotel should be in a specific area, in a specific price
category etc). The user has no direct access to the data, and thus needs to
communicate with the agent to achieve the pre-specified goals. The agent
accesses the data (e.g. hotel information) through a database interface, and
their job is to convert the user’s requests into database queries, informing
the user when the requests succeeds or fails, supplying the information found
by the database search, and prompting the user for additional information in
case the request is incomplete, or when the request can not be satisfied.

Two types of annotations are present in MultiWOZ:

  * •

Dialogue state - the database query that the agent ran at each turn is saved,
and is used as a proxy for the dialogue state - i.e. considered as a
representation of the agent’s belief regarding the user’s wishes at that time
point. This represents an accumulation of all the turns until that point, and
may depend on the agent’s subjective interpretation of the user requests;

  * •

Dialogue acts - a separate annotation pass was done (by a separate group of
annotators), marking what information was actually communicated in each turn
(separately for user and agent).

The MultiWOZ dataset has been used by many researchers, and is one of the most
commonly used dataset for comparison and benchmarking in dialogue system
research.

### 2.1. Annotation issues

Both the annotation format, as well as the actual annotations have gone
through several iterations of improvements, underlying the inherent
difficulties in trying to achieve complete and objective annotation of natural
dialogues. In this work, we use the MultiWOZ-2.2 version [Zang et al., 2020],
which is considered the cleanest version of the dataset.

Despite this, there are still many issues with this annotation, stemming from
the assumption that the agent’s database query is an exact and objective
description of the dialogue state.

In some cases, the values entered into the database query are clearly wrong
(the agent may have mistyped, missed a value, or surmised a value which was
not given yet). In other cases, the state may be ambiguous, which is not
supported by the annotation scheme (e.g. after suggesting a value to the user,
it may not be immediately clear if the user accepted it or not). The human
agent can easily recover from making a wrong choice in such a case, but the
resulting annotation is problematic as far as training and evaluation are
concerned.

One specific issue with the design of the data collection process is that
using the agent’s database queries as a proxy to the user’s wishes relies on
the assumption that the agents can only see the information they specified in
their database query, and therefore are forced to explicitly describe what
they are looking for. If, for example, the agents could see all the
information all of the time (e.g. if they had a screen big enough to display
all the information), they would not be forced to create exact queries.

In practice, there are several situations in the interaction, where the agents
see more information than they explicitly asked for, and thus are not forced
to write full and exact queries. To see why this is a problem consider the
following example interaction:

User: ”I want a train leaving at 16:15”.

Agent: ” there is a train at 16:30”.

User: ”How much does it cost?”.

Agent: ”the price is …”.

The agent typed a query with (leave=16:15) and then got the information for
several trains at or after the specified time, and suggested one of them (at
16:30). The user then asked a question about the suggested train (at 16:30),
and the agent is able to see the information without having to change the
query. It is difficult to say what is the ”correct” annotation for this
situation (should the time be changed to 16:30 or not), as there is an
inherent ambiguity regarding the user’s wish at this point, but using the
query as a proxy for the state in this situation is problematic.

## 3\. Dataflow Dialogues

The dataflow dialogue approach uses computational graphs, which are composed
of a rich set of functions (both general and application specific) to
represent the user requests as rich compositional (hierarchical) executable
expressions.

The computational graphs (also referred to as DF expressions) are used for
representing the dialogue state/history. In addition, the DF expressions can
be executed, which results in manipulating the dialogue state/history,
generating an answer (possibly an error message), and optionally producing
some side effects through API’s to external services (e.g. updating the user’s
calendar appointments on an external database).

The prominent features of this paradigm are:

  * •

The dialogue history is represented as a set of graphs, where each
computational graph typically represents one user turn;

  * •

It has a refer operation to search over the current and previous computational
graphs (as well as external resources) which allows easy look-up and re-use of
graph nodes which occurred previously in the dialogue;

  * •

It has a revise operation which allows modification and reuse of previous
computations

  * •

It has an exception mechanism which allows convenient interaction with the
user (e.g. asking for missing information, and resuming the computation once
the information is supplied).

These features correspond to essential phenomena in natural conversations
(referring to previous turns, modifying previous requests, reacting to wrong
information, etc.), which allows the system to effectively handle these kinds
of user requests.

DF is an object-oriented approach to dialogue design, encouraging
modularization and re-use, and may offer practical advantages in terms of
scaling and ease of implementing actual dialogue systems.

One interesting aspect of this design is that state (dialogue history), data
and computations are all represented using the same format (well structured
graphs), which could be useful for new machine learning graph based models
(e.g. methods using graph attention), as it allows the model easy access to
the state/data.

## 4\. MultiWOZ and DF

Despite the fact that MultiWOZ’s annotation is essentially flat intent/entity
frames, as opposed to the hierarchical (deep) annotations of SMCalFlow,
[Semantic Machines et al., 2020] showed that a DF approach may still be
advantageous for MultiWOZ.

In an experiment, the MultiWOZ annotations were converted into DF expressions,
which were then fed into the same pipeline used for training and evaluating
the SMCalFlow seq2seq model. The results showed a small improvement in the
joint goal (average dialogue-state exact match) and dialogue (average
dialogue-level exact match) metrics, compared to the TRADE [Wu et al., 2019]
baseline.

Unfortunately, SM did not release the code for real execution of the DF
expressions, which hinders examination and further experimentation with this
approach.

In this work, we release an executable version of the DF implementation of
MultiWOZ (based on OpenDF), which should allow researchers to reproduce the
MultiWOZ-DF experiments, as well as to extend the work presented here.

### 4.1. Converting MultiWOZ

When converting MultiWOZ to the DF format, SM converted a dialogue state to a
call to a find function, which gets as parameters the type of service
(domain), as well as the values for specified slots. Within a dialogue, any
turn that initiates a new type of booking is re-annotated as a call to find.
Turns that merely modify some of the slots are re-annotated as revise() calls.
refer() calls are used to substitute slot values which do not appear verbatim
in the user request (provided the refer is correctly resolved).

While the code for converting the MultiWOZ annotations to the DF format were
released by SM, we use a different conversion scheme. The differences are
described below.

#### 4.1.1. DF format

SM’s DF expressions use the S-Expression format (a LISP-like format), while
our annotations use a Python-like format (which is the standard in OpenDF).

#### 4.1.2. MultiWOZ version

SM used MultiWOZ version 2.1. As mentioned above we use the cleaner version
2.2.

#### 4.1.3. Conversion source

SM’s conversion used the annotated dialogue state as the base of conversion.
As mentioned above, the dialogue state annotation is derived from the database
query, which is manually written by the human agent to describe the user’s
wishes at that time (the agent generates one query after getting the user’s
request). SM’s conversion used the ”state delta” (simply put, the difference
between two successive queries) to decide which slots and values should be
included in the DF expression for the current user turn. Note that the state
delta does not explicitly state which slots/values came from the user, and
which from the agent.

Our conversion, on the other hand, is based on the dialogue act annotations.
In this conversion, the DF expressions include only the slots mentioned in the
user’s dialogue acts (which has separate annotation for user and agent turns).

In most cases, the two conversions produce essentially similar results
(although in different formats). However, when information from the agent is
incorporated into the dialogue state, the conversions produce different
results. As a concrete example, look at the following dialogue:

1\. User: ”I want a restaurant in the center of town”

2\. Agent: ”How about restaurant X?”

3\. User: ”good. I want to book a table on Monday”

4\. Agent: ”. . .”

Looking at the conversion for the second user turn (turn #3), the converted DF
expression contains the following slots:

  * •

Using the state delta based conversion: (day=Monday, name=Restaurant X)

  * •

Using the dialogue acts based conversion: (day=Monday)

Practically, this means that for dialogue state based DF expressions, the
translation of the user’s text request to a DF expression has to also look at
the agent’s text in order to extract relevant agent’s slots/values from it (in
this example - the restaurant name).

For dialogue act based DF expressions, the translation needs only to extract
the user’s slots/values. The information from the agent (described by the
dialogue acts of the agent) is incorporated into the graphs not through DF
expressions, but rather consumed directly by the execution logic.

This makes the DF expression closer to the user request’s surface form, and
reduces the load on the seq2seq model.

In a practical dialogue system set-up, this assumption is reasonable, since at
run time the human agent is replaced by a programmed agent, which gives us
direct access to its internal state and decisions (see section 5 for more
detail).

#### 4.1.4. Conversion scope

SM’s conversion is focused on achieving a dialogue state which matches the
manual MultiWOZ state annotation.

Our conversion also tries to approximate the behaviour of a more complete
dialogue system (the converted expressions should actually execute the
dialogues in a way which is acceptable to users).

In a case when the state delta (used by SM) is empty (e.g. when the user asks
for some information, like the price of a train), they produce an empty
expression. While this behaviour still results in a correct (unchanged) state,
it is not a desirable behaviour for a real dialogue system.

In our conversion, such cases are converted into domain relevant get-info
expressions (which will then produce an answer with the requested
information), when the dialogue act indicates information requests by the
user. In addition, our implementation takes care of prompting the user for
input and keeping the conversation ”alive”, rather than passively waiting for
the user’s next input.

## 5\. Agent oracle

Developing a dialogue system, like any other software development, is a
process of iterative improvements: the system is tested on real data, problems
are identified, solutions are implemented, followed by more tests, etc.

Due to the context dependent nature of dialogues, a different response from a
new version of the system in one turn may cause the rest of the dialogue to
follow a different path. This is not a problem if the system interacts with
live users, but during the development phase, repeatedly collecting large sets
of human-machine interactions for successive iterations of the system is not
practical.

Instead, the collection of user interactions is done once, using either a
fixed implementation for the system (agent) part, or a WOZ set-up where
another human plays the agent.

Therefore, developers face a problem: how to use a fixed dialogue to test a
changing system? More specifically, the problem is how to use the fixed part
of the human user (since the agent part can be re-generated).

The problem is more severe when the dialogue system introduces some non-
deterministic behaviour. For example, when several pieces of information are
missing, a fully deterministic system may ask for the information pieces one
by one in a fixed order, while a non fully-deterministic system may ask for
the information in random order, either one piece at a time or several
together (and use different wordings), or even proactively suggest or
recommend some values.

The WOZ set-up, where the agent is played by a human, exacerbates the problem
further.

### 5.1. Agent oracle

In our implementation we handle this problem by allowing an agent oracle to
influence the system behaviour. Conceptually, the human agent is considered as
a non-deterministic system.

In the implementation of the agent, we separate the non-deterministic part
(the decision what actions to take) from the deterministic part (the execution
of the decision). Using this separation, we can run the system in different
modes during training (where the given agent annotations act as an oracle
influencing the decision) and inference (where a rule based decision can be
made).

The system can be switched between one of three ’agent oracle’ modes:

  1. 1.

Oracle off: no oracle is present - the agent behaviour and output are
generated by executing the programmed logic of the dialogue, this is the
typical mode used when running the final system on unseen dialogues;

  2. 2.

Full Oracle: an agent’s (human) behaviour and response is available - output
the agent’s response as is. This is equivalent to the approach taken by
[Semantic Machines et al., 2020];

  3. 3.

Partial Oracle: an agent’s behaviour and response are available - use the
agent’s behaviour (specifically, the agent’s dialogue acts) to guide the
programmed logic, and generate the output programmatically.

The partial oracle mode may also be used to standardize the dialogues (by
replacing the human agent’s language by the response programmatically
generated by the programmed logic), and thus make the seq2seq translation
model’s work easier. We plan to explore this further in the future.

Using the oracle makes it possible to have ”live” interactions with the
dialogue system - the dialogues are actually executed by the system,
generating DF graphs corresponding to the actual dialogue path. In other
words, this means the annotation of MultiWOZ can be extended by complete
execution graphs, which could be used for learning and evaluating various
models.

Although the oracle’s policy (action selected given a specific state) may not
always match the policy of the implemented system, the graphs are (hopefully)
similar enough to allow the learning of useful inference models.

## 6\. Conversion alternatives

We have experimented with two annotation schemes for the DF expressions
representing MultiWOZ turns.

### 6.1. Full expressions

This style of DF expressions is closer to the original SM annotations, making
direct use of the ”raw” revise() function, which requires the explicit
inclusion of ”formal” parameters (such as empty type constraints).

### 6.2. Simplified expressions

Similar to the work in [Meron, 2022], we also implemented a simplified version
of the annotation, where the expressions use a modified version of the
revise() function, resulting in shorter, more natural looking expressions,
which are closer to the surface natural language request. The simplified
expressions were originally introduced to both improve understandability (less
relevant in this context) and help the natural language to DF expression
translation model.

### 6.3. Expression scope

As mentioned previously, our focus was to make a functional DF dialogue system
which can demonstrate how this paradigm works, while using a well known
domain. While the goal of SM’s experiment was to maximize the match with the
annotated state match, our implementation tried to include some additional
aspects. For example, when the user asks for information, and the answer does
not change the state (e.g. after a restaurant was chosen, the user asks: ”Is
it expensive?”) the SM conversion would produces an empty expression. In our
conversion, we actually want the system to respond to the answer with a
question, so this will be converted to ”get_restaurant_info(pricerange)”.

On top of the full and simplified expression alternatives, a flag -
omit_get_info \- can be used to omit these get_info expressions from the
conversion.

## 7\. Metrics

In this section we describe the metrics used in our experiments. Figure 1
gives an overview of the way these metrics are used.

Figure 1:  Overview of comparisons and metrics used in our experiments. Blue
arrows indicate exact match, green arrows indicate lenient match.

### 7.1. Translation match

This metric compares the translation of the users’ natural language requests
to DF expressions. In SM’s paper, the exact match metric is used.

### 7.2. State match

This metric compares the dialogue state annotations of MultiWOZ 2.2, at each
dialogue turn, to a dialogue state collected from the execution graphs for the
same turn.

The collection of the state from the graph is done in the following way:

  * •

For complete tasks, we take the complete information - e.g. if a specific
hotel was agreed on, all of that hotel’s information (which were retrieved
from the database and used to instantiate a full hotel sub graph) are added to
the collected state.

  * •

For incomplete tasks, we take the currently existing fields for the
corresponding constraint - e.g. if the user requested a hotel in a price
range, but a specific hotel was not selected yet, the collected state will
only include the price range field.

Our DF conversion is based on the dialogue act annotations of MultiWOZ 2.2.
During dialogue execution, we perform a comparison of MultiWOZ’s manual
dialogue state annotation with the dialogue state collected from the execution
graph (as described above). This means that we execute the dialogue acts, but
compare the result to the dialogue state, which is bound to cause mismatch
when the two separate manual annotations do not agree.

In our current version, for the test set , about 45% of the dialogues have one
or more state mismatch, and almost 15% of turns have a state mismatch.

Taking a small set of dialogues with state mismatch (randomly selected 25
mismatching dialogues from the development set), we carried out a manual
analysis of the cause of the mismatch. The result showed that all of these
cases are the result of human annotation errors.

Note that when comparing the manually annotated state (MS) to the graph state
(GS), a more lenient state matching is used than when comparing MS to MS. This
is due to practical reasons.

The GS has a set of fields, and for each one (assuming it exists) there can be
only one value, while for each MS field there can be a list of values. During
comparison we check the following: 1. The set of GS fields is a superset of
the set MS fields. 2. For MS field, at least one of the values is in the
corresponding GS field.

The motivation for this were the many cases where the state is ambiguous (and
the annotation is arbitrary) - the agent made a suggestion, but it’s not clear
if the suggestion should be considered as accepted by the user (MultiWOZ,
unlike SMCalFlow, does not include explicit annotation for accept/reject
suggestions). Further work is needed to address this issue in more detail.

## 8\. Experiments

The implemented MultiWOZ-DF was in the following experiments (as shown in
figure 1):

### 8.1. Translation accuracy

The users’ natural language requests were translated to DF expressions using
the same seq2seq translation pipeline used by [Semantic Machines et al.,
2020]. The translation accuracy results are shown in table 1.

| Turn level exact match
---|---
Original | 71.8%
Simplified | 73.5%
Original omit | 76.5%
Simplified omit | 78.3%
Table 1: Turn exact match, on test set. (not averaged over several runs)

The table confirms that simplified annotations are simpler for the seq2seq
translation model to learn, despite the fact that they have identical
semantics. It also confirms that omitting the added get_info expressions
further increases translation accuracy.

### 8.2. State match

Table 2 shows the match result between the manual dialogue state annotation
and the execution results of the different conversion alternatives.

| Dialogue | Turn
---|---|---
Original, Converted | 55.8% | 87.2%
Simplified, Converted | 56.1% | 87.8%
Original, Translated | 40.9% | 77.9%
Simplified, Translated | 42.7% | 82.1%
Table 2:  State match, full-dialogue level as well as turn level, on the test set. | Dialogue | Turn
---|---|---
Original | 47.9% | 72.2%
Simplified | 54.3% | 76.0%
Table 3:  Graph state match, comparing converted vs. translated execution
graphs, full-dialogue level as well as turn level, on the test set.

Table 3 shows the result of comparing the execution graph state between the
converted (ground truth) expressions and the translated expressions, for the
non-simplified (”original”) and simplified conversion alternatives. Note that
the comparison metric used here is exact match (as opposed to the more lenient
comparison in table 2).

## 9\. Further Work

This work explored the application of the DF paradigm to MultiWOZ. MultiWOZ
has an intent-and-entities type of annotation, which is a flat (non-
hierarchical) annotation. DF expressions are inherently hierarchical, capable
to easily accommodate richer annotations, as exemplified in SMCalFlow.

Still, even for flat annotations datasets, DF may offer benefits. On one hand,
it could lead to improvement in learning related aspects of the system (e.g.
reducing the need for learning capacity through the use of the refer() and
revise() functions). On the other hand, DF has a potential to simplify the
practical aspects of dialogue system design, with its different approach to
dialogue flow design (e.g. as compared to systems based on a state-machine
dialogue management).

## 10\. Conclusion

In this work we presented MultiWOZ-DF, a dataflow implementation of the widely
used MultiWOZ dataset.

We also showed several alternative strategies for converting the MultiWOZ
dataset to a dataflow dataset, and the effect this can have on translation and
execution accuracy.

The code to reproduce this work has been publicly released at
https://github.com/ telepathylabsai/OpenDF.

Previous experiments on a dataflow version of MultiWOZ were reported in
[Semantic Machines et al., 2020], but since that system is not publicly
available, follow-up work has been limited.

While direct quantitative comparison of that work’s result to our is difficult
due to different design decisions taken, our main goal was to allow
researchers to get hands-on experience with a functioning dataflow dialogue
system using a familiar dataset, and to encourage further work in this
direction.

## 11\. Bibliographical References

## References

  * Budzianowski et al., 2018 Budzianowski, P., Wen, T.-H., Tseng, B.-H., Casanueva, I., Ultes, S., Ramadan, O., and Gašić, M.  (2018).  MultiWOZ - a large-scale multi-domain Wizard-of-Oz dataset for task-oriented dialogue modelling.  In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium.
  * Meron, 2022 Meron, J.  (2022).  Simplifying semantic annotations of SMCalFlow.  In Proceedings of the 18th Joint ACL - ISO Workshop on Interoperable Semantic Annotation within LREC2022, pages 81–85, Marseille, France, June. European Language Resources Association.
  * Semantic Machines et al., 2020 Semantic Machines et al.  (2020).  Task-oriented dialogue as dataflow synthesis.  Transactions of the Association for Computational Linguistics, 8:556–571.
  * Wu et al., 2019 Wu, C.-S., Madotto, A., Hosseini-Asl, E., Xiong, C., Socher, R., and Fung, P.  (2019).  Transferable multi-domain state generator for task-oriented dialogue systems.  In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 808–819, Florence, Italy, July. Association for Computational Linguistics.
  * Zang et al., 2020 Zang, X., Rastogi, A., Sunkara, S., Gupta, R., Zhang, J., and Chen, J.  (2020).  Multiwoz 2.2 : A dialogue dataset with additional annotation corrections and state tracking baselines.  CoRR, abs/2007.12720.

##  Appendix A Examples of Dataflow expressions

Table 4 shows some examples of user requests translated to different
alternatives of DF expressions: the SM version, our original version (non-
simplified), and our simplified version.

source | text
---|---
user | I am looking for a particular restaurant called city stop restaurant.
SM | (find (Constraint[Restaurant] :name (?= "city stop restaurant")))
Ours, original | cont_turn(raise_task(FindRestaurant),
|  revise(old=Restaurant??(), newMode=overwrite,
|  new=Restaurant?(name=LIKE(Name(city stop restaurant)))))
Ours, simplified | revise_restaurant(name=city stop restaurant)
user | Yes, I would. Please reserve a table for 4 at 17:30 on Thursday.
SM | (ReviseConstraint :new (Constraint[Restaurant]
|  :book-day (?= "thursday")
|  :book-people (?= "4") :book-time (?= "17:30"))
|  :oldLocation (Constraint[Constraint[Restaurant]])
|  :rootLocation (roleConstraint #(Path "output")))
Ours, original | revise(old=RestaurantBookInfo?(), newMode=overwrite,
|  new=RestaurantBookInfo(bookday=thursday,
|  bookpeople=4, booktime=17:30))
Ours, simplified | revise_restaurant(bookday=thursday, bookpeople=4, booktime=17:30)
Table 4:  User requests, and their corresponding conversion to DF expressions
in three alternatives: SM’s version, our original version, our simplified
version.

##  Appendix B Example dialogue

Figure 2 shows the execution of a short dialogue, and table 5 shows the user
requests, their translation to DF expressions (for the simplified version),
and the agent responses for the same dialogue. For the agent response, the
table shows both the original agent text (”full oracle”), and the response
generated programmatically by the implemented DF nodes.

Figure 2:  Execution graph for short dialogue (SNG0551), using the simplified expressions. Turn | source | text
---|---|---
1 | user | I am looking for a particular restaurant called city stop restaurant.
1 | DF-expression | revise_restaurant(name=city stop restaurant)
1 | full oracle | It is an expensive european restaurant in the north part of town.
|  | Would you like to make a booking?
1 | partial oracle | OK, city stop restaurant, serves european food, in the north, expensive price range, …
|  | On which day would you like to book the restaurant?
2 | user | Yes, I would. Please reserve a table for 4 at 17:30 on Thursday.
|  | I would like the reference number as well, please.
2 | DF-expression | revise_restaurant(bookday=thursday, bookpeople=4, booktime=17:30)
2 | full oracle | Alright, I’ve booked a table for 4 at 17:30 on Thursday. Your reference number is VLG5U01Z.
2 | partial oracle | I have made the reservation as requested. The confirmation code is VLG5U01Z.
|  | Is there anything else I can do for you?
3 | user | Thanks, that’s all I need. Have a nice day.
3 | DF-expression | General_bye()
3 | full oracle | You too, enjoy your meal!
3 | partial oracle | Thank you! Goodbye!
Table 5:  User requests, DF expressions, and agent responses (full oracle and
partial oracle) for the turns of the short dialogue SNG0551.