%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[submission]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{75}
\addbibresource{75.bib}

\usepackage{tikz,url}


\usepackage{pgf}
\usetikzlibrary{arrows,automata}
\usepackage[latin1]{inputenc}
\usepackage{wrapfig}
%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{defn}{Definition}
\newtheorem{conj}{Conjecture}
\newtheorem{example}{Example}
\newtheorem{cor}{Corollary}

\def\O{\mathrm{O}}
\def\sgn{\operatorname{sgn}}
\def\diag{\operatorname{diag}}
\def\clap#1{\hbox to0pt{\hss#1\hss}}
\let\ideal\unlhd

\def\bigtimes{\mathop{\hbox{\Large$\times$}}}

\makeatletter
\def\testb#1{\testb@i#1,,\@nil}%
\def\testb@i#1,#2,#3\@nil{%
  \draw[->] (O) --++(#1);
  \ifx\relax#2\relax\else\testb@i#2,#3\@nil\fi}
\makeatother
\newcommand{\makediag}[1]{
    \coordinate (O) at (0,0); \coordinate (N) at (0,0.8);
    \coordinate (NE) at (0.8,0.8); \coordinate (E) at (0.8,0);
    \coordinate (SE) at (0.8,-0.8); \coordinate (S) at (0,-0.8);
    \coordinate (SW) at (-0.8,-0.8);\coordinate (W) at (-0.8,0);
    \coordinate (NW) at (-0.8,0.8); \coordinate (B1) at (1.2,1.2);
    \coordinate (B2) at (-1.2,-1.2);
    \testb{#1}
}
\newcommand{\diagr}[1]{
  \begin{tikzpicture}[baseline=-3pt,scale=0.3]\makediag{#1}\end{tikzpicture}
}

%% define your title in the usual way
\title{Inhomogeneous Restricted Lattice Walks}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Manfred Buchacher \and Manuel Kauers\thanks{Both authors were supported by the Austrian FWF grant F5004.}}

%% then use \addressmark to match authors to institutions here
\address{Institute for Algebra, Johannes Kepler University, Linz, Austria}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We consider inhomogeneous lattice walk models in a half-space and in the quarter plane.
  For the models in a half-space, we show by a generalization of the kernel method to
  linear systems of functional equations that their generating functions are always algebraic.
  For the models in the quarter plane, we have carried out an experimental classification of
  all models with small steps. We discovered many (apparently) D-finite cases for most of
  which we have no explanation yet.
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Functional Equations, Kernel Method, Formal Power Series, D-finiteness}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\let\set\mathbb


\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

Given a specific counting problem, it is often easy to write down a functional equation for the corresponding
generating function, but it can be quite hard to derive from it something interesting about its solution.
Counting problems for restricted lattice walks are a source of functional equations which are neither trivial nor hopeless,
and therefore interesting.
Using the kernel method, Banderier and Flajolet~\cite{banderier02} have shown that the generating functions for
lattice walks restricted to a half-space are always algebraic.
For walks restricted to the quarter plane, the functional equations are more intricate, and as a consequence, the
resulting generating functions come in more flavours. A systematic classification was initiated by Bousquet-M\'elou and Mishna~\cite{bousquet10} and
has since led to a substantial amount of literature, see~\cite{bostan17} and the references given there,
as well as \cite{bernardi17,dreyfus18} for some more recent developments.

Since the main questions raised in the paper of Bousquet-M\'elou and Mishna have been answered, the focus has shifted to
modified versions of the problem, including, for example, weighted steps~\cite{kauers15c,courtiel17}, longer
steps~\cite{melczer18}, higher dimensions~\cite{bostan16a,bacher16,bogosel18}, or interacting
boundaries~\cite{beaton18}. All these variations are homogeneous in the sense that the walks are formed from a fixed set
of admissible steps. Little is known about inhomogeneous models, e.g., lattice walk models where the set
of admissible steps may vary with the time and/or the position of the walk. Bousquet-M\'elou and Xin~\cite{bousquet06b}
have studied such a case. They analyzed a quarter plane model where the step set varies with the parity of the time.
Also D'Arco et al.~\cite{darco16} have studied an inhomogeneous case.
They determined the asymptotics for walks in the quarter plane where at position $(i,j)$, the next step is taken
from \diagr{W,N,S,E} if $i+j$ is even and from \diagr{W,N,S,E,NW,NE,SW,SE} if $i+j$ is odd.
In the present paper, we study such inhomogeneous models more systematically.

We consider half-space models and quarter plane models.
For the half-space, we show for a general class of inhomogeneities that the generating function is invariably algebraic.
Our proof is an adaption of an argument given by Bousquet-M\'elou and Jehanne~\cite{bousquet06} to the case of linear systems
of functional equations (\cref{sec:3}).
The statement also follows from a deep theorem of Popescu~\cite{popescu86} (see also Theorem~16 in~\cite{bousquet16}).
For regions defined by more than one restriction, we generalize the notion of dimension
introduced by Bostan et al.~\cite{bostan16a} to inhomogeneous models (\cref{sec:4a}).
For the quarter plane (\cref{sec:4}), we give an experimental classification for models with short steps and
two specific inhomogeneities. We recognize many generating functions as D-finite,
but in most cases we have no explanation for their D-finiteness.

% // inhomogeneous can mean a lot of things, e.g., restriction can be seen as special case of inhomogeneous

% // we consider ``linear'' inhomogeneity in combination with restriction to half-space and quarter plane

% // motivation: isolate the boundary between d-finite and non-d-finite

\vspace{-1ex}
\section{Inhomogeneous Lattice Walks in the Half-Space}\label{sec:2}

We consider walks in a half-space $\set Z_{\geq0}\times\set Z^{d-1}$ which start at some point $(i_0,\mathbf j_0)$ of the half-space,
consist of $n$ steps, and end at some point $(i,\mathbf j)$ of the half-space.
Restrictions are imposed on the steps the walks consist of.
For a \emph{homogeneous} model, there is a fixed finite set $\mathbf{S}\subseteq\set Z^d$, called
the step set, from which each step of the walk is taken.

For an \emph{inhomogeneous} model, the allowed steps are governed by a deterministic finite automaton.
A finite automaton is a directed multigraph $(\mathcal{Q}, \mathcal{E})$ whose (finitely many) edges are
labelled by letters of some alphabet.
The vertices $q\in\mathcal{Q}$ are called states.
One particular state $q_0\in\mathcal{Q}$ is called the initial state,
and there is a subset $\bar{\mathcal{Q}}\subseteq\mathcal{Q}$ of final states.
In our setting the edges are labelled by elements of~$\mathbb{Z}^d$.
To be deterministic means that for every pair $(q,\mathbf s)$ with $q\in\mathcal{Q}$ and $\mathbf s\in\mathbb{Z}^d$
there is at most one edge starting from $q$ and labelled by~$s$.
A lattice walk $w = w_0,\dots,w_n$ belongs to the inhomogeneous model if $w_k\in\set Z_{\geq0}\times\set Z^{d-1}$
for $k=0,\dots,n$ and there is a path in the automaton starting at the initial state, ending at one of the final states, and
such that the $k$th edge of the path is labelled with $w_k-w_{k-1}\in\set Z^d$ for $k=1,\dots,n$.
Below we will write $\mathbf{S}_{pq}$ for the set of all $s\in\set Z^d$ which label an edge from $p$ to~$q$.

 \begin{example}\label{0}
  Let $\mathbf{S}_0=\diagr{N,E,S,W}$
  and $\mathbf{S}_1=\diagr{N,E,S,W,SW,SE,NW,NE}$,
  and consider walks in $\set Z_{\geq0}\times \set Z$ starting at $(0,0)$
  and consisting of steps taken from $\mathbf{S}_0\cup\mathbf{S}_1$
  with the restriction that whenever the current position of a walk is $(i,j)$,
  the next step must be taken from $\mathbf{S}_{(i+j)\bmod2}$. In the notation
  from above we can take $\mathcal{Q}=\bar{\mathcal{Q}}=\{0,1\}$, $q_0=0$, and
  $\mathbf{S}_{01}= \diagr{N,E,S,W}$, $\mathbf{S}_{10}=\diagr{N,E,S,W}$ and $\mathbf{S}_{11}=\diagr{SW,SE,NW,NE}$.

  \end{example}

%   \begin{wrapfigure}{l}{5.5cm}
%   \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,
%                     semithick]
%   \tikzstyle{every state}=[fill=black,draw=none,text=white]
%   %\tikzset{loop left/.style={min distance=10mm,in=240,out=120,looseness=12}}
%   \tikzset{loop  right/.style={min distance=10mm,in=420,out=300,looseness=12}}
%
%   \node[state, minimum size=0.2cm]         (A)                                 {$0$};
%   \node[state, minimum size=0.2cm]         (B) [right of=A]                    {$1$};
%
%   \path (A) edge  [bend right]            node [below] {$\mathbf{S}_{01}$} (B)
%         (B) edge  [bend right]            node [above] {$\mathbf{S}_{10}$} (A)
%         (B) edge  [loop right]            node [right] {$\mathbf{S}_{11}$} (B);
%
% \end{tikzpicture}
% \caption{}
% \label{fig:1}
% \end{wrapfigure}


When the admissible steps only depend on the current position $(i,\mathbf j)$, as in
\cref{0}, we call the model \emph{space inhomogeneous.}  When they only
depend on the time~$n$, the model is called \emph{time inhomogeneous}.

Fix an inhomogeneous lattice walk model as introduced above, and for each set
$\mathbf{S}_{pq}$ fix a function $w_{pq}\colon\mathbf S_{pq}\to\set K$,
where $\set K$ is a field of characteristic zero.
We call $w_{pq}(u,\mathbf v)$ the \emph{weight}
of the step $(u,\mathbf v)\in\mathbf S_{pq}$. The weight of a walk is the product
of the weights of the steps it consists of. Note that the weight does not only
depend on the step $(u,\mathbf v)$ but also on the edge it labels.

For any $i,\mathbf j,n$, let $f_{i,\mathbf j,n}$ be the sum of the weights of all walks from $(i_0,\mathbf j_0)$
to $(i,\mathbf j)$ of length~$n$, and let $F(x,\mathbf y,t)=\sum_{i,\mathbf j,n}f_{i,\mathbf j,n}x^i\mathbf y^{\mathbf j}t^n\in\set K[x,\mathbf y,\mathbf y^{-1}][[t]]$ be the
corresponding generating function, where we write $\mathbf y$ and $\mathbf y^{-1}$
for $y_1,\dots,y_{d-1}$ and $y_1^{-1},\dots,y_{d-1}^{-1}$, respectively, and $\mathbf y^{\mathbf j}$
for $y_1^{j_1}\cdots y_{d-1}^{j_d}$.
Note that $f_{i,\mathbf j,n}$ is just the total number of walks in the model if all weights
are defined as~$1$. If $F_q$ is the generating function of walks associated with paths
in the automaton ending at state~$q$, then $F=\sum_{q\in\bar{\mathcal{Q}}} F_q$.

\begin{example}
  Continuing the previous example, $F_0$ is the generating function counting walks ending
  at a point $(i,j)$ with $i+j$ even and $F_1$ is the generating function counting walks
  ending at a point $(i,j)$ with $i+j$ odd.
  The full generating function is $F=F_0+F_1$.
\end{example}

For the inhomogeneities under consideration the $F_q$'s satisfy a system of functional
equations: writing $S_{pq}:=\sum_{(u,\mathbf v)\in\mathbf{S}_{pq}} w_{pq}(u,\mathbf v)x^u \mathbf y^{\mathbf v}$,
the combinatorial specification, including the boundary condition, translates into the system of functional equations
\[
\forall\ q: \
F_q= [q = q_0]
+ t \sum_p ([x^{\geq0}]S_{pq}) F_p
+ t \sum_{k\geq 1} \sum_p x^{-k} ([x^{-k}] S_{pq}) [x^{\geq k}] F_p,
\]
where $[x^{\geq0}]S_{pq}\in\set K[x,\mathbf y,\mathbf y^{-1}]$ is the Laurent polynomial
obtained from $S_{pq}$ by discarding all terms with negative exponents in~$x$,
where $[x^{-k}] S_{pq}\in\set K[\mathbf y,\mathbf y^{-1}]$ is the coefficient of $x^{-k}$ of
$S_{pq}\in\set K[x,x^{-1},\mathbf y,\mathbf y^{-1}]$, and where
$[x^{\geq k}] F_p$ denotes the series obtained from $F_p$ by discarding
all terms $x^i \mathbf y^{\mathbf j} t^n$ with $i<k$.
The functional equation can also be expressed using the $\Delta$ operator defined
by $\Delta F(x,\mathbf y,t) := (F(x,\mathbf y,t)-F(0,\mathbf y,t))/x$.
Note that $[x^{\geq k}] F = x^k\Delta^k F$ for all~$k\in\set N$,
so $x^{-k} ([x^{-k}] S_{pq}) [x^{\geq k}] F_p$
simplifies to $([x^{-k}] S_{pq})\Delta^k F_p$.

\begin{example}
  Continuing the previous example and taking all weights to be~$1$,
  we have
  \begin{alignat}1
    F_0(x,y) &= 1 + t (y + y^{-1} + x)F_1(x,y) + t x^{-1} (F_1(x,y) - F_1(0,y)),\label{eq:ex1a} \\
    F_1(x,y) &= t (y + y^{-1} + x)F_0(x,y) + tx(y + y^{-1})F_1(x,y) \notag\\
    &\quad{}+ t x^{-1}(F_0(x,y) - F_0(0,y)) + tx^{-1} (y + y^{-1})(F_1(x,y) - F_1(0, y)).\notag
  \end{alignat}
  Eliminating $F_0(x,y)$ from these equations leads to the equation
  \begin{equation}\label{eq:ex1c}
    \begin{array}{l}
      \bigl(x^2y^2 - t^2(x+y)^2(1+x y)^2 - t x (1+x^2)y(1+y^2)\bigr) F_1(x,y)\\
      =t x y (x+y)(1+x y) - t x y^2 F_0(0,y) - t y (x (1+y^2) + t(x+y)(1+x y)) F_1(0,y).
    \end{array}
  \end{equation}
  which we can solve using the kernel method: the polynomial
  $x^2y^2 - t^2(x+y)^2(1+x y)^2 - t x (1+x^2)y(1+y^2)\in\set Q(y)[[t]][x]$ has two roots in $\overline{\set Q(y)}[[t]]$,
  and if we substitute them for $x$ in \eqref{eq:ex1c}, we get a system of two linear equations for the two unknown
  series $F_0(0,y)$ and $F_1(0,y)$.
  This system turns out to have a unique solution, which implies that $F_0(0,y)$ and $F_1(0,y)$ are algebraic.
  Consequently, by \eqref{eq:ex1c}, also $F_1(x,y)$ is algebraic.
  Consequently, by \eqref{eq:ex1a}, also $F_0(x,y)$ is algebraic.
  Finally, it follows by algebraic closure properties that $F(x,y)=F_0(x,y)+F_1(x,y)$ is algebraic.
\end{example}

For any particular choice of inhomogeneity
we can write down an explicit system of functional equations for the auxiliary
series $F_q$, which we can attempt to solve as illustrated in the example above.
Potentially, such an attempt could fail, for example because there are too few roots for
applying the kernel method, or because there are too many solutions of the linear system for the
evaluated auxiliary series $F_q(0,\mathbf y)$. The next theorem says that we do not need to
worry about such problems.

\begin{thm}\label{thm:1}
  The generating function $F(x,\mathbf y,t)\in\set K[x,\mathbf y,\mathbf y^{-1}][[t]]$
  for a model of inhomogeneous lattice walks and a choice of weight functions $w_{pq}$
  as specified above is algebraic over $\set K[x,\mathbf y,t]$.
\end{thm}
\begin{proof}
  As argued above, for every $q$ there is a functional equation $F_q=\cdots$,
  where the right hand side is a $\set K(\mathbf y)[x,t]$-linear combination of $1$ and
  the series $\Delta^i F_q$. These equations together
  form a system of functional equations which can be written as
  \[
    \mathbf f = \mathbf a + t \sum_{i=0}^k \mathbf B_i \Delta^i\mathbf f,
  \]
  where $\mathbf f$ is the vector of the $F_q$'s, where
  $\mathbf a$ is a certain explicit vector, and where the $\mathbf B_i$'s are certain explicit matrices
  with entries in $\set K(\mathbf y)[x,t]$.
  According to \cref{thm:main} shown in the next section
  (applied with $\set K(\mathbf y)$ in place of~$\set K$),
  the unique solution vector of such a system always has algebraic components.
  This means that every $F_q$ is algebraic,
  and consequently, the finite sum $F=\sum_{q\in\bar{\mathcal{Q}}}F_q$ is algebraic too.
\end{proof}

\vspace{-2ex}
\section{Systems of Linear Functional Equations}\label{sec:3}

The purpose of the present section is to prove the following theorem,
which says that the solutions of certain systems of linear
functional equations are always algebraic.
For a more general statement on systems of
polynomial equations see Popescu~\cite{popescu86}.

Throughout this section, let $\set K$ be a field of characteristic zero.
Recall from the previous section that $\Delta\colon\set K[x][[t]]\to\set K[x][[t]]$
is defined by $\Delta f(x,t) = \frac1x(f(x,t)-f(0,t))$.
Applied to a vector of series, the action of $\Delta$ is meant componentwise.

\begin{thm}\label{thm:main}
  Let $\mathbf{a}\in\mathbb{K}[x][t]^n$ and $\mathbf{B}_i\in\mathbb{K}[x][t]^{n\times n}$
  ($i=0,\dots,k$). Then the functional equation
  \begin{equation}\label{eq:fun}
    \mathbf{f} = \mathbf{a} + t \sum_{i=0}^k \mathbf{B}_i \Delta^i \mathbf{f}
  \end{equation}
  has a unique solution $\mathbf{f}$ in $\mathbb{K}[x][[t]]^n$, and its components
  are algebraic over $\mathbb{K}[x,t]$.
\end{thm}

It is clear that the functional equation has a unique solution in $\mathbb{K}[x][[t]]^n$,
because we can compute its coefficients recursively via
\[
  [t^0]\mathbf f=\mathbf [t^0] a
  \quad\text{and}\quad
  [t^{n+1}]\mathbf f=[t^{n+1}]\mathbf a+
            \sum_{i=0}^{\smash k}\sum_{\smash j=0}^n ([t^j]\mathbf B_i)\Delta^i [t^{n-j}]\mathbf f\quad(n\in\set N).
\]
The nontrivial part of the theorem is that the components of the solution are algebraic.
For proving this part of the theorem, we may assume without loss of generality that $\set K$ is
algebraically closed, and we will do so from now on.

Our proof is an adaption of the proof idea of Thm.~3 in~\cite{bousquet06} to linear systems.
We first bring the unevaluated terms $\mathbf f(x,t)$ hidden in the delta terms to the left hand side,
so that the right hand side only contains $\mathbf f(0,t)$ or other evaluated versions of $\mathbf f$.
This can be done by translating the delta terms into evaluations of partial derivatives. Using
$[x^j]\Delta^i\mathbf f(x,t)=[x^{i+j}]\mathbf f(x,t)$
and
$[x^j]\mathbf f(x,t) = \frac1{j!}\mathbf f^{(j)}(0,t)$,
where $\mathbf f^{(j)}(0,t)$ is the $j$th derivative with respect to~$x$, evaluated at $x=0$, we
can write
\vspace{-0.5ex}
\[
 \Delta^i\mathbf f(x,t) = \frac1{x^i}\biggl(\mathbf f(x,t) - \sum_{j=0}^{i-1}\frac{x^j}{j!}\mathbf f^{(j)}(0,t)\biggr).
\]
\vspace{-1ex}
The functional equation~\eqref{eq:fun} can therefore be rewritten in the form
\begin{equation}\label{eq:fun2}
\biggl(x^k\mathbf I_n - t\sum_{i=0}^k x^{k-i}\mathbf B_i\biggr)\mathbf f(x,t)
= x^k\mathbf a - t \sum_{j=0}^{k-1}\biggl(\sum_{i=j+1}^k\frac{x^{k+j-i}}{j!}\mathbf B_i\biggr)\mathbf f^{(j)}(0,t).
\end{equation}
The key to the proof is the matrix on the left side. We will first prove the theorem
under the additional assumption that this matrix has the form $x^k\mathbf I_n - t\mathbf P$ for some
matrix $\mathbf P$ such that $[t^0x^0]\mathbf P$ is a non-singular diagonal matrix (\cref{3}).
Afterwards, the general case is reduced to this situation by a perturbation argument.
In the proof of \cref{3}, we will relate eigenvectors of $[t^0x^0]\mathbf P$
to eigenvectors of $\mathbf P$, using the following fact.

\begin{lem}\label{1}
  Let $\mathbf{P}\in\mathbb{K}[x][t]^{n\times n}$ such that $\mathbf{P}_0 = [t^0]\mathbf{P}\in\mathbb{K}^{n\times n}$,
  and let $\mathbf{K}= x^k\mathbf{I}_n- t\mathbf{P}\in\set K[x][t]^{n\times n}$, for some $k\in\set N$.
  Let $\lambda$ be an eigenvalue of~$\mathbf{P}_0$, let $\omega$ be a primitive $k$-th root of unity, and let $i\in\{0,\dots,k-1\}$.
  Then there is a series $y(t)=\omega^i\lambda^{1/k}t^{1/k} + \O(t^{2/k})\in\mathbb{K}[[t^{1/k}]]$ such that
  $\det(\mathbf{K}(y(t),t))=0$.
  Furthermore, there is a vector $\mathbf{v}(t)\in\mathbb{K}[[t^{1/k}]]^n$ with algebraic coordinates such that
  $\mathbf{v}(t)\mathbf{K}(y(t),t) = 0$ and $\mathbf{v}(0)$ is an eigenvector of $\mathbf{P}_0$ for~$\lambda$.
\end{lem}
\begin{proof}
By definition of the determinant,
$\det(\mathbf{K}) = \det(x^k \mathbf{I}_n-t\mathbf{P}) = \det(x^k\mathbf{I}_n-t\mathbf{P}_0) + \O(t^2)$.
The polynomial $\det(x^k\mathbf{I}_n-t\mathbf{P}_0) = (-1)^n t^n \det(\mathbf{P}_0 - \frac{x^k}{t}\mathbf{I}_n)\in\set K(t)[x]$
has the root $\omega^i \lambda^{1/k}t^{1/k}$.
Hence, by the Newton-Puiseux algorithm~\cite{kauers10j}, there is a series
$y(t)=\omega^i\lambda^{1/k}t^{1/k}+\O(t^{2/k})\in\set K[[t^{1/k}]]$
such that $\det(\mathbf{K}(y(t),t))=0$.
It follows that the matrix $\mathbf{K}(y(t),t)\in\set K(y(t),t)^{n\times n}$ is singular,
so its left-kernel has a nonzero element $\mathbf{v}\in\set K(y(t),t)^n$.
Since $y(t)$ is algebraic (because $\det(\mathbf K)$ is a polynomial in~$x$), also the components of $\mathbf{v}$ are algebraic.
After multiplying by a suitable power of~$t$, we may assume
that the components of $\mathbf{v}(t)$ are in $\set K[[t^{1/k}]]$ and that $\mathbf{v}(0)$ is not
the zero vector. Then $\mathbf{v}(t)\mathbf{K}(y(t),t)=0$ implies $\mathbf{v}(0)(\lambda\mathbf{I}_n-\mathbf{P}_0)=0$,
which completes the proof.
\end{proof}

Secondly, we will need to ensure that a certain matrix is nonsingular.

\begin{lem}\label{2}
Let $\lambda_0,\dots,\lambda_{n-1}\in\mathbb{K}\setminus\{0\}$ and let $\omega$ be a primitive $k$-th root of unity. For $u,v=0,\dots,nk-1$ define $c_{u,v}=(\omega^{u \bmod k}\lambda_{\lfloor u/k \rfloor})^{\lfloor v/n\rfloor} \delta_{\lfloor u/k \rfloor,v \bmod n}$. Then
\[
\det((c_{u,v})_{u,v=0}^{nk-1}) = \pm\Bigl(\prod_{0\leq i<j<k}(\omega^j - \omega^i)\Bigr)^n \prod_{\ell=0}^{n-1}\lambda_\ell^{\binom{k}{2}}.
\]
In particular, this determinant is not zero.
\end{lem}
\begin{proof}
The expression on the right is non-zero because $\lambda_\ell\neq 0$ for all $\ell$ and $\omega$ is a primitive root of unity. It remains to prove the claimed identity.

We permute the columns of the matrix such that the entry at position $(u,v)$ is
\[
 (\omega^{u \bmod k}\lambda_{\lfloor u/k \rfloor})^{v \bmod k} \delta_{\lfloor u/k \rfloor,\lfloor v/k \rfloor}.
\]
The resulting matrix is block diagonal with $n$ blocks of size $k\times k$. The $\ell$-th block is
the Vandermonde matrix $((\omega^{ij}\lambda_\ell^j))_{i,j=0}^{k-1}$, whose determinant is $\lambda_{\ell}^{\binom{k}{2}}\prod_{i<j}(\omega^j-\omega^i)$. Since the determinant of a block diagonal matrix is the product of the determinants of its blocks,
we arrive at the desired conclusion.
\end{proof}

The idea for the proof of \cref{3} is to replace $x$ by various algebraic
series $y(t)$ in such a way that the terms $\mathbf f(x,t)$ in \eqref{eq:fun2} disappear and a linear
system for the components of $\mathbf f^{(j)}(0,t)$ arises, and then to show that this system has a unique solution.

\begin{lem}\label{3}
  Let $\lambda_0,\dots,\lambda_{n-1}\in\set K\setminus\{0\}$ be pairwise distinct, and let $\mathbf{E}=\diag(\lambda_0,\dots,\lambda_{n-1})\in\set K^{n\times n}$.
  Let $\mathbf{a}\in\set K[x][t]^n$, and let $\mathbf{P},\mathbf{Q}_0,\dots,\mathbf{Q}_{k-1}\in\set K[x][t]^{n\times n}$.
  Suppose that $\mathbf{P}=\mathbf{E}+\O(t)$ and $\mathbf{Q}_j=x^j \mathbf{E} + \O(t)$ for $j=0,\dots,k-1$.
  If $\mathbf{f}\in\set K[x][[t]]^n$ and $\mathbf{g}_0,\dots,\mathbf{g}_{k-1}\in\set K[[t]]^n$ are such that
  \begin{alignat}1\label{funeq}
    \left(x^k \mathbf{I}_n - t \mathbf{P}\right)\mathbf{f} = x^k \mathbf{a} - t\sum_{j=0}^{k-1} \mathbf{Q}_j\mathbf{g}_j,
  \end{alignat}
  then the components of $\mathbf{g}_0,\dots,\mathbf{g}_{k-1}$ and $\mathbf{f}$ are algebraic over $\set K[x][t]$.
\end{lem}

\begin{proof}
  By \cref{1}, the polynomial $\det(x^k\mathbf{I}_n-t\mathbf{P})$ has $nk$
  series roots $y_{ij}(t)$ of the form $y_{ij}(t) =
  \omega^i\lambda_j^{1/k}t^{1/k} + \O(t^{2/k})$.  For each such root, the matrix
  $y_{ij}(t)^k\mathbf{I}_n-t\mathbf{P}(y_{ij}(t),t)$ is singular, and, again
  by \cref{1}, the left-kernel of
  $y_{ij}(t)^k\mathbf{I}_n-t\mathbf{P}(y_{ij}(t),t)$ contains a vector
  $\mathbf{v}_{ij}(t)=\lambda_j^{-1}\mathbf{e}_j + \O(t^{1/k})$, with algebraic coefficients.
  Here $\mathbf e_j$ is the $j$th unit vector.

  For $i=0,\dots,k-1$ and $j=0,\dots,n-1$ we replace $x$ by $y_{ij}(t)$ in
  \eqref{funeq} and multiply with $\mathbf{v}_{ij}(t)$ on the
  left. This gives an inhomogeneous linear system with $nk$ equations for the $nk$ unknown
  components of $\mathbf{g}_0(t),\dots,\mathbf{g}_{k-1}(t)\in\mathbb{K}[[t]]^n$,
  whose coefficient matrix is
  \[
  \begin{pmatrix}
    \mathbf{v}_{0,0}(t) \mathbf{Q}_0(y_{0,0}(t),t) & \cdots & \mathbf{v}_{0,0}(t) \mathbf{Q}_{k-1}(y_{0,0}(t),t) \\
    \mathbf{v}_{1,0}(t) \mathbf{Q}_0(y_{1,0}(t),t) & \cdots & \mathbf{v}_{1,0}(t) \mathbf{Q}_{k-1}(y_{1,0}(t),t) \\
    \vdots & \ddots & \vdots \\
    \mathbf{v}_{k-1,n-1}(t) \mathbf{Q}_0(y_{k-1,n-1}(t),t) & \cdots & \mathbf{v}_{k-1,n-1}(t) \mathbf{Q}_{k-1}(y_{k-1,n-1}(t),t)
  \end{pmatrix}.
  \]
  We are done if we can show that this matrix is invertible, because this
  implies that the inhomogeneous linear system for the components of
  $\mathbf{g}_0,\dots,\mathbf{g}_{k-1}$ has a unique solution. The components of its
  solution vector must be algebraic, because all the series appearing in the
  linear system are algebraic. From \eqref{funeq}, we finally
  see that the algebraicity of the components of
  $\mathbf{g}_0,\dots,\mathbf{g}_{k-1}$ implies the algebraicity of the
  components of~$\mathbf{f}$.

  To see that the matrix above is invertible, we use the assumption that
  $\mathbf{Q}_\ell(y_{ij}(t),t) = \mathbf{E}\hspace{1 pt} y_{ij}(t)^\ell + \O(t) = (\omega^i\lambda_j^{1/k})^\ell \mathbf{E} t^{\ell/k} + \O(t^{(\ell+1)/k}) \in\set K[[t^{1/k}]]^{n\times n}$.
  Together with $\mathbf{e}_j\mathbf{E}=\lambda_j \mathbf{e}_j$, where $\mathbf e_j$ is again the $j$th unit vector, it follows that
  \[
    \mathbf{v}_{ij}(t) \mathbf{Q}_\ell(y_{ij}(t),t) =  (\omega^i\lambda_j^{1/k})^\ell \mathbf{e}_j t^{\ell/k} + \O(t^{(\ell+1)/k})\in\set K[[t^{1/k}]]^n,
  \]
  for $i=0,\dots,k-1$, $j=0,\dots,n-1$ and $\ell=0,\dots,k-1$.
  Therefore, for $u=0,\dots,nk-1$ and $v=0,\dots,nk-1$, the entry of the matrix at position $(u,v)$
  is
  \[
  c_{u,v}:=(\omega^{u\bmod k}\lambda_{\lfloor u/k\rfloor}^{1/k})^{\lfloor v/n\rfloor}t^{\lfloor v/n \rfloor /k}\delta_{\lfloor u/k\rfloor,v\bmod n} + \O(t^{(\lfloor v/n \rfloor + 1) /k}).
  \]
  By \cref{2}, we have $\det((c_{u,v})_{u,v=0}^{nk-1})\neq0$.
  This completes the proof.
\end{proof}

\begin{proof}[Proof of \cref{thm:main}]
  We have already argued that existence and uniqueness of a solution in $\set K[x][[t]]^n$ are evident.
  To show that its components are algebraic, we bring \eqref{eq:fun} into a form
  where \cref{3} applies.
  Let $\epsilon$ be a new variable,
  let $\lambda_1,\dots,\lambda_n\in\set K\setminus\{0\}$ be pairwise distinct
  and set $\mathbf E=\epsilon\diag(\lambda_1,\dots,\lambda_n)$.
  Set $\tilde{\mathbf a}(x,t):=\mathbf{a}(x,t^2)$,
  $\tilde{\mathbf B}_i(x,t):=t\mathbf{B}_i(x,t^2)$ ($i=0,\dots,k-1$), and
  $\tilde{\mathbf B}_k(x,t):=\mathbf{E} + t\mathbf{B}_k(x,t^2)$, and
  consider the system
  \[
    \tilde{\mathbf f} = \tilde{\mathbf a} + t\sum_{i=0}^k\tilde{\mathbf B}_i\Delta^i\tilde{\mathbf f}.
  \]
  This system has a unique solution $\tilde{\mathbf f}\in\set K[x,\epsilon][[t]]^n$,
  which is related to the solution $\mathbf f$ of the original equation~\eqref{eq:fun}
  via $\mathbf f(x,t^2)=[\epsilon^0]\tilde{\mathbf f}(x,t)$.
  We are done if we can show that the components of $\tilde{\mathbf f}$ are algebraic, because then so are
  the components of $\mathbf f$.

  Indeed, translating the delta terms to partial derivatives, as earlier, gives
  \[
   \biggl(x^k\mathbf I_n - t\sum_{i=0}^k x^{k-i}\tilde{\mathbf B}_i\biggr)\tilde{\mathbf f}(x,t)
   = x^k\tilde{\mathbf a} -
   t \sum_{j=0}^{k-1}\biggl(\sum_{i=j+1}^k\frac{x^{k+j-i}}{j!}\tilde{\mathbf B}_i\biggr)\tilde{\mathbf f}{\vphantom{\mathbf f}}^{(j)}(0,t).
  \]
  For the matrix $\mathbf P=\sum_{i=0}^k x^{k-i}\tilde{\mathbf{B}}_i\in\set K(\epsilon)[x,t]^{n\times n}$
  we have $\mathbf P=\mathbf E+\O(t)$,
  and for the matrices $\mathbf Q_j=k!\sum_{i=j+1}^k\frac{x^{k+j-i}}{j!}\tilde{\mathbf B}_i\in\set K(\epsilon)[x,t]^{n\times n}$
  we have $\mathbf Q_j=x^j\mathbf E+\O(t)$ for $j=0,\dots,k-1$.
  Therefore, \cref{3} applies to the perturbed equation above and yields the desired algebraicity result.
  (The lemma is applied with $\set K$ replaced by some algebraic closure of $\set K(\epsilon)$
  and with $\tilde{\mathbf f}^{(j)}(0,t)/k!$ in the role of~$\mathbf g_j$.)
\end{proof}

\vspace{-2ex}
\section{Models with more than one restriction}\label{sec:4a}

We have seen that inhomogeneous models in a half-space $\mathbb{Z}_{\geq 0}\times\mathbb{Z}^{d-1}$ always have an
algebraic generating function. More generally, consider walks restricted to $\set Z_{\geq 0}^{d_1}\times\set Z_{\vphantom{\geq0}}^{d_2}$.
In this case, the question arises whether some of the $d_1$ constraints are
implied by the others, which has led Bostan et al.~\cite{bostan16a} to introduce the \emph{dimension} of a model. Here
we generalize this notion to inhomogeneous walks.

First consider unrestricted models in~$\set Z^d$. Fix an inhomogeneity as in \cref{sec:2}.
Let $\mathbf{S}$ be the union of some disjoint copies of the sets $\mathbf{S}_{pq}$, so that
a walk in $\set Z^d$ of length $n$ can be viewed as a word $w$ over the alphabet~$\mathbf S$.
To any such walk~$w$, we associate the vector $(a_{\mathbf u})_{\mathbf u\in\mathbf S}$
where $a_{\mathbf u}\in\set N$ is the number of occurrences of $\mathbf u$ in~$w$. While for unrestricted homogeneous
models, every vector of natural numbers is associated with some walk, this is not true for inhomogeneous
models. For example, for space-inhomogeneous walks in $\set Z^2$ with $\mathbf S_0=\{\nearrow\}$ and
$\mathbf S_1=\{\swarrow\}$,
the vector $(1,1)$ is not associated with a walk. The next lemma is a characterization of vectors associated with walks.

\begin{lem}\label{lem:4}
  Consider a finite automaton and the inhomogeneity defined by it as in \cref{sec:2}.
  Let $\mathbf{S}$ be a disjoint union of the sets
  $\mathbf{S}_{pq}$, and $(a_{\mathbf u})_{\mathbf u\in\mathbf S}$ be a vector of nonnegative integers.
  Let $G$ be the multigraph obtained from the automaton by replacing an edge labelled with $\mathbf{u}$ by $a_{\mathbf{u}}$
  many (unlabelled) edges. Then $(a_{\mathbf{u}})_{\mathbf u \in \mathbf{S}}$ is associated with a walk if
  and only if $G$ has an Eulerian path starting at the initial state $q_0$ and ending at some final state.
\end{lem}
\begin{proof}
  Since $\mathbf{S}$ is the union of disjoint copies of the step sets $\mathbf{S}_{pq}$, every step $\mathbf{u}\in\mathbf{S}$
  belongs to exactly one such set. Therefore, any walk $w$ in the model which has $(a_{\mathbf u})_{\mathbf{u}\in\mathbf{S}}$
  as associated vector can be translated into a path in $G$ starting at~$q_0$, ending at some final state, and using
  $\sum_{\mathbf{u} \in\mathbf{S}_{pq}} a_{\mathbf{u}}$ times an edge from $p$ to~$q$, for all vertices $p$ and~$q$.
  This is an Eulerian path. Conversely, let $(q_0,q_1,\dots,q_n)$ be an Eulerian path in $G$ with $q_n$ being a final state.
  Then for any two $p,q$ states there are $\sum_{\mathbf u \in \mathbf{S}_{pq}} a_{\mathbf u}$ many indices
  $i\in\{1,\dots,n\}$ such that $(q_{i-1},q_i)=(p,q)$. For every $i\in\{1,\dots,n\}$, assign an arbitrary step
  $\mathbf{u}\in\mathbf{S}_{q_{i-1}q_i}$ in such that each step $\mathbf{u}$ is chosen exactly $a_{\mathbf u}$ times, and let $w$ be
  the walk composed of the selected steps. By definition of the $\mathbf{S}_{pq}$'s, it belongs to the model.
  \end{proof}

  The condition for a graph to have an Eulerian path can be encoded as a system of linear constraints on the in-degree and
  out-degrees of the vertices of the graph~\cite{bollobas98}. In our case these are linear equations for the variables~$a_{\mathbf{u}}$.
  It can also be encoded into linear equations that the Eulerian path should start or end at prescribed vertices.


A walk $w$ ends in $\mathbb{Z}_{\geq 0}^{d_1}\times\set Z_{\vphantom{\geq0}}^{d_2}$ iff for its associated vector
$(a_{\mathbf u})_{\mathbf u\in\mathbf S}$ we have
\begin{equation}\label{eq:10}
\sum_{\mathbf{u} = (u_1,\dots,u_{p+q})\in\mathbf S} a_\mathbf{u} u_i\geq 0\quad\text{for all $i=1,\dots,d_1$,}
\end{equation}
and it stays entirely in $\mathbb{Z}_{\geq 0}^{d_1}\times\set Z_{\vphantom{\geq0}}^{d_2}$ iff these
inequalities hold for all prefixes of~$w$. Extending Def.~2 of~\cite{bostan16a},
we define the \emph{dimension} of an inhomogeneous model
for $\mathbb{Z}_{\geq 0}^{d_1}\times\set Z_{\vphantom{\geq0}}^{d_2}$ as the smallest $\delta\in\set
N$ such that there are $\delta$ inequalities in~\eqref{eq:10} which imply all
the others. In view of \cref{lem:4}, the dimension of a model can be
found by linear programming.

\vspace{-2ex}
\section{Inhomogeneous Lattice Walks in the Quarter Plane}\label{sec:4}

We have no satisfactory theory for inhomogeneous models for the quarter plane.
% The problem turns out to be more difficult since the functional equations involve
% sections which depend on $x$ as well as sections which depend on $y$. In particular
% we cannot apply the theorem from the previous section.
However, for all time-inhomogeneous and all space-inhomogeneous models with small steps as
in the introduction, we have produced an experimental classification which is
available at \url{http://www.algebra.uni-linz.ac.at/people/mkauers/inhomogeneous/}.
Up to symmetry, there are 32993 pairs $\mathbf S_0,\mathbf S_1\subseteq\diagr{N,E,S,W,NE,SE,NW,SW}$.
Removing trivial cases (whose counting sequence is ultimately constant),
zero- and one-dimensional cases (whose generating function is algebraic by \cref{thm:1}),
and homogeneous cases (whose nature is known)
leaves us with 23906 space-inhomogeneous and 25370 time-inhomogeneous cases.

For each of these, we computed the first 10000 terms (modulo the prime 45007)
of the generating function $F(1,1,t)$ and tried to guess a differential equation.
When an equation was found, we also searched for an algebraic equation.
These computations took altogether about 30 years of computing time.
As a result, 3784 space-inhomogeneous models and 2603 time-inhomogeneous models seem to be D-finite,
including 2474 and 1535 seemingly algebraic cases, respectively.
For space-inhomogeneous models, the largest differential equations we found have order 24 and degree~1183,
such an equation appears for $\mathbf S_0=\diagr{SW,N,NE}$ and $\mathbf S_1=\diagr{SW,S,NE,E,SE}$.
For time-inhomogeneous models, the largest differential equation we found has order 28 and degree~1256
and appears for $\mathbf S_0=\diagr{N,S,W,E}$, $\mathbf S_1=\diagr{W,N,E,SE,SW}$.
Very likely further D-finite models could be discovered with more terms.

The techniques of~\cite{bousquet10} for proving D-finiteness seem to apply only to a very limited number of
cases. We conclude with two examples where they work and invite our readers to find proofs for further
conjecturally D-finite cases.

\begin{example}\label{ex:4}
 Consider the time-inhomogeneous model in $\set Z_{\geq0}^2$ with $\mathbf{S}_0 = \diagr{NE,NW,S}$ and
  $\mathbf{S}_1 = \diagr{N,W,E,SW,SE}$. Let $S_0,S_1\in\mathbb{Q}[x,x^{-1},y,y^{-1}]$ be the corresponding Laurent polynomials,
and let $F_0(x,y),F_1(x,y)\in\mathbb{Q}[x,y][[t]]$ be the power series
counting the number of walks of even and odd lengths, respectively. Then $F(x,y)
= F_0(x,y) + F_1(x,y)$ is the generating function of the model.
 The functional equations for $F_0(x,y)$ and $F_1(x,y)$ are
\begin{align*}
F_0(x,y) &= 1 + t S_1 F_1(x,y) - t([y^{<0}]S_1)F_1(x,0)- t([x^{<0}]S_1)F_1(0,y) + t([x^{<0}y^{<0}]S_0)F_1(0,0)\\
 F_1(x,y) &= tS_0 F_0(x,y) - t([y^{<0}]S_0)F_0(x,0).
\end{align*}
  We consider
  the groups $G_0$ and $G_1$ generated by the rational maps $\Phi_0\colon (x,y)\mapsto (\frac1x,y)$ and
  $\Psi_0\colon (x,y)\mapsto(x,\frac{1}{y(x+\frac1x)})$,
  and $\Phi_1\colon (x,y)\mapsto (\frac1x,y)$ and
  $\Psi_1\colon (x,y)\mapsto(x,\frac1y (x+\frac1x))$, respectively. These groups act
  on pairs of rational functions. By construction their generators alter only one of two of its components,
  and leave the corresponding step polynomials invariant, see~\cite{bousquet10} for details.
  We multiply the two equations above by $xy$ and take the so-called
  orbit sum of the first equation with respect to $G_1$, and of the second one with respect to~$G_0$.
  This eliminates all terms $F_q(x,0)$, $F_q(0,y)$ and $F_q(0,0)$
  with $q\in\{0,1\}$ and leaves us with
  \begin{alignat*}1
    \sum_{g\in G_1} \sgn(g) g(xyF_0(x,y)) &= \sum_{g\in G_1} \sgn(g) g(xy) + t S_1 \sum_{g\in G_1} \sgn(g) g(xyF_1(x,y))\\
    \sum_{g\in G_0} \sgn(g) g(xyF_1(x,y)) &= t S_0 \sum_{g\in G_0} \sgn(g) g(xyF_0(x,y)),
  \end{alignat*}
  where $\sgn(g)=(-1)^\ell$ when $g$ is a product of $\ell$ generators.
  It is easy to check that replacing $y$ by $\frac{1}{y}(x+\frac1x)$ in the second equation gives
  \[
   \sum_{g\in G_1} \sgn(g) g(xyF_1(x,y)) = t S_0(x,\frac{1}{y}(x+\frac1x)) \sum_{g\in G_1} \sgn(g) g(xyF_0(x,y)).
  \]
  From this equation and the first of the two previous two equations we get
    \begin{equation*}
    \sum_{g \in G_1} \sgn(g) g(xyF_0(x,y)) =
    \frac{1}{1-t^2 S_0(x,\frac{1}{y}(x+\frac1x)) S_1} \sum_{g\in G_1} \sgn(g)g(xy)
  \end{equation*}
  Extracting the positive part gives
  \begin{equation*}
    F_0(x,y) = \frac{1}{xy}[x^{>0}y^{>0}]  \frac{1}{1-t^2 S_0(x,\frac{1}{y}(x+\frac1x)) S_1} \sum_{g\in G_1} \sgn(g) g(xy).
  \end{equation*}
  This expression implies D-finiteness of $F_0(x,y)$, and back-substituting into the earlier equations and using
  D-finite closure properties gives the D-finiteness of $F_1(x,y)$ and of $F(x,y)$.
\end{example}

\begin{example}\label{ex:5}
  Consider the space-inhomogeneous model in $\set Z_{\geq0}^2$
  with $\mathbf{S}_0=\diagr{N,S,E,W}$
  and $\mathbf{S}_1=\diagr{N,S,E,W,SE,SW,NE,NW}$
  studied by D'Arco et al.~\cite{darco16}.
  Define $\mathbf{S}_{pq}$ for $p,q\in\{0,1\}$
  as in \cref{sec:2},
  and let $S_{pq}\in\set Q[x,x^{-1},y,y^{-1}]$ be the corresponding Laurent polynomials.
  Write $F_q(x,y)$ for $q\in\{0,1\}$ for
  the power series that count the number of walks ending at points $(i,j)$ with $i+j=q\bmod 2$.
  The functional equations for $F_0(x,y)$ and $F_1(x,y)$ are
  \begin{alignat*}1
     F_0(x,y) &= 1 + t S_{10} F_1(x,y) - t([y^{<0}]S_{10}) F_1(x,0) - t([x^{<0}]S_{10}) F_1(0,y)\\
     F_1(x,y) &= t S_{01} F_0(x,y) - t ([y^{<0}]S_{01}) F_0(x,0) - t([x^{<0}]S_{01}) F_0(0,y) \\
     &\quad{} + t S_{11} F_1(x,y) - t ([y^{<0}]S_{11}) F_1(x,0) - t([x^{<0}]S_{11}) F_1(0,y).
  \end{alignat*}
  Consider the group $G$ generated by the rational maps $\Phi\colon (x,y)\mapsto (x,\frac1y)$ and
  $\Psi\colon (x,y)\mapsto(\frac1x,y)$.
  Like in the previous example, multiply both equations by $xy$ and take the orbit sum for~$G$.
  This eliminates all terms $F_q(x,0)$ and $F_q(0,y)$ and leaves us with
  \begin{alignat*}2
    \sum_{g\in G} \sgn(g) g(xyF_0(x,y)) &= \sum_{g\in G} \sgn(g) g(xy) + tS_{10} \sum_{g\in G} \sgn(g) g(xyF_1(x,y))\\
    \sum_{g\in G} \sgn(g) g(xyF_1(x,y)) &= tS_{01} \sum_{g\in G} \sgn(g) g(xyF_0(x,y)) + tS_{11} \sum_{g\in G} \sgn(g) g(xyF_1(x,y)).
  \end{alignat*}
  From those equations we deduce
  \begin{equation*}
    \sum_{g \in G} \sgn(g) g(xyF_1(x,y)) = \frac{tS_{01}}{1-tS_{11}-t^2S_{01}S_{10}} \sum_{g\in G} \sgn(g)g(xy),
  \end{equation*}
  and extracting the positive part gives
  \begin{equation*}
    F_1(x,y) = \frac1{xy}[x^{>0}y^{>0}] \frac{tS_0}{1-tS_{11}-t^2S_{01}S_{10}} \sum_{g\in G} \sgn(g) g(xy).
  \end{equation*}
  This expression implies D-finiteness of $F_1(x,y)$, and back-substituting into the earlier equations
  and using D-finite closure properties gives the D-finiteness of $F_0(x,y)$ and of the full
  generating function $F(x,y)=F_0(x,y)+F_1(x,y)$.
 \end{example}

 We were able to guess a differential equation of order~$3$ with polynomial coefficients of degree~$9$
 for the generating function $F(1,1,t)$ in \cref{ex:5}.
 For the model in \cref{ex:4} we could not find any.

% \par\medskip\noindent\textbf{Acknowledgement.} We thank Marni Mishna for making us aware of~\cite{bousquet06b}, and
% the referees for pointing us to~\cite{popescu86}.

\vspace{-2ex}
\acknowledgements{We thank Marni Mishna for making us aware of~\cite{bousquet06b}, and
the referees for pointing us to~\cite{popescu86}.}

\printbibliography

\end{document}

