# Cobordisms and commutative categorial grammars

Sergey Slavnov
National Research University Higher School of Economics
<EMAIL_ADDRESS>

###### Abstract

We propose a concrete surface representation of abstract categorial grammars
in the category of word cobordisms or cowordisms for short, which are certain
bipartite graphs decorated with words in a given alphabet, generalizing linear
logic proof-nets. We also introduce and study linear logic grammars, directly
based on cobordisms and using classical multiplicative linear logic as a
typing system.

##  1 Introduction

The best known categorial grammars are based on noncommutative variants of
linear logic, most notably, on Lambek calculus [Lam58] and its
variations/extensions. On the other hand, such formalisms as abstract
categorial grammars (ACG) [dG01], also known (with minor variations) as
$\lambda$-grammars [Mus07] or linear grammars [MP12], arise from an
alternative or, rather, complementary approach, and use ordinary implicational
linear logic and linear $\lambda$-calculus. These can be called “commutative”
in contrast to the “noncommutative” Lambek grammars. Commutative grammars are
attractive because of the much more familiar and intuitive underlying logic,
besides they are remarkably expressive. Unfortunately, basic constituents of
ACG used for syntax generation seem extremely abstract: they are just linear
$\lambda$-terms. Identifying an abstract $\lambda$-term with some element of
language is not so easy, and syntactic analysis becomes complicated. It seems
that some more concrete surface representation for commutative grammars would
be highly desirable.

In this work we propose that such a representation is indeed possible. We
introduce a specific structure of word cobordisms, or, simply cowordisms, as
we abbreviate for a joke.

Word cobordism is a bipartite graph, more precisely, a perfect matching
(generalizing linear logic proof-nets), whose edges are labeled with words in
a given alphabet, and whose vertex set is subdivided into the input and the
output parts. This can be seen as a one-dimensional topological cobordism (see
[Sto16], [BD95]) decorated with words, which explains our terminology. (For a
pedestrian discussion of cobordisms that might be relevant to the content of
this paper, see [BS11].)

Just as topological cobordisms, word cobordisms can be organized into a
category, with composition given by gluing inputs to outputs. The resulting
category has a rich structure, in particular it is compact closed (see [KL80],
also [AC09]), and, as any compact closed category, it provides a denotational
model for multiplicative linear logic and for linear $\lambda$-calculus. The
latter model gives rise to the geometric cowordism representation of string
ACG that we discuss.

On the other hand, the very structure of cowordism category with its
involutive duality, suggests using classical (rather than intuitionistic)
multiplicative linear logic (MLL) as more natural for this setting. Thus, we
also define and study linear logic grammars (LLG), based directly on the
cowordism representation and using MLL as the typing system. String ACG can be
seen as a particular case of LLG.

LLG with their underlying compact category could be seen as a commutative
version of pregroup grammars (see [Lam99]). This suggests possible connections
with categorical compositional distributional semantics (DisCoCat) [CSC10],
which use pregroup grammars a lot. Indeed, DisCoCat models are based on
finite-dimensional vector spaces and use their symmetric and compact closed
categorical structure in an essential way. Arguably, LLG match these
structures just better than other syntactic formalisms. Although such a
matching is not required for any known construction, and we cannot say even if
it is useful at all, it seems at least interesting that a parallel symmetric
compact structure can be found on the syntactic side as well.

(We should add though that the above parallelism does not go to the extreme.
Typically, DisCoCat models, apart from using the canonical symmetric compact
structure of vector spaces, impose additional, non-canonical structure of
commutative Frobenius algebra, so called “spiders” [CSC13]. This latter
commutativity has no analogue on the syntactic, surface level.)

In any case, we think that the cowordism representation with its simple
geometric meaning and diagrammatic reasoning might be helpful for studying
language generation, some examples are given. Hopefully, it can also be used
for applying ideas of DisCoCat to various “commutative” formalisms, thus going
beyond context-free languages.

##  2 Boundaries and multiwords

Let $T$ be a finite alphabet. We denote the set of all finite words in $T$ as
$T^{*}$, and the empty word as $\epsilon$. For consistency of definitions, we
will also need cyclic words, which are equivalence classes of elements of
$T^{*}$ quotiented by cyclic permutations of letters. For $w\in T^{*}$ we
denote the corresponding cyclic word as $[w]$.

For a set $X$ of natural numbers and an integer $n$ we use the notation
$n+X=\\{n+m|~{}m\in X\\}$, and $n-X=\\{n-m|~{}m\in X\\}$. For multisets $A$,
$B$ we denote their disjoint union as $A+B$. For a positive integer $N$, we
denote ${\bf I}(N)=\\{1,\ldots,N\\}$.

Finally, for positive integers $N,M$ with $M\leq N$, we will use the shifted
embedding function $\mbox{shift}_{k}^{s}:{\bf{I}}(M)\to{\bf I}(N)$, where
$M+s\leq N$, defined as $\mbox{shift}_{k}^{s}(i)=i,\mbox{ if
}i<k,~{}\mbox{shift}_{k}^{s}(i)=i+s\mbox{ if }i\geq k$.

A boundary $X$ consists of a natural number $|X|$, the cardinality of $X$, and
a subset $X_{l}\subseteq{\bf I}(|X|)$ of left endpoints of $X$. We will denote
${\bf I}(|X|)={\bf I}(X)$.

The complement of $X_{l}$ in ${\bf I}(X)$ is denoted as $X_{r}$. Elements of
$X_{l}$ are called left endpoints of $X$ and are said to have left polarity,
while elements of $X_{r}$ are right endpoints of $X$ and have right polarity.

A boundary $X$ is, basically, a linearly ordered finite set of cardinality
$|X|$, equipped with a partition into left and right endpoints.

For two boundaries $X,Y$ and an integer $i$ such that $i+|Y|\leq|X|$, we say
that $i+Y$ is a subboundary of $X$ if $i+Y_{l}\subseteq X_{l}$ and
$i+Y_{r}\subseteq X_{r}$.

Given two boundaries $X$ and $Y$, the tensor product boundary $X\otimes Y$ and
the dual boundary $X^{\bot}$ are obtained, respectively, by concatenation and
order and polarity reversal, i.e. $|{X\otimes Y}|=|X|+|Y|$, $(X\otimes
Y)_{l}=X_{l}\cup(|X|+Y_{l})$, and $|{X^{\bot}}|=|X|$,
$(X^{\bot})_{l}=|X|+1-X_{r}$. The neutral element for tensor product is the
unit boundary ${\bf 1}$ defined by $|{\bf 1}|=0$, ${\bf 1}_{l}=\emptyset$.

Note that we have the identity $(X\otimes Y)^{\bot}=Y^{\bot}\otimes X^{\bot}$.
This should not suggest any sort of noncommutativity in the category of
boundaries. We will have a natural isomorphism between $(X\otimes Y)^{\bot}$
and $X^{\bot}\otimes Y^{\bot}$, just not equality. The flip of tensor factors
will allow somewhat better pictures, with fewer crossings.

Given an alphabet $T$, a regular multiword $M$ over $T$ with boundary $X$ is a
directed graph on the set ${\bf I}(X)$ of vertices, whose edges are labelled
with words in $T^{*}$, such that each vertex is adjacent to exactly one edge
(so that it is a perfect matching), and for every edge its left endpoint is in
$X_{l}$ and its right endpoint is in $X_{r}$.

In the following we will identify a regular multiword with the set of its
labeled edges. The notation $[x,w,y]$ will stand for an edge from $x$ to $y$
labeled with the word $w$.

xybaBoundary: $X$, $|X|=6$, $X_{l}=\\{2,5,6\\}$.Edges: $[6,xy,1]$, $[2,ba,4]$,
$[5,\epsilon,3]$. Figure 1: Multiword

A general multiword $M$ over $T$ with boundary $X$ is defined as a pair
$M=(M_{0},M_{c})$, where $M_{0}$, the regular part, is a regular multiword
over $T$ with the boundary $X$, and $M_{c}$, the singular part, is a finite
multiset of cyclic words over $T$. A multiword is acyclic or regular if its
singular part is empty. Otherwise it is singular.

Singular multiwords should be understood as pathological (in the context of
this work), but we need them for consistency of definitions. Geometrically, a
multiword can be understood as the disjoint union of an edge-labeled graph and
a collection of closed curves (i.e. circles) labeled with cyclic words.

We will use certain conventions for depicting multiwords, which guarantee
unambiguous reading of pictures. Unless otherwise stated, points of the
boundary are ordered from left to right. Left endpoints are marked as solid
dots, and right endpoints as arrowheads. Also, our strict convention for
reading edge labels is that words in a picture are always read from left to
right, in the usual way, no matter what is the direction of edges. An example
is in Figure 1.

Given two multiwords $M=(M_{0},M_{c})$ and $N=(N_{0},N_{c})$ with boundaries
$X$ and $Y$ respectively, the tensor product multiword $M\otimes N$ has
boundary $X\otimes Y$ and is defined as the disjoint union, i.e. $(M\otimes
N)_{c}=M_{c}+N_{c}$ and $(M\otimes N)_{0}=\\{[i,w,j]|~{}[i,w,j]\in
M_{0}\\}\cup\\{[|X|+i,w,|X|+j]|~{}[i,w,j]\in N_{0}\\}$.

A crucial operation on multiwords is contraction, which consists in gluing
neighboring endpoints of opposite polarity and concatenating the corresponding
edge labels in the direction from the left endpoint to the right. Here is an
accurate definition.

Let $M$ be a multiword with boundary $X$, and $n<|X|$ be such that $n$ and
$n+1$ have opposite polarity in $X$. Let $x$ be the right endpoint in the pair
$(n,n+1)$ and $y$ be the left one.

The elementary contraction $\langle M\rangle_{n,n+1}$ of $M$ along $n$ and
$n+1$ is the multiword $M^{\prime}$ with the boundary $X^{\prime}$, where
$|{X^{\prime}}|=|X|-2$, $(X^{\prime})_{l}=(\mbox{shift}_{n}^{2})^{-1}(X_{l})$,
constructed as follows.

If $x$ and $y$ are not connected with an edge in $M_{0}$, then
$M_{c}^{\prime}=M_{c}$, and $M^{\prime}_{0}$ consists of all edges $[i,w,j]$
such that $[\mbox{shift}_{n}^{2}(i),w,\mbox{shift}_{n}^{2}(j)]\in M_{0}$ plus
the edge $[\alpha,uv,\beta]$ such that $[\mbox{shift}_{n}^{2}(\alpha),u,x]$,
$[y,v,\mbox{shift}_{n}^{2}(\beta)]$ are in $M_{0}$.

If there is an edge $[y,w,x]\in M_{0}$, then $M_{c}^{\prime}=M_{c}+\\{[w]\\}$,
and $M^{\prime}_{0}$ consists of all edges $[i,w,j]$ such that
$[\mbox{shift}_{n}^{2}(i),w,\mbox{shift}_{n}^{2}(j)]\in M_{0}$.

It is easy to see that in all cases $M_{0}^{\prime}$ is a perfect matching and
its edges start at left endpoints of $X_{l}^{\prime}$. Also, when the
contracted vertices $x$ and $y$ happen to be connected with an edge, the
resulting multiword necessarily is singular.

Elementary contractions can be iterated.

Let $X$, $Y$ be boundaries, $i\in{\bf N}$ and assume that $i+Y^{\bot}\otimes
Y$ is a subboundary of $X$. Let $n=|Y|=|{Y^{\bot}}|$.

AnnJimgoes out witha lot$\Longrightarrow$AnnJim“goes out with”“a lot”

Figure 2: Iterated contractions

Then for any multiword $M$ with boundary $X$ we define the iterated
contraction $\langle M\rangle_{i+Y^{\bot}\otimes Y}$ of $M$ along
${i+Y^{\bot}\otimes Y}$ by $\langle M\rangle_{i+Y^{\bot}\otimes
Y}=\langle\ldots\langle~{}\langle~{}\langle
M\rangle_{i+n,i+n+1}\rangle_{i+n-1,i+n}\rangle\ldots\rangle_{i+1,i+2}$.

It is easy to check that the above is well defined.

In order to avoid possible ambiguity in pictures with iterated contractions,
we will use quotation marks. An example is shown in Figure 2, where dotted
lines connect neighboring vertices that will be contracted. When we replace
dotted lines with solid ones, the resulting graph has discontinuous edge
labels, and it is not immediately clear how to read them. Our convention is
that any block in quotation marks is read from left to right, as usual, while
several blocks labeling one edge are read in the order in which they appear as
we traverse the edge from the left endpoint to the right one. In particular,
in Figure 2, when all the zigzagging is reduced, we obtain the sentence “Jim
goes out with Ann a lot”.

##  3 Word cobordisms

Let $X,Y$ be boundaries and $T$ be an alphabet.

A word cobordism or, simply, a cowordism $\sigma:X\to Y$ over $T$ from $X$ to
$Y$ is a multiword over $T$ with boundary $X^{\bot}\otimes Y$. We say that $Y$
is the outgoing boundary of $\sigma$, and $X$ is the incoming boundary. A
cowordism is regular if its underlying multiword is regular, otherwise it is
singular.

When depicting a cowordism $\sigma:X\to Y$, we put elements $1,\ldots,|X|$ of
the subboundary $X^{\bot}$ on one vertical line, with the increasing order
corresponding to the direction up, and we put the elements
$|X|+1,\ldots,|X|+|Y|$ of the subboundary $|X|+Y$ on a parallel line to the
right, in the increasing order corresponding to the direction down.

For example, if the boundaries $X,Y$ are given by

$|X|=4,\quad X_{l}=\\{3\\},\quad|Y|=4,\quad Y_{l}=\\{2\\},$ (1)

then a cowordism $\sigma:X\to Y$ will be depicted as in Figure 3(a) (where we
indicate vertex numbers for clarity). The subboundary $X^{\bot}$ of $\sigma$
corresponds to the incoming boundary $X$ by means of an order and polarity
reversing bijection. In particular the right endpoint $2$ in the picture
corresponds to the left endpoint $3$ of $X$.

$X$$1$$2$$3$$4$$8$$7$$6$$5$$\sigma$$Y$ (a) Detailed picture

$\sigma:$$X_{1}$$Y_{1}$$\cdots$$\cdots$$\tau$$X_{n}$$Y_{m}$ (b) Many inputs
and outputs

$\sigma:$$X$$Y$$\sigma$$\tau:$$Y$$Z$$\tau$$\tau\circ\sigma:$$X$$\sigma$$Z$$\tau$
(c) Composition, schematic picture

$\sigma:$$X$$\sigma$$Y$$\tau:$$Y$$Z$$\tau$$\tau\circ\sigma:$$X$$\sigma$$Z$$\tau$

(d) Composition, detailed picture

Figure 3: Cowordisms

In general, when the structure of boundaries is not important, we “squeeze”
parallel edges into one and represent a cowordism $\sigma:X\to Y$
schematically as a box with an incoming wire labeled with $X$ and an outgoing
wire labeled with $Y$. More generally, we represent a cowordism
$\sigma:X_{1}\otimes\ldots\otimes X_{n}\to Y_{1}\otimes\ldots\otimes Y_{m}$ as
a box whose $n$ incoming wires are labeled with $X_{i}$’s and $m$ outgoing
wires are labeled with $Y_{i}$’s, as in Figure 3(b). Such a “squeezed” picture
is consistent with the full picture. If we “expand” each edge into parallel
edges adjacent to points in the corresponding subboundary, we obtain the
detailed picture. When we depict a cowordism $\sigma:{\bf 1}\to X$,
respectively $\tau:X\to{\bf 1}$, we do not have wires on the left,
respectively right.

This is, of course, a variation of the familiar pictorial language for
monoidal categories. Note, however, that, since cowordisms are, by definition,
geometric objects, the diagrammatic representation is quite literal, and
diagrammatic reasoning is valid automatically, without further justification.

Matching cowordisms are composed by gluing incoming and outgoing boundaries.

Let boundaries $X,Y,Z$ and cowordisms $\sigma:X\to Y$, $\tau:Y\to Z$, with the
underlying multiwords $M_{\sigma}$, $M_{\tau}$ respectively be given. The
composition $\tau\circ\sigma:X\to Z$ is the cowordism whose underlying
multiword $M_{\tau\circ\sigma}$ is obtained as the iterated contraction
$M_{\tau\circ\sigma}=\langle M_{\sigma}\otimes M_{\tau}\rangle_{|X|+Y\otimes
Y^{\bot}}$.

It is easy to see that, with our conventions, composition of cowordisms
$\sigma:X\to Y$, $\tau:Y\to Z$ corresponds to the schematic picture in Figure
3(c).

We get a detailed, “full” picture by expanding every edge into as many
parallel edges as there are points in the corresponding boundary. For example,
if $X,Y$ are as in (1), and $Z$, say, has two points of opposite polarity,
then the schematic picture in Figure 3(c) translates to the detailed picture
in Figure 3(d).

It is evident from geometric representation that composition of cowordisms is
associative.

The identity cowordism $\mbox{id}_{X}:X\to X$ is the regular multiword with
the boundary $X^{\bot}\otimes X$ defined as

$\mbox{id}_{X}=\\{[|X|+i,\epsilon,|X|-i+1]|~{}i\in
X_{l}\\}\cup\\{[|X|-i+1,\epsilon,|X|+i]|~{}i\in X_{r}\\}.$

In a schematic, “squeezed” picture, the identity cowordism corresponds to a
single wire: $\mbox{id}_{X}:$$X$$X$. In the full picture there are as many
parallel wires as there are points in $X$. If $X$ is as in (1), then the full
picture is the following: $\mbox{id}_{X}:$$X$$X$.

Now let boundaries $X,Y,Z,T$ and cowordisms $\sigma:X\to Y$, $\tau:Z\to T$ be
given. Let us write $\sigma_{0}$, respectively $\tau_{0}$, for the regular
part of (the underlying multiword of) $\sigma$, respectively $\tau$, and let
us write $\sigma_{c}$, $\tau_{c}$ for the respective singular parts.

The tensor product cowordism $\sigma\otimes\tau:X\otimes Z\to Y\otimes T$ is
defined by the multiword with the singular part
$(\sigma\otimes\tau)_{c}=\sigma_{c}+\tau_{c}$, and the regular part
$(\sigma\otimes\tau)_{0}$ obtained as the union of edge sets $\sigma_{0}$,
$\tau_{0}$ appropriately shifted:

$(\sigma\otimes\tau)_{0}=\\{[i+|Z|,w,j+|Z|]|~{}[i,w,j]\in\sigma_{0}\\}\cup$
$\\{[\mbox{shift}_{|Z|+1}^{|X|+|Y|}(i),w,\mbox{shift}_{|Z|+1}^{|X|+|Y|}(j)]|~{}[i,w,j]\in\tau_{0}\\}.$

In the graphical language, tensor product of cowordisms corresponds simply to
putting two boxes side by side, as in Figure 4(a).

$\sigma\otimes\tau:$$X$$Y$$\sigma$$Z$$T$$\tau$ (a) Tensor product

$s_{XY}:$$X$$Y$$X$$Y$ (b) Symmetries

$\sigma:$$X$$Y$$\sigma$$\sigma^{\bot}:$$X^{\bot}$$\sigma$$Y^{\bot}$ (c)
Duality

$\sigma:$$X$$\sigma$$Y$$Y^{\bot}$$X^{\bot}$$\sigma^{\bot}:$$\sigma$

(d) Duality in detail

$X$$Y$$Z$$\cong$$X$$Y^{\bot}$$Z$

(e) Compact structure

Figure 4: Structure of the cowordism category

The symmetry cowordism $s_{X,Y}:X\otimes Y\to Y\otimes X$ is defined by the
regular multiword with the set of edges

$\\{[|Y|-i+1,\epsilon,|X|+|Y|+i]|~{}i\in
Y_{r}\\}\cup\\{[|Y|+|X|-i+1,\epsilon,|X|+2|Y|+i]|~{}i\in X_{r}\\}\cup$
$\\{[|X|+|Y|+i,\epsilon,|Y|-i+1]|~{}i\in
Y_{l}\\}\cup\\{[|X|+2|Y|+i,\epsilon,|Y|+|X|-i+1]|~{}i\in X_{l}\\}.$

A schematic picture of $s_{X,Y}$ is given in Figure 4(b).

Finally, let us extend duality from boundaries to cowordisms.

Let $X$, $Y$ be boundaries, and $\sigma:X\to Y$ be a cowordism. Let us
identify $\sigma$ with the underlying multiword
$\sigma=(\sigma_{0},\sigma_{c})$.

The dual cowordism $\sigma^{\bot}:Y^{\bot}\to X^{\bot}$ of $\sigma$ is the
multiword with the same singular part $\sigma_{c}$ and the regular part
$\sigma_{0}^{\bot}$ obtained from $\sigma_{0}$ by a cyclic permutation of
boundary vertices:
$\sigma_{0}^{\bot}=\\{[\phi(i),w,\phi(j)]|~{}[i,w,j]\in\sigma_{0}\\}$, where
$\phi(i)=i+|Y|,\mbox{ if }i\leq|X|,~{}\phi(i)=i-|X|,\mbox{ if }i>|X|$.

In a schematic picture, duality is shown in Figure 4(c).

The full picture, again, can be recovered by expanding every wire into a
parallel cluster. For example, if $X,Y$ are as in (1), the above picture
translates to the one in Figure 4(d). (We defined duality to flip tensor
factors precisely in order to have this consistency with “parallel wires
substitution” in the graphical language.)

It is very easy to check that, for a fixed alphabet $T$, we have a well-
defined category ${\bf Coword_{T}}$ of boundaries and cowordisms, and the
operation of tensor product together with symmetry cowordisms make it a
symmetric monoidal category. Moreover there are natural isomorphisms

$(X\otimes Y)^{\bot}\cong X^{\bot}\otimes Y^{\bot}\quad\mbox{Hom}(Y\otimes
X,Z)\cong\mbox{Hom}(X,Y^{\bot}\otimes Z),$ (2)

which means that the duality makes the category compact (see [KL80], also
[AC09]). The first isomorphism in (2) is the symmetry; the second one is shown
in Figure 4(e).

In fact, in a sense that can be made precise, the category of cowordisms over
an alphabet $T$ is a free compact category generated by the free monoid
$T^{*}$, where the latter is seen as a category with one object (compare with
[Abr05]).

##  4 Representing linear $\lambda$-calculus

Here we assume that the reader is familiar with basic notion of
$\lambda$-calculus, see [Bar85] for reference.

We assume that we are given sets $X$ and $C$ of variables and constants, with
$C\cap X=\emptyset$. The set $\Lambda=\Lambda(X,C)$ of $\lambda$-terms is
constructed from $X$ and $C$ by applications and $\lambda$-abstractions.

In linear $\lambda$-calculus, terms are typed using (intuitionistic)
implicational linear logic (ILL).

Given a set $N$ of literals or atomic types, the set $Tp=Tp(N)$ of linear
implicational types (over $N$), is defined by the grammar $Tp::=N|Tp\multimap
Tp$.

A typing judgement is a sequent of the form
$x_{1}:A_{1},\ldots,x_{n}:A_{n}\vdash t:A$, where $x_{1},\ldots x_{n}\in X$
are pairwise distinct ($n$ may be zero), $t\in\Lambda(X,C)$, and
$A_{1},\ldots,A_{n},A\in Tp(N)$.

${x:A\vdash x:A}(\mbox{Id})$,
$\cfrac{\Gamma,x:A,\Delta\vdash t:B}{\Gamma,\Delta\vdash(\lambda
x.t):A\multimap B}(\multimap\mbox{I})$, $\cfrac{\Gamma\vdash
s:A\quad\Delta\vdash t:A\multimap
B}{\Gamma,\Delta\vdash(ts):B}(\multimap\mbox{E})$.

(a) Typing rules

$\Gamma$$A$$\Delta$$B$$\Longrightarrow$$\Gamma$$A^{\bot}$$\Delta$$B$$(\multimap
I)$$A$$\Gamma$$A^{\bot}$$B$$\Delta$$\Longrightarrow$$\Gamma$$B$$\Delta$$(\multimap
E)$

(b) Cowordism representation

Figure 5: Cowordism representation of linear $\lambda$-calculus

A linear signature, or, simply, a signature, $\Sigma$ is a triple
$\Sigma=(N,C,\mathfrak{T})$, where $N$ is a finite set of atomic types, $C$ is
a finite set of constants and $\mathfrak{T}$ is a function assigning to each
constant $c\in C$ a linear implicational type $\mathfrak{T}(c)\in Tp(N)$. We
say that $\Sigma$ is a signature over the set $N$ of atomic types.

Typing judgements of the form $\vdash c:\mathfrak{T}(c)$, where $c\in C$, are
called signature axioms of $\Sigma$.

Typing judgements are derived using type inference rules in Figure 5(a) (which
happen to be natural deduction rules of ILL decorated with $\lambda$-terms).
Given a signature $\Sigma$, we say that a typing judgement is derivable in
$\Sigma$ if it is derivable from axioms of $\Sigma$ by rules of linear
$\lambda$-calculus. We write in this case $\Gamma\vdash_{\Sigma}t:A$.

It is well known [BBdPH92] that any symmetric monoidal closed category, in
particular, a compact closed category, provides a denotational model for
linear $\lambda$-calculus (invariant under $\beta\eta$-equivalence). We
specialize to the concrete case of the category ${\bf Coword_{T}}$ of
cowordisms over the given alphabet $T$.

So, let the sets $N$ and $T$ of literals and terminal symbols respectively be
given. An interpretation $\xi$ of linear types over $N$ in ${\bf Coword_{T}}$
consists in assigning to each atomic type $p\in N$ a boundary $\xi(p)$. This
is extended to all types in $Tp(N)$ by $\xi(A\multimap
B)=\xi(A)^{\bot}\otimes\xi(B)$.

Now, given a linear signature $\Sigma$ over $N$ and $T$, we want to extend the
interpretation to derivable typing judgements, so that a judgement of the form
$x_{1}:A_{1},\ldots,x_{n}:A_{n}\vdash t:A$ is interpreted as a cowordism of
the form $\xi(A_{1})\otimes\ldots\otimes\xi(A_{n})\to\xi(A)$.

Interpretation of typing judgements consists in assigning, for each constant
$c$ and axiom $\vdash c:A$ of $\Sigma$ (here $A=\mathfrak{T}(c)$), a multiword
$\xi(c)$ with boundary $\xi(A)$, which we identify with a cowordism
$\xi(c):{\bf 1}\to\xi(A)$.

This is extended to all typing judgements derivable in $\Sigma$ by induction
on type inference rules. The (Id) axiom $x:A\vdash x:A$ is interpreted as the
identity cowordism $\mbox{id}_{\xi(A)}$. Typing judgements obtained by the
($\multimap\mbox{I}$) or ($\multimap\mbox{E}$) rules are interpreted according
to Figure 5 (where the symbol $\xi$ is omitted).

In the sequel we often will abuse notation and denote a type in $Tp(N)$ and
its interpretation in ${\bf Coword_{T}}$ with the same symbol, as is customary
in the literature.

##  5 String abstract categorial grammars

The string signature $Str_{T}$ over $T$, where $T$ is a finite alphabet, is
the linear signature with a single atomic type $O$, the alphabet $T$ as the
set of constants and the typing assignment $\mathfrak{T}(c)=O\multimap
O~{}\forall c\in T.$ We denote the type $O\multimap O$ as $str$.

Any word $w=a_{1}\ldots a_{n}$ in the alphabet $T$ can be represented as the
term $\rho(w)=a_{1}\circ\ldots\circ a_{n}$, where $a_{1}\circ\ldots\circ
a_{n}=(\lambda x.a_{1}(\ldots(a_{n}(x))\ldots))$, and
$\vdash_{Str_{T}}\rho(w):str$.

Moreover, it can be shown that, for any term $t$, if $\vdash_{Str_{T}}t:str$
then $t\sim_{\beta\eta}\rho(w)$ for some $w\in T^{*}$.

The cowordism representation $\xi_{0}$ of the string signature $Str_{T}$ over
the alphabet $T$ is given by the following interpretation in ${\bf
Coword_{T}}$.

For the atomic type $O$ we put $\xi_{0}(O)=\\{1\\}$,
$(\xi_{0}(O))_{l}=\emptyset$. (I.e. $\xi_{0}(O)$ is a single-point boundary).

Then for each axiom $\vdash c:O\multimap O$, where $c\in T$, we put
$\xi_{0}(c)=[1,c,2]$. The latter is the multiword with boundary
$O^{\bot}\otimes O$ consisting of a single edge labeled with $c$: $c$.

Given linear signatures $\Sigma_{i}=(N_{i},C_{i},\mathfrak{T}_{i})$, $i=1,2$,
a homomorphism of signatures $\phi:\Sigma_{1}\to\Sigma_{2}$ is a pair of maps

$\phi_{Tp}:Tp(N_{1})\to
Tp(N_{2}),\quad\phi_{Tm}:\Lambda(X,C_{1})\to\Lambda(X,C_{2}),$

such that $\phi_{Tp}(A\multimap B)=\phi_{Tp}(A)\multimap\phi_{Tp}(B)$,
$\phi_{Tm}(ts)=(\phi_{Tm}(t)\phi_{Tm}(s))$, $\phi_{Tm}(\lambda x.t)=(\lambda
x.\phi_{Tm}(t))$, $\phi_{Tm}(x)=x$ for $x$ a variable, and for any $c\in
C_{1}$ it holds that
$\vdash_{\Sigma_{2}}\phi_{Tm}(c):\phi_{Tp}(\mathfrak{T}(c))$.

An abstract categorial grammar over string signature (string ACG) $G$ is a
tuple $G=(\Sigma_{abstr},T,\phi,S)$, where $\Sigma_{abstr}$, the abstract
signature, is a linear signature, $T$ is a finite alphabet of terminal
symbols, $\phi:\Sigma_{abstr}\to Str_{T}$, the lexicon, is a homomorphism of
signatures, and $S$, the initial type, is an atomic type of $\Sigma_{abstr}$
with $\phi_{Tp}(S)=str$. We say that $G$ is a string ACG over $T$.

The string language $L(G)$ generated by a string ACG $G$ is the set of words
$L(G)=\\{w\in T^{*}|~{}\exists
t~{}\phi_{Tm}(t)\sim_{\beta\eta}\rho(w)\&\vdash_{\Sigma_{abstr}}t:S\\}$.

In the setting as above, the cowordism representation $\xi_{0}$ of $Str_{T}$
immediately gives us an interpretation $\xi$ of the abstract signature
$\Sigma$ in the category ${\bf Coword_{T}}$ of cowordisms over $T$, obtained
as the composition $\xi=\xi_{0}\circ\phi$.

That is, for any type $A\in Tp(\Sigma)$ we put $\xi(A)=\xi_{0}(\phi_{Tp}(A))$,
and for any signature axiom $\vdash c:\mathfrak{T}(c)$ of $\Sigma$ we put
$\xi(c)=\xi_{0}(\phi_{Tm}(c))$. The latter is a multiword with boundary
$\xi(\phi_{Tp}(\mathfrak{T}(c)))=\xi_{0}(\mathfrak{T}(c))$.

Because $\phi$ is a homomorphism of signatures, an easy induction on
derivation shows that for any typing judgement
$x_{1}:A_{1},\ldots,x_{n}:A_{n}\vdash t:A$ derivable in $\Sigma$, its
interpretation coincides with the interpretation of the typing judgement
$x_{1}:\phi_{Tp}(A_{1}),\ldots,x_{n}:\phi_{Tp}(A_{n})\vdash\phi_{Tm}(t):\phi_{Tp}(A)$
(which is derivable in $Str_{T}$).

In particular, for the initial type $S$ we have
$\xi(S)=\xi_{0}(O^{\bot}\otimes O)$ is a two-point boundary, and any derivable
typing judgement of the form $\vdash_{\Sigma}t:S$ is interpreted as a single-
edge multiword, labeled with $\rho(\phi_{Tm}(t))$ .

$\vdash JOHN:NP,\quad\vdash MARY:NP,\quad\vdash LOVES:NP\multimap NP\multimap
S$,

$\vdash MADLY:(NP\multimap S)\multimap NP\multimap S,$
$\vdash WHOM:(NP\multimap S)\multimap NP\multimap NP$.

(a) Axioms

$\phi_{Tp}(NP)=\phi_{Tp}(S)=O\multimap O$,
$\phi_{Tm}(JOHN)=\mbox{John},\quad\phi_{Tm}(MARY)=\mbox{Mary},\quad\phi_{Tm}(JIM)=\mbox{Jim}$,
$\phi_{Tm}(LOVES)=\lambda xy.(y\circ\mbox{loves}\circ
x),\quad\phi_{Tm}(MADLY)=\lambda fx.((f\cdot x)\circ(\mbox{madly}))$,
$\phi_{Tm}(WHOM)=\lambda fx.(x\circ(\mbox{whom})\circ(f\cdot(\lambda y.y))).$

(b) Lexicon

$NP$John$JOHN$$NP$Mary$MARY$loves$NP^{\bot}$$NP^{\bot}$$S$$LOVES$

madly$S^{\bot}$$S$$NP$$NP^{\bot}$$MADLY$

$S^{\bot}$whom$NP$$NP^{\bot}$$NP$$WHOM$

(c) Cowordism representation

Figure 6: Cowordism representation of a string ACG

We give a concrete example of a string ACG and its cowordism representation.

We consider the set of atomic types $\\{NP,S\\}$ and the terminal alphabet
$\\{\mbox{John},\mbox{Mary},\mbox{loves},\mbox{madly},\mbox{whom}\\}$.

The signature axioms and the lexicon are collected in Figures 6(a), 6(b),
while the translation to cowordisms is shown in Figure 6(c). We rotated
pictures of cowordisms $90^{\circ}$ counterclockwise, so that outgoing
boundaries are shown on the top, with the ordering of vertices from left to
right.

We generate the noun phrase “Mary whom John loves madly”, represented as a
term of type $NP$. The derivation is shown in Figure 7(a); for convenience, we
break it into five consecutive steps. A step-by-step translation into the
language of cowordisms is shown in Figures 7(b), 8(a) with omission of the
last step, which should become clear by the end.

1) $\frac{x:NP\vdash x:NP\quad\vdash LOVES:NP\multimap MP\multimap
S}{x:NP\vdash LOVES\cdot x:NP\multimap S}~{}(\multimap\mbox{E})$

2) $\cfrac{x:NP\vdash LOVES\cdot x:NP\multimap S\quad\quad\vdash
MADLY:(NP\multimap S)\multimap NP\multimap S}{x:NP\vdash MADLY(LOVES\cdot
x):NP\multimap S}~{}(\multimap\mbox{E})$

3) $\cfrac{\cfrac{\vdash JOHN:NP\quad x:NP\vdash MADLY(LOVES\cdot
x):NP\multimap S}{x:NP\vdash MADLY(LOVES\cdot
x)JOHN:S}~{}(\multimap\mbox{E})}{\vdash\lambda x.MADLY(LOVES\cdot
x)JOHN:NP\multimap S}~{}(\multimap\mbox{I})$

4) $\cfrac{\vdash\lambda x.MADLY(LOVES\cdot x)JOHN:NP\multimap
S\quad\quad\vdash WHOM:(NP\multimap S)\multimap NP\multimap NP}{\vdash
WHOM(\lambda x.MADLY(LOVES\cdot x)JOHN):NP\multimap NP}~{}(\multimap\mbox{E})$

5) $\cfrac{\vdash MARY:NP\quad\vdash WHOM(\lambda x.MADLY(LOVES\cdot
x)JOHN):NP\multimap NP}{\vdash(WHOM(\lambda x.MADLY(LOVES\cdot x)JOHN))\cdot
MARY:NP}~{}(\multimap\mbox{E})$

(a) Derivation

1)$NP$$NP$loves$NP^{\bot}$$NP^{\bot}$$S$$\Longrightarrow$$NP$loves$NP^{\bot}$$S$$=$
loves$NP$$NP^{\bot}$$S$

2)loves$NP$$NP^{\bot}$$S$$S^{\bot}$$NP$madly$S$$NP^{\bot}$$\Longrightarrow$

loves$NP$madly$S$$NP^{\bot}$$=$lovesmadly$NP$$NP^{\bot}$$S$

(b) Cowordism representation, steps 1)-2)

Figure 7: ACG representation example

lovesmadly$NP$$NP^{\bot}$$S$3)$NP$John$\Longrightarrow$“loves”madly$NP$$S$“John”

$=$John lovesmadly$NP$$S$$\Longrightarrow$$S$$NP^{\bot}$John lovesmadly

4)$S$$NP^{\bot}$John
lovesmadly$S^{\bot}$whom$NP$$NP^{\bot}$$NP$$\Longrightarrow$

“John loves”“madly”“whom”$NP^{\bot}$$NP$$=$

$NP$$NP^{\bot}$whom John loves madly

(a) Cowordism representation, steps 2)-4) Figure 8: ACG representation example
(continued)

##  6 Linear logic grammars

Recall that, given a set $N$ of positive literals or atoms, the set $Fm=Fm(N)$
of multiplicative linear logic (MLL) formulas over $N$ is defined by the
grammar $Lit::=N|N^{\bot}$, $Fm::=Lit|Fm\otimes Fm|Fm\parr Fm$.

Connectives $\otimes$ and $\parr$ are called respectively tensor (also times)
and cotensor (also par).

Linear negation $(.)^{\bot}$ is not a connective, but is definable by
induction as $(P^{\bot})^{\bot}=P$, for $P\in N$, and $(A\otimes
B)^{\bot}=B^{\bot}\parr A^{\bot}$, $(A\parr B)^{\bot}=B^{\bot}\otimes
A^{\bot}$.

Note that, somewhat non-traditionally, we follow the convention that negation
flips tensor/cotensor factors, typical for noncommutative systems. This does
not change the logic (the formulas $A\otimes B$ and $B\otimes A$ are provably
equivalent), but is more consistent with the intended interpretation in the
category of cowordisms.

An ${\bf MLL}$ sequent (over the alphabet $N$) is a finite sequence of ${\bf
MLL}$ formulas (over $N$). The sequent calculus for ${\bf MLL}$ [Gir87] is
shown in Figure 9(a).

$\vdash X^{\bot},X~{}(\mbox{Id})$, $\frac{\vdash\Gamma,X\quad\vdash
X^{\bot},\Delta}{\vdash\Gamma,\Delta}~{}(\mbox{Cut})$,
$\frac{\vdash\Gamma,X,Y,\Delta}{\vdash\Gamma,Y,X,\Delta}~{}(\mbox{Ex})$,
$\frac{\vdash\Gamma,X,Y}{\vdash\Gamma,X\parr
Y}~{}(\parr)\quad\frac{\vdash\Gamma,X\quad\vdash
Y,\Delta}{\vdash\Gamma,X\otimes Y,\Delta}~{}{}(\otimes)$.

(a) MLL sequent calculus

$\sigma$$\tau$$\Gamma$$X$$\Delta$$X^{\bot}$$\Rightarrow$$\sigma$$\Gamma$$\tau$$\Delta$$(\mbox{Cut})$$\sigma$$\Gamma$$X$$\Delta$$Y$$\Rightarrow$$\sigma$$\Gamma$$X$$\Delta$$Y$$(\mbox{Ex})$

$\sigma$$\Gamma$$X$$Y$$\Rightarrow$$\sigma$$\Gamma$$X\parr
Y$$(\parr)$$\sigma$$\tau$$\Gamma$$X$$\Delta$$Y$$\Rightarrow$$\sigma$$\Gamma$$\tau$$\Delta$$X\otimes
Y$$(\otimes)$

(b) Cowordism representation

Figure 9: Cowordism representation of MLL

It is well known [See89] that semantics of MLL proof theory is provided by
$*$-autonomous categories. Compact categories are a particular (degenerate)
case of these, so the category ${\bf Coword}_{T}$ of cowordisms over an
alphabet $T$ allows interpretation of MLL (invariant under cut-elimination).

Just as in the case of linear $\lambda$-calculus (and ILL), an interpretation
$\xi$ consists in assigning to every atom $A\in N$ a boundary $\xi(A)$. This
is extended to all formulas in $Fm(N)$ by $\xi(A\otimes B)=\xi(A\parr
B)=\xi(A)\otimes\xi(B)$ and $\xi(A^{\bot})=\xi(A)^{\bot}$ (note that the
extension is well defined).

A sequent $\Gamma=A_{1},\ldots A_{n}$ is interpreted as the cotensor of its
formulas: $\xi(\Gamma)=\xi(A_{1}\parr\ldots\parr
A_{n})=\xi(A_{1})\otimes\ldots\otimes\xi(A_{n})$. A proof $\sigma$ of the
sequent $\vdash\Gamma$ is interpreted as a multiword with boundary
$\xi(\Gamma)$, which we identify with a cowordism $\xi(\sigma):{\bf
1}\to\xi(\Gamma)$. Rules for interpreting sequent calculus proofs are
represented in Figure 9(b) (the symbol $\xi$ omitted and picture rotated
counterclockwise with outgoing boundaries on the top, as before).

Given an interpretation $\xi$ of $Fm(N)$ in the category ${\bf Coword_{T}}$,
we say that a cowordism typing judgement (over $N$ and $T$) is an expression
of the form $\cfrac{\sigma}{\vdash\Gamma}$, where $\Gamma$ is an ${\bf MLL}$
sequent (over $N$), and $\sigma:{\bf 1}\to\xi(\Gamma)$ is a cowordism (over
$T$).

A linear logic grammar LLG $G$ is a tuple $G=(N,\xi,T,Lex,S)$, where $N$,
$\xi$, $T$ are as above, while $Lex$, the lexicon, is a finite set of
cowordism typing judgements over $N$ and $T$, called axioms, and $S\in N$, the
initial type, is a positive literal with $|\xi(S)|=2$ and $(\xi(S))_{l}$ a
singleton.

We say that the cowordism typing judgement $\cfrac{\sigma}{\vdash\Gamma}$ is
derivable in $G$, or that $G$ generates cowordism $\sigma$ of type $\Gamma$ if
there exists a derivation of $\vdash\Gamma$ from axioms of $G$ whose
interpretation is $\sigma$.

Any regular cowordism of the initial type $S$ generated by $G$ is an edge-
labeled graph containing a single edge labeled with a word over $T$. Thus the
set of type $S$ regular cowordisms can be identified with a set of words in
$T^{*}$. The language $L(G)$ generated by $G$ is the set of words labeling
type $S$ regular cowordisms generated by $G$.

###### Theorem 1

A language generated by a string ACG is also generated by an LLG.

Proof Given a string ACG $G=(\Sigma,T,\phi,S)$ over the set $N$ of atomic
types and the terminal alphabet $T$, we identify types of $\Sigma$ with a
subset of the set $Fm(N)$ of MLL formulas using the translation $A\multimap
B=A^{\bot}\parr B$.

Then the cowordism representation $\xi$ of $G$ gives us an interpretation of
$Fm(N)$ in ${\bf Coword_{T}}$. Taking as the lexicon $Lex$ the set of all
cowordism typing judgements $\cfrac{\xi(c)}{\vdash A}$, where $\vdash c:A$ is
an axiom of $\Sigma$, we obtain the LLG $G^{\prime}=(N,\xi,T,Lex,S)$.

By induction on derivations it can be shown that for any cowordism $\sigma$ of
the form $\sigma:\xi(A_{1})\otimes\ldots\otimes\xi(A_{n})\to\xi(A)$, where
$A_{1},\ldots,A_{n},A$ are in $Tp(N)$, the cowordism typing judgement
$\cfrac{\sigma}{\vdash A_{n}^{\bot},\ldots,A_{1}^{\bot},A}$ is derivable in
$G^{\prime}$ iff $\sigma$ is the cowordism representation of some typing
judgement $A_{1},\ldots,A_{n}\vdash A$ derivable in $\Sigma$. (Essentially,
this repeats the proof that ILL is a conservative fragment of MLL.) The
statement follows. $\Box$

It seems reasonable to ask whether the converse is true. We would expect that
the answer is yes, and the formalism of LLG does not add extra expressivity.

##  7 LLG and multiple context-free grammars

We discuss relations between LLG and multiple context-free grammars.

Assume that we are given a finite alphabet $N$ of nonzero arity predicate
symbols called nonterminal symbols and a finite alphabet $T$ of terminal
symbols.

Production is a sequent of the form

$B_{1}(x^{1}_{1},\ldots,x^{1}_{k_{1}}),\ldots,B_{n}(x^{n}_{1},\ldots,x^{n}_{k_{n}})\vdash
A(s_{1},\ldots,s_{k}),$ (3)

where $A,B_{1},\ldots,B_{n}\in N$ have arities $k,k_{1},\ldots,k_{n}$
respectively, $\\{x^{j}_{i}\\}$ are pairwise distinct variables not from $T$,
and $s_{1},\ldots,s_{k}$ are words built of terminal symbols and
$\\{x_{i}^{j}\\}$, so that each of the variables $x^{j}_{i}$ occurs exactly
once in exactly one of $s_{1},\ldots s_{k}$ (here $n$ may be zero).

A multiple context-free grammar (MCFG) [SMFK91] $G$ is a tuple $G=(N,T,S,P)$
where $N,T$ are as above, $P$ is a finite set of productions, and $S\in N$,
the initial symbol, is unary.

The set of predicate formulas derivable in $G$ is defined by the following
induction.

Formula $A(t_{1},\ldots,t_{k})$ is derivable, if there is a production of the
form (3) in $P$, such that
$B_{1}(s^{1}_{1},\ldots,s^{1}_{k_{1}}),\ldots,B_{n}(s^{n}_{1},\ldots,s^{n}_{k_{n}})$
are derivable, and $t_{m}$ is the result of substituting the word $s^{j}_{i}$
for every variable $x^{j}_{i}$ in $s_{m}$, $m=1,\ldots,k$. (The case $n=0$ is
the base of induction.)

The language generated  by an MCFG $G$ is the set of words $w$ for which
$S(w)$ is derivable.

It is well known that any MCFG translates to a string ACG [Sal06], hence to an
LLG as well.

A concrete example of a cowordism representation for an MCFG is given in
Figure 10. Here we have the terminal alphabet $T=\\{a,b\\}$, and nonterminal
symbols $P$, $Q$ and $S$ of arities 2, 2 and 1 respectively. The MCFG is
defined by the six productions in Figure 10(a). It is easy to see that the
above generates the language $\\{wa^{n}wb^{n}|w\in T^{*},n\geq 0\\}$.

Six cowordisms representing the productions are shown in Figure 10(b) (for
better readability, we label vertices with corresponding variables, the
subscripts $l,r$ denoting left and right endpoints respectively).

$\vdash P(\epsilon,\epsilon)~{}(1)$, $\vdash Q(\epsilon,\epsilon)~{}(2)$,
$P(x,y)\vdash P(xa,yb)~{}(3)$, $Q(z,t)\vdash Q(za,ta)~{}(4)$,

$Q(z,t)\vdash Q(zb,tb)~{}(5)$, $Q(z,t),P(x,y)\vdash S(zxty)~{}(6)$.

(a) MCFG

$(1)$$x_{l}$$x_{r}$$y_{l}$$y_{r}$$P$$(2)$$Q$$z_{l}$$z_{r}$$t_{l}$$t_{r}$$(3)$$P$$P$$x_{l}$$x_{r}$$y_{l}$$y_{r}$$x_{l}$$x_{r}$$y_{l}$$y_{r}$$b$$a$$(4)$$Q$$Q$$z_{l}$$z_{r}$$t_{l}$$t_{r}$$z_{l}$$z_{r}$$t_{l}$$t_{r}$$a$$a$$(5)$$Q$$Q$$z_{l}$$z_{r}$$t_{l}$$t_{r}$$z_{l}$$z_{r}$$t_{l}$$t_{r}$$b$$b$$(6)$$z_{l}$$z_{r}$$t_{l}$$t_{r}$$x_{l}$$x_{r}$$y_{l}$$y_{r}$$Q$$P$$S$

(b) Cowordism representation

Figure 10: Cowordism representation of an MCFG

In order to turn these into axioms for an LLG, we have to get rid of the
incoming wires. We make all wires outgoing using the bijection $Hom(X,Y)\cong
Hom({\bf 1},X^{\bot}\otimes Y)$ (which is a particular case of (2), whose
geometric meaning is shown in Figure 4(e)).

###### Theorem 2

A language is generated by an MCFG iff it can be generated by an LLG $G$ with
$\otimes$-free lexicon.

Proof Translation from MCFG to a ($\otimes$-free) LLG is easy, an example has
just been shown. Let us prove the other direction.

For a boundary $X$ and a regular multiword $M$ with boundary $X$, we define
the pattern $pat(M)$ of $M$ as the graph obtained by erasing from $M$ all
letters. The set $Patt(X)$ of all graphs obtained in this way as $M$ varies is
the set of possible patterns of $X$. Note that $Patt(X)$ is finite (maybe
empty).

Now, for any $\pi\in Patt(X)$ choose an enumeration of edges in $\pi$ and
introduce a $k$-ary predicate symbol $X^{\pi}$, where $k$ is the number of
edges in $\pi$ (obviously, $k$ is the same for all possible patterns of $X$).
Then any regular multiword $M$ with boundary $X$ can be unambiguously
represented as the predicate formula $X^{\pi}(w_{1},\ldots,w_{k})$, where
$\pi=pat(M)$, and $w_{i}$ is the word labeling the $i$-th edge of $\pi$ in
$M$, $i=1,\ldots,k$.

In a similar way, any cowordism $\sigma:X_{1}\otimes\ldots\otimes X_{n}\to X$
can be encoded into a finite set of productions. (The above described
representation of a multiword is a particular case when $n=0$).

Fix possible patterns $\pi_{1},\ldots,\pi_{n}$ of $X_{1},\ldots X_{n}$
respectively. There exists at most one possible pattern $\pi$ of $X$ such
that, whenever $pat(M_{i})=\pi_{i}$, $i=1,\ldots,n$, it holds that
$pat(\sigma\circ(M_{1}\otimes\ldots\otimes M_{n}))=\pi$. If such a $\pi$ does
not exist, then the chosen combination of patterns composed with $\sigma$ does
not produce a regular multiword and is irrelevant for us.

Otherwise choose fresh variables $x^{i}_{j}$, $j=1,\ldots,k_{i}$, where
$k_{i}$ is the number of edges in $\pi_{i}$, $i=1,\ldots,n$. Let $M_{i}$ be
the multiword obtained from $\pi_{i}$ by labeling the $j$-th edge with
$x^{i}_{j}$. Let $M=\sigma\circ(M_{1}\otimes\ldots\otimes M_{n})$. It is a
multiword with $pat(M)=\pi$. Let $s_{j}$ be the word labeling the $j$-th edge
of $M$, $j=1,\ldots,k$, where $k$ is the number of edges in $\pi$. The
interaction of $\sigma$ with the chosen combination of patterns is represented
as the production
$X^{\pi_{1}}_{1}(x^{1}_{1},\ldots,x^{1}_{k_{1}}),\ldots,X^{\pi_{n}}_{n}(x^{n}_{1},\ldots,x^{n}_{k_{n}})\vdash
X^{\pi}(s_{1},\ldots,s_{k})$.

Let $Prod(\sigma)$ be the set of all productions obtained in this way from
$\sigma$ by varying possible patterns of $X_{1},\ldots,X_{n}$. Again, note
that $Prod(\sigma)$ is finite.

Now, let $G=(N,\xi,T,S,Lex)$ be a $\otimes$-free LLG. The symbol $\xi$ will be
omitted in what follows.

We know that a sequent $\vdash\Gamma,A\parr B$ is derivable in MLL iff
$\vdash\Gamma,A,B$ is. And since axioms of $G$ do not use any connective other
than $\parr$, it follows that $G$ is equivalent to a grammar that does not use
any logical connective at all. By cut-elimination, any derivation of the
sequent $\vdash S$ from axioms of $G$ is equivalent to a derivation not using
any logical rule either, i.e. to a one using only the Cut rule.

We construct an equivalent MCFG $G^{\prime}=(N^{\prime},T,S^{\prime},P)$, by
taking the set of nonterminal symbols $N^{\prime}=\\{A^{\pi}|~{}A\in N\cup
N^{\bot},\pi\in Patt(A)\\}$, and writing for each axiom $\alpha\in Lex$ of the
form $\cfrac{\sigma}{\vdash A_{1},\ldots,A_{n}}$, where $A_{1},\ldots,A_{n}$
are literals, all productions representing cowordisms

$\sigma_{i}:A_{i+1}^{\bot}\otimes\ldots\otimes A_{n}^{\bot}\otimes
A_{1}^{\bot}\otimes\ldots\otimes A_{i-1}^{\bot}\to A_{i},\quad i=1,\ldots,n,$

obtained from $\sigma$ using correspondence (2) and symmetry transformations.

We put $Prod(\alpha)=\bigcup\limits_{i}Prod(\sigma_{i})$, and then
$P=\bigcup\limits_{\alpha\in Lex}Prod(\alpha)$.

As for the initial symbol $S^{\prime}$ of $G^{\prime}$, we observe that there
is only one possible pattern $s$ for the boundary $S$, and we put
$S^{\prime}=S^{s}$. An easy induction on derivations shows that $G$ and
$G^{\prime}$ generate the same language. $\Box$

As a corollary we obtain the known result that any second order ACG generates
a multiple context-free language [Sal06]. Thus, we gave a new, geometric
proof, arguably quite simple and intuitive.

##  8 Backpack problem

An LLG of a general form can generate an NP-complete language, just as an ACG
(see [YK05]). We give the following, last example as another try to convince
the reader that the geometric language of cowordisms is indeed intuitive and
convenient for analyzing language generation.

We will consider the backpack problem in the form of the subset sum problem
(SSP): given a finite sequence $s$ of integers, determine if there is a
subsequence $s^{\prime}\subseteq s$ such that $\sum\limits_{z\in
s^{\prime}}z=0$. It is well known [MT90] that SSP is NP-complete. We will
generate by means of an LLG an NP-complete language, essentially representing
solutions of SSP.

We represent integers as words in the alphabet $\\{+,-\\}$, we call them
numerals. An integer $z$ is represented (non-uniquely) as a word for which the
difference of $+$ and $-$ occurrences equals $z$. We say that a numeral is
irreducible, if it consists only of pluses or only of minuses.

We represent finite sequences of integers as words in the alphabet
$T=\\{+,-,\bullet\\}$, with $\bullet$ interpreted as a separation sign. Thus a
word in this alphabet should be read as a list of numerals separated by
bullets. When all numerals in the list are irreducible, we say that the list
is irreducible.

Now consider two positive literals $H,S$ and interpret each of them as the
boundary $X$ of cardinality 2 with $X_{l}=\\{2\\}$.

First we construct a system of cowordisms which, together with symmetry
transformations, generates all irreducible lists of integers that sum to zero.
The three cowordisms $cons:S\otimes S\to S$, $push:S\otimes S\to S\otimes S$,
$close:{\bf 1}\to S$ are shown in Figure 11(a).

$S$$S$$S$$cons:$$S$$S$$+$$S$$S$$-$$push:$$\bullet$$S$$close:$

(a) Cowordisms for lists summing to zero

$H$$S$$S$$open_{H}:$$\bullet$$H$$close_{H}:$$H$$H$$+$$push_{+}:$$H$$H$$-$$push_{-}:$

(b) Cowordisms for deceptive slots

Figure 11: Encoding the backpack problem

The cowordism $cons$, by iterated compositions with itself, generates lists
with arbitrary many empty slots, then $push$ fill the slots with pluses and
minuses (always in pairs), and $close$ closes them. All generated lists will
sum to zero, and all irreducible lists summing to zero will be generated.

Now, in order to generate solutions of SSP we need some extra, “deceptive”
slots, which contain elements not summing to zero. These slots will be
represented by the boundary $H$. The corresponding cowordisms
$open_{H}:H\otimes S\to S$, $push_{+}:H\to H$, $push_{-}:H\to H$,
$close_{H}:{\bf 1}\to H$ are shown in Figure 11(b). The cowordism $open_{H}$
adds deceptive slots to the list, $push_{-}$ and $push_{+}$ fill them with
arbitrary numerals, and $close_{H}$ closes them.

Although, pedantically speaking, the above system is not an LLG according to
our definitions, we obtain an LLG by making all wires outgoing, just as in the
above discussion of MCFG. Let us denote the generated language as $L_{0}$.

It is easy to see that $L_{0}$ membership problem is, essentially, SSP. More
precisely SSP polynomially reduces to $L_{0}$ membership problem. Indeed, a
sequence $s$ of integers is a solution of SSP iff the corresponding
irreducible list is in $L_{0}$. It follows that $L_{0}$ is NP-hard.

On the other hand, it is also easy to see that $L_{0}$ membership problem is
itself in NP. Indeed, in order to show that a list $s$ is in $L_{0}$ it is
sufficient to demonstrate a sequence of cowordisms from Figures 11(a), 11(b)
generating $s$, and the number of cowordisms in such a sequence clearly is
bounded linearly in the size of $s$. Thus $L_{0}$ is, in fact, NP-complete.

## References

  * [Abr05] Samson Abramsky.  Abstract scalars, loops, and free traced and strongly compact closed categories.  In José Luiz Fiadeiro, Neil Harman, Markus Roggenbach, and Jan Rutten, editors, Algebra and Coalgebra in Computer Science, pages 1–29, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
  * [AC09] Samson Abramsky and Bob Coecke.  Categorical quantum mechanics.  In Handbook of Quantum Logic and Quantum Structures, pages 261–323. Elsevier, 2009.
  * [Bar85] Hendrik Pieter Barendregt.  The Lambda Calculus - Its Syntax and Semantics, volume 103 of Studies in logic and the foundations of mathematics.  North-Holland, 1985.
  * [BBdPH92] P. N. Benton, Gavin M. Bierman, Valeria de Paiva, and Martin Hyland.  Linear lambda-calculus and categorial models revisited.  In Egon Börger, Gerhard Jäger, Hans Kleine Büning, Simone Martini, and Michael M. Richter, editors, Computer Science Logic, 6th Workshop, CSL ’92, San Miniato, Italy, September 28 - October 2, 1992, Selected Papers, volume 702 of Lecture Notes in Computer Science, pages 61–84. Springer, 1992.
  * [BD95] John C. Baez and James Dolan.  Higher-dimensional algebra and topological quantum field theory.  Journal of Mathematical Physics, 36(11):6073–6105, 1995.
  * [BS11] J. Baez and M. Stay.  Physics, topology, logic and computation: a Rosetta Stone.  In Bob Coecke, editor, New Structures for Physics, pages 95–172, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
  * [CSC10] Bob Coecke, Mehrnoosh Sadrzadeh, and Stephen Clark.  Mathematical foundations for a compositional distributional model of meaning.  In Linguistic Analysis (Lambek Festschrift), pages 345–384, 2010\.
  * [CSC13] Bob Coecke, Mehrnoosh Sadrzadeh, and Stephen Clark.  The Frobenius anatomy of word meanings I: subject and object relative pronouns.  Journal of Logic and Computation, 23(6):1293–1317, 2013.
  * [dG01] Philippe de Groote.  Towards abstract categorial grammars.  In Proceedings of 39th Annual Meeting of the Association for Computational Linguistics, pages 148–155, 2001.
  * [Gir87] Jean-Yves Girard.  Linear logic.  Theoretical Computer Science, 50:1–102, 1987.
  * [KL80] G.M. Kelly and M.L. Laplaza.  Coherence for compact closed categories.  Journal of Pure and Applied Algebra, 19:193–213, 1980.
  * [Lam58] Joachim Lambek.  The mathematics of sentence structure.  The American Mathematical Monthly, 65(3):154–170, 1958.
  * [Lam99] J. Lambek.  Type grammar revisited.  In Alain Lecomte, François Lamarche, and Guy Perrier, editors, Logical Aspects of Computational Linguistics, pages 1–27, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.
  * [MP12] Vedrana Mihaliček and Carl Pollard.  Distinguishing phenogrammar from tectogrammar simplifies the analysis of interrogatives.  In Philippe de Groote and Mark-Jan Nederhof, editors, Formal Grammar, pages 130–145, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
  * [MT90] Silvano Martello and Paolo Toth.  Knapsack Problems: Algorithms and Computer Implementations.  John Wiley & Sons, Inc., USA, 1990.
  * [Mus07] R.A. Muskens.  Separating syntax and combinatorics in categorial grammar.  Research on Language and Computation, 5(3):267–285, 2007.  Pagination: 17.
  * [Sal06] Sylvain Salvati.  Encoding second order string ACG with deterministic tree walking transducers.  In Shuly Wintner, editor, The 11th conference on Formal Grammar, FG Online Proceedings, pages 143–156, Malaga, Spain, 2006. Paola Monachesi; Gerald Penn; Giorgio Satta; Shuly Wintner, CSLI Publications.
  * [See89] R.A.G. Seely.  Linear logic, *-autonomous categories and cofree coalgebras.  In Categories in Computer Science and Logic, pages 371–382. American Mathematical Society, 1989.
  * [SMFK91] Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami.  On multiple context-free grammars.  Theoretical Computer Science, 88(2):191–229, 1991.
  * [Sto16] Robert E. Stong.  Notes on Cobordism Theory.  Princeton University Press, 2016.
  * [YK05] Ryo Yoshinaka and Makoto Kanazawa.  The complexity and generative capacity of lexicalized abstract categorial grammars.  In Philippe Blache, Edward Stabler, Joan Busquets, and Richard Moot, editors, Logical Aspects of Computational Linguistics, pages 330–346, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.


# Scene Completeness-Aware Lidar Depth Completion for Driving Scenario

###### Abstract

This paper introduces Scene Completeness-Aware Depth Completion (SCADC) to
complete raw lidar scans into dense depth maps with fine and complete scene
structures. Recent sparse depth completion for lidars only focuses on the
lower scenes and produces irregular estimations on the upper because existing
datasets, such as KITTI, do not provide groundtruth for upper areas. These
areas are considered less important since they are usually sky or trees of
less scene understanding interest. However, we argue that in several driving
scenarios such as large trucks or cars with loads, objects could extend to the
upper parts of scenes. Thus depth maps with structured upper scene estimation
are important for RGBD algorithms. SCADC adopts stereo images that produce
disparities with better scene completeness but are generally less precise than
lidars, to help sparse lidar depth completion. To our knowledge, we are the
first to focus on scene completeness of sparse depth completion. We validate
our SCADC on both depth estimate precision and scene-completeness on KITTI.
Moreover, we experiment on less-explored outdoor RGBD semantic segmentation
with scene completeness-aware D-input to validate our method.

Index Terms—  Sparse Depth Completion, Driving Scenario, Scene Completeness,
Sensor Fusion.

##  1 Introduction

Autonomous driving usually adopts lidars as the main depth acquisition sensors
due to their high precision and practicability on outdoor depth sensing.
However, lidar scans are limited to number of scanlines and spatial
resolutions, and thus they are sparse when aligned with images. Recent
research on lidar depth completion for autonomous driving tries to complete
sparse lidar depth into a dense map [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] using
KITTI Depth Completion Dataset [12].

However, their depth map processing and evaluations always crop out the upper
side of maps for two reasons. First, these upper side areas are usually sky or
trees of low scene understanding interest. Second, lidars are active sensors
with limited scanlines and smaller vertical field-of-view than cameras. Thus,
most lidar scans do not span the whole image height and are concentrated on
the lower parts of images. For KITTI, topside 1/3 to 1/4 areas are unscanned
by lidars. Also, KITTI’s depth groundtruth is acquired by accumulating 3D
point clouds with a 64-scanline lidar. Hence their groundtruth are also
concentrated on the lower parts of images. Both of KITTI’s quantitative and
qualitative evaluations focus only on the lower parts.

Fig. 1: Comparison of depth from stereo matching network [13], depth
completion network [4], and our SCADC. Our results leverage advantages of both
stereo matching, which have more structured upper scenes, and lidars, which
have more precise depth measurements.

Nevertheless, upper scenes are especially important under several autonomous
driving scenarios, such as a huge truck beside or just in front occupies a
large area of the upper scene when close enough. Traffic signs or lights are
important road structures extending to the upper parts. Although more and more
research focuses on multi-modal learning from images and depth, scene
incompleteness issue is mostly ignored for the following reasons. First, depth
completion is treated as a standalone task in previous works without
validating their completed depth maps on other scene understanding tasks such
as semantic segmentation. Second, not enough data of large objects extending
to the upper scenes are collected, and thus the issue is generally omitted.
However, autonomous driving needs to take care of all kinds of scenarios to
prevent accidents and thus needs more attention to scene completeness issue.

In contrast, stereo matching produces disparity maps with much structured
upper scenes because disparities are derived from images. However, stereo
matching is known for less reliable depth measurements for far-range sensing
and edge bleeding artifact [14], which produces distorted shapes.

In this work, we leverage the completeness of disparity maps to help sparse
depth completion. To our knowledge, we are the first one focusing on the scene
completeness issue of depth completion. Our Scene Completeness-Aware Depth
Completion (SCADC) fuses depth estimations from a stereo matching network and
a lidar depth completion network. We propose Attentional Point Confidence
(APC) to regress confidence maps to fuse multi-modal information. Later, we
use a stacked hourglass network to refine estimations stage by stage with
groundtruth. Output examples are in Fig. 1. We use both quantitative and
qualitative comparisons to validate that our SCADC combines the advantages of
stereo cameras and lidars, producing both scene completeness-aware and precise
depth maps.

Unlike previous works that treat depth completion as a standalone task, we
further validate our scene completeness-aware depth on semantic segmentation.
We use SSMA [15], a high-performing outdoor RGB-D semantic segmentation
framework, as the baseline to show that our recovered depth could help better
scene understanding.

##  2 Related Work

Sparse Depth Completion. Recent work of sparse depth completion works on
completing lidar depth using real-world data from KITTI Depth Completion
Benchmark. Sparse-to-Dense [2] stacks sparse depth maps and images to form a
4-channel input to a ResNet-based depth completion network. SSDC [4] uses ego-
pose coherence with a photometric loss to regress depth. CSPN [16] and Non-
local [17] adopt convolutional spatial propagation to enhance local
information. Other studies, such as Deep-Lidar [3] and PwP [18] adopt an extra
surface normal regression to help the depth estimation. However, these methods
either crop out the upper scene of depth maps or produce random structures on
the upper areas since KITTI only provides groundtruth for lower scenes.
Besides, they work on depth completion alone without further vision
applications using their depth maps. By contrast, we utilize scene
completeness of disparity maps to help depth completion. In addition, we use
our completed depth maps to help outdoor RGBD semantic segmentation, which
further shows the values of depth completion.

Fig. 2: Network pipeline of our SCADC. Fig. 3: Structure of APC module and
Sparisty Attentional Convolution (SAConv) [5]. $\odot$ is for point-wise
product.

Stereo Matching. Stereo matching is a fundamental problem in computer vision.
Traditional SGM and variants [19, 20, 21, 22] match left/right frame features
and output sparse disparity estimations. Recent stereo matching methods [13,
23, 24] using neural networks could estimate dense disparity maps. They
usually aggregate features into a cost volume and then apply 3D convolutions
to regress disparities. The estimated dense disparities have more structured
upper scenes than lidar completion since they are directly derived from image
space with upper scene details. However, stereo matching usually suffers from
edge bleeding that estimated disparities bleed out from object contours and
form distorted areas [25, 14]. Further, stereo matching-based methods are
unreliable for long-range sensing or areas without textures, and in general
they produces depth less precise than lidar measurements. Our SCADC combines
advantages of preciseness of lidars at lower scenes and structured upper
scenes of stereo matching to better utilize the two modalities.

RGBD Semantic Segmentation. There are much fewer works on RGBD outdoor
semantic segmentation than indoors since high-quality outdoor depth maps are
hard to get to match information from image and depth domains. SSMA [15]
combines two AdapNet++ [15] branches and densely fuses information from images
and depth encoders with a decoder to regress the depth map. We adopt SSMA and
validate completed depth from our SCADC on outdoor semantic segmentation.

##  3 Methods

The whole network design of our SCADC is in Fig. 2. Our goal is to construct a
network for sensor fusion, which takes advantage of depth from stereo matching
with more structured upper scenes, and depth from lidar completion with higher
precision, to generate both scene completeness-aware and precise depth maps.

PSMNet [13] and SSDC [4] are adopted as our base methods for stereo matching
and lidar completion respectively. We use the estimated depth maps from two
modalities, $D_{stereo}$ and $D_{lidar}$, as inputs to our SCADC. SCADC
consists of two parts, multi-modal fusion and regression with a stacked
hourglass network.

At the multi-modal fusion stage, we utilize the early fusion strategy. Early
fusion incorporates multi-modal information before an encoder stage and has
the advantage of retaining finer local structures and neighborhood
relationships. Opposed to early fusion, late fusion is usually adopted for
multi-modal learning with modalities from different domains to capture higher-
level semantics, such as fusing information of images and depth [5, 26]. Our
SCADC operates information fusion only on the depth domain, and thus early
fusion of retaining local features and structures is more desirable.

We propose a novel confidence regression module, Attentional Point Confidence
(APC), to estimate the pixel-level confidence of lidars,
$M_{lidar}\in[0,1]^{H\times W}$, where $H$ and $W$ are height and width of
inputs. APC decides for each pixel which modality is more probable to estimate
more reliable depth. Previous works [3, 27] also use confidence maps for RGBD
fusion without direct supervision on confidence regression. However, for
stereo cameras/lidars fusion, since we have priors that depth from stereo
matching is more structured on upper scenes and depth from lidar scans is more
precise in general, using direct supervision on confidence regression could
make the network generate better confidence maps of maintaining and combining
both advantages from stereo cameras and lidars.

We create guiding confidence $M_{g}$ from the raw lidar scans. Lidar
measurements are comparatively precise, so pixel positions at raw lidar points
should have higher confidence. We set their scores to 1. Next, the depths of
neighboring pixels are generally similar, so we dilate confidence at each raw
lidar point using Gaussian kernels to obtain $M_{g}$. Kernel size and variance
are based on point density of raw lidar scans. We find density along a
scanline for KITTI is 44.6% at the center and 30.6% near the left/right side.
Thus, we use a $3\times 3$ kernel and choose a variance which makes confidence
scores drop to half with 1-pixel distance from the center. $M_{g}$ provides
better priors of confidence maps for learning. Note that (1) $M_{g}$ is not a
hard constraint. The network could still generate confidence maps learned from
all loss combinations. (2) Estimating a confidence map from one modality is
enough for the probabilistic fusion of two modalities using the sum to 1
constraint. We choose to estimate lidars’ since their scanned points are
generally more precise, giving convenience to create $M_{g}$.

Sparse data are intrinsically hard for CNN to extract effective features. In
APC, We utilize Sparsity-Attentional Convolution (SAConv) [5] to extract
features from sparse lidar maps. SAConv attends on feature extraction of each
nonzero point with an extra mask to keep track of visibility. After regressing
$M_{lidar}$, we calculate the confidence loss as
$L_{c}=\|M_{lidar}-M_{g}\|^{2}_{2}$. Structures are illustrated in Fig. 3. The
confidence for stereo is $M_{stereo}=1-M_{lidar}$, and the fused depth is
$D_{f}=D_{stereo}\times M_{stereo}+D_{lidar}\times M_{lidar}.$

The second stage is depth regression. We use a stacked hourglass network [28]
with dense connections for regressing depth. Our stacked hourglass network
consists of 3 cascaded encoder-decoder structures. It has the advantage of
refining depth maps stage by stage when compared with mostly used single
encoder-decoder of FCN-like structure in other depth completion works [4] [2]
[5] [26]. The stacked hourglass produces 3 stage outputs ($S1$, $S2$, and
$S3$). We further use skip connection and densely connect each corresponding
layer of these hourglasses and feed the regressed depth to every subsequent
stage to enhance information flow. Finer depth is regressed at later stages.
At inference time, $S3$ is the final depth output. ReLU [29] and batch
normalization [30] are adopted after each convolution in stacked hourglass and
APC.

We use groundtruth, $D_{gt}$, to directly supervise the regression and
calculate loss terms for each stage output. The corresponding mean square
error losses are computed as follows.

$L_{i}=\|D_{gt}-Si\|^{2}_{2},\forall i\in[1,3].$ (1)

The total loss is $L_{1}+L_{2}+L_{3}+L_{c}$. Note that $D_{gt}$ from KITTI
Depth Completion does not contain points on the upper scenes. We find that
using more stages or deeper network would cause overfitting on the lower parts
and yield unstructured upper scenes.

##  4 Experiments

###  4.1 Sparse Depth Completion

Fig. 4: (Left) Qualitative results of stereo matching (PSMNet [13]), SSDC
(direct lidar completion [4]), and our SCADC on KITTI Depth Completion
validation set. We show driving scenarios of large trucks beside and cars with
loads. Vehicle structures extend to upper scenes. SSDC fails to regress upper
structures. Shape distortion of PSMNet could be seen in highlights (a) Bicycle
contour. (b) Bridge structure bleeds into the background and creates irregular
estimations. (Right) Comparison on KITTI Depth Completion test set. Results of
other works are directly from KITTI website. ADNN [9] shows null on the upper
since there are no groundtruth points. We are the only that reconstructs upper
scene structures.

Dataset. We evaluate spare depth completion on KITTI Depth Completion
Benchmark, which contains 42K stereo pairs and lidar scans as training data
and 3.4K frames for validation. Following [4], we uniformly bottom crop the
size to $352\times 1216$. Inputs to our SCADC are generated by PSMNet [13] and
SSDC [4]. We use their released code and best-pretrained weights on KITTI.

Error Metrics. We follow error metrics from previous works. (1) RMSE: root
mean square error; (2) Rel: mean absolute relative error; (3) $\delta_{i}$:
percentage of predicted pixels where the relative error is within 1.25i.
Formally,

$\vspace{-7pt}\delta_{i}=\frac{|\\{\hat{d}:max(\frac{\hat{d}}{d},\frac{d}{\hat{d}})<1.25^{i}\\}|}{|\\{d\\}|},$
(2)

where $|.|$ denotes the cardinality of a set. $\hat{d}$ and $d$ are prediction
and groundtruth. Most studies adopt $i=1,2,3$.

Results. The quantitative comparison of depth error on KITTI Depth Completion
val set is in Table 1. Depth maps for comparison from PSMNet [13] and SSDC [4]
are generated following their steps. Note that the numerical results only
evaluate depth estimations on the lower scenes. A qualitative comparison is
shown in Fig.4 Left. From both numerical and visual results, although PSMNet
produces more structured upper scenes than SSDC, the depth estimation error is
larger on the lower part. By contrast, while SSDC has a smaller numerical
error, it creates irregular and unstructured depth estimations on the upper
scenes. Our SCADC combines the advantages of both stereo matching and depth
completion to generates both scene completeness-aware and precise depth
estimations. We also compare with other depth completion methods on KITTI test
set. The comparison is shown in Fig.4 Right. Our SCADC is the only work that
successfully reconstructs the upper scene structures among the comparison.

Table 1: Evaluation on KITTI Depth Completion val set. Methods |  RMSE |  Rel |  $\delta$1 |  $\delta$2 |  $\delta$3
---|---|---|---|---|---
PSMNet |  2.4107 |  0.1296 |  98.6 |  99.8 |  99.9
SSDC |  1.0438 |  0.0191 |  99.3 |  99.8 |  99.9
SCADC |  1.0096 |  0.0226 |  99.5 |  99.9 |  100.0
Table 2: Comparison on KITTI Semantic Segmentation dataset. Our depth could enhance SSMA performance. Methods |  mIoU
---|---
SDNet [31] |  51.15
SGDepth [32] |  53.04
SSMA [15] |  54.76
SSMA + Our SCADC depth |  61.57
Fig. 5: Semantic Segmentation results of SSMA with depth from our SCADC on
KITTI Semantic Segmentation dataset.

###  4.2 Outdoor RGBD Semantic Segmentation

Datasets. We next validate our SCADC on outdoor semantic segmentation. KITTI
Semantic Segmentation dataset contains only images, and we match the
corresponding lidar frames in KITTI Raw that contains all public raw data. We
split the fetched data into 6:1 training and validation set. Although
Cityscapes has more data for semantic segmentation, they only adopt stereo
cameras as the depth acquisition.

Evaluations. SSMA [15] is a high-performing framework on outdoor RGBD semantic
segmentation. We follow SSMA’s setting and use their Cityscapes pretrains to
perform fine-tuning on KITTI. Standard mean intersection over union (mIoU) is
adopted as the metrics. Two other RGBD outdoor semantic segmentation methods
SDNet [31] and SGDepth [32] are included for comparison. The quantitative and
qualitative results are in Table 2 and Fig. 5. From the results, our scene
completeness-aware and precise depth could further help performance
improvements. In the visual results, finer structures such as road signs and
traffic poles that extend to the upper scenes could be clearly segmented.

##  5 CONCLUSIONS

Our SCADC combines the advantages of scene completeness from stereo matching
to help lidar depth completion, obtaining both scene complete and precise
depth maps. Our APC module predicts confidences of lidars with a guiding
supervision. With APC, information fusion from the two modalities are
successfully performed. We show that our depth maps have good upper scene
control for practical scenarios that objects of interest extend to the upper
scenes. Furthermore, we validate that our depth maps help outdoor RGBD scene
understanding, showing more values of depth completion.

## References

  * [1] Jonas Uhrig, Nick Schneider, Lukas Schneider, Uwe Franke, Thomas Brox, and Andreas Geiger,  “Sparsity invariant cnns,”  in IEEE International Conference on 3D Vision (3DV), 2017, pp. 11–20.
  * [2] Fangchang Ma and Sertac Karaman,  “Sparse-to-dense: Depth prediction from sparse depth samples and a single image,”  in IEEE International Conference on Robotics and Automation (ICRA), 2018.
  * [3] Jiaxiong Qiu, Zhaopeng Cui, Yinda Zhang, Xingdi Zhang, Shuaicheng Liu, Bing Zeng, and Marc Pollefeys,  “Deeplidar: Deep surface normal guided depth prediction for outdoor scene from sparse lidar data and single color image,”  IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [4] Fangchang Ma, Guilherme Venturelli Cavalheiro, and Sertac Karaman,  “Self-supervised sparse-to-dense: Self-supervised depth completion from lidar and monocular camera,”  in 2019 International Conference on Robotics and Automation (ICRA). IEEE, 2019, pp. 3288–3295.
  * [5] Yiqi Zhong, Cho-Ying Wu, Suya You, and Ulrich Neumann,  “Deep rgb-d canonical correlation analysis for sparse depth completion,”  in Advances in Neural Information Processing Systems (NeurIPS), 2019, pp. 5332–5342.
  * [6] Byeong-Uk Lee, Hae-Gon Jeon, Sunghoon Im, and In So Kweon,  “Depth completion with deep geometry and context guidance,”  in IEEE International Conference on Robotics and Automation (ICRA), 2019.
  * [7] Tsun-Hsuan Wang, Fu-En Wang, Juan-Ting Lin, Yi-Hsuan Tsai, Wei-Chen Chiu, and Min Sun,  “Plug-and-play: Improve depth estimation via sparse data propagation,”  in IEEE International Conference on Robotics and Automation (ICRA), 2019.
  * [8] Saif Imran, Yunfei Long, Xiaoming Liu, and Daniel Morris,  “Depth coefficients for depth completion,”  in CVPR, 2019.
  * [9] Simon Lucey Nathaniel Chodosh, Chaoyang Wang,  “Deep Convolutional Compressed Sensing for LiDAR Depth Completion,”  in Asian Conference on Computer Vision (ACCV), 2018.
  * [10] Yun Chen, Bin Yang, Ming Liang, and Raquel Urtasun,  “Learning joint 2d-3d representations for depth completion,”  in Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2019, pp. 10023–10032.
  * [11] Shreyas S. Shivakumar, Ty Nguyen, Steven W. Chen, and Camillo J. Taylor,  “Dfusenet: Deep fusion of rgb and sparse depth information for image guided dense depth completion,”  arXiv preprint arXiv:1902.00761, 2019.
  * [12] Andreas Geiger, Philip Lenz, and Raquel Urtasun,  “Are we ready for autonomous driving? the kitti vision benchmark suite,”  in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012, pp. 3354–3361.
  * [13] Jia-Ren Chang and Yong-Sheng Chen,  “Pyramid stereo matching network,”  in CVPR, 2018, pp. 5410–5418.
  * [14] Qiaosong Wang, Zhan Yu, Christopher Rasmussen, and Jingyi Yu,  “Stereo vision–based depth of field rendering on a mobile device,”  Journal of Electronic Imaging, vol. 23, no. 2, pp. 023009, 2014\.
  * [15] Abhinav Valada, Rohit Mohan, and Wolfram Burgard,  “Self-supervised model adaptation for multimodal semantic segmentation,”  International Journal of Computer Vision (IJCV), jul 2019,  Special Issue: Deep Learning for Robotic Vision.
  * [16] Xinjing Cheng, Peng Wang, and Ruigang Yang,  “Learning depth with convolutional spatial propagation network,”  European Conference on Computer Vision (ECCV), 2018.
  * [17] Jinsun Park, Kyungdon Joo, Zhe Hu, Chi-Kuei Liu, and In So Kweon,  “Non-local spatial propagation network for depth completion,”  European Conference on Computer Vision (ECCV), 2020.
  * [18] Yan Xu, Xinge Zhu, Jianping Shi, Guofeng Zhang, Hujun Bao, and Hongsheng Li,  “Depth completion from sparse lidar data with depth-normal constraints,”  in Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2019, pp. 2811–2820.
  * [19] Heiko Hirschmuller,  “Stereo processing by semiglobal matching and mutual information,”  IEEE Transactions on pattern analysis and machine intelligence (TPAMI), vol. 30, no. 2, pp. 328–341, 2007.
  * [20] Heiko Hirschmuller,  “Accurate and efficient stereo processing by semi-global matching and mutual information,”  in IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2005, vol. 2, pp. 807–814.
  * [21] Stefan K Gehrig, Felix Eberli, and Thomas Meyer,  “A real-time low-power stereo vision engine using semi-global matching,”  in International Conference on Computer Vision Systems (ICCV). Springer, 2009, pp. 134–143.
  * [22] Simon Hermann and Reinhard Klette,  “Iterative semi-global matching for robust driver assistance systems,”  in Asian Conference on Computer Vision (ACCV). Springer, 2012, pp. 465–478.
  * [23] Xiaoyang Guo, Kai Yang, Wukui Yang, Xiaogang Wang, and Hongsheng Li,  “Group-wise correlation stereo network,”  in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [24] Feihu Zhang, Victor Prisacariu, Ruigang Yang, and Philip H.S. Torr,  “Ga-net: Guided aggregation net for end-to-end stereo matching,”  in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [25] David A Forsyth and Jean Ponce,  “Computer vision: A modern approach,”  2003\.
  * [26] Maximilian Jaritz, Raoul De Charette, Emilie Wirbel, Xavier Perrotton, and Fawzi Nashashibi,  “Sparse and dense data with cnns: Depth completion and semantic segmentation,”  IEEE International Conference on 3D Vision (3DV), 2018.
  * [27] Wouter Van Gansbeke, Davy Neven, Bert De Brabandere, and Luc Van Gool,  “Sparse and noisy lidar completion with rgb guidance and uncertainty,”  in 2019 16th International Conference on Machine Vision Applications (MVA). IEEE, 2019, pp. 1–6.
  * [28] Alejandro Newell, Kaiyu Yang, and Jia Deng,  “Stacked hourglass networks for human pose estimation,”  in European conference on computer vision (ECCV). Springer, 2016, pp. 483–499.
  * [29] Vinod Nair and Geoffrey E Hinton,  “Rectified linear units improve restricted boltzmann machines,”  in Proceedings of the 27th international conference on machine learning (ICML-10), 2010, pp. 807–814.
  * [30] Sergey Ioffe and Christian Szegedy,  “Batch normalization: Accelerating deep network training by reducing internal covariate shift,”  arXiv preprint arXiv:1502.03167, 2015.
  * [31] Matthias Ochs, Adrian Kretz, and Rudolf Mester,  “Sdnet: Semantically guided depth estimation network,”  in German Conference on Pattern Recognition (GCPR). Springer, 2019, pp. 288–302.
  * [32] Marvin Klingner, Jan-Aike Termöhlen, Jonas Mikolajczyk, and Tim Fingscheidt,  “Self-supervised monocular depth estimation: Solving the dynamic object problem by semantic guidance,”  European Conference on Computer Vision (ECCV), 2020.