\section{Introduction}
With the exploding growth of online platforms in recent years, recommendation systems have become an essential component in elevating user  engagement levels and thus have taken a central role in business success. Many services leverage historical data of users and their interactions with their service (e.g., an app or a website) to  personalize recommendations. Such recommendation systems are increasingly popular in various domains including: e-commerce, social media, search engines, content portals, and online publishing platforms.

In this work, we focus on exploiting the sequential behavior of users in order to predict their upcoming interactions. Existing sequential recommender designs, e.g., Markov chains, recurrent neural networks (RNN), graph convolutional neural networks (GCN), and self-attention based models (to name a few), primarily focus on various ways to model such historical data. However, these sequential models tend to disregard the relationship between items. In particular, platforms usually have access to two types of information that can be valuable for recommendations: (i) interactions of users and the service, which may evolve over time, and (ii)  side information about users, items, and other auxiliary components. Recommender systems can generate more relevant content by taking advantage of item relations that are hard to elicit from interaction sequences of users. Such side information about the items can be based on higher-order item-entity connections and co-occurrence patterns, which can provide implicit information about related items (for instance, a mouse and a laptop).

Efficient exploitation of both temporal data of users and side information is the primary gap this paper attempts to fill. While there are many well-performing solutions in the literature, they do not effectively capture both types of information. For instance, models such as BERT4Rec, SASRec, and GRU4Rec \citep{sun2019bert4rec, kang2018self, hidasi2015session} heavily focus on the temporal aspect by encoding user behavior sequences. Another stream of literature focuses on graph structure to capture item relations and side information, for example: TransE \citep{bordes2013translating}, TransH \citep{wang2014knowledge}, and TransR \cite{lin2015learning}. In this work, we build on both these prior works and provide a novel way to integrate them. We follow this up by systematically exploring the importance of capturing both types of information on recommendation quality.

To capture the short-term preferences, long-term interests, and item-item relations, we propose the Knowledge Aware aTtentive Sequential Recommendations (KATRec) system. Our recommendation system consists of two modules: (i) a bidirectional transformer, which captures sequential interests by considering the inter-dependencies among items at any temporal distance, and (ii) a knowledge graph attention network that models higher-order user-item and item-item relations. The user-item relations are based on the interactions of users with items, e.g., click, purchase, view, etc., and capture \emph{collaborative information}. The item-item relations capture the \emph{semantic relatedness} among items based on their shared entities (e.g., movies with the same actor or genre). The importance of capturing such information while making sequential recommendations has been previously discussed in \citet{ji2019sequential, ma2019memory, zhang2020adaptive} to name a few. In addition to first-order relations, sequential recommendations generated by KATRec can use higher-order connections and relations among items (e.g., an individual can be an actor in a movie and a producer in another). Figure~\ref{illustration} illustrates two sequences of user interactions. A traditional sequential recommendation system models these two users differently, as they interact with different movies, although these users show similar interests to movies with shared entities (genre, actor, producer, etc.). Therefore, incorporating information using a knowledge graph can enhance their representations, and consequently improve recommendation performance \citet{KGAT19, zhao2019kb4rec}.

\begin{figure}[h]
\centering
\includegraphics[  page=1,
  width=0.7 \textwidth,
  height=\textheight,
  keepaspectratio,
  trim=0 0 0 20pt,]{2movie_KATRec.pdf}\caption{Sequential interactions of two users with the systems. While users interact with different items, their collaborative signal can be detected via shared entities.}\label{illustration}

\end{figure}

This work proposes a novel deep neural network architecture incorporating both sequential behavior of users and side information about items. Our proposed structure captures the temporal information using a sequential attention mechanism and spatial information via a knowledge graph attention mechanism. To summarize, the key contributions of this work are:
\begin{itemize}
    \item KATRec builds on a knowledge graph neural network that captures multi-relationships between items by tying them together using the underlying entities. This allows for better representations of items and enhances the recommendation performance.
    \item KATRec models the short-term and long-term user preferences by adaptively aggregating dynamic interactions and item-item multi-relations through a gating mechanism. This mechanism can significantly alleviate the sparsity in both user sequences and item relationships.
    \item KATRec captures co-occurrence information and collaborative signals by leveraging attention mechanisms in the knowledge graph, which ultimately impact the attention weights in the bidirectional transformer module and the overall recommendations.
    \item We conduct experiments to evaluate the impact of different components on the performance of KATRec, and show that it outperforms state-of-the-art baselines on three public datasets.
\end{itemize}

The paper is organized as follows: in Section \ref{lit}, we review the relevant prior literature. Section \ref{model} defines the problem and presents the new architecture KATRec. We conduct a detailed comparison of the performance of KATRec with multiple competitive baselines in Section~\ref{experiment}. Section~\ref{conclusion} concludes with some pointers to future directions.

\section{Literature Review}\label{lit}

\subsection{General Recommendations}
Early work on recommendation systems uses collaborative filtering (CF) to make recommendations based on common interests between users \citep{koren2008factorization}, which can be modeled using either explicit or implicit ratings \citep{hu2008collaborative}. CF based models usually suffer from the sparsity of the user-item interactions, which makes them susceptible to the cold start problem. To address this issue, newer variants of matrix factorization, including point-wise and pair-wise methods, have been proposed \citep{rendle2012bpr, he2016fusing}.

Recent advances in deep neural networks (DNNs) have resulted in the development of recommendation models that have higher flexibility in learning user and item representations \citep{zhang2019deep}. Among several recent works in this area, \cite{wu2016collaborative} and \cite{he2017neural} use conventional matrix factorization with DNNs to predict ratings using autoencoders, and also predict user preferences using certain multi-layer perceptron architectures.

\subsection{Sequential Recommendations}
Given a user's temporally structured historical interaction logs, sequential recommendations predict the next item that a user is likely to adopt. Early works incorporated Markov chains to capture the underlying temporal behavior. For example, \citep{rendle2010factorizing, he2016fusing} look at the most recently interacted item(s) to predict the next item to recommend. Newer methods have incorporated higher-order Markov chains to capture a better representation of user behavior. For instance, the Convolutional Sequence Model (Caser) in \cite{tang2018personalized} learns the sequential patterns of a user via an embedding matrix of a fixed size that captures the previous $L$ items, using it as an image input and leveraging convolutional filters. A collection of works has similarly adopted RNNs to encode temporal user preferences into a context vector~\citep{hidasi2015session, donkers2017sequential}.
The attention mechanism has recently been used as a key modeling component for time series data in natural language processing, including in architectures such as the transformer \citep{vaswani2017attention} and BERT \citep{devlin2018bert}. Inspired by these initial works, \cite{kang2018self} proposes a two-layer transformer decoder, namely SASRec, to capture sequential user behavior. \cite{sun2019bert4rec} encodes user preferences with a bidirectional model using the Cloze task setup. While all these models encode sequential preferences of users, they have limited power in capturing the relationships between items themselves and between items and users in a parsimonious way. Our proposed approach aggregates higher-order and multi-relation item connections and dynamic preferences of users to predict the next item while retaining modular interpretability.

\subsection{Knowledge-aware Recommendations}
There have been multiple prior works that focus on enhancing recommendation system performance by explicitly considering multi-relations between items \citep{qin2020survey}. These models usually leverage the structure of an associated knowledge graph and a static user-item interaction graph to exploit such higher-order relationships, typically through path selection algorithms \citep{wang2019explainable, lei2020interactive} and meta-paths heuristics \citep{huang2020meta,hu2018leveraging}. However, these approaches can be sub-optimal for the recommendation objective, and may requires a reasonably high degree of domain knowledge, making them less suitable for generating highly relevant recommendations. A recent work focuses on regularizing the recommendation objective by adding a loss that captures the knowledge graph structure \citep{wang2019knowledge,KGAT19}. Due to certain modeling choices, it is not fully clear if higher-order connectivity is being captured effectively, while retaining interpretability. In contrast to these methods, some of which are focused on generic graphs, we incorporate a knowledge graph while taking the higher-order connectivity between entities and their neighbors into account in a parsimonious way, and fuse these signals into an attention-based sequential model that captures dynamic preferences of a user.

\section{Method}\label{model}

Our goal is to provide a personalized next item recommendation for users based on their history and higher-order relations between items. In this section, we first state a formal definition of the problem, and then we elaborate on different parts of our proposed solution.

\subsection{Problem Definition and Solution Overview}

Given a set of users $\mathcal{U}$ and items $\mathcal{I}$, we have a sequence of items $\mathcal{S}^u = \{S_1^u,  \cdots, S^u_{T}\}$ that user $u$ has interacted with over $T$ time steps ($T = |\mathcal{S}^u|$). Also, we have access to side information related to items (e.g., actors, directors, and genre as shown in Figure \ref{illustration}). Based on the historical interaction sequence $\mathcal{S}^u$, our goal is to predict the item that user $u$ is most likely interested in at the next time step $T+1$.

In KATRec, we build a knowledge-aware attentive sequential recommendation system to facilitate modeling of dynamic behavior of users while capturing the multi-relations between items. Specifically, our model contains two modules as shown in Figure \ref{katrec}, namely: (a) a graph neural network $\mathcal{G}$ which captures item level multi-relations, and (b) a bidirectional transformer module that incorporates item embeddings from the knowledge graph network into the representations of dynamic preferences exhibited by the users. In the following, we discuss the details of each.

\begin{figure}[h]
\centering
\includegraphics[width=\textwidth]{katrec.pdf}\caption{Illustration of different components of the knowledge graph attention module (left) and the dynamic user interaction module (right). First, we learn the initial item embeddings using the knowledge graph attention module. Then, we feed these item embeddings and the user's interaction sequence $\mathcal{S}^u$ through $M$ layers of the bidirectional transformer (TFL) to obtain the final item embeddings that are then used for next item recommendation.}\label{katrec}
\end{figure}

\subsection{Knowledge Graph Module with Attention}\label{subsec:gat}

This module encodes items' metadata as a unified graph to exploit the higher-order connectivity between items. The graph $\mathcal{G} = (\mathcal{E}, \mathcal{R})$, where $\mathcal{I} \subset \mathcal{E}$, incorporates entities as nodes and relationships as the edges. For instance, entities in a movie data set include the items and their side information e.g., genres, producer, actor, etc.  We use entities as building blocks that capture connections between items, and we focus on paths that start and end with items. Formally, the $K$-order connectivity between items is a path that captures a higher-order relationship between items $(i, j)$ as: $i \xrightarrow{r_1} \ent_1 \xrightarrow{r_2} \ent_2 \xrightarrow{r_3} \cdots \xrightarrow{r_K} j$, where $(i, j) \in \mathcal{I}$, entity $\ent_k \in \mathcal{E}$, and relation $r_k \in \mathcal{R}$ for $k \in \{1,2, \cdots, K\}$. In addition to item and entities in the paths, we also model the joint occurrence of commonly related items using a collaborative knowledge graph by adding users as nodes in the graph. In particular, we integrate the item-user relations $\mathcal{R}_{\mathcal{U}}$ into the knowledge graph, so in the resulting graph, the interactions of users with items are also captured. We can represent the graph by a pair of nodes and their relation as $\mathcal{G} = \{(h, r, t)|h,t \in \mathcal{E}', r \in \mathcal{R}'\}$, where $\mathcal{E}' \subset \mathcal{E} \cup \mathcal{U}$ and $\mathcal{R}' \subset \mathcal{R} \cup \mathcal{R}_{\mathcal{U}}$. Figure \ref{kg_fig} illustrates a collaborative knowledge graph where movie $i$ and movie $j$ are second order neighbors related by entity $\ent_1$ in the path $i \xrightarrow{r_4} \ent_1 \xrightarrow{r_5} j$ or related by user $u_2$ in the path $i \xrightarrow{r_3} u_2 \xrightarrow{r_2} j$.

\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{KG_fig.pdf}\caption{Collaborative knowledge graph relates items $i$ and $j$ through user $u_2$ and entity $\ent_1$ with different types of relations.}\label{kg_fig}
\end{figure}

In order to encode these relations as item embeddings, we use the TransR method \citep{lin2015learning}. TransR learns the embedding of each node and relation via the translation principle: $W^r e_h + e_r \approx W^r e_t$ ($e_h, e_t \in \mathbb{R}^d$, $e_r\in \mathbb{R}^k$, and $W^r \in \mathbb{R}^{k\times d}$), if triplet $(h, r, t)$ exists in the knowledge graph. For each triplet $(h, r, t)$ the dissimilarity score is computed using:
\begin{displaymath} s(h, r, t) = \lVert W^r e_h+e_r - W^re_t \rVert_2^2,
\end{displaymath}
The lower the score of $s(h, r, t)$ the more likely is the triplet in the KG. Following \cite{KGAT19}, we capture each relation's importance by generating attentive weights between a node and its higher-order neighbors. So, for each node $h$, we initially consider all nodes that have the first-order relation with it, i.e.,
\begin{displaymath}\mathcal{N}_{h} = \{(h', r, t)|(h', r, t)\in \mathcal{G} \textrm{ with } h'=h\}.
\end{displaymath}

The first order connectivity embedding of head node $h$ is defined as the linear combination of the embeddings of its ego network:
\begin{displaymath}
e_{\mathcal{N}_h} = \sum_{(h, r, t)\in \mathcal{N}_h} \pi(h, r, t)e_t,
\end{displaymath}
where attention factor $\pi(h, r, t)$ controls how much information from different tails can be propagated to head $h$ based on specific relations, and can be computed as follows:
\begin{displaymath}
\pi(h, r, t) = (W^r e_t)^\top \tanh(W^r e_h+e_r).
\end{displaymath}

This attention mechanism will propagate more information from closer entities in the relationship space. Then, we normalize the coefficients across all $h$'s first-order relations using a softmax function:
\begin{displaymath}\pi'(h, r, t) = \frac{\exp(\pi(h, r, t))}{\sum_{(h, r', t')\in \mathcal{N}_h}\exp(\pi(h, r', t'))}.
\end{displaymath}

We update the node's representation by aggregating its representation and its ego network/connectivity representation using the relation: $e_h^{(1)} = f^{(1)}_{\mathcal{G}}(e_h, e_{\mathcal{N}_h})$, where aggregator $f^{(1)}_{\mathcal{G}}$ is defined as follows:
\begin{displaymath}
f^{(1)}_{\mathcal{G}} = \sigma\Big(W^{(1)}_1(e_h+e_{\mathcal{N}_h})\Big)+\sigma\Big(W^{(1)}_2(e_h\odot e_{\mathcal{N}_h})\Big).
\end{displaymath}
Here $\sigma$ is the Leaky ReLU activation function and $W^{(1)}_1, W^{(1)}_2 \in \mathbb{R}^{d^{(1)}} \times \mathbb{R}^d$ are trainable weight matrices. We follow a similar intuition for residual connections by aggregating information through the sum of two representations $e_h$ and $e_{\mathcal{N}_h}$ and retain a copy of input by using the identity transformation. Note that $\odot$ is the element-wise product that captures feature interaction between $e_h$ and $e_{\mathcal{N}_h}$, and ensures richer propagation of information from similar nodes.

For higher-order propagation, we stack more propagation layers to cascade information from higher-order neighbors. The $l$-th step node representation can be formulated as:
\begin{displaymath}
e_h^{(l)} = f^{(l)}_{\mathcal{G}}(e_h^{(l-1)}, e^{(l-1)}_{\mathcal{N}_h}),
\end{displaymath}
where the information cascaded from $l-1$-th ego network is defined as:
\begin{displaymath}
e_{\mathcal{N}_h}^{(l-1)} = \sum_{(h,r,t)\in \mathcal{N}_h} \pi'(h,r,t)e_t^{(l-1)}.
\end{displaymath}
Using this embedding propagation mechanism to stack $L$ layers, the higher-order connectivities can be captured in the node representation. Finally, we concatenate these representations into one vector to get the final representation of the node.
\begin{displaymath}e_h^* = [e_h^{(0)} \mathbin\Vert \cdots \mathbin\Vert \textrm{ } e_h^{(L)}]  \in \mathbb{R}^q,
\end{displaymath}
where $e_h^{(0)} := e_h$ and $q = d + d^{(1)} + \cdots + d^{(L)}$. The different layers of knowledge graph attention module described above are shown in Figure \ref{katrec} (left).

\subsection{Dynamic User Interaction Module}
To capture the sequential patterns among successive items that a user has interacted with, we use the Bidirectional Encoder Representations from Transformers (BERT) architecture \citep{vaswani2017attention, devlin2018bert}. In our context, BERT uses the historical item sequence $\mathcal{S}^u$ corresponding to user $u$ and aims to predict the item that the user is interested in the next time step $T+1$. BERT models $M$ bidirectional transformer layers and revises each item's representation at each layer by exchanging information across all positions at the previous layer. Our key contribution is that we embed the higher-order connectivity of the item relations discussed in subsection \ref{subsec:gat} into the BERT module to capture user preferences under a more informative context. Below, we briefly discuss the self-attention structure used in the BERT module of KATRec.

\subsubsection{Embedding Layer}
{Positional Embedding:}
Since the self-attention mechanism doesn't include any recurrent or convolutional blocks, it cannot be aware of items' position embeddings. So, we incorporate a pre-determined positional embedding $P \in \mathbb{R}^{T \times q}$ into the input embedding:
\begin{displaymath}
     v^{(0)}_i = e^*_i +  p_i,
\end{displaymath}
where $ v^{(0)}_i$ computes the input representation of items at each position index $i = 1,\cdots,T$. Concatenating embedding of $T$ items in a user sequence, $v^{(0)}_i \in \mathbb{R}^{q}$, results in $V^{(0)} \in \mathbb{R}^{T \times q}$. Next, this positional embedding matrix is provided as an input to the first transformer layer. The transformer layer contains two sublayers, a multi-head self-attention sublayer, and a position-wise feed-forward network. In the following, we describe each of these sublayers briefly.

\subsubsection{Transformer Layer}
Multi-Head Self-Attention: The attention mechanism helps the model capture dependencies between each pair of items at any distance in the input sequence, across multiple subspace representations simultaneously. To learn information in different representation subspaces, we use multi-head attention \citep{devlin2018bert}. First, we linearly project ${V}^{(0)}$ into $k$ subspaces using different learnable projections and then apply attention function on each in parallel to create $k$ heads $H_1, \cdots, H_k$ as follows:

\begin{displaymath}H_j = \text{Attention}(V^{(0)} W_j^\mathcal{Q}, V^{(0)} W_j^\mathcal{K}, V^{(0)} W_j^\mathcal{V}),
\end{displaymath}

where $W_j^\mathcal{Q}$, $W_j^\mathcal{K}$ and $W_j^\mathcal{V}$ are all $\mathbb{R}^{q\times q/k}$ learnable projection matrices corresponding to head index $j = 1, \cdots, k$. The attention function is a scaled dot-product defined as $\text{Attention}(\mathcal{Q},\mathcal{K},\mathcal{V}) = \text{softmax}\Big(\frac{\mathcal{Q}\mathcal{K}^\top}{\sqrt{q/k}}\Big)\mathcal{V}$. To compute the multi-head attention output, we concatenate these $k$ heads and then project it as follows:
 \begin{displaymath}\text{MH}({V^{(0)}}) = [{H}_1 \mathbin\Vert {H}_2\mathbin\Vert \cdots \mathbin\Vert {H}_k]W^O,
\end{displaymath}
where the learnable projection matrix $W^O \in \mathbb{R}^{q\times q}$. Next, we input $\text{MH}(V^{(0)})$ to a feed-forward sublayer described below.\\

\noindent Position-wise Feed-Forward Network: Since the self-attention sub-layer mainly leverages linear transformations, we need another sub-layer to implement non-linearity and also capture interactions between different dimensions. We use a position-wise feed-forward network on the outputs of the multi-head self-attention sublayer at each position $i = 1, \cdots, T$.
\begin{displaymath}
\text{PFF}(V^{(0)}) = [FF(v_1^{(0)})^\top \mathbin\Vert \cdots \mathbin\Vert FF(v_{T}^{(0)})^\top]
\end{displaymath}
where $FF(x) = \text{GELU}(xW^1+b^1)W^2+b^2$ uses the GELU non-linearity, and $W^1, {W^2}^\top \in \mathbb{R}^{q\times 4q}$, $b^1 \in \mathbb{R}^{4q}$ and $b^2 \in \mathbb{R}^{q}$ are learnable and shared at different positions.

Furthermore, we apply dropout to the output of both multi-head self-attention and position-wise feed-forward sub-layers. Due to the architecture depth, we also add residual connections to capture item-item interactions better. Finally, we apply layer normalization (LN) to  stabilize and accelerate training. These operations can be summarized as $\textrm{LN}(x + \textrm{Dropout}(\textrm{sublayer}(x)))$. In order to learn a more complex representation of items in the sequence, we stack $M$ Transformer layers as illustrated in Figure \ref{katrec}. Again, we note that the above choices are informed by the original BERT architecture for language modeling.

\subsubsection{Output Layer}
Item Co-occurrence Modeling: Capturing pairwise item relations plays an important role in the effectiveness of the recommendation systems and also allows some degree of interpretability. To include item-item relations in item embeddings, we concatenate item embeddings learned by the sequential module and the knowledge graph.
\begin{displaymath}
    \hat{E} = \sigma((V^*\mathbin\Vert E^*)\hat{W} + {\hat{b}}),
\end{displaymath}
where $\hat{E}\in \mathbb{R}^{|\mathcal{I}|\times q}$ is the set of final KATRec embeddings for item set $\mathcal{I}$ and $\hat{W} \in \mathbb{R}^{2q\times q}$ and $\hat{b} \in \mathbb{R}^{q}$ are learnable parameters. $V^*$ is the embedding matrix of items learned by sequential module, and $E^*$ is the items embedding table learned by the knowledge graph. Finally, the next item at time $T+1$ is predicted by:
\begin{displaymath}
P(\mathcal{I}) = \mbox{softmax}(\mbox{GELU}({v}^{(M)}_{T+1} {W}^P + {b}^P) {\hat{E}^\top} + {b}^O),
\end{displaymath}
where ${W}^P, {b}^P$, and ${b}^O$ are learnable parameters, ${\hat{E}} \in \mathbb{R}^{|\mathcal{I}| \times q}$ is the embedding matrix for item set $\mathcal{I}$, and $P(\cdot)$ is the KATRec model's predicted distribution over the target items. $v^{(M)}_{T+1}$ is the hidden state of position $T+1$ after $M$ transformer layers, denoted by $v^*_{T+1}$ in figure \ref{katrec}. \\

\noindent Explicit User Modeling: Existing approaches provide personalized recommendation by modeling the user embedding either explicitly \citep{koren2008factorization, rendle2010factorizing, tang2018personalized} based on users' previous actions, or implicitly \citep{Hidasi2018, kang2018self, sun2019bert4rec} based on embeddings of the sequence of visited items by a user. KATRec belongs to the latter category as we predict the next item at time step $T+1$ by considering the hidden state embedding $v^{(M)}_{T+1}$.

As an aside, we also considered explicit user behavior by incorporating user embeddings learned from the knowledge graph into the user's hidden state via concatenation: $[e^*_u \mathbin\Vert v^{(M)}_{T+1}]$, where $e^*_u$ is the embedding of user $u$ in the knowledge graph. Although this concatenation seems promising, we empirically did not observe improvement in the model's performance. This could be potentially because the model learned users' embedding very well by considering the sequence of interacted items.

\subsection{Optimization}

The loss function of KATRec contains the TransR objective along with a regularizer. In particular, we use the TransR to train the entity embeddings. The objective function can be minimized by discriminating between valid and invalid triplets in the collaborative knowledge graph:
\begin{equation}\label{loss_CKG}
\mathcal{L}_{\mathcal{G}} = \sum_{(h, r, t, t')} -\text{ln} \ \sigma \Big(s(h, r, t')-s(h, r, t)\Big) + \lambda \lVert \Theta\rVert_2^2,\end{equation}
where the sum is over all valid $(h, r, t) \in \mathcal{G}$ and invalid $(h, r, t') \notin \mathcal{G}$ triplets in the knowledge graph $\mathcal{G}$, $\sigma(\cdot)$ is the sigmoid function, and $\lambda \lVert \Theta\rVert_2^2$ represents $\ell_2$ regularization. Similar to \cite{devlin2018bert}, we  implement the \textit{Cloze task} training approach in addition to pairwise ranking loss in equation (\ref{loss_CKG}). This allows us to learn the parameters of the encoders in the transformer layers. In this approach, we randomly mask a portion of items in the input sequence $\mathcal{S}_u$ and try to predict them. The loss for each masked input $S'_u$ is given by:
\begin{displaymath}
    \mathcal{L}_{\mathcal{S}} = \frac{1}{|\mathcal{S}_u^m|} \sum_{i_m \in \mathcal{S}_u^m} - \log P(i_m = i^\star_m| \mathcal{S}'_u ),
\end{displaymath}
where $\mathcal{S}_u^m$ is the set of randomly masked items, $i^\star_m$ is the true item corresponding to the masked item $i_m$, and $P(.)$ is the predicted probability mass function over the target item. These two losses are jointly minimized over their respective parameters using standard first-order approaches (see the next section for details).

\section{Experiments}\label{experiment}

We evaluate our model on three real-world datasets, which are different in domains and have varying levels of sparsity\footnote{Code is available at \url{https://github.com/DanialTaheri/KATRec}}. We aim to answer the following questions in this section:\\
{Q1:} How does KATRec perform compared to the current state-of-the-art sequential recommendation methods?\\
{Q2:} How do different components of the model (viz., knowledge graph based attention mechanism, information aggregation, and pre-training) affect the performance of KATRec?\\
{Q3:} How KATRec's performance change in different settings and datasets?

Following prior work \cite{sun2019bert4rec, kang2018self}, we convert all numeric ratings to positive interaction with a value of $1$, which indicates that the user has interacted with the item. Then, we sort each user's interactions by timestamp to build her interaction sequence.  Similar to prior works, we split the user sequences into three parts. The test dataset includes the most recent item each user has interacted with ($S^u_{T+1}$), the validation dataset consists of the second most recent item interacted by each user ($S^u_{T}$), and the remaining items in the sequence belong to the training data. To construct knowledge graph aware attention, we first build the item knowledge graph for each dataset. We follow \cite{zhao2019kb4rec, KGAT19} to capture knowledge graph triplets by mapping items into \emph{freebase} entities. We include triplets with one-hop and two-hop neighbor entities and filter out entities with less than ten occurrences, and relations less than fifty occurrences. For $\mathcal{L}_{\mathcal{G}}$ in equation (\ref{loss_CKG}), we pair each observed triplet with a broken (unobserved) triplet.
\subsection{Datasets Description}
We evaluate our model on three real-world datasets, which are different in domain and sparsity. For most of the experiments, we only include users and items with at least ten interactions to ensure data quality \cite{KGAT19}. The statistics of the datasets described below are presented in Table~\ref{tab:data} for ease of reference:\\

\begin{table}[ht]
	\centering
	\caption{Statistics of datasets}\label{tab:data}
	\resizebox{\textwidth}{!}{%
	\begin{tabular}{lccccccc}
	\hlineB{2}
    \textbf{Datsets} & Users  & Items & Interactions & Entities & Relations & Triplets & Density \\
    \hline
Amazon-book & 70679 & 24915 & 846434 & 88572 & 39 & 2557746 &0.048\%\\
LastFM & 23566 & 48123 & 8057269 & 58266 & 9 & 464567 &0.7105\%\\
Yelp2018 & 45919 & 45538 & 1185068 & 90961 &42 & 1853704 &0.057\%\\
	\hlineB{2}
    \end{tabular}%
    }%
\end{table}

{Amazon-book}: Amazon review data is one of the popular datasets in the recommendation systems literature \cite{he2016ups}. The data has been categorized based on different product categories, and in this paper, we focus on the book category.\\
{LastFM}: This is a dataset about music listening patterns collected from the Last.fm online music platform \cite{schedl2016lfm}. In this dataset, tracks are viewed as items, and we consider a subset of the dataset from January 2014 to August 2014.\\
{Yelp2018}: This dataset is adopted from the Yelp 2018 recommendation system challenge. In this dataset, local restaurants and bars are represented as items.

\noindent We calculate each dataset's density based on the number of interactions, users, and items as $\frac{|Interactions|}{|Users| \cdot |Items|}$. Therefore, larger values in the density column represent datasets with more interactions (per user and item). Table \ref{tab:data} lists specific properties and the density of each dataset. It also highlights that LastFM has a substantially lesser number of relations and is significantly denser than others.

\subsection{Experimental Settings}
\subsubsection{Evaluation Metrics}
We use two common top-K metrics to evaluate the performance of our model. Hit@K and NDCG@K count the fraction of the time the ground truth item is among the top $K$ recommendations, without and with defining a position-aware weight respectively. Mean Average Precision (MAP) is also a ranked precision metric over all users that emphasizes correct predictions at the top of the list with a position-aware weight. Given a list of top $K$ predicted items $\hat S^u_{1:K}$ for a representative user $u$, and the ground truth last item $S^u_{T+1}$, Hit@K, NDCG@K, and MAP  are computed as:
\begin{align*}
    Hit@K &= \frac{1}{|\mathcal{U}|}\sum_{u \in \mathcal{U}}|\hat S^u_{1:K} \bigcap S^u_{T+1}|,\\
    NDCG@K &= \frac{1}{|\mathcal{U}|}\sum_{u \in \mathcal{U}}\sum_{i=1}^K\frac{rel_i}{\log_2(i+1)},\\
    MAP &= \frac{1}{|\mathcal{U}|}\sum_{u \in \mathcal{U}}\sum_{i=1}^{|\hat S^u|} Prec@i \times rel_i,
\end{align*}
where $rel_i = 1$ if the $i^{th}$ item in $\hat S^u_{1:K}$ equals $S^u_{T+1}$, and $Prec@i$ is the precision (fraction of  recommendations that end up being correct) up till position $i$. Following the works of \cite{kang2018self, sun2019bert4rec}, we randomly sample $100$ negative items for each user besides the ground-truth item. We report the average of the metrics Hit@K, NDCG@K over all users.

\subsubsection{Baselines}
To compare the performance of our model with others, we consider the following competitive baselines:
\begin{itemize}
    \item GRU4Rec \citep{hidasi2015session}: It implements a session-based recommendation model based on RNNs. We consider each user's sequence as a session.
    \item GRU4Re$c^{++}$ \citep{Hidasi2018}: It modifies the way GRU4Rec is optimized by implementing a new loss function and a new sampling approach.
    \item SASRec \citep{kang2018self}: It uses a self-attention mechanism with a left-to-right Transformer to improve the capturing of useful patterns in user sequences.
    \item BERT4Rec \citep{sun2019bert4rec}: This is a recent state-of-the-art sequential recommendation model that adapts the bidirectional Transformers language model architecture to learn the temporal behavior of users.
\end{itemize}

\subsubsection{Parameters for Models}

We implement KATRec with Tensorflow (version 2.2.0). All parameters are initialized using a truncated normal distribution in the interval $[-0.02, 0.02]$. We use the Adam optimiser \citep{kingma2014adam} with learning rate $10^{-4}$ that decays linearly, $\beta_1 = 0.9$, $\beta_2 = 0.999$, and a weight decay of $0.01$. We fix the maximum sequence length proportional to the average sequence length in the dataset, i.e., $50, 50$, and $200$ for Amazon-book, Yelp, and LastFM respectively. We set the dimension of the hidden fully connected layers of KATRec to be $128$. We propagate neighbors' information up to three levels into each entity's embedding with hidden dimensions $32$, $16$, and $16$. Finally, we set the embedding of entities in the knowledge graph to be $64$.

We search for hyperparameters to select the best parameters for different baselines. These include changing embedding size from $\{8, 16, 32, 64, 128\}$ and the regularization hyperparameter $\lambda$ across $\{0.1, 0.05, 0.01, 0.005, 0.001, 0.0001\}$. We use the optimization schemes and parameters suggested by the authors whenever possible. The models are trained on a single GeForce GTX 1080Ti GPU.

\subsubsection{Performance Comparison}

Table \ref{tab:PerformanceComparison} shows the recommendation performance of KATRec and baselines. We do not include Hit@1 since Hit@1 and NDCG@1 are equivalent. Since we have a single ground-truth, Hit@K is equivalent to Recall@K, and it is proportional to Precision@K. \emph{We observe that KATRec provides improved relative recommendation performance over all alternatives by 6.29\% and 3.82\% in Hit and 7.15\% and 4.64\% in NDCG on average, respectively on the Amazon-book and Yelp2018 datasets.}

\begin{table}[ht]

  \caption{KATRec versus baselines over three datasets. The improvement percentage compares KATRec versus the next-best alternative.}
  \label{tab:PerformanceComparison}
  \begin{tabular}{clcccccc}
    \hlineB{2}
    Datasets  & Metrics &GRU &$GRU^{++}$ &SASRec &BERT &KATRec &Improv. \\
    \hline
    &NDCG@1 &0.3485 &0.3464 &0.3749 &\underline{0.4344} &\textbf{0.4706} &8.33\%\\
    &NDCG@5 &0.4404 &0.4358 &0.5267 &\underline{0.5715} &\textbf{0.6110} &6.91\%\\
    {Amazon}&NDCG@10 &0.4598 &0.4574 &0.5600 &\underline{0.6022} &\textbf{0.6401} &6.2\%\\
    &Hit@5 &0.5202 &0.5148 &0.6594 &\underline{0.6910} &\textbf{0.7321} &5.94\%\\
    &Hit@10 &0.58 &0.5814 &0.7621  &\underline{0.7856} &\textbf{0.8217} &4.6\%\\
    &MAP &0.42 &0.4259 &0.5065 &\underline{0.5539} &\textbf{0.5907} &6.64\%\\
    \hline

    & NDCG@1 &0.3646 &0.3523 &\underline{0.6771} &0.6339 &\textbf{0.6931} &2.36\%\\
    &NDCG@5 &0.4648& 0.4448 &\textbf{0.7765} &0.7606 &\underline{0.7725}  &-0.51\%\\
    {LastFM}&NDCG@10 &0.4881 &0.4674 &\textbf{0.7930} &0.7786 &\underline{0.7911} &-0.24\%\\
    &Hit@5 &0.5531 &0.5263 &\textbf{0.8600} &0.8281 &\underline{0.8426}  &-2.06\%\\
    &Hit@10 &0.6249 &0.5958 &\textbf{0.9105}  &0.8836 &\underline{0.9001} &-1.15\%\\
    &MAP &0.4577&0.4357&\underline{0.7598} & 0.7509  &\textbf{0.7618} &0.26\%\\
    \hline

    &NDCG@1 &0.3946&0.4148&0.3723 &\underline{0.4149} &\textbf{0.4405} &6.17\%\\
    &NDCG@5 &0.5041 &0.5143 &0.5703 &\underline{0.6039} &\textbf{0.629} &4.15\%\\
    {Yelp2018}&NDCG@10 &0.5278 &0.5395 &0.6068 &\underline{0.6400} &\textbf{0.663} &3.6\%\\
    &Hit@5 &0.5991 &0.6021 &0.7434 &\underline{0.7690} &\textbf{0.7927} &3.08\%\\
    &Hit@10 &0.6721 &0.68 &0.8551 &\underline{0.8796} &\textbf{0.899} &2.2\%\\\
    &MAP &0.49&0.515&0.5351 &\underline{0.5706} &\textbf{0.5946} &4.21\%\\
    \hlineB{2}
\end{tabular}
\end{table}

In particular, KATRec consistently outperforms BERT4Rec on Amazon-book and Yelp2018 datasets, which shows the importance of modeling item-item and user-item relations. KATRec achieves a considerable performance improvement in Amazon-book, while the improvement in Yelp is relatively small. This observation can be attributed to the difference in the sparsity of these two datasets. The importance of the impact of data density and number of relations on KATRec's performance is highlighted explicitly with the LastFM dataset, which we discuss in further detail in the ablation study that follows.

\subsubsection{Ablation Study}
In this section, we analyze variants of KATRec to understand the impact of different components on model performance. The variations are as follows:
(1) \textit{No Attention}: we remove the attention mechanism in the knowledge graph and allocate equal weights to each entity's neighbors.
(2) \textit{Level-1}: we decrease the level of information that can propagate from the neighbors to a node, and study the impact of only using immediate neighbors to improve node embeddings.
(3) \textit{Connection}: While there exists a connection between two encoder modules in our model, we consider the setting where both modules train independently using learnable embeddings.
(4) \textit{No Pretraining}: We forgo the pre-trained embeddings of entities in the knowledge graph.
(5) \textit{Concat}:  We remove a part of our model that deals with item co-occurrence, and only consider the item embedding vector that results from the sequential module.

Results are shown in Table \ref{tab:Ablation}. We observe that incorporating the side information in the bidirectional encoder module during the training results in better parameter learning as shown in column \textit{Connection}. Furthermore, the results of making the \textit{NoPretrain} choice in the knowledge graph show that incorporating pre-trained embeddings increases the performance of the sequential recommendation model. The attention mechanism between neighbors in the knowledge graph increases the recommendation's performance. However, this increase is not substantial. We also observe that multiple layer information propagation in an item's embedding plays an important role in making next item recommendations. Also, as expected, propagating the first layer's information in the knowledge graph has a higher impact, and this impact decreases when we incorporate higher level of connections. Finally, the results of the \textit{Concat} choice shows that incorporating non-linearity in the final layer is beneficial for learning item embeddings, especially by combining features learned through the knowledge graph and the bidirectional encoder.
\begin{table}[ht]
    \centering
    \caption{Ablation study of design choices in KATRec using three datasets.}
    \label{tab:Ablation}
    \begin{tabular}{clcccccc}
    \hlineB{2}
     Datasets &Metrics &KATRec &NoAtten. &Level-1 &Connect. &NoPretrain &Concat.\\
     \hline
     {Amazon-}&NDCG@10 &0.6401 &0.6371 &0.6386&0.621 &0.6306 &0.6318 \\
     {book}&Hit@10 &0.8217 &0.8178 &0.8195 &0.801  &0.8092 &0.8142 \\
     \hline
     {LastFM}&NDCG@10 &0.7911 &0.7836 & 0.7853 &0.763 &0.7587 &0.7855 \\
            &HIT@10 &0.9001 &0.8967 &0.8957 &0.8796 &0.8752 &0.8908 \\
    \hline
     {Yelp2018}&NDCG@10 &0.663 &0.6567 &0.6546 &0.6458 &0.6359 &0.6515 \\
        &HIT@10 &0.899 &0.8954 &0.8929 &0.885 &0.8696 &0.8881\\
    \hlineB{2}
    \end{tabular}
\end{table}

We also study the recommendation performance of KATRec for users with different sequence lengths and compare it with competitive baselines. The intuition here is that the use of side information can compensate for potentially sparse user item interactions. In Figure \ref{seq-analysis}, we illustrate the percentage of users with varying sizes of item sequences associated with them in each dataset, and report each method's performance for each of the resulting user groups. KATRec outperforms two other competitive baselines for all user groups for Yelp2018 and Amazon-book datasets. Results for LastFM show that KATRec provides a reasonably robust recommendation performance across user groups, while the performance of the baselines is more sensitive to the user sequence length. This robustness of KATRec can be attributed to the item-item and user-item relationships that are explicitly learned. Our model performs relatively better for users with small sequence lengths. However, SASRec marginally outperforms KATRec for users with long sequence lengths. This can be attributed to the high number of interactions and low number of relations in the LastFM dataset, which indicates that the impact of side information on dense datasets may not be significant enough.

\begin{figure}[h]
\begin{subfigure}{0.325\textwidth}
\centering
\includegraphics[width=\textwidth]{amazon_seq.pdf}
\subcaption{Amazon-book}
\end{subfigure}
\begin{subfigure}{0.33\textwidth}
\centering
\includegraphics[width=\textwidth]{lstfm_seq.pdf}
\subcaption{LastFm}
\end{subfigure}
\begin{subfigure}{0.325\textwidth}
\centering
\includegraphics[width=\textwidth]{yelp_seq.pdf}
\subcaption{Yelp}
\end{subfigure}
\caption{Performance comparison of models across users with different sequence lengths on the Amazon-book, LastFM and Yelp2018 datasets.}\label{seq-analysis}
\end{figure}

\subsubsection{Visualizing attention weights} This section visualizes the attention weights related to items and positions to find a meaningful pattern and discuss their differences with the BERT model's attention weights. Figure \ref{Attention_weights} shows the heatmaps of the average attention weights on the last 15 items of the sequences in the test dataset of Yelp2018. In order to calculate the accurate average weights, we do not incorporate weights of padded items in sequences shorter than 15 items. Comparing heatmaps $(a)$ and $(b)$ shows the impact of positional embeddings (PE). In particular, heatmap $(a)$ illustrates how positional embeddings results in items attending more on recent items. Heatmaps $(a)$ and $(c)$ points out how items in various heads and layers focus on different parts of the sequence at both the right and left sides. To compare attentions in BERT4Rec and KATRec, we analyze weights in the final layer as it is directly connected to the output layer and plays an important role in the prediction (heatmaps $(d)$ and $(c)$). The comparison indicates that while BERT4Rec inclines to focus more on the recent items due to the sparsity of the dataset, KATRec tends to attend on less recent items due to incorporating side information through the knowledge graph. This behavior is similar to the attention weights of self-attention blocks in dense datasets in \cite{kang2018self}.
\begin{figure}[h]
\centering
\captionsetup[subfigure]{justification=centering}
\begin{subfigure}{0.24\textwidth}
\centering
\includegraphics[width=\textwidth]{KATREC_L0_H0.png}
\subcaption{KATRec,\\ Layer 1, head 1}
\end{subfigure}
\begin{subfigure}{0.24\textwidth}
\centering
\includegraphics[width=\textwidth]{KATREC_woPoss_L0_H0.png}
\subcaption{KATRec, Layer 1,\\ head 1, w/o PE}
\end{subfigure}
\begin{subfigure}{0.24\textwidth}
\centering
\includegraphics[width=\textwidth]{KATREC_L1_H1.png}
\subcaption{KATRec,\\ Layer 2, head 2}
\end{subfigure}
\begin{subfigure}{0.24\textwidth}
\centering
\includegraphics[width=\textwidth]{BERT_L1_H1.png}
\subcaption{BERT4Rec,\\ Layer 2, head 2}
\end{subfigure}
\caption{Average attention weights on positions (x-axis) at different time (y-axis) on Yelp}
\label{Attention_weights}
\end{figure}

\subsubsection{Attention Weight Case Study}
Figure \ref{cooccurence_Parta} illustrates the co-occurrence ratio between six items in user sequences, computed by the average number of times that a pair of items appeared simultaneously in users' sequence. Figure \ref{att_Partb} compares weights of the final attention layer in KATRec and Bert4Rec between the last item (item $6$) and the rest of the items in a user sequence. Figure \ref{cooccurence_Parta} shows that item $6$ has a high co-occurrence value with items $0, 2, 4$, and $5$. Figure \ref{att_Partb} confirms that KATRec places a higher attention values for items $4$ and $5$ and lower values for items with low co-occurrence value, i.e., time $1$ and $3$. However, we observe that BERT4Rec considers a higher weight between item $6$ and $0$ which is more aligned to their co-occurrence value.

\begin{figure}[h]
\centering
\captionsetup[subfigure]{justification=centering}
\begin{subfigure}{0.4\textwidth}
\centering
\includegraphics[width=\textwidth]{cooccurence_matrix.png}
\subcaption{Co-occurence information}\label{cooccurence_Parta}
\end{subfigure}
\begin{subfigure}{0.4\textwidth}
\centering
\includegraphics[width=\textwidth]{Attention_Weights.png}
\subcaption{Attention weights}\label{att_Partb}
\end{subfigure}
\caption{Attention heatmap comparison of a random user in Yelp2018 dataset. \ref{cooccurence_Parta} shows the co-occurrence ratio, which is the co-occurrence frequency of each pair of six items among all users' sequences. \ref{att_Partb} compares these items' attention weight at the last position in KATRec and BERT4Rec.}
\end{figure}
\section{Conclusion and Future Work}\label{conclusion}
Designing robust deep neural network architectures that produce quality recommendations is challenging for several reasons. A couple of these challenges were addressed in this work, namely leveraging of side information and getting around data sparsity. In particular, we proposed incorporating item side information to alleviate both these shortcomings while making recommendations. This information is readily available in many real-world applications.

Our work introduces a novel neural network structure that leverages collaborative knowledge graphs to improve the representations of items in a sequential recommendation system setup. Empirical results are provided to illustrate the benefit via multiple evaluation metrics: the proposed solution is compared against multiple state-of-the-art sequential recommendation systems on three different datasets. Similar to the way we included item metadata in building a more performant recommendation system, further research in incorporating user metadata can be undertaken.

\vskip 0.2in


\section{Introduction}

\emph{Input-driven pushdown automata} (IDPDA),
also known under the name of \emph{visibly pushdown automata},
are an important special class of pushdown automata,
introduced by Mehlhorn~\cite{Mehlhorn}.
In these automata, the input symbol determines
whether the automaton pushes a stack symbol,
pops a stack symbol
or does not access the stack at all.
These symbols are called
\emph{left brackets}, \emph{right brackets}
and \emph{neutral symbols},
and the symbol pushed at each left bracket
is always popped when reading the corresponding right bracket.
As shown by von Braunm\"uhl and Verbeek~\cite{vonBraunmuehl_Verbeek},
deterministic (DIDPDA)
and nondeterministic (NIDPDA) input-driven automata
are equivalent in power,
and the languages they recognize lie in the deterministic logarithmic space.
Input-driven automata enjoy excellent closure properties,
which almost rival those of finite automata,
and their complexity on terms of the number of states
has been extensively studied.
For more details, the reader is directed
to a survey by Okhotin and Salomaa~\cite{idpda_sigact_survey}.

A systematic study of input-driven automata was undertaken in a famous paper
by Alur and Madhusudan~\cite{AlurMadhusudan,AlurMadhusudan_JACM},
who, in particular,
generalized these automata to the case of infinite strings ($\omega$-IDPDA),
and identified them as a suitable model for verification.
By analogy with finite automata,
one can consider deterministic and nondeterministic $\omega$-IDPDA,
with B\"uchi and Muller acceptance conditions.
However, their properties are different:
for instance, unlike finite-state Muller $\omega$-automata,
Muller $\omega$-IDPDA cannot be determinized~\cite{AlurMadhusudan,AlurMadhusudan_JACM}.

This issue with determinization
was further studied by L\"oding et al.~\cite{LoedingMadhusudanSerre},
who discovered a more sophisticated acceptance condition,
under which determinization is possible.
The analysis made by L\"oding et al.~\cite{LoedingMadhusudanSerre} clearly indicates
that the main difficulty is caused by \emph{ill-nested inputs},
that is, infinite strings that may have \emph{unmatched left brackets}.
Recalling an important motivation for $\omega$-IDPDA
as a model of infinite computation traces
involving a stack~\cite{AlurMadhusudan,AlurMadhusudan_JACM},
an ill-nested input often means
a particular type of faulty behaviour: a memory leak.
A computation trace represented by a \emph{well-nested infinite string}
of the form $u_1 u_2 \ldots u_i \ldots$,
where each $u_i$ is a well-nested finite string,
is the normal behaviour.

This observation motivates the study
of a special class of $\omega$-IDPDA
operating on well-nested infinite strings.
These automata model a normal behaviour of an infinite process without memory leaks,
and they avoid the difficulties with determinization
discovered by L\"oding et al.~\cite{LoedingMadhusudanSerre}.

This paper investigates the properties of well-nested $\omega$-IDPDA,
which are defined in Section~\ref{idomega} in usual variants:
deterministic and nondeterministic,
with B\"uchi and Muller acceptance conditions.

In Section~\ref{section_characterization}, a characterization
of the corresponding $\omega$-IDPDA languages of well-nested strings
in terms of IDPDA on finite strings
and the usual $\omega$-regular languages is obtained.
This characterization leads to a determinization procedure for
well-nested Muller IDPDA,
as well as to the proof of their equivalence to nondeterministic B\"uchi IDPDA.

Besides the determinization question,
another property investigated by L\"oding et al.~\cite{LoedingMadhusudanSerre}
is the topology of $\omega$-languages
recognized by $\omega$-IDPDA.
These results motivate the study of Wadge degrees of $\omega$-IDPDA languages.
Although this collection is larger than that for the regular $\omega$-languages,
there is a hope to obtain an effective extension of Wagner hierarchy~\cite{wag}
to such languages which would nicely contrast
the case of (deterministic) context-free $\omega$-languages~\cite{fin,dup}.

The result of this paper, presented in Section~\ref{section_wadge},
is that the hierarchy of Wadge degrees of $\omega$-IDPDA languages of well-nested strings,
essentially coincides with the classical Wagner hierarchy of $\omega$-regular languages.

\section{Input-driven $\omega$-automata} \label{idomega}

Let $\Sigma$ be a finite alphabet.
The set of finite strings over $\Sigma$ is $\Sigma^*$,
the set of one-sided infinite strings is $\Sigma^\omega$.

In input-driven automata, the alphabet is
split into three disjoint sets
of \emph{left brackets} $\Sigma_{+1}$,
\emph{right brackets} $\Sigma_{-1}$
and \emph{neutral symbols} $\Sigma_0$.
In this paper, symbols from $\Sigma_{+1}$ and $\Sigma_{-1}$
shall be denoted by left and right angled brackets, respectively ($<$, $>$),
whereas lower-case Latin letters from the beginning of the alphabet ($a, b, c, \ldots$)
shall be used for symbols from $\Sigma_0$.

In a well-nested string,
any left bracket from $\Sigma_{+1}$ can match any right bracket from $\Sigma_{-1}$.
Formally, the set of well-nested finite strings, $\wn$,
is defined by the following grammar.
\begin{align*}
	S &\to SS
		\\
	S &\to {<} S {>}
		&& ({<} \in \Sigma_{+1}, \: {>} \in \Sigma_{-1})
		\\
	S &\to c
		&& (c \in \Sigma_0)
		\\
	S &\to \epsilon
\end{align*}
An \emph{elementary well-nested string}
is a well-nested string that is either a single symbol,
or a well-nested string enclosed in a pair of matching brackets:
$\ewn=\Sigma_0 \cup \Sigma_{+1} \wn \Sigma_{-1}$.

An infinite string $\alpha \in \Sigma^\omega$ is called \emph{well-nested},
if it is a concatenation of infinitely many elementary well-nested finite strings.
\begin{equation*}
	\wnomega = \ewn^\omega = \set{x_1 x_2 \ldots x_i \ldots}{x_i \in \ewn \text{ for all } i \geqslant 1}
\end{equation*}
Equivalently, an infinite string $\alpha$ is in $\wnomega$
if it has infinitely many well-nested prefixes.
Note that if the above definition had $x_i \in \wn$,
then it would also include all finite strings.

Input-driven automata on finite strings~\cite{Mehlhorn}
are pushdown automata with the following restriction on their use of the stack.
If the input symbol is a left bracket from $\Sigma_{+1}$,
then the automaton always pushes one symbol onto the stack.
For a right bracket from $\Sigma_{-1}$,
the automaton must pop one symbol.
Finally, for a neutral symbol in $\Sigma_0$,
the automaton may not access the stack at all.
The acceptance of a finite string
is determined by the state reached in the end of the computation,
whether it belongs to a set of accepting states $F \subseteq Q$.

The definition was extended to infinite strings
by adopting the notions of acceptance from finite $\omega$-automata.

\begin{definition}[Alur and Madhusudan~\cite{AlurMadhusudan}]\label{definition_idpda}
A nondeterministic input-driven pushdown automaton on infinite strings ($\omega$-NIDPDA)
consists of the following components.
\begin{itemize}
\item
	The input alphabet $\Sigma$
	is a finite set split into three disjoint classes:
	$\Sigma=\Sigma_{+1} \cup \Sigma_{-1} \cup \Sigma_0$.
\item
	The set of (internal) states $Q$
	is a finite set,
	with an initial state $q_0 \in Q$.
\item
	The stack alphabet $\Gamma$
	is a finite set,
	and a special symbol $\bot \notin \Gamma$
	is used to denote an empty stack.
\item
	For each neutral symbol $c \in \Sigma_0$,
	the transitions by this symbol
	are described by a function $\delta_c \colon Q \to 2^Q$.
\item
	For each left bracket symbol ${<} \in \Sigma_{+1}$,
	the behaviour of the automaton
	is described by a function $\delta_< \colon Q \to 2^{Q \times \Gamma}$,
	which, for a given current state, provides
	possible actions of the form
	``push a given stack symbol and enter a given state''.
\item
	For every right bracket symbol ${>} \in \Sigma_{-1}$,
	there is a function $\delta_> \colon Q \times \Gamma \to 2^Q$
	specifying possible next states,
	assuming that the given stack symbol is popped from the stack.
\item
	Acceptance is determined either by a B\"uchi condition,
	with a set of accepting states $F \subseteq Q$,
	or by a Muller condition,
	with a set of subsets $\mathcal{F} \subseteq 2^Q$.
\end{itemize}
A triple $(q, \alpha, x)$,
in which $q \in Q$ is the current state,
$\alpha \in \Sigma^\omega$ is the remaining input
and $x \in \Gamma^*$ is the stack contents,
is called a \emph{configuration}.
For each configuration, the next configuration is defined as follows.
\begin{align*}
	(q, c\alpha, x) &\vdash (r, \alpha, x)
		&& (q \in Q, \: c \in \Sigma_0, \: r \in \delta_c(q))
		\\
	(q, {<}\alpha, x) &\vdash (r, \alpha, sx),
		&& (q \in Q, \: {<} \in \Sigma_{+1}, \: (r, s) \in \delta_{<}(q))
		\\
	(q, {>}\alpha, sx) &\vdash (r, \alpha, x)
		&& (q \in Q, \: {>} \in \Sigma_{-1}, \: s \in \Gamma, \: r \in \delta_{>}(q, s))
\end{align*}

A \emph{run} on a well-nested string $\alpha \in \Sigma^\omega$
is any sequence of configurations $\rho = C_0, C_1, \ldots, C_i, \ldots$,
with $C_0=(q_0, \alpha, \epsilon)$
and $C_{i-1} \vdash C_i$ for all $i \geqslant 1$.
The set of states that occur in a run infinitely many times
is denoted by $\inf(\rho)$.

Under a B\"uchi acceptance condition,
an infinite string $\alpha$ is accepted,
if there exists a run
with at least one of the accepting states repeated infinitely often.
\begin{align*}
	L(\mathcal{B})
		&=
	\set{\alpha}{\exists \rho: \: \rho \text{ is a run on } \alpha, \: \inf(\rho) \cap F \neq \emptyset}
\intertext
Under a Muller acceptance condition,
the set of states repeated infinitely often
must be among the specified subsets.
}
	L(\mathcal{M})
		&=
	\set{\alpha}{\exists \rho: \: \rho \text{ is a run on } \alpha, \: \inf(\rho) \in \mathcal{F}}
\end{align*}
An automaton is deterministic,
if the cardinality of $\delta_c(q)$, $\delta_{<}(q)$ and $\delta_{>}(q, s)$
is at most 1 for any choice of arguments.
\end{definition}

Actually, the definition by Alur and Madhusudan~\cite{AlurMadhusudan}
further allows ill-nested infinite strings:
on unmatched right brackets,
it uses special transitions by an empty stack,
in which the automaton detects the stack emptiness
and leaves the stack empty;
on unmatched left brackets,
an automaton pushes symbols that shall never be popped.

In the case of finite strings,
the extension to ill-nested strings
does not affect the principal properties,
such as determinization and decidability.
For infinite strings, as it turns out, this detail makes a difference.
In the rest of this paper, all infinite strings are assumed to be well-nested.

\section{A characterization of $\omega$-input-driven languages of well-nested strings}\label{section_characterization}

The results of this paper are based on a characterization of $\omega$-input-driven languages
by $\omega$-regular languages,
which allows parts of the classical theory of $\omega$-regular languages
to be lifted to the case of well-nested infinite strings of brackets.

If an $\omega$-input-driven automaton $\mathcal{M}$ operates on a well-nested string,
this means that it reaches the bottom level of brackets infinitely often,
reading a well-nested string $x \in \ewn$ between every two consecutive visits.
The idea is to replace this string by a single symbol of a new alphabet,
which represents the essential information
on all possible computations of $\mathcal{M}$ on $x$.
Then the language of such encoded strings
shall be proved to be $\omega$-regular.

\begin{lemma}\label{muller_idpda_by_muller_regular_characterization_lemma}
Let $L \subseteq \wnomega$ be a language of well-nested infinite strings
over an alphabet $\Sigma=\Sigma_{+1} \cup \Sigma_{-1} \cup \Sigma_0$
recognized by an $n$-state deterministic input-driven Muller automaton.
Then there exists a finite set of pairwise disjoint languages,
$K_1, \ldots, K_m \subseteq \ewn$,
with $m \leqslant 2^{n^2} \cdot n^n$,
each recognized by an input-driven automaton,
and a regular $\omega$-language $M$ over the alphabet $\Omega=\{a_1, \ldots, a_m\}$
such that $L$ has the following representation.
\begin{equation*}
	L = \set{x_1 x_2 \ldots x_j \ldots}{x_j \in K_{i_j} \text{ for each } j \geqslant 0, \:
		a_{i_1} a_{i_2} \ldots a_{i_j} \ldots \in M}
\end{equation*}
The language $M$ is recognized
by a deterministic Muller automaton with $n \cdot 2^n$ states.
\end{lemma}
\begin{proof}
Let $\mathcal{M}=(\Sigma, Q, \Gamma, q_0, \langle\delta_\sigma\rangle_{\sigma \in \Sigma}, \mathcal{F})$
be a deterministic input-driven Muller automaton
that processes a string $x_1 x_2 \ldots x_\ell \ldots$.
The goal is to construct a deterministic finite Muller automaton $\mathcal{A}$
operating on a corresponding string $a^{(1)} a^{(2)} \ldots a^{(\ell)} \ldots$,
so that, after reading each prefix $a^{(1)} a^{(2)} \ldots a^{(\ell)}$,
the automaton $\mathcal{A}$ would know
the state reached by $\mathcal{M}$ after reading the prefix $x_1 x_2 \ldots x_\ell$,
as well as the set of all states passed through by $\mathcal{M}$
while reading the most recent well-nested substring $x_\ell$.
With this information, $\mathcal{A}$ can use its Muller acceptance condition
to simulate the Muller acceptance condition of $\mathcal{M}$.

The data to be computed for each well-nested substring $x \in \ewn$
is represented by a function $f_x \colon Q \to Q \times 2^Q$,
which maps a state $p$, in which $\mathcal{M}$ begins reading $x$,
to a pair $(q, S)$,
where $q$ is the state in which $\mathcal{M}$ finishes reading $q$,
and $S$ is the set of all states visited by $\mathcal{M}$ in this computation.
In the context of this proof, $f$ represents \emph{the behaviour of $\mathcal{M}$ on $x$.}

There are $m=2^{n^2} \cdot n^n$ different behaviour functions.
For each behaviour function $f$,
let $K_f \subseteq \ewn$ be the set of all strings,
on which $\mathcal{M}$ demonstrates the behaviour $f$.
A new Muller finite automaton promised in the statement of the lemma
shall be defined over an alphabet
$\Omega=\set{a_f}{f \colon Q \to Q \times 2^Q}$,
so that each symbol $a_f$
stands for any string $x \in K_f$.

Let $\rho$ be the run of $\mathcal{M}$ on $x_1 x_2 \ldots x_j \ldots$,
and denote by $q_{j,\ell}$ the state entered after reading $\ell$ first symbols of $x_j$.
\begin{equation*}
	\rho
		=
	\underbrace{q_{1,0}, q_{1,1}, \ldots, q_{1, |x_1|-1}}_{\text{reading } x_1},
	\underbrace{q_{2,0}, q_{2,1}, \ldots, q_{2, |x_2|-1}}_{\text{reading } x_2},
	q_{3, 1}, \ldots,
	\underbrace{q_{j,0}, q_{j,1}, \ldots, q_{q,|x_j|-1}}_{\text{reading } x_j},
	\ldots
\end{equation*}
For each substring $x_j$,
let $f_j=f_{x_j}$ be the behaviour function of $\mathcal{M}$ on this substring.
Then each $f_j$, applied to $q_{j,0}$,
provides the following data on the computation on $x_j$.
\begin{equation*}
	f_j(q_{j, 0})=\big(q_{j+1, 0}, \{q_{j,0}, q_{j,1}, \ldots, q_{j,|x_j|-1}, q_{j+1, 0}\}\big)
\end{equation*}

\begin{claim}\label{muller_idpda_by_muller_regular_characterization_lemma__acceptance_condition_claim}
A state $q$ occurs in the sequence $\{q_{j,\ell}\}$ infinitely many times
	if and only if
there exists a pair $(p, S)$, with $q \in S$,
which occurs as $\big(q_{j+1, 0}, \{q_{j,0}, q_{j,1}, \ldots, q_{j,|x_j|-1}, q_{j+1, 0}\}$
for infinitely many values of $j$.
\end{claim}
\begin{proof}
\begin{description}
\item[\textcircled{$\Rightarrow$}]
Assume that $q$ occurs in the run infinitely often.
Each time it occurs within some block $x_j$,
the corresponding pair
$(p, S)=\big(q_{j+1, 0}, \{q_{j,0}, q_{j,1}, \ldots, q_{j,|x_j|-1}, q_{j+1, 0}\}$
includes $q$ in the second component.
Since there are only finitely many pairs $(p, S)$,
at least one pair with the property $q \in S$ must occur infinitely many times.

\item[\textcircled{$\Leftarrow$}]
Let such a pair $(p, S)$, with $q \in S$,
occur as
$(p, S)=\big(q_{j+1, 0}, \{q_{j,0}, q_{j,1}, \ldots, q_{j,|x_j|-1}, q_{j+1, 0}\}$
for infinitely many $j$.
Every such occurrence indicates an occurrence of $q$ among the states $q_{j,\ell}$.
Then $q$ occurs in $\rho$ infinitely many times.
\end{description}
\end{proof}

Now the task is to simulate a run $\rho$ of $\mathcal{M}$ on $x_1 x_2 \ldots x_j \ldots$
by an automaton $\mathcal{M}'$
operating on the string $a_{f_1} a_{f_2} \ldots a_{f_j} \ldots$,
with every substring $x \in \ewn$ represented by a symbol $a_{f_x}$.

The desired Muller finite automaton $\mathcal{M}'$
is defined over the alphabet $\Omega=\set{a_f}{f \colon Q \to Q \times 2^Q}$
as follows.
Its states are pairs $(q, S)$,
where $q$ shall be the state in the corresponding run of $\mathcal{M}$ at this point,
whereas $S$ shall be the set of states visited by $\mathcal{M}$
on the last well-nested substring.
\begin{align*}
	P &= \set{(q, S)}{q \in Q, \: S \subseteq Q}
\intertext
A transition by $a_f$ applies the behaviour function $f$ to $q$
to determine the next state of $\mathcal{M}$,
as well as the set of states visited on the next well-nested substring.
}
	\Delta((q, S), a_f) &= f(q)
\end{align*}

\begin{claim}
In the run $\rho'$ of $\mathcal{M}'$ on $a_{f_1} a_{f_2} \ldots a_{f_j} \ldots$,
the state reached after reading each $a_{f_j}$
is $\big(q_{j+1, 0}, \{q_{j,0}, q_{j,1}, \ldots, q_{j,|x_j|-1}, q_{j+1, 0}\}\big)$.
\end{claim}

Putting together this property
and Claim~\ref{muller_idpda_by_muller_regular_characterization_lemma__acceptance_condition_claim},
a state $q$ occurs in $\rho$ infinitely often
	if and only if
there exists a pair $(p, S)$, with $q \in S$,
which occurs in $\rho'$ infinitely often.
\begin{equation*}
	\inf \rho = \bigcup_{(p, S) \in \inf \rho'} S
\end{equation*}

Then the Muller acceptance condition for $\mathcal{M'}$
is defined by putting together all states of $\mathcal{M}$
visited infinitely often and checking whether this set is in $\mathcal{F}$.
\begin{equation*}
	\mathcal{G} = \setbig{R}{R \subseteq Q \times 2^Q, \: \bigcup_{(q, S) \in R} S \in \mathcal{F}}
\end{equation*}

\begin{claim}
Let $x_1 x_2 \ldots x_j \ldots$, with $x_j \in \ewn$,
be an infinite string,
and let $f_j \colon Q \to Q \times 2^Q$ be the behaviour function on each $x_j$.
Then $\mathcal{M}$ accepts $x_1 x_2 \ldots x_j \ldots$
	if and only if
$\mathcal{M}'$ accepts $a_{f_1} a_{f_2} \ldots a_{f_j} \ldots$.
\end{claim}

In order to complete the proof of the lemma,
it remains to prove that
each language $K_f \subseteq \ewn$ of finite strings
is recognized by an input-driven automaton.

\begin{claim}
There exists a deterministic input-driven automaton $\mathcal{A}$
with the set of states
$Q'=\{q'_0\} \cup \set{(f, b)}{f \colon Q \to Q \times 2^Q, \: b \in \{0, 1\}}$,
which, upon reading a well-nested string $x \in \ewn$,
enters a state $(f, 0)$,
where $f \colon Q \to Q \times 2^Q$
is the behaviour function of $\mathcal{M}$ on $x$.
\end{claim}
\begin{proof}
Besides computing the behaviour,
the automaton also has to verify that the input string is in $\ewn$,
and for that reason it has to remember whether it is currently inside any brackets.
In a state $(f, b)$,
the first component is the desired behaviour function
for the longest well-nested suffix $v \in \ewn$,
whereas the second component indicates
whether the automaton is currently at the outer level of brackets ($0$) or not ($1$).
No transitions in a state of the form $(f, 0)$ are possible.
The stack alphabet is
$\Gamma'=\set{(f, <)}{f \colon Q \to Q \times 2^Q, \: {<} \in \Sigma_{+1}} \cup \Sigma_{+1}$,
where a symbol of the form $(f, <)$ is pushed while inside the brackets,
whereas on the outer level of brackets, the automaton pushes just a left bracket.

Let $f_\epsilon \colon Q \to Q \times 2^Q$
be the behaviour function on the empty string,
defined by $f(q)=(q, \{q\})$ for each $q \in Q$.
For each neutral symbol $c \in \Sigma_0$,
the behaviour on this symbol, $f_c \colon Q \to Q \times 2^Q$,
is defined by $f(q)=(\delta_c(q), \{q, \delta_c(q)\})$.
If $f$ is the behaviour function on $u \in \wn$,
and $g$ is the behaviour function on $v \in \wn$,
then the behaviour function on $uv$
is the following kind of function composition
that accummulates the states visited.
\begin{align*}
	(g \circ f)(p)=(r, \: S \cup T),
		&& \text{ where } f(p)=(q, S), \; g(q)=(r, T)
\end{align*}

The initial state of $\mathcal{A}$ is $\widehat{q}_0$;
upon reading a neutral symbol $c \in \Sigma_0$ in the initial state,
the automaton enters the state corresponding to the desired behaviour on $c$.
\begin{equation*}
	\delta'_c(q'_0)=(f_c, 0)
\end{equation*}
If the automaton reads a left bracket ${<} \in \Sigma_{+1}$ in the initial state,
it begins constructing a new behaviour function on the inner level,
remembering the bracket in the stack.
\begin{equation*}
	\delta'_<\big((f, 0)\big)=\big((f_\epsilon, 1), {<}\big)
\end{equation*}
When a matching right bracket ${>} \in \Sigma_{-1}$ is read,
the automaton pops the left bracket ${<} \in \Sigma_{+1}$ from the stack,
and therefore knows that it is returning to the outer level of brackets.
Then it merges the computed behaviour on the substring inside the brackets
with the actions made on the outer pair of brackets.
\begin{align*}
	\delta'_>\big((f, 1), {<}\big)=(f', 0),
		&& \text{ where } f'(p)=(r, S \cup \{p, r\}), \:
		\delta_<(p)=(q, s), \: r=\delta_>(f(q), s)
\end{align*}
Inside the brackets, upon reading a neutral symbol $c \in \Sigma_0$,
behaviour functions are composed as follows.
\begin{equation*}
	\delta'_c\big((f, 1)\big)=f_c \circ f
\end{equation*}
When a left bracket ${<} \in \Sigma_{+1}$ is encountered inside the brackets,
a new simulation is started inside,
but the current behaviour function is stored in the stack.
\begin{equation*}
	\delta'_<\big((f, 1)\big)=\big((f_\epsilon, 1), (f, {<})\big)
\end{equation*}
Upon reading a matching right bracket ${>} \in \Sigma_{-1}$,
the two simulations are composed.
\begin{align*}
	\delta'_>\big((g, 1), (f, {<})\big)=(h \circ f, \: 1),
		&& \text{ where } h(p)=(r, S \cup \{p, r\}), \:
		\delta_<(p)=(q, s), \: r=\delta_>(f(q), s)
\end{align*}
The transitions of the automaton $\mathcal{A}$ have been defined.
For each behaviour function $f \colon Q \to Q \times 2^Q$,
setting the set of accepting states to be $F_f=\{(f, 0)\}$
yields the desired IDPDA recognizing the language $K_f$
of all strings in $\ewn$, on which $\mathcal{M}$ behaves as specified by $f$.
\end{proof}

This completes the proof of the lemma.
\end{proof}

The same characterization as in Lemma~\ref{muller_idpda_by_muller_regular_characterization_lemma}
also extends to nondeterministic input-driven Muller automata,
at the expense in using exponentially more types of well-nested strings.

\begin{lemma}\label{muller_nidpda_by_muller_regular_characterization_lemma}
Let $L \subseteq \wnomega$ be a language of well-nested infinite strings
over an alphabet $\Sigma=\Sigma_{+1} \cup \Sigma_{-1} \cup \Sigma_0$
recognized by an $n$-state nondeterministic input-driven Muller automaton.
Then there exists a finite set of pairwise disjoint languages,
$K_1, \ldots, K_m \subseteq \ewn$,
with $m \leqslant 2^{n^2 \cdot 2^n}$,
each recognized by an input-driven automaton,
and a regular $\omega$-language $M$ over the alphabet $\Omega=\{a_1, \ldots, a_m\}$
such that $L$ has the following representation.
\begin{equation*}
	L = \set{x_1 x_2 \ldots x_j \ldots}{x_j \in K_{i_j} \text{ for each } j \geqslant 0, \:
		a_{i_1} a_{i_2} \ldots a_{i_j} \ldots \in M}
\end{equation*}
The language $M$ is recognized
by a nondeterministic Muller automaton with $n \cdot 2^n$ states.
\end{lemma}
\begin{proof}[Sketch of a proof.]
The construction differs from that in Lemma~\ref{muller_idpda_by_muller_regular_characterization_lemma}
in two respects.

First, since the original input-driven Muller automaton is now nondeterministic,
its behaviour on a well-nested substring $x \in \ewn$
can no longer be characterized
by an object as simple as a function $f \colon Q \to Q \times 2^Q$
describing the computation on $x$ beginning in each state.
For a nondeterministic automaton, a computation on $x$
may begin in any state $p$, pass through any set of states $S \subseteq Q$,
and finish reading $x$ in any state $q$:
this is a triple $(p, S, q)$.
The automaton's behaviour on $x$
is a \emph{set of possible triples},
or a \emph{ternary relation} $R \subseteq Q \times 2^Q \times Q$.
This accounts for the increase in the alphabet size $m$.

Second, besides the nondeterminism exercised while reading a substring $x$,
the nondeterministic input-driven Muller automaton
can also behave nondeterministically
when proceeding from one well-nested substring to another.
This nondeterminism is directly simulated
by the nondeterministic finite Muller automaton constructed in the lemma.
\end{proof}

The representation of well-nested $\omega$-input-driven languages
by $\omega$-regular languages
given in Lemmata~\ref{muller_idpda_by_muller_regular_characterization_lemma}--\ref{muller_nidpda_by_muller_regular_characterization_lemma}
has the following converse representation.

\begin{lemma}\label{muller_regular_characterization_to_muller_didpda_lemma}
Let $K_1, \ldots, K_m \subseteq \ewn$ be pairwise disjoint languages,
each recognized by an input-driven automaton,
and let $M$ be a regular $\omega$-language over the alphabet $\Omega=\{a_1, \ldots, a_m\}$.
Then, the following language is recognized by a deterministic input-driven Muller automaton.
\begin{equation*}
	L = \set{x_1 x_2 \ldots x_j \ldots}{x_j \in K_{i_j} \text{ for each } j \geqslant 0, \:
		a_{i_1} a_{i_2} \ldots a_{i_j} \ldots \in M}
\end{equation*}
\end{lemma}
\begin{proof}
Let each $K_i$ be recognized by a DIDPDA
$\mathcal{A}_i=(\Sigma, Q_i, \Gamma_i, q^{(i)}_0, \langle\delta^{(i)}\rangle_{c \in \Sigma}, F_i)$,
and let $\mathcal{M}=(\Omega, P, p_0, \eta, \mathcal{F})$
be a deterministic Muller automaton recognizing $M$.
A new deterministic input-driven Muller automaton $\mathcal{M}'$
uses the following set of states.
\begin{align*}
	Q'
		&=
	P
	\cup
	\underbrace{(Q_1 \times \ldots \times Q_m)}_{\text{used inside brackets}}
	\cup
	\{p_{dead}\}
	\\
	\Gamma'
		&=
	(P \times \Sigma_{+1})
	\cup
	(\Gamma_1 \times \ldots \times \Gamma_m)
\end{align*}
The states from $P$ are used outside all brackets.
The initial state is $p_0$.
Whenever the automaton reads a neutral symbol $c \in \Sigma_0$ at the outer level of brackets,
it simulates $\mathcal{M}$.
\begin{equation*}
	\delta'_c(p) = \eta_c(p)
\end{equation*}
If a left bracket ${<} \in \Sigma_{+1}$ is read at the outer level of brackets,
the new automaton begins simulating all $m$ input-driven automata
on the substring beginning with this bracket,
whereas the bracket is pushed onto the stack
along with the current state $p \in P$.
\begin{align*}
	\delta'_<(p) &= \big(\delta_<(q^{(1)}_0), \ldots, \delta_<(q^{(m)}_0)\big)
		\\
	\gamma'_<(p) &= (p, {<})
\end{align*}
Inside the brackets, the $m$ input-driven automata are simulated independently of each other.
\begin{align*}
	\delta'_c\big(q^{(1)}, \ldots, q^{(m)}\big) &= \big(\delta_c(q^{(1)}), \ldots, \delta_c(q^{(m)})\big)
		\\
	\delta'_<\big(q^{(1)}, \ldots, q^{(m)}\big) &= \big(\delta_<(q^{(1)}), \ldots, \delta_<(q^{(m)})\big)
		\\
	\gamma'_<\big(q^{(1)}, \ldots, q^{(m)}\big) &= \big(\gamma_<(q^{(1)}), \ldots, \gamma_<(q^{(m)})\big)
		\\
	\delta'_>\big((q^{(1)}, \ldots, q^{(m)}), (s^{(1)}, \ldots, s^{(m)})\big) &=
		\big(\delta_>(q^{(1)}, s^{(1)}), \ldots, \delta_>(q^{(m)}, s^{(m)})\big)
\end{align*}
Eventually, a right bracket at the outer level is read,
and the new automaton pops a pair $(p, {<})$.
Let the current state of the automaton be $(q^{(1)}, \ldots, q^{(m)})$.
The matching left bracket ($<$) was read by the simulated automata
in the states $\delta_<(q^{(1)}_0), \ldots, \delta_<(q^{(m)}_0)$.
Then, after reading the right bracket ${>} \in \Sigma_{-1}$,
each $i$-th simulated automaton is in the state
$\widehat{q}^{(i)}=\delta_>(q^{(i)}, \gamma(q^{(i)}_0, {<}))$.
Since the languages $K_1, \ldots, K_m$ are pairwise disjoint,
at most one of these automata can be in an accepting state.
If the $i$-th automaton accepts,
this indicates that a well-nested string $x \in K_i$ has just been read,
and the simulated Muller automaton
accordingly makes the transition by the symbol $a_i$;
if none of the input-driven automata accept,
the new automaton's entire computation fails.
\begin{equation*}
	\delta'_>(p, {<}) = \begin{cases}
		\eta(p, a_i),
			& \text{if } \delta_>(q^{(i)}, \gamma(q^{(i)}_0, {<})) \in F_i
		\\
		p_{dead},
			& \text{if there is no such $i$}
	\end{cases}
\end{equation*}
The Muller acceptance conditions for the new automaton
are defined to check that the set of states in $P$
visited on the outer level of brackets infinitely often
is in the set $\mathcal{F}$,
whereas the states visited inside the brackets do not affect acceptance.
\begin{equation*}
	\mathcal{F}'=\set{F \subseteq Q'}{F \cap P \in \mathcal{F}}
\end{equation*}
\end{proof}

A variant of the same construction produces an automaton
with a B\"uchi acceptance condition.

\begin{lemma}\label{buchi_regular_characterization_to_buchi_nidpda_lemma}
Let $K_1, \ldots, K_m \subseteq \ewn$ be pairwise disjoint languages,
each recognized by an input-driven automaton,
and let $M$ be a regular $\omega$-language over the alphabet $\Omega=\{a_1, \ldots, a_m\}$.
Then, the following language is recognized by a nondeterministic input-driven B\"uchi automaton.
\begin{equation*}
	L = \set{x_1 x_2 \ldots x_j \ldots}{x_j \in K_{i_j} \text{ for each } j \geqslant 0, \:
		a_{i_1} a_{i_2} \ldots a_{i_j} \ldots \in M}
\end{equation*}
\end{lemma}
\begin{proof}[Sketch of a proof.]
This time, the proof begins with taking
a \emph{nondeterministic B\"uchi} automaton
$\mathcal{B}=(\Omega, P, p_0, \eta, F)$
recognizing $M$.
As in Lemma~\ref{muller_regular_characterization_to_muller_didpda_lemma},
let $\mathcal{A}_i=(\Sigma, Q_i, \Gamma_i, q^{(i)}_0, \langle\delta^{(i)}\rangle_{c \in \Sigma}, F_i)$,
be an IDPDA recognizing $K_i$.

A nondeterministic input-driven B\"uchi automaton $\mathcal{B}'$
uses the same states as $\mathcal{M}'$
in Lemma~\ref{muller_regular_characterization_to_muller_didpda_lemma},
and has basically the same transitions as $\mathcal{M}'$,
except for using nondeterminism on the outer level of brackets
whenever so does the automaton $\mathcal{B}$ being simulated.
Its set of accepting states under the B\"uchi acceptance condition
is the same as in $\mathcal{B}$.
\end{proof}

Putting the above results together
completes the characterization of well-nested $\omega$-input-driven languages
by $\omega$-regular languages,
and also establishes the equivalence
of several kinds of input-driven automata
on well-nested infinite strings.

\begin{theorem}\label{main_theorem}
Let $\Sigma=\Sigma_{+1} \cup \Sigma_{-1} \cup \Sigma_0$ be an alphabet.
Let $L \subseteq \Sigma^\omega$ be a language of infinite strings
and assume automata operating only on well-nested infinite strings.
Then the following three conditions are equivalent:
\begin{enumerate}
\item\label{main_theorem_detM}
	$L$ is recognized by a deterministic input-driven Muller automaton;
\item\label{main_theorem_nondetM}
	$L$ is recognized by a nondeterministic input-driven Muller automaton;
\item\label{main_theorem_nondetB}
	$L$ is recognized by a nondeterministic input-driven B\"uchi automaton;
\item\label{main_theorem_condition}
	there is a finite set of pairwise disjoint languages,
	$K_1, \ldots, K_m \subseteq \Sigma_0 \cup \Sigma_{+1} \mathrm{wn}(\Sigma) \Sigma_{-1}$,
	each recognized by an input-driven automaton,
	and a regular $\omega$-language $M$ over the alphabet $\Omega=\{a_1, \ldots, a_m\}$
	such that $L$ has the following representation.
	\begin{equation*}
		L = \set{x_1 x_2 \ldots x_j \ldots}{a_{i_1} a_{i_2} \ldots a_{i_j} \ldots \in M,
			\; x_j \in K_{i_j} \text{ for each } j \geqslant 0}
	\end{equation*}
\end{enumerate}
\end{theorem}
\begin{proof}
\textbf{($\ref{main_theorem_detM} \Rightarrow \ref{main_theorem_nondetM}$)}
Trivial.

\textbf{($\ref{main_theorem_nondetB} \Rightarrow \ref{main_theorem_nondetM}$)}
Trivial.

\textbf{($\ref{main_theorem_nondetM} \Rightarrow \ref{main_theorem_condition}$)}
By Lemma~\ref{muller_nidpda_by_muller_regular_characterization_lemma}.

\textbf{($\ref{main_theorem_condition} \Rightarrow \ref{main_theorem_detM}$)}
By Lemma~\ref{muller_regular_characterization_to_muller_didpda_lemma}.

\textbf{($\ref{main_theorem_condition} \Rightarrow \ref{main_theorem_nondetB}$)}
By Lemma~\ref{buchi_regular_characterization_to_buchi_nidpda_lemma}.
\end{proof}

The exact complexity of the transformation between models
is left as a question for future research.

\section{On the Wadge-Wagner hierarchy}\label{section_wadge}

Here we apply the results of Section~\ref{section_characterization}
to relate the Wadge degrees of IDPDA-recognisable languages in $\wnomega$ (w.r.t. the topology induced by the Cantor topology on $\Sigma^\omega$)
to those of regular $\omega$-languages.

Recall that for subsets $L,M\subseteq X$ of a topological space $X$,
the subset $L$ is {\em Wadge reducible} to $M$ (denoted by $L\leq^X_WM$)
if $L=f^{-1}(M)$ for some continuous function $f$ on $X$.
The sets $L,M$ are {\em Wadge equivalent} ($L\equiv^X_WM$)
if $L\leq^X_WM$ and $M\leq^X_WL$.
The equivalence classes under the Wadge equivalence
are known as {\em Wadge degrees} in $X$. More generally, one can define Wadge reducibility
between subsets $L\subseteq X$ and $M\subseteq Y$
of different topological spaces $X,Y$ as follows:
$L\leq_WM$, if $L=f^{-1}(M)$ for some continuous function $f \colon X \to Y$. Recall that the {\em Borel sets} in $X$ are generated from the open sets by repeated applications of complement and countable intersection. The Borel sets are organised in the Borel hierarchy; in particular, the $\mathbf{\Pi}_2$-sets in $X$ are the countable intersections of Boolean combinations of open sets.

The structure of Wadge degrees of Borel sets was first introduced and studied in \cite{wad} for the Baire space $X=\omega^\omega$ of infinite words over a countable alphabet. A remarkable fact is that this structure is very simple (almost well ordered) which leads to an elegant topological classification of the Borel sets. With minor modifications, the results for the Baire space also hold for the Cantor space $X=\Sigma^\omega$ (the open sets for this space are sets of the form $U\cdot\Sigma^\omega$, $U\subseteq\Sigma^*$). This is of interest for theoretical computer science because
one can consider Wadge degrees of $\omega$-languages over $\Sigma$
recognized by different kinds of automata and obtain topological classifications of the corresponding $\omega$-languages.

This direction was initiated by Wagner~\cite{wag} who characterised the structure $(\mathcal{R}_\Sigma;\leq_W)$ of Wadge degrees of regular $\omega$-languages over $\Sigma$
now known as the \emph{Wagner hierarchy}.
This result also holds for the structure $(\mathcal{R};\leq_W)$
of Wadge degrees of regular $\omega$-languages
over arbitrary finite alphabets: for any finite non-unary alphabet $\Omega$ we have $(\mathcal{R};\leq_W)\simeq(\mathcal{R}_\Omega;\leq_W)$,
where the relation $\simeq$ between preorders
means isomorphism of the corresponding quotient-posets.

Later, Wadge degrees of several important classes of $\omega$-languages were investigated. It was shown, in particular, that Wadge degrees of push down $\omega$-languages are much richer than those of regular $\omega$-languages (see e.g. \cite{dup,fin} and references therein).
In the context of our paper, a natural question is to characterise the structure $(\omega\textrm{-IDPDA}(\Sigma);\leq_W)$ of Wadge degrees of languages recognized by input-driven automata.
A theorem by L\"oding et al.~\cite[Thm.~6]{LoedingMadhusudanSerre}
implies that this structure is larger than $(\mathcal{R};\leq_W)$,
and that $(\mathcal{R};\leq_W)\not\simeq(\omega\textrm{-IDPDA}(\Sigma);\leq_W)$. We postpone the discussion of  the structure $(\omega\textrm{-IDPDA}(\Sigma);\leq_W)$  till a next publication because it requires  techniques different from those we used in this paper.

Here, we formulate some immediate corollaries of the results of Section~\ref{section_characterization} to the relevant structure $(\wnID;\leq_W^X)$, where $\wnID$ is the class of languages of well-nested $\omega$-words recognised by the IDPDA, and $\leq_W^X$ is the Wadge reducibility in the space $X=\wnomega$ (considered as a subspace of $\Sigma^\omega$).
Namely, we show that $(\mathcal{R};\leq_W)\simeq(\wnID;\leq_W^X)$,
for any non-unary alphabet $\Sigma$. Note that the structure $(\wnID;\leq_W^X)$ is different from $(\wnID;\leq_W)$ where $\leq_W$ is the Wadge reeducibility on $\Sigma^\omega$. The Wadge reducibility in ``natural'' spaces was studied by several authors (see e.g. \cite{mss15,du20} and references therein). We start with some lemmas.

\begin{lemma}\label{lem0}
The set $\wnomega$ is a $\mathbf{\Pi}_2$-subset of $\Sigma^\omega$ homeomorphic to the Baire space.
 \end{lemma}

\begin{proof}
Considering $\ewn$ as a countable alphabet, we may think that $\ewn^\omega$ is the Baire space. By the remarks in the beginning of Section \ref{idomega}, the infinite concatenation $h:\ewn^\omega\to\Sigma^\omega$ is a bijection between $\ewn^\omega$ and $\wnomega$. Comparing the topologies on $\ewn^\omega$ and on $\Sigma^\omega$ we see that $h$ is a homeomorphism between $\ewn^\omega$ and the subspace $\wnomega$ of $\Sigma^\omega$.

It remains to show that $\wnomega$ is a $\mathbf{\Pi}_2$-subset of $\Sigma^\omega$. This immediately follows from the obvious remark that, for each $\alpha\in\Sigma^\omega$, the condition $\alpha\in\wnomega$ is equivalent to $\forall i\exists u\in \wn(\alpha[i]\sqsubseteq u\sqsubseteq\alpha)$, where $\alpha[i]$ is the prefix of $\alpha$ of length $i$ and $\sqsubseteq$ is the prefix relation.
 \end{proof}

\begin{lemma}\label{lem1}
For any $L\in\wnID$
there exists a regular $\omega$-language $M$ over a finite alphabet $\Omega=\{a_1, \ldots, a_m\}$
such that $L\equiv_WM$.
\end{lemma}
\begin{proof}
Let $K_1, \ldots, K_m$, $\Omega=\{a_1, \ldots, a_m\}$, and $M$
be as in Lemma~\ref{muller_idpda_by_muller_regular_characterization_lemma}.
Without loss of generality, one can assume that every $K_i$ is non-empty
(otherwise, it is omitted from the list)
and that $K_1\cup\cdots\cup K_m=\ewn$
(otherwise, the language $K_{m+1}=\ewn\setminus(K_1\cup\cdots\cup K_m)$ is added to the list,
and the letter $a_{m+1}$ is added to $\Omega$).

Define $f \colon \wnomega\to \Omega^\omega$ by $f(x_1x_2\cdots)=a_{i_1} a_{i_2} \cdots$,
where, for each $j\geq1$, $i_j$ is the unique element of $\{1,\ldots,m\}$ with $x_j\in K_{i_j}$.
Then $f$ is continuous and $L=f^{-1}(M)$, so $L\leq_WM$ via $f$.
Define $g \colon \Omega^\omega\to\wnomega$ by $g(a_{i_1} a_{i_2} \cdots)=x_{i_1} x_{i_2} \cdots$,
where, for each $j\in\{1,\ldots,m\}$, $x_j$ is a fixed element of $K_j$.
Then $g$ is continuous and $M=f^{-1}(L)$, so $M\leq_WL$ via $g$. Therefore, $M\equiv_WL$.
 \end{proof}

\begin{lemma}\label{lem2}
Let $m\geq1$, $\Omega=\{a_1, \ldots, a_m\}$,
and let $\{K_1,\ldots,K_m\}$ be a partition of $\ewn$
into non-empty languages recognized by input-driven automata.
Then, for every regular $\omega$-language $M$ over $\Omega$,
there exists $L \in \wnID$ such that $L\equiv_WM$.
\end{lemma}
\begin{proof}
Let $f \colon \wnomega\to \Omega^\omega$ be as in the proof of Lemma~\ref{lem1}.
By Lemma~\ref{muller_regular_characterization_to_muller_didpda_lemma}, for the language
$L=f^{-1}(M)$ we have $L\equiv_WM$.
\end{proof}

\begin{theorem}\label{theor}
For any non-unary  $\Sigma=\Sigma_{+1} \cup \Sigma_{-1} \cup \Sigma_0$ we have:
$(\mathcal{R};\leq_W)\simeq(\wnID\leq^X_W)$.
 \end{theorem}
\begin{proof}
Associate with any $L\in\wnID$
a language $M\in\mathcal{R}$ as in Lemma~\ref{lem1},
so in particular $L\equiv_WM$.
Then $L\leq L'$ clearly implies $M\leq_WM'$ for all $L,L'\in\wnID$.

Now we show that for any $M\in\mathcal{R}$ there exists $L\in\wnID$
such that $L\equiv_WM$.
Let $\Omega=\{a_1, \ldots, a_m\}$ be a finite alphabet with $M\in\mathcal{R}_\Omega$.
Since $\Sigma$ is non-unary,
there is clearly a partition $\{K_1,\ldots,K_m\}$ of $\ewn$ into non-empty languages
recognized by input-driven automata. By the proof of Lemma~\ref{lem2}, we can take $L=f^{-1}(M)$.

Returning to the map $L\mapsto M$ from the beginning of the proof,
it remains to show that $M\leq_WM'$ implies $L\leq_WL'$.
Let $\Omega$ be any non-unary finite alphabet.
By remarks in the beginning of this section,
there are $M_1,M'_1\in\mathcal{R}_\Omega$ such that $M\equiv_WM_1$ and $M'\equiv_WM'_1$.
By the preceding paragraph, there exist $L_1,L'_1\in\wnID$
such that $L_1\equiv_WM_1$ and $L'_1\equiv_WM'_1$.
Since also $L\equiv_WL_1$ and $L'\equiv_WL'_1$, it follows that $L\leq_WL'$. Therefore, $L\mapsto M$ induces a desired isomorphism between the quotient-posets of $(\wnID\leq^X_W)$ and $(\mathcal{R};\leq_W)$.
 \end{proof}