# A Categorial Equivalence for semi-Nelson algebras

Juan Manuel Cornejo  INMABB UNS CONICET, Departamento de Matemática - Av. Alem
1253, Bahía Blanca, Buenos Aires, Argentina.  Andrés Gallardo  INMABB UNS
CONICET, Departamento de Matemática - Av. Alem 1253, Bahía Blanca, Buenos
Aires, Argentina.  Ignacio Viglizzo  INMABB UNS CONICET, Departamento de
Matemática - Av. Alem 1253, Bahía Blanca, Buenos Aires, Argentina.
Corresponding author<EMAIL_ADDRESS>ORCiD:0000-0002-5303-623X

###### Abstract

We present a category equivalent to that of semi-Nelson algebras. The objects
in this category are pairs consisting of a semi-Heyting algebra and one of its
filters. The filters must contain all the dense elements of the semi-Heyting
algebra and satisfy an additional technical condition. We also show that in
the case of dually hemimorphic semi-Nelson algebras, the filters are not
necessary and the category is equivalent to that of dually hemimorphic semi-
Heyting algebras.

##  1 Introduction

Semi-Heyting algebras were introduced in 1985 by H. Sankappanavar [San85] as a
variety generalizing that of Heyting algebras while keeping many of its good
features like being distributive pseudocomplemented lattices and having their
congruences determined by filters.

On the other hand, D. Vakarelov provided in [Vak77] a way of constructing
Nelson algebras from Heyting ones, by means of what is now known as twist
product, thus extending work by Kalman [Kal58]. This program was continued by
Sendlewski [Sen84], [Sen90], who gave a full representation of Nelson algebras
using Heyting algebras and a boolean congruence on them. Later, L. Monteiro
and I. Viglizzo [Vig99] and [MV19], used filters instead of congruences to
study this representation.

It turned out that another one of the nice features of semi-Heyting algebras
is that Vakarelov’s construction can be carried out on them as well. The
resulting algebras form the variety of semi-Nelson algebras [CV16].
Vakarelov’s construction gives a categorial equivalence between semi-Heyting
algebras and centered semi-Nelson algebras [CSM18], but this leaves out many
semi-Nelson algebras. In this work we prove that considering pairs of semi-
Heyting algebras and one of its filters satisfying some extra conditions, we
can construct all the semi-Nelson algebras. This gives a good representation
that can be seen as a categorial equivalence, and permits understanding semi-
Nelson algebras in terms of the better-known semi-Heyting algebras.

H. Sankappanavar defined in [San11] the variety of semi-Heyting algebras with
a dual hemimorphism, or dually hemimorphic semi-Heyting algebras, $\cal DSH$,
as an expansion of semi-Heyting algebras with an unary operator that is a
common generalization of both De Morgan and pseudocomplemented algebras. J. M.
Cornejo and H. San Martín applied Vakarelov’s construction to this expansion
to obtain the variety of dually hemimorphic semi-Nelson algebras, $\cal
DSN$[CSM18]. We prove here that dually hemimorphic semi-Nelson algebras are
centered, and therefore they can be represented by dually hemimorphic semi-
Heyting algebras.

The paper is organized as follows: Section 2 introduces the varieties of
algebras we will be dealing with, recalls some of the basic results on them
that we will be using, and provides background on Vakarelov’s construction.
Section 3 details the representation of semi-Nelson algebras by pairs
consisting of a semi-Heyting algebra and one of its filters containing the
dense elements of the algebra and satisfying an additional condition, proving
this representation is an equivalence of two categories. The final section
deals with the case of dually hemimorphic semi-Nelson algebras.

##  2 Preliminaries

###  2.1 Definitions and elementary properties

In this section we will recall the definitions and some basic properties of
the varieties of Heyting and semi-Heyting algebras, Nelson and semi-Nelson
algebras, pseudocomplemented lattices, and dually hemimorphic semi-Heyting and
semi-Nelson algebras.

###### Definition 2.1

A _semi-Heyting algebra_ is an algebra $\mathbf{H}=\langle
H;\land,\lor,\Rightarrow,0,1\rangle$ of type $(2,2,2,0,0)$ such that the
following conditions are satisfied for all $x,y,z\in A$:

  1. (SH1)

$\langle H,\land,\lor,0,1\rangle$ is a bounded lattice,

  2. (SH2)

$x\land(x\Rightarrow y)=x\land y$,

  3. (SH3)

$x\land(y\Rightarrow z)=x\land((x\land y)\Rightarrow(x\land z))$,

  4. (SH4)

$x\Rightarrow x=1$.

A semi-Heyting algebra is a _Heyting algebra_ if it satisfies the identity:

  1. (H)

$(x\land y)\Rightarrow x=1$.

On a semi-Heyting algebra $\mathbf{H}$ one can always define the term
$x\mbox{$\ \Rightarrow_{\text{\tiny H}}\ $}y=x\Rightarrow(x\land y)$. With
this operation, the system $\langle H,\land,\lor,\mbox{$\
\Rightarrow_{\text{\tiny H}}\ $},0,1\rangle$ is a Heyting algebra [ACDV13].

Nelson algebras are the algebraic counterpart of D. Nelson’s constructive
logic with strong negation. The equations presented here were proved to be a
complete and independent axiomatization in [MM96]:

###### Definition 2.2

A _Nelson algebra_ is an algebra $\mathbf{A}=\langle
A;\land,\lor,\to,\sim,1\rangle$ of type $(2,2,2,1,0)$ such that the following
conditions are satisfied for all $x,y,z\in A$:

  1. (N1)

$x\land(x\lor y)=x$,

  2. (N2)

$x\land(y\lor z)=(z\land x)\lor(y\land x)$,

  3. (N3)

$\sim\sim x=x$,

  4. (N4)

$\sim(x\land y)=\sim x\lor\sim y$,

  5. (N5)

$x\land\sim x=(x\land\sim x)\land(y\lor\sim y)$,

  6. (N6)

$x\to x=1$,

  7. (N7)

$x\to(y\to z)=(x\land y)\to z$,

  8. (N8)

$x\land(x\to y)=x\land(\sim x\lor y)$.

The variety of semi-Nelson algebras was introduced in [CV16] as a
generalization of Nelson algebras.

###### Definition 2.3

A _semi-Nelson algebra_ is an algebra $\mathbf{A}=\langle
A;\land,\lor,\to,\sim,1\rangle$ of type $(2,2,2,1,0)$ such that the following
conditions are satisfied for all $x,y,z\in A$:

  1. (SN1)

$x\land(x\lor y)=x$,

  2. (SN2)

$x\land(y\lor z)=(z\land x)\lor(y\land x)$,

  3. (SN3)

$\sim\sim x=x$,

  4. (SN4)

$\sim(x\land y)=\sim x\lor\sim y$,

  5. (SN5)

$x\land\sim x=(x\land\sim x)\lor(y\lor\sim y)$,

  6. (SN6)

$x\land(x\mbox{$\ \to_{\text{\tiny N}}\ $}y)=x\land(\sim x\lor y)$,

  7. (SN7)

$x\mbox{$\ \to_{\text{\tiny N}}\ $}(y\mbox{$\ \to_{\text{\tiny N}}\
$}z)=(x\land y)\mbox{$\ \to_{\text{\tiny N}}\ $}z$,

  8. (SN8)

$(x\mbox{$\ \to_{\text{\tiny N}}\ $}y)\mbox{$\ \to_{\text{\tiny N}}\
$}[(y\mbox{$\ \to_{\text{\tiny N}}\ $}x)\mbox{$\ \to_{\text{\tiny N}}\
$}[(x\to z)\mbox{$\ \to_{\text{\tiny N}}\ $}(y\to z)]]=1$,

  9. (SN9)

$(x\mbox{$\ \to_{\text{\tiny N}}\ $}y)\mbox{$\ \to_{\text{\tiny N}}\
$}[(y\to_{N}x)\mbox{$\ \to_{\text{\tiny N}}\ $}[(z\to x)\mbox{$\
\to_{\text{\tiny N}}\ $}(z\to y)]]=1$,

  10. (SN10)

$(\sim(x\to y))\mbox{$\ \to_{\text{\tiny N}}\ $}(x\land\sim y)=1$,

  11. (SN11)

$(x\land\sim y)\mbox{$\ \to_{\text{\tiny N}}\ $}(\sim(x\to y))=1$,

where $x\mbox{$\ \to_{\text{\tiny N}}\ $}y:=x\to(x\land y)$.

For a semi-Nelson algebra $\mathbf{A}$, the system $\langle
A,\land,\lor,\mbox{$\ \to_{\text{\tiny N}}\ $},\sim,1\rangle$ is a Nelson
algebra [CV16].

We will denote by $\cal H$, $\cal SH$, $\cal N$ and $\cal SN$ the varieties of
Heyting, semi-Heyting, Nelson and semi-Nelson algebras respectively.

Heyting algebras, as is well known, are pseudocomplemented (with $x^{*}=x\to
0$ as the pseudocomplement of $x\in H$) in the sense of the following
definition:

###### Definition 2.4

An algebra $\mathbf{A}=\langle A;\land,\lor,^{*},0,1\rangle$ is a
_pseudocomplemented lattice_ if the following conditions hold:

  1. PS1)

$\langle A;\land,\lor,0,1\rangle$ is a bounded lattice,

  2. PS2)

$x\land(x\land y)^{*}=x\land y^{*}$,

  3. PS3)

$0^{*}=1$ and $1^{*}=0$.

If we define in a semi-Heyting algebra the term $x^{c}=x\Rightarrow 0$, it
turns out that $x^{c}$ is the pseudocomplement of $x$ in the sense of the
previous definition. Moreover, $x\mbox{$\ \Rightarrow_{\text{\tiny H}}\
$}0=x\Rightarrow(x\land 0)=x\Rightarrow 0$, so $x^{*}$ and $x^{c}$ coincide in
$\cal SH$. From now on we will use indistinctly the notation $x^{*}$ for both
$x^{c}$ and $x^{*}$.

We will use some properties of pseudocomplemented lattices. Their proof can be
found in [BD74]:

###### Proposition 2.5

If $\mathbf{A}=\langle A;\land,\lor,^{*},0,1\rangle$ is a pseudocomplemented
lattice, then for every $x,y\in A$, if $x\land y=0$, then $x\leq y^{*}$. It
also holds that $(x\lor y)^{*}=x^{*}\land y^{*}$.

###### Definition 2.6

Let $\mathbf{A}=\langle A;\land,\lor,^{*},0,1\rangle$ be a pseudocomplemented
lattice. We say that an element $a\in A$ is _dense_ if $a^{*}=0$. We denote by
$\mathcal{D}_{s}(A)$ the set of all dense elements of $A$.

The following characterization of dense elements is going to be useful:

###### Lemma 2.7

If $\mathbf{H}\in\mbox{$\cal SH$}$, then $x\in\mathcal{D}_{s}(H)$ if and only
if $x=y\lor y^{*}$ for some $y\in H$.

For the results in section 4, we now define the varieties of dually
hemimorphic semi-Heyting and semi-Nelson algebras. The former were introduced
by H.P. Sankappanavar in [San11], and the latter were presented in [CSM19].

###### Definition 2.8

An algebra $\mathbf{A}=\langle A;\land,\lor,\to,^{\dagger},0,1\rangle$ of type
$(2,2,2,1,0,0)$ is said to be a _dually hemimorphic semi-Heyting algebra_ if
$\langle A;\land,\lor,\to,0,1\rangle$ is a semi-Heyting algebra and the
following equations are satisfied:

  1. DSM1)

$0^{\dagger}=1$,

  2. DSM2)

$1^{\dagger}=0$,

  3. DSM3)

$(x\land y)^{\dagger}=x^{\dagger}\lor y^{\dagger}$.

We write $\cal DSH$ to denote the variety of dually hemimorphic semi-Heyting
algebras.

###### Definition 2.9

An algebra $\mathbf{A}=\langle A;\land,\lor,\to,\sim,^{\prime},1\rangle$ of
type $(2,2,2,1,0)$ is said to be a _dually hemimorphic semi-Nelson algebra_ if
$\langle A;\land,\lor,\to,\sim,1\rangle$ is a semi-Nelson algebra and the
following equations are satisfied:

  1. DSN1)

$(\sim 1)^{\prime}=1$,

  2. DSN2)

$1^{\prime}\to(\sim 1)=1$,

  3. DSN3)

$((x\to y)\land(y\to x)\land x^{\prime})\to((x\to y)\land(y\to x)\land
y)^{\prime}=1$,

  4. DSN4)

$\sim x^{\prime}\to(\sim x\land(x^{\prime}\to x))=1$,

  5. DSN5)

$(\sim x\land(x^{\prime}\to x))\to\sim x^{\prime}=1$,

  6. DSN6)

$(x\land y)^{\prime}\to(x^{\prime}\lor y^{\prime})=1$,

  7. DSN7)

$(x^{\prime}\lor y^{\prime})\to(x\land y)^{\prime}=1$.

We use the convention that the unary operation ′ has higher priority than
$\sim$, so the expression $\sim x^{\prime}$ means $\sim(x^{\prime})$.

We write $\cal DSN$ to denote the variety of dually hemimorphic semi-Nelson
algebras.

###  2.2 Vakarelov’s Construction

In this section we review some well known results that established the
connection between Heyting and Nelson algebras, and later allowed the
definition of (dually hemimorphic) semi-Nelson algebras as a variety
constructed from the one of (dually hemimorphic) semi-Heyting algebras.

Let $\mathbf{A}\in\mbox{$\cal H$}$. We denote with $V_{k}(A)$ the set
$\\{(a,b)\in A^{2}:a\land b=0\\}$ and with $\mathbf{V_{k}(A)}$ the system
$\langle V_{k}(A);\sqcap,\sqcup,\to,\sim,\top\rangle$ algebrized in the
following way

  1. (V1)

$(a,b)\sqcap(c,d)=(a\land c,b\lor d)$,

  2. (V2)

$(a,b)\sqcup(c,d)=(a\lor c,b\land d)$,

  3. (V3)

$(a,b)\to(c,d)=(a\Rightarrow c,a\land d)$,

  4. (V4)

$\sim(a,b)=(b,a)$,

  5. (V5)

$\top=(1,0)$.

###### Observation 2.10

From the previous definitions we can deduce the rule

$(\mbox{\rm V}6)\ (a,b)\mbox{$\ \to_{\text{\tiny N}}\ $}(c,d)=(a\mbox{$\
\Rightarrow_{\text{\tiny H}}\ $}c,a\land d).$

It was shown in [Vak77] that $\mathbf{V_{k}(A)}\in\mbox{$\cal SN$}$.

Vakarelov’s construction can be generalized the following way: if
$\mathbf{A}\in\mbox{$\cal H$}$, and $F$ is a filter of $\mathbf{A}$, we define
the structure

$N(A,F):=\\{(a,b)\in A^{2}:a\land b=0,a\lor b\in F\\}.$

It was proved in [Vig99, MV19] that $N(A,F)$, algebrized with (V1)-(V5), is
well defined and it is a Nelson algebra. This algebra will be denoted by
$\mathbf{N(A,F)}$.

A different generalization was to start from a semi-Heyting algebra, which
lead to the definition of semi-Nelson algebras [CV16]: if $\mathbf{A}$ is a
semi-Heyting algebra, then $\mathbf{V_{k}(A)}$ is a semi-Nelson algebra.

Going in the other direction, we can go from semi-Nelson algebras to semi-
Heyting algebras by means of the following quotient:

Let $\mathbf{A}=\langle A,\land,\lor,\to,\sim,1\rangle\in\mbox{$\cal SN$}$,
and define:

$x\equiv y\mbox{ if and only if }x\to y=1\mbox{ and }y\to x=1.$

It can be proved that “$\equiv$” is an equivalence relation and a congruence
with respect of the operations $\land$, $\lor$ and $\to$. We denote with
$[\\![a]\\!]$ the equivalence class of an element $a\in A$ under the relation
$\equiv$.

We consider $\mathbf{sH}(\mathbf{A})=\langle
A/_{\equiv},\cap,\cup,\Rightarrow,\bot,\top\rangle$, where

  * •

$\bot=[\\![\sim 1]\\!]$,

  * •

$\top=[\\![1]\\!]$,

  * •

$[\\![x]\\!]\cap[\\![y]\\!]=[\\![x\land y]\\!]$,

  * •

$[\\![x]\\!]\cup[\\![y]\\!]=[\\![x\lor y]\\!]$,

  * •

$[\\![x]\\!]\Rightarrow[\\![y]\\!]=[\\![x\to y]\\!]$.

Then $\mathbf{sH}(\mathbf{A})\in\mbox{$\cal SH$}$ ([CV16]).

We will use the next result in the following sections:

###### Proposition 2.11

[CV16, Lemma 2.7 (h) and (l)] Let $\mathbf{A}\in\mbox{$\cal SN$}$, and
$a,b,c\in A$. Then the following properties hold:

  1. (1)

$a\mbox{$\ \to_{\text{\tiny N}}\ $}b=b\mbox{$\ \to_{\text{\tiny N}}\ $}a=1$ if
and only if $a\to b=b\to a=1$,

  2. (2)

If $a\mbox{$\ \to_{\text{\tiny N}}\ $}b=1=b\mbox{$\ \to_{\text{\tiny N}}\
$}c=1$, then $a\mbox{$\ \to_{\text{\tiny N}}\ $}c=1$.

Part (1) of the previous proposition tells us that the congruence $\equiv$ is
the same as the one that can be defined if we replace $\to$ with $\
\to_{\text{\tiny N}}\ $.

The following representation theorem establishes the connection between semi-
Heyting and semi-Nelson algebras using Vakarelov’s construction and the
quotient by the relation $\equiv$.

###### Theorem 2.12

([CV16, Theorem 5.3 and Corollary 5.2]) If $\mathbf{A}\in\mbox{$\cal SH$}$,
then $\mathbf{A}$ is isomorphic to $\mathbf{sH}(\mathbf{V_{k}}(\mathbf{A}))$
through the isomorphism $g(a)=[\\![(a,a^{*})]\\!]$. Also, if
$\mathbf{A}\in\mbox{$\cal SN$}$, then $\mathbf{A}$ is isomorphic to a
subalgebra of $\mathbf{V_{k}(sH(\mathbf{A}))}$ through the application
$h(a)=([\\![a]\\!],[\\![\sim a]\\!])$.

##  3 Representations

Theorem 2.12 gives a representation of any semi-Nelson algebra $\mathbf{A}$ as
a subalgebra of $\mathbf{V_{k}}(\mathbf{sH}(\mathbf{A}))$, but there can be
more than one non-isomorphic semi-Nelson algebra having the same quotient
semi-Heyting algebra $\mathbf{sH}(\mathbf{A})$ (up to isomorphism). In order
to get a sharper representation we are going to consider pairs consisting of a
semi-Heyting algebra and one of its filters satisfying extra conditions. To be
more precise, we obtain a categorial equivalence between the category of semi-
Nelson algebras and a category whose objects are pairs $(\mathbf{H},F)$ where
$\mathbf{H}$ is a semi-Heyting algebra and $F$ is a filter of $\mathbf{H}$
that contains all the dense elements of $\mathbf{H}$ and satisfies an extra
condition.

Recall the construction $N(A,F)=\\{(a,b)\in A^{2}:a\land b=0,a\lor b\in F\\}$
for some Heyting algebra $\mathbf{A}$, and $F$ a filter of $\mathbf{A}$. For
any $\mathbf{A}\in\mbox{$\cal H$}$, we consider $\mathbf{V_{k}(A)}$, and a
subalgebra $\mathbf{S}$ such that the projection over the first component,
$\pi_{1}$, verifies $\pi_{1}(S)=A$. It was shown in [Vig99] that there is a
filter $F\subseteq A$ containing the dense elements of $A$ such that
$\mathbf{S}=\mathbf{N(A,F)}$.

To extend these results to the variety $\cal SH$, we define:

###### Definition 3.1

Let $\mathbf{H}\in\mbox{$\cal SH$}$. A subset $F\subseteq H$ is an $i$-filter,
if the following conditions hold:

  1. IF1)

$F$ is a lattice filter of $\mathbf{H}$.

  2. IF2)

$\mathcal{D}_{s}(H)\subseteq F$.

  3. IF3)

If $z\lor t\in F$, then for all $x\in H$, $(x\Rightarrow z)\lor(x\land t)\in
F$.

It is immediate from the definition that every $i$-filter is a filter. The
converse is not true, as the following example shows:

###### Example 3.2

Consider the semi-Heyting algebra $\mathbf{A}=\langle A;\land,\lor,$
$\Rightarrow,1\rangle$, with the operation $\Rightarrow$ indicated in the
table:

$0$$1$$A$

$\Rightarrow$ | $0$ | $1$
---|---|---
$0$ | $1$ | $0$
$1$ | $0$ | $1$

The subset $F=\\{1\\}$ of $\mathbf{A}$ is a filter, and it satisfies $IF2)$
(since the only dense element is 1). But $F$ does not satisfy $IF3$) because
$1\lor 0=1\in F$, but $(0\Rightarrow 1)\lor(0\land 0)=0\lor 0=0\notin F$.

###### Observation 3.3

If we consider the structure $\mathbf{N(H,F)}$, with $\mathbf{H}\in\mbox{$\cal
SH$}$, an $i$-filter $F$, and $(a,b),(c,d)\in N(H,F)$, then (1) $c\land d=0$
and (2) $c\lor d\in F$. Notice that

$(a\Rightarrow c)\land(a\land d)=a\land(a\Rightarrow c)\land
d\underset{(SH\ref{infimoeimplicaSH})}{=}(a\land c)\land d=a\land(c\land
d)\underset{(1)}{=}a\land 0=0.$

Also, using (2) and $IF3)$ we have that $(a\Rightarrow c)\lor(a\land d)\in F$,
so the pair $(a\Rightarrow c,a\land d)$ is in $N(H,F)$ and we can use it to
define $(a,b)\to(c,d)=(a\Rightarrow c,a\land d)$.

###### Lemma 3.4

If $\mathbf{H}\in\mbox{$\cal SH$}$ and $F$ is an $i$-filter of $\mathbf{H}$,
then the system $\langle N(H,F);$ $\sqcap,\sqcup,\to,\sim,\top\rangle$ with
the operations defined as in (V1)-(V5) is a semi-Nelson algebra.

Proof.  Using that $F$ is a filter we can prove that the operations $\sqcap$,
$\sqcup$, $\top$ and $\sim$ are well defined in $N(H,F)$ (see [MV19]). Also,
by observation 3.3, it follows that the operation $\to$ is well defined.
Furthermore, following the proof of Theorem 4.1 in[CV16], $\mathbf{N(H,F)}$
verifies the axioms $SN1)$-$SN11)$ so it is is a semi-Nelson algebra.
$\blacksquare$

###### Lemma 3.5

Let $\mathbf{H}\in\mbox{$\cal SH$}$. If $\mathbf{S}$ is a subalgebra of
$\mathbf{V_{k}}(\mathbf{H})$, such that $\pi_{1}(S)=H$ (with $\pi_{1}$ the
projection over the first component of ${V_{k}}(H)$), then there exists an
$i$-filter $E$ of $\mathbf{H}$ such that $S=N(H,E)$.

Proof.  Let $E=\\{x\in H:x=a\lor b\text{ for some }(a,b)\in S\\}$. We are
going to prove that $E$ is an $i$-filter.

It was shown in [Vig99] that if $\mathbf{H}\in\mbox{$\cal H$}$, then $E$ is a
filter of $\mathbf{H}$. But that proof can be extended naturally to the
variety $\cal SH$, because it only uses lattice properties.

Consider a dense element $x\in H$. Since $\pi_{1}(S)=H$, then there exists
$y\in H$ such that $(x,y)\in S$. Besides, since $S$ is a subalgebra of
$\mathbf{V_{k}(H)}$, $(0,1)\in S$, and therefore $(x,y)\to(0,1)=(x\Rightarrow
0,x\land 1)=(x^{*},x)=(0,x)\in S$. Hence, $x\in E$ because $x=x\lor 0$, and we
conclude that $E$ satisfies $IF2$).

Suppose now that for $z,t\in H$ we have $z\lor t\in E$,

Since $z\lor t\in E$, there exists a pair $(a,b)\in S$ such that $z\lor
t=a\lor b$. But $S$ is a subalgebra of $\mathbf{V_{k}(H)}$, so
$\sim(a,b)=(b,a)\in S$, and therefore $(a,b)\cup(b,a)=(a\lor b,a\land
b)=(a\lor b,0)\in S$. This means that $(z\lor t,0)\in S$, and hence

$\sim(z\lor t,0)=(0,z\lor t)\in S.$ (3.1)

Using the hypothesis $\pi_{1}(S)=H$, and $x,z,t\in H$, it follows that there
exist some $x^{\prime},z^{\prime},t^{\prime}\in H$ such that
$(x,x^{\prime}),(z,z^{\prime}),(t,t^{\prime})\in S$. This implies that the
next term belongs to $S$:

$((x,x^{\prime})\to(z,z^{\prime}))\cup((x,x^{\prime})\cap(t,t^{\prime}))=(x\Rightarrow
z,x\land z^{\prime})\cup(x\land t,x^{\prime}\lor t^{\prime})=$ $((x\Rightarrow
z)\lor(x\land t),(x\land z^{\prime})\land(x^{\prime}\lor t^{\prime})).$ (3.2)

Since $(x\land z^{\prime})\land(x^{\prime}\lor t^{\prime})=(x\land
z^{\prime}\land x^{\prime})\lor(x\land z^{\prime}\land
t^{\prime})=0\lor(x\land z^{\prime}\land t^{\prime})=x\land z^{\prime}\land
t^{\prime}$, (3.2) yields

$((x\Rightarrow z)\lor(x\land t),x\land z^{\prime}\land t^{\prime})\in S.$
(3.3)

Combining (3.1) with (3.3) we get

$((x\Rightarrow z)\lor(x\land t),x\land z^{\prime}\land
t^{\prime})\cup(0,z\lor t)=((x\Rightarrow z)\lor(x\land t),x\land
z^{\prime}\land t^{\prime}\land(z\lor t))\in S.$ (3.4)

Since $x\land z^{\prime}\land t^{\prime}\land(z\lor t)=(x\land z^{\prime}\land
t^{\prime}\land z)\land(x\land z^{\prime}\land t^{\prime}\land t)=(x\land
t^{\prime}\land(z\land z^{\prime}))\lor(x\land z\land(t\land
t^{\prime}))=0\lor 0=0$, from (3.4) it follows that

$((x\Rightarrow z)\lor(x\land t),0)\in S.$

By the definition of $E$ it follows that

$(x\Rightarrow z)\lor(x\land t)\lor 0=(x\Rightarrow z)\lor(x\land t)\in E.$

Hence, $E$ is an $i$-filter.

Let us prove now that $N(H,E)=S$. It is clear that $S\subseteq N(H,E)$. If we
have $(a,b)\in N(H,E)$, then $a\land b=0$, and $a\lor b\in E$, so there exists
$(c,d)\in S$ such that $c\lor d=a\lor b$. Then, as before
$(c,d)\cup(d,c)=(c\lor d,0)=(a\lor b,0)\in S$. On the other hand, since
$\pi_{1}(S)=H$, there exists some $b^{\prime}\in H$ such that
$(b,b^{\prime})\in S$, and therefore $(b,b^{\prime})\to(0,1)=(b^{*},b)\in S$.
By properties of the pseudocomplement, $a\land b=0$ implies that $a\leq b^{*}$
and hence $(a\lor b)\land b^{*}=(a\land b^{*})\lor(b\land b^{*})=a\lor 0=a$,
so we can conclude that $(a\lor b,0)\cap(b^{*},b)=((a\lor b)\land b^{*},0\lor
b)=(a,b)\in S$. $\blacksquare$

###### Theorem 3.6

Every semi-Nelson algebra $\mathbf{A}$ is isomorphic to an algebra of the form
$\mathbf{N(H,F)}$, for some semi-Heyting algebra $\mathbf{H}$ and some
$i$-filter $F$ of $\mathbf{H}$.

Proof.  By Theorem 2.12, every semi-Nelson algebra $\mathbf{A}$ can be
obtained as a subalgebra of $\mathbf{V_{k}}(\mathbf{sH}(A))$, and clearly
$\pi_{1}(\mathbf{V_{k}}(\mathbf{sH}(A)))=\mathbf{sH}(A)$, so $\mathbf{A}$ is
isomorphic to $\mathbf{N}(\mathbf{sH}(\mathbf{A}),\mathbf{E})$, where $E$ is
the $i$-filter of Lemma 3.5. $\blacksquare$

Much in the same manner as for the case of Heyting algebras, for
$\mathbf{H}\in\mbox{$\cal SH$}$, the $i$-filters $E$ such that
$\pi_{1}(N(H,E))=H$ are exactly the ones that contain the dense elements of
$H$:

###### Lemma 3.7

If $\mathbf{H}\in\mbox{$\cal SH$}$, and $F$ is an $i$-filter of $\mathbf{H}$,
then $\pi_{1}(N(H,F))=H$.

Proof.  If $x\in H$, by Lemma 2.7, we have that $x\lor
x^{*}\in\mathcal{D}_{s}(H)\subseteq F$. Also, $x\land x^{*}=0$ is valid, so
$(x,x^{*})\in N(H,F)$ and $x\in\pi_{1}(N(H,F))$. $\blacksquare$

###  3.1 Categorial equivalence

We define now the category $\mathbf{sHF}$, which has as objects pairs
$(\mathbf{H},F)$ (where $\mathbf{H}\in\mbox{$\cal SH$}$, and $F$ is an
$i$-filter of $H$), and as morphisms, functions
$f:(\mathbf{H},F)\longrightarrow(\mathbf{H}^{\prime},F^{\prime})$ such that
$f:H\longrightarrow H^{\prime}$ is a homomorphism of semi-Heyting algebras and
$f(F)\subseteq F^{\prime}$.

Consider now the category $\mathbf{sN}$ of semi-Nelson algebras and their
morphisms; our objective now is to establish an equivalence between these
categories. For this we define functors
$\alpha:\mathbf{sHF}\longrightarrow\mathbf{sN}$ and
$\beta:\mathbf{sN}\longrightarrow\mathbf{sHF}$.

###### Proposition 3.8

The application $\alpha:\mathbf{sHF}\longrightarrow\mathbf{sN}$ defined on the
objects of $\mathbf{sHF}$ by $\alpha((\mathbf{H},F))=\mathbf{N(H,F)}$, and on
morphisms by $\alpha(f)(a,b)=(f(a),f(b))$ for all $(a,b)\in N(H,F)$, is a
functor from $\mathbf{sHF}$ to $\mathbf{sN}$.

Proof.  Let us check that $\alpha$ is well defined. If $(\mathbf{H},F)$ is an
object of $\mathbf{sHF}$, then $\alpha((\mathbf{H},F))=\mathbf{N(H,F)}$ is a
semi-Nelson algebra due to Lemma 3.4.

Now we take a morphism
$f:(\mathbf{H},F)\longrightarrow(\mathbf{H}^{\prime},F^{\prime})$. Since $f$
is a Heyting homomorphism, we have by straightforward calculations that:
$\alpha(f)((a,b)\to(c,d))=(f(a\Rightarrow c),f(a\land
d))=(f(a),f(b))\to((f(c),f(d)))=$ $\alpha(f)(a,b)\to\alpha(f)(c,d)$, and
similarly for the rest of the operations.

For all $(a,b)$ $\in$ $N(H,F)$, $(a,b)=(Id_{(H,F)}(a),Id_{(H,F)}(b)))$,
therefore $\alpha(Id_{(\mathbf{H},F)})=Id_{\alpha(\mathbf{H},F)}$.

Finally, for any two given morphisms
$f:(\mathbf{H}^{\prime},F^{\prime})\longrightarrow(\mathbf{H}^{\prime\prime},F^{\prime\prime})$,
and $g:(\mathbf{H},F)\longrightarrow(\mathbf{H}^{\prime},F^{\prime})$, we have
that for all $(a,b)\in N(H,F)$, $\alpha(f\circ g)(a,b)=((f\circ g)(a),(f\circ
g)(b))=(f(g(a)),f(g(b)))=\alpha(f)((g(a),g(b)))=((\alpha(f))\circ(\alpha(g)))(a,b)$.
$\blacksquare$

###### Definition 3.9

Let $A\in\mbox{$\cal SN$}$. We say that an element $a\in A$ is _positive_ if
$\sim a\leq a$. We denote by $A^{+}$ the set of positive elements of $A$.

###### Observation 3.10

If $A\in\mbox{$\cal SN$}$, then $A^{+}=\\{x\lor\sim x:x\in A\\}$. Indeed, if
$x\in A^{+}$, then $\sim x\leq x$, so $x=x\lor\sim x$. On the other hand, if
$y=x\lor\sim x$, by $SN$4) and $SN$5) it follows that $y=x\lor\sim x\geq
x\land\sim x=\sim(\sim x\lor x)=\sim y$.

We write $[\\![A^{+}]\\!]$ for the set $\\{[\\![a]\\!]:a\in A^{+}\\}$.

###### Lemma 3.11

If $\mathbf{A}\in\mbox{$\cal SN$}$, then $[\\![A^{+}]\\!]$ is an $i$-filter of
$\mathbf{sH}(A)$.

Proof.  By Theorem 2.12, there exists a subalgebra $\mathbf{S}$ of
$\mathbf{V_{k}}(\mathbf{sH}(A))$ such that $\mathbf{A}$ is isomorphic to
$\mathbf{S}$, and the isomorphism is given by $h(a)=([\\![a]\\!],[\\![\sim
a]\\!])$ for all $a\in A$. Therefore $S=\\{([\\![a]\\!],[\\![\sim a]\\!]):a\in
A\\}$. Then, it is immediate that $\pi_{1}(S)=\mathbf{sH}(A)$.

By Lemma 3.5, $S=N(\mathbf{sH}(A),E)$, where $E=\\{[\\![a]\\!]\lor[\\![\sim
a]\\!]:a\in A\\}$ is an $i$-filter of $\mathbf{sH}(\mathbf{A})$. But
$E=[\\![A^{+}]\\!]$, due to observation 3.10, which completes the proof.
$\blacksquare$

###### Proposition 3.12

The application $\beta:\mathbf{sN}\longrightarrow\mathbf{sHF}$ defined on the
objects of $\mathbf{sN}$ by
$\beta(\mathbf{A})=(\mathbf{sH}(\mathbf{A}),[\\![A^{+}]\\!])$, and on
morphisms $f:A\longrightarrow A^{\prime}$ by
$\beta(f)([\\![a]\\!])=[\\![f(a)]\\!]$ for all $a\in A$, is a functor from
$\mathbf{sN}$ to $\mathbf{sHF}$.

Proof.  Let us check that $\beta$ is well defined. For an object $\mathbf{A}$
of $\mathbf{sN}$, $\mathbf{sH}(\mathbf{A})$ is a semi-Heyting algebra, and by
Lemma 3.11 we have that $[\\![A^{+}]\\!]$ is an $i$-filter of
$\mathbf{sH}(\mathbf{A})$. Therefore, $(\mathbf{sH}(A),[\\![A^{+}]\\!])$ is an
object in $\mathbf{sHF}$.

For any semi-Nelson morphism $f:A\longrightarrow A^{\prime}$, we calculate:
$\beta(f)([\\![a\to b]\\!])=$ $[\\![f(a\to b)]\\!]=$ $[\\![f(a)\to f(b)]\\!]=$
$[\\![f(a)]\\!]\Rightarrow[\\![f(b)]\\!]=$
$\beta(f)([\\![a]\\!])\Rightarrow\beta(f)([\\![b]\\!])$, and similarly for the
other operations.

Also, if $[\\![x]\\!]\in[\\![A^{+}]\\!]$, then by observation 3.10 we can
write $[\\![x]\\!]=$ $[\\![y\lor$ $\sim y]\\!]$, for some $y\in A$, and so
$\beta(f)([\\![x]\\!])=\beta(f)([\\![y\lor\sim
y]\\!])=\beta(f)([\\![y]\\!])\cup\beta(f)([\\![\sim
y]\\!])=[\\![f(y)]\\!]\cup[\\![f(\sim y)]\\!]=$ $[\\![f(y)]\\!]\cup[\\![\sim
f(y)]\\!]=$ $[\\![f(y)\lor\sim f(y)]\\!]$. Since $f(y)\in f(A)\subseteq
A^{\prime}$, it follows that $\beta(f)([\\![x]\\!])\in[\\![A^{\prime+}]\\!]$.
This shows that $\beta(f)([\\![A^{+}]\\!])\subseteq[\\![A^{\prime+}]\\!]$, so
$\beta(f)$ is a morphism in $\mathbf{sHF}$.

It is straightforward to check that $\beta$ preserves identities and
compositions, so it is indeed a functor. $\blacksquare$

The connection between theorems 3.8 and 3.12 is the following:

###### Theorem 3.13

The functors $\alpha$ and $\beta$ establish an equivalence between the
categories $\mathbf{sHF}$ and $\mathbf{sN}$.

Proof.

Notice that
$\beta\alpha(\mathbf{A},F)=\beta(\mathbf{N(\mathbf{A},F)})=(\mathbf{sH(N(\mathbf{A},F))},[\\![N(A,F)^{+}]\\!])$,
with $\mathbf{sH(N(\mathbf{A},F))}=\\{[\\![(x,y)]\\!]:(x,y)\in
N(A,F)\\}=\\{[\\![(x,y)]\\!]:x,y\in A,x\land y=0,x\lor y\in F\\}$.

We define now $\eta_{A}(x)=[\\![(x,x^{*})]\\!]$, for each object $\mathbf{A}$
of $\mathbf{sHF}$ and for all $x\in A$, and we prove that
$\eta=\\{\eta_{A}\\}$ is a natural isomorphism from $id_{\mathbf{sHF}}$ to
$\beta\alpha$.

$\eta_{A}$ is well defined: Since $x\land x^{*}=0$ and also
$\mathcal{D}_{s}(A)\subseteq F$ it follows that $x\lor
x^{*}\in\mathcal{D}_{s}(A)\subseteq F$. Hence, $(x,x^{*})\in N(A,F)$.

$\eta_{A}$ is surjective: If $[\\![(x,y)]\\!]\in\beta\alpha(A,F)$, then
$[\\![(x,y)]\\!]=[\\![(x,x^{*})]\\!]$. Indeed, since
$(x,y)\to(x,x^{*})=(x\Rightarrow x,$ $x\land x^{*})=(1,0)$ and
$(x,x^{*})\to(x,y)=(x\Rightarrow x,x\land y)=(1,0)$, so by definition we have
that $[\\![(x,y)]\\!]=[\\![(x,x^{*})]\\!]$. Therefore
$\eta_{A}(x)=[\\![(x,y)]\\!]$.

$\eta_{A}$ is injective: If $[\\![(x,x^{*})]\\!]=[\\![(y,y^{*})]\\!]$, then
$(x,x^{*})\to(y,y^{*})=(x\Rightarrow y,x\land y^{*})=(1,0)$. Therefore, from
$x\Rightarrow y=1$, using properties of semi-Heyting algebras we obtain $x\leq
y$. Analogously, $(y,y^{*})\to(x,x^{*})=$ $(y\Rightarrow x,y\land
x^{*})=(1,0)$ implies $y\leq x$.

$\eta_{A}$ is a $\mathbf{sHF}$-morphism:

  * •

$\eta_{A}(x)\cup\eta_{A}(y)=[\\![(x,x^{*})]\\!]\cup[\\![(y,y^{*})]\\!]=[\\![(x,x^{*})\sqcup(y,y^{*})]\\!]=[\\![(x\lor
y,x^{*}\land y^{*})]\\!]=[\\![(x\lor y,$ $(x\lor y)^{*})]\\!]=\eta_{A}(x\lor
y)$.

  * •

$\eta_{A}(x)\cap\eta_{A}(y)=[\\![(x,x^{*})]\\!]\cap[\\![(y,y^{*})]\\!]=[\\![(x,x^{*})\sqcap(y,y^{*})]\\!]=[\\![(x\land
y,x^{*}\lor y^{*})]\\!]$. Also, $\eta_{A}(x\land y)=[\\![(x\land y,(x\land
y)^{*})]\\!]$. Since $(x\land y,x^{*}\lor y^{*})\to(x\land y,(x\land
y)^{*})=((x\land y)\Rightarrow(x\land y),(x\land y)\land(x\land y)^{*})=(1,0)$
and $(x\land y,(x\land y)^{*})\to(x\land y,x^{*}\lor y^{*})=((x\land
y)\Rightarrow(x\land y),(x\land y)\land(x^{*}\lor y^{*}))=(1,(x\land y\land
x^{*})\lor(x\land y\land y^{*}))=(1,0)$, we have that
$\eta_{A}(x)\cap\eta_{A}(y)=\eta_{A}(x\land y)$.

  * •

$\eta_{A}(x)\Rightarrow\eta_{A}(y)=[\\![(x,x^{*})]\\!]\Rightarrow[\\![(y,y^{*})]\\!]=[\\![(x,x^{*})\Rightarrow(y,y^{*})]\\!]=[\\![(x\Rightarrow
y,x\land y^{*})]\\!]$. Also, $\eta_{A}(x\Rightarrow y)=[\\![(x\Rightarrow
y,(x\Rightarrow y)^{*})]\\!]$. Since $(x\Rightarrow y,x\land
y^{*})\to(x\Rightarrow y,(x\Rightarrow y)^{*})=((x\Rightarrow
y)\Rightarrow(x\Rightarrow y),(x\Rightarrow y)\land(x\Rightarrow
y)^{*})=(1,0)$ and $(x\Rightarrow y,(x\Rightarrow y)^{*})\to(x\Rightarrow
y,x\land y^{*})=((x\Rightarrow y)\Rightarrow(x\Rightarrow y),(x\Rightarrow
y)\land(x\land y^{*}))\underset{SH\ref{infimoeimplicaSH})}{=}(1,x\land(y\land
y^{*}))=(1,0)$, we have that $[\\![(x\Rightarrow y,x\land
y^{*})]\\!]=[\\![(x\Rightarrow y,(x\Rightarrow y)^{*})]\\!]$. Therefore, we
conclude that $\eta_{A}(x)\Rightarrow\eta_{A}(y)=\eta_{A}(x\Rightarrow y)$.

  * •

$\eta_{A}(F)\subseteq[\\![N(A,F)^{+}]\\!]$

If $y\in\eta_{A}(F)$, then $y=\eta_{A}(x)$, for some $x\in F$. Hence,
$y=[\\![(x,x^{*})]\\!]$, with $x\in F$.

We observe that for $x\in F$, we have that $(x,0)\in N(A,F)$. Besides,
$[\\![(x,x^{*})]\\!]=[\\![(x,0)]\\!]$ because $(x,0)\to(x,x^{*})=(x\Rightarrow
x,x\land x^{*})=(1,0)$ and $(x,x^{*})\to(x,0)=(x\Rightarrow x,x\land
0)=(1,0)$.

Therefore, we can write $y=[\\![(x,0)]\\!]$. Now, since
$\sim(x,0)=(0,x)\leq(x,0)$, it follows that $(x,0)\in N(A,F)^{+}$, and hence
$y\in[\\![N(A,F)^{+}]\\!]$.

Finally, we check the naturality of $\eta$, that is, the following diagram
commutes:

$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\eta_{A}}$$\scriptstyle{f}$$\textstyle{\beta\alpha(A)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\beta\alpha(f)}$$\textstyle{A^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\eta_{A^{\prime}}}$$\textstyle{\beta\alpha(A^{\prime})}$

Notice that since $\eta_{A}$ is an isomorphism,
$\eta_{A}^{-1}([\\![(x,y)]\\!])=x$ for every $x\in A$. Then we have

$(\eta_{A^{\prime}}^{-1}\circ\beta\alpha(f)\circ\eta_{A})(x)=\eta_{A^{\prime}}^{-1}(\beta\alpha(f)([\\![(x,0)]\\!]))=$
$=\eta_{A^{\prime}}^{-1}([\\![\alpha(f)(x,0)]\\!])=\eta_{A^{\prime}}^{-1}([\\![f(x),0)]\\!]=f(x).$

Thus $f=\eta_{A^{\prime}}^{-1}\circ\beta\alpha(f)\circ\eta_{A}$, and therefore
$\eta_{A^{\prime}}\circ f=\beta\alpha(f)\circ\eta_{A}$.

Now we consider the functor $\alpha\beta$, which transforms every object
$\mathbf{A}$ of $\mathbf{sN}$ into $\mathbf{N(sH(A),[\\![A^{+}]\\!])}$. On a
morphism $f:A\longrightarrow A^{\prime}$ it is defined by
$\alpha\beta(f)([\\![x]\\!],[\\![y]\\!])=([\\![f(x)]\\!],[\\![f(y)]\\!])$. We
define for each object $\mathbf{A}$ of $\mathbf{sN}$,
$\delta_{A}:A\longrightarrow\mathbf{N(sH(A),[\\![A^{+}]\\!])}$ by
$\delta_{A}(x)=([\\![x]\\!],[\\![\sim x]\\!])$.

$\delta_{A}$ is well defined: On the one hand, $[\\![x]\\!]\cap[\\![\sim
x]\\!]=[\\![x\land\sim x]\\!]=[\\![0]\\!]$, because $(x\land\sim x)\to
0=(x\land\sim x)\to(x\land\sim x\land 0)=(x\land\sim x)\mbox{$\
\to_{\text{\tiny N}}\ $}0=1$ and $0\mbox{$\ \to_{\text{\tiny N}}\
$}(x\land\sim x)=1$ by well known properties of Nelson algebras. On the other
hand, using $SN$5) and De Morgan properties we have $\sim(x\lor\sim x)=\sim
x\land x\leq x\lor\sim x$, so $x\lor\sim x\in A^{+}$. Therefore
$[\\![x]\\!]\cup[\\![\sim x]\\!]=[\\![x\lor\sim x]\\!]\in[\\![A^{+}]\\!]$.

$\delta_{A}$ is surjective: If $([\\![x]\\!],[\\![y]\\!])\in\alpha\beta(A,F)$,
then $([\\![x]\\!],[\\![y]\\!])=([\\![x]\\!],[\\![\sim x]\\!])$. Indeed, this
is a consequence of $([\\![x]\\!],[\\![y]\\!])\to([\\![x]\\!],[\\![\sim
x]\\!])=([\\![x]\\!]\Rightarrow[\\![x]\\!],[\\![x]\\!]\cap[\\![\sim
x]\\!])=([\\![1]\\!],[\\![x\land\sim x]\\!])=([\\![1]\\!],[\\![0]\\!])$ and
$([\\![x]\\!],[\\![\sim
x]\\!])\to([\\![x]\\!],[\\![y]\\!])=([\\![x]\\!]\Rightarrow[\\![x]\\!],[\\![x]\\!]\cap[\\![y]\\!])=([\\![1]\\!],[\\![0]\\!])$.
Therefore $\delta_{A}(x)=([\\![x]\\!],[\\![y]\\!])$.

$\delta_{A}$ is injective: If $([\\![x]\\!],[\\![\sim
x]\\!])=([\\![y]\\!],[\\![\sim y]\\!])$, then $[\\![x]\\!]=[\\![y]\\!]$ and
$[\\![\sim x]\\!]=[\\![\sim y]\\!]$, so we have the following: $x\to y=1$,
$y\to x=1$, $\sim x\to\sim y=1$, $\sim y\to\sim x=1$. By proposition 2.11 (1),
we have that $x\mbox{$\ \to_{\text{\tiny N}}\ $}y=1$, $y\mbox{$\
\to_{\text{\tiny N}}\ $}x=1$, $\sim x\mbox{$\ \to_{\text{\tiny N}}\ $}\sim
y=1$, $\sim y\mbox{$\ \to_{\text{\tiny N}}\ $}\sim x=1$, which implies (see
for example [Vig99], (1.15)) that $x=y$.

$\delta_{A}$ is a $\mathbf{sN}$-morphism:

  * •

$\delta_{A}(x)\sqcup\delta_{A}(y)=([\\![x]\\!],[\\![\sim
x]\\!])\sqcup([\\![y]\\!],[\\![\sim
y]\\!])=([\\![x]\\!]\cup[\\![y]\\!],[\\![\sim x]\\!]\cap[\\![\sim
y]\\!])=([\\![x\lor y]\\!],[\\![\sim x\land\sim y]\\!])=([\\![x\lor
y]\\!],[\\![\sim(x\lor y)]\\!])=\delta_{A}(x\lor y)$. In a similar manner we
can prove that $\delta_{A}(x)\sqcap\delta_{A}(y)=\delta_{A}(x\land y)$.

  * •

$\sim\delta_{A}(x)=\sim([\\![x]\\!],[\\![\sim x]\\!])=([\\![\sim
x]\\!],[\\![x]\\!])=\delta_{A}(\sim x)$.

  * •

$\delta_{A}(x)\to\delta_{A}(y)=([\\![x]\\!],[\\![\sim
x]\\!])\to([\\![y]\\!],[\\![\sim
y]\\!])=([\\![x]\\!]\Rightarrow[\\![y]\\!],[\\![x]\\!]\cap[\\![\sim
y]\\!])=([\\![x\to y]\\!],[\\![x\land\sim y]\\!])$.

By $SN$10) and $SN$11), we see that $[\\![x\land\sim y]\\!]=[\\![\sim(x\to
y)]\\!]$. Hence $\delta_{A}(x)\to\delta_{A}(y)=([\\![x\to
y]\\!],[\\![x\land\sim y]\\!])=([\\![x\to y]\\!],[\\![\sim(x\to
y)]\\!])=\delta_{A}(x\to y)$.

Finally, $\delta$ is a natural transformation: to see that this diagram
commutes,

$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\delta_{A}}$$\scriptstyle{f}$$\textstyle{\alpha\beta(A)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\alpha\beta(f)}$$\textstyle{A^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\delta_{A^{\prime}}}$$\textstyle{\alpha\beta(A^{\prime})}$

we calculate
$\alpha\beta(f)\circ\delta_{A}(x)=\alpha\beta(f)([\\![x]\\!],[\\![\sim
x]\\!])=([\\![f(x)]\\!],[\\![f(\sim x)]\\!])=([\\![f(x)]\\!],[\\![\sim
f(x)]\\!])=\delta_{A^{\prime}}\circ f(x)$. $\blacksquare$

###### Example 3.14

Consider the semi-Nelson algebra $\mathbf{A}$, with Hasse diagram indicated
below, in which the operations $\to$ and $\sim$ are given by the following
tables:

$0$$a$$b$$d$$c$$e$$f$$g$$1$$A$

$\to$ | $0$ | $a$ | $b$ | $c$ | $d$ | $e$ | $f$ | $g$ | $1$
---|---|---|---|---|---|---|---|---|---
$0$ | $1$ | $1$ | $1$ | $1$ | $g$ | $1$ | $g$ | $1$ | $g$
$a$ | $1$ | $1$ | $1$ | $1$ | $g$ | $1$ | $g$ | $1$ | $g$
$b$ | $1$ | $1$ | $1$ | $1$ | $g$ | $1$ | $g$ | $1$ | $g$
$c$ | $1$ | $1$ | $1$ | $1$ | $g$ | $1$ | $g$ | $1$ | $g$
$d$ | $e$ | $g$ | $e$ | $g$ | $1$ | $e$ | $1$ | $g$ | $1$
$e$ | $d$ | $d$ | $f$ | $f$ | $a$ | $1$ | $c$ | $1$ | $g$
$f$ | $e$ | $g$ | $e$ | $g$ | $1$ | $e$ | $1$ | $g$ | $1$
$g$ | $d$ | $d$ | $f$ | $f$ | $a$ | $1$ | $c$ | $1$ | $g$
$1$ | $0$ | $a$ | $b$ | $c$ | $d$ | $e$ | $f$ | $g$ | $1$

$x$ | $0$ | $a$ | $b$ | $c$ | $d$ | $e$ | $f$ | $g$ | $1$
---|---|---|---|---|---|---|---|---|---
$\sim x$ | $1$ | $g$ | $f$ | $c$ | $e$ | $d$ | $b$ | $a$ | $0$

$S=\\{0,a,d,e,g,1\\}$ is the universe of a subalgebra $\mathbf{S}$ of
$\mathbf{A}$. Both $\mathbf{S}$ and $\mathbf{A}$ have the same quotient semi-
Nelson algebra $\mathbf{H}$ indicated below:

$[\\![0]\\!]$$[\\![d]\\!]$$[\\![e]\\!]$$[\\![1]\\!]$$H$

$\Rightarrow$ | $[\\![0]\\!]$ | $[\\![d]\\!]$ | $[\\![e]\\!]$ | $[\\![1]\\!]$
---|---|---|---|---
$[\\![0]\\!]$ | $[\\![1]\\!]$ | $[\\![e]\\!]$ | $[\\![1]\\!]$ | $[\\![e]\\!]$
$[\\![d]\\!]$ | $[\\![e]\\!]$ | $[\\![1]\\!]$ | $[\\![e]\\!]$ | $[\\![1]\\!]$
$[\\![e]\\!]$ | $[\\![d]\\!]$ | $[\\![0]\\!]$ | $[\\![1]\\!]$ | $[\\![e]\\!]$
$[\\![1]\\!]$ | $[\\![0]\\!]$ | $[\\![d]\\!]$ | $[\\![e]\\!]$ | $[\\![1]\\!]$

$E=\\{[\\![e]\\!],[\\![1]\\!]\\}$ is an i-filter of $\mathbf{H}$, and
$\mathbf{N(H,E)}$ is isomorphic to $\mathbf{S}$, while
$\mathbf{N(H,H)}=\mathbf{V_{k}(H)}$ is isomorphic to $\mathbf{A}$.

##  4 Dually Hemimorphic semi-Nelson Algebras

In this section we will show some results about the variety of dually
hemimorphic semi-Heyting and semi-Nelson algebras, which were presented in
definitions 2.8 and 2.9 respectively. We omit some proofs of the following
results, since it can be founded in [CSM19].

###### Lemma 4.1

Let $\mathbf{A}\in\mbox{$\cal DSN$}$. If we consider the equivalence relation
$\equiv$ defined in section 2.2, then that relation is compatible with respect
of the operation ′. Hence, $\equiv$ is a congruence in $\cal DSN$.

In view of the previous lemma, we can define

$[\\![x]\\!]^{\dagger}=[\\![x^{\prime}]\\!]$

and moreover, it can be proved that $\mathbf{dsH}(A)=\langle
A/\equiv;\cap,\cup,\Rightarrow,^{\dagger},\bot,\top\rangle\in\mbox{$\cal
DSH$}$.

###### Definition 4.2

Let $\mathbf{A}=\langle
A;\cap,\cup,\Rightarrow,^{\dagger},\bot,\top\rangle\in\mbox{$\cal DSH$}$. For
$(a,b)\in V_{k}(A)$ we define the following unary operation on $V_{k}(A)$:

$(a,b)^{\prime}=(a^{\dagger},b\cap(a^{\dagger}\Rightarrow a)).$

The operation is well defined. Indeed, using $SH\ref{infimoeimplicaSH}$) we
have $a^{\dagger}\cap b\cap(a^{\dagger}\Rightarrow a)=b\cap
a^{\dagger}\cap(a^{\dagger}\Rightarrow a)$ $=b\cap a^{\dagger}\cap a=0$.

###### Theorem 4.3

If $\mathbf{A}\in\mbox{$\cal DSH$}$, then the system
$\mathbf{V_{k}(A)}=\langle
V_{k}(A);\sqcap,\sqcup,\to,\sim,^{\prime},\top\rangle$ is a dually hemimorphic
semi-Nelson algebra.

In a similar manner as on section 2.1, we have the following representations:

###### Theorem 4.4

[CSM19] If $\mathbf{A}\in\mbox{$\cal DSH$}$, then $\mathbf{A}$ is isomorphic
to $\mathbf{dsH}(\mathbf{V_{k}}(\mathbf{A}))$. Also, if
$\mathbf{A}\in\mbox{$\cal DSN$}$, then $\mathbf{A}$ is isomorphic to a
subalgebra of $\mathbf{V_{k}(dsH(A))}$.

Now we will generalize the results of section 3. In [CSM18] the authors
introduced the category $\mbox{$\cal SN$}_{c}$ of centered semi-Nelson
algebras whose objects are algebras $\mathbf{A}=\langle
A;\land,\lor,\to,\sim,c,1\rangle$ of type $(2,2,2,1,0,0)$ such that $c=\sim
c$, and the morphisms are the algebra homomorphisms. The element $c$ is called
a _center_ of the algebra $A$, and it is necessarily unique. We can expand the
category $\mbox{$\cal SN$}_{c}$ to $\mbox{$\cal DSN$}_{c}$ of dually
hemimorphic centered semi-Nelson algebras whose objects are algebras
$\mathbf{A}=\langle A;\land,\lor,\to,\sim,^{\prime},c,1\rangle$ of type
$(2,2,2,1,1,0,0)$ such that $c=\sim c$, and the morphisms are the algebra
homomorphisms.

We will prove that the categories $\cal DSN$ and $\mbox{$\cal DSN$}_{c}$
actually coincide.

###### Proposition 4.5

If $\mathbf{A}\in\mbox{$\cal DSN$}$, then $\mathbf{A}$ is centered, with
center $1^{\prime}$.

Proof.  We want to prove that $\sim 1^{\prime}=1^{\prime}$, or equivalently,
the following conditions holds simultaneously:

$\sim 1^{\prime}\to 1^{\prime}=1,\ 1^{\prime}\to\sim 1^{\prime}=1,$ $\sim
1^{\prime}\to\sim(\sim 1^{\prime})=1,\ \sim(\sim 1^{\prime})\to\sim
1^{\prime}=1.$ (4.1)

By Proposition 2.11 (1), (4.1) is equivalent to

$\sim 1^{\prime}\mbox{$\ \to_{\text{\tiny N}}\ $}1^{\prime}=1,\
1^{\prime}\mbox{$\ \to_{\text{\tiny N}}\ $}\sim 1^{\prime}=1,\ $ $\sim
1^{\prime}\mbox{$\ \to_{\text{\tiny N}}\ $}\sim(\sim 1^{\prime})=1,\ \sim(\sim
1^{\prime})\mbox{$\ \to_{\text{\tiny N}}\ $}\sim 1^{\prime}=1,$

which is equivalent to show that

$\sim 1^{\prime}\mbox{$\ \to_{\text{\tiny N}}\ $}1^{\prime}=1,$ (4.2)
$1^{\prime}\mbox{$\ \to_{\text{\tiny N}}\ $}\sim 1^{\prime}=1.$ (4.3)

By (DSN4), (DSN5), and proposition 1, we have that $\sim 1^{\prime}\mbox{$\
\to_{\text{\tiny N}}\ $}(\sim 1\land(1^{\prime}\to 1))=1$, that is (1) $\sim
1^{\prime}\mbox{$\ \to_{\text{\tiny N}}\ $}0=1$. Since in every Nelson algebra
$0\mbox{$\ \to_{\text{\tiny N}}\ $}x=x$ holds for all $x$, it follows that (2)
$0\mbox{$\ \to_{\text{\tiny N}}\ $}1^{\prime}=1^{\prime}$. By (1), (2) and
proposition 2.11 (2), we have that $\sim 1^{\prime}\mbox{$\ \to_{\text{\tiny
N}}\ $}1^{\prime}=1$, which proves (4.2).

By (DSN2) we have (3) $1=1^{\prime}\to\sim 1=1^{\prime}\to
0=1^{\prime}\to(1^{\prime}\land 0)=1^{\prime}\mbox{$\ \to_{\text{\tiny N}}\
$}0$. Using again that $0\mbox{$\ \to_{\text{\tiny N}}\
$}1^{\prime}=1^{\prime}$, and proposition 2.11 (2), gives us $\sim
1^{\prime}\mbox{$\ \to_{\text{\tiny N}}\ $}1=1$, which proves (4.3).
$\blacksquare$

Proposition 4.5 shows us that the category $\cal DSN$ it can be viewed as the
category $\mbox{$\cal DSN$}_{c}$ with a distinguished element $c$, but despite
the change of the language, both categories are essentially the same.

It was proved in [CSM18] that there is a categorial equivalence between semi-
Heyting algebras and centered semi-Nelson algebras. Moreover, the function $h$
defined in the proof of Theorem 4.4 is an isomorphism. This gives us the
following:

###### Theorem 4.6

If $\mathbf{A}\in\mbox{$\cal DSN$}$, then $\mathbf{A}$ is isomorphic to
$\mathbf{V_{k}(dsH(A))}$.

###### Observation 4.7

Another way of proving Theorem 4.6 is the following: if we consider the
structure $\mathbf{N(H,E)}$ as in Lemma 3.5, and take
$\mathbf{H}\in\mbox{$\cal DSH$}$, we have no guarantee that this set is going
to be a closed under the operation †. If instead we consider a subalgebra
$\mathbf{S}$ such that $\pi_{1}(S)=H$, then the proof indicated in the lemma
still holds for the variety $\cal DSH$, since it does not use the operations ′
or †. Hence, the sets $S$ and $N(H,E)$ are equal, so $N(H,E)$ inherits the
operations from $\mathbf{S}$. Indeed, due to Theorem 4.4, we know that the
function $h:A\to\mathbf{V_{k}}(\mathbf{dsH}(A))$ defined by
$h(a)=([\\![a]\\!],[\\![\sim a]\\!])$ is a monomorphism. Hence, $A\cong h(A)$.
Let us take then the subalgebra $\mathbf{S}=h(\mathbf{A})$ of
$\mathbf{V_{k}}(\mathbf{dsH}(\mathbf{A}))$. It is immediate that
$\pi_{1}(S)=\mathbf{dsH}(A)$. Therefore, by Lemma 3.5,
$h(\mathbf{A})=\mathbf{N(dsH(A),E)}$ for
$E=\\{[\\![x]\\!]\in\mathbf{dsH}(A):[\\![x]\\!]=[\\![a]\\!]\lor[\\![b]\\!],([\\![a]\\!],[\\![b]\\!])\in
S\\}$.

Since $\mathbf{S}$ is a subalgebra of
$\mathbf{V_{k}}(\mathbf{dsH}(\mathbf{A}))$, we have that
$([\\![1]\\!],[\\![0]\\!])\in S$, so the center
$([\\![0]\\!],[\\![0]\\!])=([\\![1]\\!],[\\![0]\\!])^{\prime}$ is an element
of $S$. Then $[\\![0]\\!]=[\\![0]\\!]\lor[\\![0]\\!]\in E$. Since $E$ is a
filter, this shows that $E=\mathbf{dsH}(A)$.

We have proved that
$S=N(\mathbf{dsH}(A),\mathbf{dsH}(A))=\mathbf{V_{k}}(\mathbf{dsH}(A))$, and
therefore $h$ is an isomorphism.

###### Example 4.8

Consider the semi-Nelson algebras $\mathbf{A}$ and its subalgebra $\mathbf{S}$
from Example 3.14. We know by the results above that $\mathbf{S}$ cannot be
expanded by adding a unary operation ′ in such a way that the system
$\mathbf{B}=\langle B;\land,\lor,\to,\sim,^{\prime},1\rangle$ becomes a dually
hemimorphic semi-Nelson algebra, since $\mathbf{S}$ has no center.

On the other hand, any operation ′ that makes $\mathbf{sH(A)}$ into a dually
hemimorphic semi-Heyting algebra yields an operation † that will turn $A$ into
a dually hemimorphic semi-Nelson algebra.

## References

  * [ACDV13] Manuel Abad, Juan Manuel Cornejo, and Jose Patricio Diaz Varela.  Semi-heyting algebras term-equivalent to gödel algebras.  Order, (2):625–642, 2013.
  * [BD74] Raymond Balbes and Philip Dwinger.  Distributive lattices.  University of Missouri Press, Columbia, Mo., 1974.
  * [CSM18] Juan Manuel Cornejo and Hernán Javier San Martín.  A categorical equivalence between semi-Heyting algebras and centered semi-Nelson algebras.  Logic Journal of the IGPL, 26(4):408–428, 04 2018.
  * [CSM19] Juan Manuel Cornejo and Hernán Javier San Martín.  Dually hemimorphic semi-Nelson algebras.  Logic Journal of the IGPL, 11 2019.  jzz030.
  * [CV16] Juan M. Cornejo and Ignacio D. Viglizzo.  Semi-nelson algebras.  Order, 2016.  DOI: 10.1007/s11083-016-9416-x.
  * [Kal58] J. A. Kalman.  Lattices with involution.  Trans. Amer. Math. Soc., 87:485–491, 1958.
  * [MM96] António Monteiro and Luiz Monteiro.  Axiomes indépendants pour les algèbres de Nelson, de łukasiewicz trivalentes, de De Morgan et de Kleene.  In Unpublished papers, I, volume 40 of Notas Lógica Mat., page 13. Univ. Nac. del Sur, Bahía Blanca, 1996.
  * [MV19] Luiz F. Monteiro and Ignacio D. Viglizzo.  Construction of nelson algebras.  In Actas del XIV Congreso Dr. Antonio A. R. Monteiro (2017), Actas Congr. “Dr. Antonio A. R. Monteiro”, pages 63–71, Bahía Blanca, 2019\. Univ. Nac. del Sur.
  * [San85] Hanamantagouda P. Sankappanavar.  Semi-Heyting algebras.  Amer. Math. Soc. Abstracts, page 13, January 1985.
  * [San08] Hanamantagouda P. Sankappanavar.  Semi-Heyting algebras: an abstraction from Heyting algebras.  In Proceedings of the 9th “Dr. Antonio A. R. Monteiro” Congress (Spanish), Actas Congr. “Dr. Antonio A. R. Monteiro”, pages 33–66, Bahía Blanca, 2008. Univ. Nac. del Sur.
  * [San11] Hanamantagouda P. Sankappanavar.  Expansions of semi-Heyting algebras I: Discriminator varieties.  Studia Logica, 98(1-2):27–81, 2011.
  * [Sen84] Andrzej Sendlewski.  Some investigations of varieties of $n$-lattices.  Studia Logica, 43(3):257–280, 1984.
  * [Sen90] Andrzej Sendlewski.  Nelson algebras through Heyting ones. I.  Studia Logica, 49(1):105–126, 1990.
  * [Vak77] D. Vakarelov.  Notes on ${\cal N}$-lattices and constructive logic with strong negation.  Studia Logica, 36(1–2):109–125, 1977.
  * [Vig99] Ignacio Viglizzo.  Álgebras de Nelson.  Instituto de Matemática de Bahía Blanca, Universidad Nacional del Sur, 1999.  Magister dissertation in Mathematics, Universidad Nacional del Sur, Bahía Blanca, available at https://sites.google.com/site/viglizzo/viglizzo99nelson.


# A Neural Model for Text Localization, Transcription and Named Entity
Recognition in Full Pages

Manuel Carbonell<EMAIL_ADDRESS>Alicia Fornés  Mauricio Villegas
Josep Lladós  Computer Vision Center, Computer Science Department, Universitat
Autònoma de Barcelona, Spain  omni:us, Berlin, Germany

###### Abstract

In the last years, the consolidation of deep neural network architectures for
information extraction in document images has brought big improvements in the
performance of each of the tasks involved in this process, consisting of text
localization, transcription, and named entity recognition. However, this
process is traditionally performed with separate methods for each task. In
this work we propose an end-to-end model that combines a one stage object
detection network with branches for the recognition of text and named entities
respectively in a way that shared features can be learned simultaneously from
the training error of each of the tasks. By doing so the model jointly
performs handwritten text detection, transcription, and named entity
recognition at page level with a single feed forward step. We exhaustively
evaluate our approach on different datasets, discussing its advantages and
limitations compared to sequential approaches. The results show that the model
is capable of benefiting from shared features for simultaneously solving
interdependent tasks.

###### keywords:

###### MSC:

41A05, 41A10, 65D05, 65D17 document image analysis , Information extraction ,
Text detection , Handwritten text recognition , named entity recognition ,
deep neural networks , multi-task learning

††journal: Pattern Recognition Letters

##  1 Introduction

The process of information extraction from document images consists in
transcribing textual contents and classifying them into semantic categories
(i.e. named entities). It is a necessary process in digital mailroom
applications in business documents, or record linkage in historical
manuscripts. Information extraction involves localizing, transcribing and
annotating text, and varies from one domain to another. Despite the recent
improvements in neural network architectures, efficient information extraction
from unstructured or semi-structured document images remains a challenge and
human intervention is still required [1],[2].

In the particular case of handwritten text interpretation, the performance of
handwritten text recognition (HTR) is strongly conditioned by the accuracy of
a previous segmentation step. But in the other way around, a good segmentation
performance can be boosted if the words are recognized. This chicken-and-egg
problem (namely _Sayre’s paradox_) can also be stated for other steps in the
information extraction pipeline: transcription vs named entity recognition
(NER), or localization vs named entity categorization when there is an
inherent positional structure in the document (e.g. census records, invoices
or registration forms).

This fact motivates us to hypothesize that joint models may be beneficial for
information extraction. In [3] we studied the combination of handwritten text
recognition with named entity recognition in text lines. Later on, we explored
in [4] the interaction of text localization and recognition in full pages. In
both works, we observed a benefit when leveraging the dependency of these
pairs of tasks with a single joint model.

In this work we go a step further and explore the combination of the three
tasks for information extraction in full pages by unifying the whole process
in a single end-to-end architecture. We test our method on different
scenarios, including data sets in which there is bi-dimensional contextual
relevant information for the named entity tag, or there is an inherent
syntactic structure in the document. Thus, we explore the benefits and
limitations of an end-to-end model in comparison with architectures that
integrate the different tasks of the pipeline as stand alone components. We
experimentally validate the different alternatives considering different kind
of documents, in particular how relevant is the geometric context, how regular
is the layout, how is the strength of the named entities in the document, etc.

As far as we know, this is the first method that performs end-to-end
information extraction in full handwritten pages. Our joint model is able to
exploit benefits from task interaction in cases where these are strongly
interdependent. Another strength of the method is its versatility, as it can
be used in a wide variety of information extraction scenarios. Finally, we
also contribute with a baseline for full-page information extraction in semi-
structured heterogeneous documents of the IEHHR competition dataset [5].

The paper is organized as follows. In section 2 we overview the related work.
In section 3 we describe our joint model. In sections 4 and 5, we present the
datasets, the experimental results and discuss the advantages and limitations
of our joint model. Finally, in section 6 we draw the conclusions.

##  2 Related Work

Since information extraction implies localizing, transcribing and recognizing
named entities in text, we review works that deal with each of these parts
separately and with pairwise task unified models.

Text localization, which can be faced as an object detection problem, has been
divided into two main type of paradigms, one-stage and two-stage. In [6] a two
stage method is proposed by first generating a sparse set of candidate
proposals followed by a second stage that classifies the proposals into
different classes and background. Regions with CNN features (R-CNN) [7]
replaced the second stage with a CNN, improving the previous methods. The next
big improvement in terms of performance and speed came with Faster-RCNN [7],
where the concept of anchors was introduced. When prioritizing speed in front
of accuracy, we find one stage detection as the best option. Concretely, SSD
[8] and YOLO [9] have put one-stage methods close to two-stage in precision
but having much greater speed performance. The decrease in precision of one-
stage against two-stage methods is due to the class imbalance in [10], so
focal loss is introduced to cope with this problem and achieve state of the
art performance both in accuracy and speed.

Regarding the transcription part, many HTR methods already perform a joint
segmentation and recognition at line level to cope with the _Sayre’s paradox_.
In this way, they can avoid the segmentation at character or word level.
However, this is only partially solving the segmentation problem, because
lines that are not properly segmented obviously affect the recognition. For
this reason, some recent approaches propose to recognize text at paragraph
level [11], [12]. But still, an inaccurate segmentation into paragraphs will
affect the HTR performance.

Taking into account those considerations, a joint method that can perform both
tasks allows the noise in the predicted segmentation and obtains better
transcriptions. In our previous work [4] we proposed a model that predicts
text boxes together with their transcription directly from the full page, by
applying RoI pooling to shared convolutional features. In this way we avoid
the need of having a perfect segmentation to get a good transcription at word
level. It must be mentioned that in [13] the benefits of end-to-end learning
for full page text recognition are put in doubt, since the best transcription
performance is achieved by detecting the start of the text line, segmenting it
with a line follower and then transcribing it with three separately trained
networks. Nevertheless no results are shown regarding the multi-task end-to-
end trained model to draw a definitive conclusion.

There are several approaches for named entity recognition. In the scenario
where we have error-free raw digitized text and the goal is to sequentially
label entities, most approaches [14], [15], [16] use stacked long short-term
memory network layers (LSTM) to recognize sequential word patterns and a
conditional random field (CRF) to predict tags for each time step hidden
state. Also character level word representations capture morphological and
orthographic information that combined with the sequential word information
achieve good results.

In the previously mentioned cases, error-free raw text is assumed for named
entity recognition. In case text is extracted from scanned documents, the
situation changes. In [17] a single convolutional neural network (CNN) is used
to directly classify word images into different categories skipping the
recognition step. This approach, however, does not make use of the context
surrounding the word to be classified, which might be critical to correctly
predict named entity tags. In [18] and [1] a CNN is combined with a Long
short-term memory (LSTM) network to classify entities sequentially thereby
making use of the context, achieving good results. This is improved in [3] and
[19] by joining the tasks of text recognition and named entity recognition by
minimizing the Connectionist Temporal Classification loss (CTC) [20] for both.
Still, in these works there is no bi-dimensional context pattern analysis.
Very recently an attention-based method [21] performs entity extraction in a
very controlled scenario as ID cards, where a static layout implies that is
not necessary to detect complex text bounding boxes. In summary, all these
works suggest that it is promising to explore methodologies that integrate the
three tasks in a unified model.

##  3 Methodology

As introduced before, our model extracts information in a unified way. First,
convolutional features are extracted from the page image, and then, different
branches analyze these features for the tasks of classification, localization,
and named entity recognition, respectively. An overview of the architecture is
shown in Figure 1.

Fig. 1: Overview of the proposed method. Convolutional features are extracted
with ResNet18 and FPN. The classification and regression branches calculate
the positive boxes and the recognition branch predicts the transcription of
the content of each box. Cross entropy, squared-sum and CTC losses are
backpropagated through the whole model for training.

###  3.1 Shared features

Since the extracted features must be used for very different tasks, i.e.
localization, transcription and named entity recognition, we need a deeper
architecture than the one used for each isolated task. According to recent
work on object detection and text semantic segmentation [22], a proper
architecture to extract convolutional features from the image is Residual
Network 18 (ResNet18) [23]. We have considered exploring deeper architectures
or variations of ResNet18 to improve the final performance, yet the scope of
this work is not to find the best feature extraction but to unify the whole
information extraction process. ResNet18 consists of 5 residual convolutional
blocks. Each of those encloses 2 convolutional layers, followed by a rectifier
linear unit activation and a residual connection. Table 1 shows the detailed
list of blocks and configuration of the shared feature extractor.

Table 1: ResNet18 architecture used for feature extraction. Layer | output shape | kernel size |  $\mid$ kers $\mid$
---|---|---|---
res-conv-block 1 | H/2$\cdot$W/2 | 3 x 3 | 64
res-conv-block 2 | H/4$\cdot$W/4 | 3 x 3 | 64
res-conv-block 3 | H/8$\cdot$W/8 | 3 x 3 | 128
res-conv-block 4 | H/16$\cdot$W/16 | 3 x 3 | 256
res-conv-block 5 | H/32$\cdot$W/32 | 3 x 3 | 512

We have also tried to reduce the amount of layers of the ResNet18 but when
doing so, the training on the benchmark text recognition dataset IAM [24]
converged slower and the final validation error was higher than when using the
full ResNet18 architecture. We attribute this effect to the increase of noisy
detections and false positives, in which the model was confusing relevant with
non-relevant text. A visualization of the ResNet18 training compared to a 2
block lighter architecture and the corresponding predictions after 20 epochs
can be seen in Figure 2.

---
Fig. 2: (Top) Plot comparing the regression loss during training on the
benchmark dataset IAM for ResNet18 (green) against a 2 convolutional block
reduced version (red). (Middle) Predictions on IAM with 2 convolutional block
model. (Bottom) Predictions on IAM with ResNet18 model. The model does not
confuse relevant with irrelevant text.

Consequently, we chose an intermediate depth model which allows to tackle such
complex tasks at once. The output of the Feature Pyramid Network is a set of 5
down sampled feature maps with scales 1/8,1/16,1/32,1/64,1/128 with respect to
the input image. Each of these are forwarded to the upcoming branches and
their output is stacked in a single tensor, from which we later select the
most confident predictions.

###  3.2 Classification branch

Concerning the detection and classification of objects in images, there are
different approaches regarding the prediction of the probability of an object
being present in a given location of the image. The two most used options are,
either to regress the intersection over union (IoU) of the predicted box with
the ground truth box as done in [9], or to predict the probability of each
object of a given class for each location with a separate branch, encoded as a
one-hot vector as in [22]. We have chosen this second option due to its
performance for a wide variety of data sets. The architecture of this branch
is shown in table 2.

Table 2: Classification and regression branch architectures, where downsampling levels are $ds_{l_{i}}\in\\{8,16,32,64,128\\}$. Layer | output shape | kernel size |  $\mid$ kers$\mid$
---|---|---|---
conv-block 1 | $H/ds_{l_{i}}\cdot W/ds_{l_{i}}$ | 3 x 3 | 256
conv-block 2 | $H/ds_{l_{i}}\cdot W/ds_{l_{i}}$ | 3 x 3 | 256
conv-block 3 | $H/ds_{l_{i}}\cdot W/ds_{l_{i}}$ | 3 x 3 | 256
conv-block 4 | $H/ds_{l_{i}}\cdot W/ds_{l_{i}}$ | 3 x 3 | 256
conv-block 5 | $n_{\text{anchors}}\cdot\\{n_{\text{classes}},4\\}$ | 3 x 3 | 1

We also explored to use this branch as a named entity classifier. The
motivation behind is to take context into account through the prediction of
the presence of certain features in a neighbourhood of a point of the
convolutional grid. The difficult part comes when attempting to capture
dependencies between distant parts of the image, as it happens when a
sequential approach is used. More specifically, the classification branch, or
objectness loss in case of a pure text localizer classifier, is trained with
the following cross-entropy loss function:

$CE(p_{cl})=-(y_{cl}\cdot log(p_{cl})+(1-y_{cl})\cdot log(1-p_{cl}))$ (1)

###  3.3 Regression branch

To predict the coordinates of the box positives, the regression branch
receives the shared features and, after 4 convolutions with rectifier linear
unit (ReLU), it predicts the offset values of the predefined anchors.
Formally:

$\displaystyle\centering x\@add@centering$ $\displaystyle=X+{dx}\cdot W$
$\displaystyle y$ $\displaystyle=Y+{dy}\cdot H$ $\displaystyle w$
$\displaystyle=e^{dw}\cdot W$ $\displaystyle h$ $\displaystyle=e^{dh}\cdot H$
(2)

where $(x,y,w,h)$ are the predicted box coordinates, $dx,dy,dw,dh$ are the
predicted offsets and $X,Y,W,H$ are the predefined anchor box values. The
offset of the predefined anchors is regressed by minimizing the mean square
error:

$MSE(\delta,\delta^{\prime})=(\delta-\delta^{\prime})^{2}$ (3)

being $\delta$ the vector of target offsets of the anchors for each ground
truth box. The anchors are generated as the combination of the ratios
$\frac{1}{2}$,1,2 and the scales 1, $2^{\frac{1}{3}}$, $2^{\frac{2}{3}}$ with
a base size of 32 (9 anchors) as shown in Figure 3.

Fig. 3: Anchors combining ratios $\frac{1}{2},1,2$ and scales $1$,
$2^{\frac{1}{3}}$, $2^{\frac{2}{3}}$, with a base size of $32$ (9 anchors).

###  3.4 Feature pooling

Once we have predicted the class probabilities and the coordinate offsets for
each anchor in each point of the $Im_{H}/8\times Im_{W}/8$ convolutional grid,
we select the boxes whose confidence score surpasses a given threshold, and
remove the overlapping ones applying a non-maximal suppression algorithm. With
the given box coordinates, we apply RoI pooling [7] to the convolutional
features of the full page, but saving the input to allow error backpropagation
from further branches. We use the 5 levels of the feature pyramid to calculate
the box anchor offsets and the objectness values. Conversely, for
computational reasons, we only keep the least downsampled features for the
text recognition and named entity recognition branches, as we need the highest
possible resolution for those tasks.

###  3.5 Text recognition branch

As in [4] we build a recognition branch that will predict the text contained
in each box. The architecture of this branch, shown in Table 3, consists of
two convolutional blocks followed by a fully connected layer. The output of
this layer is the probability of a character for each column of each one of
the pooled features. From these predictions, we calculate the Connectionist
Temporal Classification (CTC) loss [20]. This loss, or Maximum Likelihood
error, is calculated as the negative logarithm of the probability of a ground
truth text sequence given the network outputs

$O^{ML}(\mathcal{D},Y^{\prime})=-\sum_{(x,y)\in D}ln(p(y|x))$ (4)

being $\mathcal{D}={(x,y)_{i=1}^{i=N}}$ the set of training input-target pairs
and $Y^{\prime}$ the set of network sequence outputs.

To calculate this probability, we add the probabilities of all possible paths
in the [time steps $\times$ alphabet length] matrix with the forward-backward
algorithm. Repeated output characters not separated by blank (non-character)
are joined using the collapse function $\mathcal{B}$, for example,
$\mathcal{B}$(hheeel-llo)=hello. This loss is added to the classification and
regression losses to backpropagate them together for each gradient update.

Table 3: Recognition branch architecture. Layer | Output shape | ker size |  $\mid$ kers$\mid$
---|---|---|---
conv-block 1 | pool H$\cdot$pool W | 3 x 3 | 256
conv-block 2 | pool H$\cdot$pool W | 3 x 3 | 256
Fully connected | pool W$\cdot$ $|alphabet|$ | - | -

###  3.6 Semantic annotation branch

As we mentioned before, one possibility to assign a semantic tag to each word
is to predict its class from the classification branch for each anchor.
However, this would not capture the context as the activations only rely on
the convolutional feature maps of a neighborhood of each point. For this
reason, we add this network branch to predict the semantic tags as a sequence
from the ordered pooled features of each box. For simple layouts, such as
single paragraph pages, the pooled features, which correspond to text boxes in
the page, are sorted in reading order (i.e. left to right and top to bottom)
by projecting a continuation of the right side of the text box. Once we have
the ordered pooled features, we pad them and apply two convolutions followed
by a fully connected network as a standard named entity recognition
architecture. Then, we minimize the cross entropy loss shown in equation 1 for
each of the sequence values.

###  3.7 Receptive field calculation

Our approach assumes that each activation of a neuron in the deepest layers of
a CNN depends on the values of a wide region of the input image, i.e. its
receptive field. Also it is important to notice that the closer a pixel is to
the center of the field, the more it contributes to the calculation of the
output activation. This can be a useful property for documents where the
neighboring words determine the tag of a given word, but it can also be a
limitation when distant entities are related in a document. To calculate how
much context is taken in account for each unit of the features that are fed to
the RoI pooling layer, we must look at the convolutional kernel sizes $k$ and
strides $s$ of each layer. In this way, as in [25], we can calculate the
relation between the receptive field size of a feature map depending on the
previous layer’s feature map:

$r_{out}=r_{in}+(k-1)\cdot j_{in}$ (5)

where $j_{i}n$ is the jump in the output feature map, which increases in every
layer by a factor of the stride

$j_{out}=j_{in}*s$ (6)

By using these expressions with our architecture (ResNet 18 + FPN), we obtain
a receptive field size of 1559 in the shared convolutional feature map. That
means that, since the input images are 1250$\times$1760, the values predicted
for each unit mostly depend on the content of the whole page, giving more
importance to the corresponding location of the receptive field center.

##  4 Datasets

One of the limitations when exploring learning approaches for information
extraction is the few publicly available annotated datasets, probably due to
the confidential nature of this kind of data. Nonetheless, we test our
approach on three data sets. The details of amount of pages, words, out of
vocabulary (OOV) words and partitions can be found in Table 4.

Table 4: Characteristics of the datasets used in our experiments. Entities refer to the amount of relevant words (i.e. they do not belong to the class ”other”). | Part | IEHHR | WR | sGMB
---|---|---|---|---
Pages | train | 79 | 994 | 490
valid | 21 | 231 | 53
test | 25 | 323 | 50
Words | train | 2100 | 2837 | 7010
valid | 878 | 731 | 1740
test | 1020 | 1033 | 4085
$\|$OOV$\|$ | all | 387 | 853 | 1372
% OOV | all | 37 | 82 | 34
% entities | all | 52.5 | 100 | 17
$\|$entity tags$\|$ | - | 5 | 3 | 5

###  4.1 IEHHR

The IEHHR dataset is a subset of the Esposalles dataset [5] that has been
labeled for information extraction, and contains 125 handwritten pages with
1221 marriage records (paragraphs). Each record is composed of several text
lines giving information of the husband, wife and their parents’ names,
occupations, locations and civil states. On the sides of each paragraph we
find the husband’s family name and the fees paid for the marriage. An example
page is shown in Figure 7.

###  4.2 War Refugees

The War Refugees (WR) archives contain registration forms from refugee camps,
concentration camps, hospitals and other institutions, from the first half of
20th century. We have manually annotated the bounding boxes, transcriptions
and entity tags of names, locations and dates. Due to data privacy we cannot
share the images, but instead we show in Figure 4 a plot of all annotated text
normalized bounding boxes, where the colors correspond to different tags. As
we can observe, there is a strong pattern relating the text location and its
tag, although it is not fixed enough for applying a template alignment method.
The main difficulty of this dataset is to distinguish relevant from non-
relevant text, which in most cases only differs by its location or by a nearby
printed text key description. Another challenge is the high amount (82$\%$) of
out of vocabulary words, together with the high variability of the writing
style and the mixture of printed and handwritten text.

Fig. 4: Normalized bounding boxes of the tagged text of all training images in
the WR dataset.

###  4.3 Synthetic GMB

We have generated a synthetic dataset (sGMB) to explore the limitations of our
model, concretely in a standard named entity recognition task, in which text
is unstructured and the amount of named entities within the text is low. For
this purpose, we have generated synthetic handwritten pages with the text of
the GMB dataset [26] by using synthetic handwritten fonts, applying random
distortions and noise to emulate realistic scanned documents. Although it is
easier to recognize synthetic documents than real ones, the difficulty here
remains on the sequential named entity recognition task, especially because,
contrary to the previous datasets, here the text does not follow any
structure. An example is shown in Figure 5. The dataset and ground truth are
available here 111https://github.com/omni-us/research-dataset-sGMB.

Fig. 5: A generated page from the SynthGMB dataset. A major difficulty is the
sparsity of named entities with respect the other words.

##  5 Experiments

In this section we describe the experiments performed for each data set. We
optimized our model with stochastic gradient descent on the three described
losses in section 3. When unifying tasks in a single model, the model becomes
quite memory expensive. To overcome this limitation, during the training, we
had to set our batch size to be 1 page. Based on previous object detection
work we have chosen the learning rate to $10^{-4}$, the non-maximum
suppression threshold to 0.2 and the box sampling score threshold to 0.5. We
have chosen a patience of 100 epochs to trigger early stop.

###  5.1 Setup

In this work we propose a method for unifying the whole process of extracting
information from full pages in a single model. Nevertheless, our approach has
been evaluated using the following different configurations:

  * 1.

A: Triple task model. The first method variation consists in using our
proposed model to perform all tasks in a unified way using the objectness
branch for named entity classification as explained in section 3.2, with no
sequential layers but only convolutional ones.

  * 2.

B: Triple task sequential model. The second variation also performs the three
tasks in a unified way, but by concatenating the pooled features in reading
order and predicting the labels sequentially, as explained in section 3.6.

  * 3.

C: Detection + named entity recognition. In this case we consider to face the
extraction of the relevant named entities as a detection and classification
problem. Here, we ignore the recognition part and only backpropagate the
classification and regression losses from their respective branch outputs. We
also consider the sequential version of this approach explained in section
3.6.

  * 4.

D: Detection + transcription. Here we combine in a unified model the tasks of
localization and transcription, as seen in [4], in contrast to an approach in
which the two tasks are faced separately, where the recognition model would
cope with inaccurate text segmentations. Here we aim to observe how precisely
we can obtain text boxes and transcriptions, so that named entity recognition
can be applied afterwards.

  * 5.

CNN classifier. Finally, we evaluate the variability of the cropped words
among the different categories and the difficulty of annotating words
separately. Thus, we train a CNN network, similar to the classification branch
from our proposed method, that classifies words without using any shared
features for recognition or localization. So, this network does not benefit
from context information.

Diagrams of each setup can be seen in Figure 6. The full source code for all
experiments is publicly available here 222https://github.com/omni-
us/research-e2e-pagereader.

Fig. 6: Model setup variations, A-D. The differences rely on how the named
entities are recognized, and the optional integration of the recognition
branch.

###  5.2 Metrics

Different metrics have been used to evaluate the proposed methodology. One to
evaluate the performance of the text detection, one for named entity
recognition, and another for transcription. For text localization we used the
the widely used object detection metric, average precision. For named entity
recognition, we used the $F1$ score. Let $p=\frac{TP}{TP+FP}$ be the precision
metric, i.e. the number of true positives out of the total positive
detections; $r=\frac{TP}{TP+FN}$ be the recall metric, i.e. the number of true
positives out of the total ground truth positives, i.e. the true positives
plus false negatives. We consider the recall-precision map,
$p:[0,1]\mapsto[0,1]$ which maps the recall value $r$ to the precision $p$
that we obtain if we had the detection threshold to get such a recall. Then,
the Average Precision is the value $\int_{0}^{1}p(r)$, i.e. the area under the
precision-recall graph. The $F1$ score consists of the harmonic mean between
the precision and the recall:

$F1=2\cdot\frac{precision\cdot recall}{precision+recall}$ (7)

For text localization all the word bounding boxes are considered in the
metric. In contrast, for named entity recognition only the entity words count,
as it is standard in this kind of task. Also the recognized text is not used
to match the entities, only the location of the word within the page and the
entity tag. This is so that the metric only evaluates the prediction of
entities completely decoupled from the transcription performance.

For the transcription score we use the Character Error Rate (CER), i.e. the
number of insertions, deletions and substitutions to convert the output string
into the ground-truthed one, divided by the length of the string. Formally:

$CER=\frac{i+s+d}{\text{label length}}$

###  5.3 Results

From the results shown in Table 5, we observe that the localization
performance is high in general being this one the less challenging task of
all. Differences among the different setups and datasets are not significant.

For text recognition all methods perform similarly except in WR dataset. Setup
A shows a slight better performance than B and D. This suggests that the
eavesdropping effect mentioned in [27] might be taking place in this case. The
outnumbering of non-labeled words vs labeled in WR dataset increases
considerably the difficulty of the recognition task for this dataset due to
the same type of error observed in figure 2. We cannot show images of this
phenomena observable during training due to the confidential nature of the
documents. A possible solution to this would be to also have annotated words
which are not entities as it happens in IEHHR and sGMB.

For the entity recognition part, we do not observe significant differences
among the end-to-end approaches in the IEHHR dataset. This suggests that the
local neighborhood information seems enough to give correct predictions. The
high named entity recognition performance using the triple task sequential
approach (case B) in WR dataset suggests that it is beneficial to combine the
tasks of named entity recognition and localization. To have a better idea of
whether our method makes use of context or the sole content of the word is
sufficient, we compare its performance to the CNN classifier for segmented
words. Since we are facing a named entity recognition task, we only take into
account the entities, i.e. words labeled as ’other’ are not taken into account
after the text localization step. By doing so, in the IEHHR dataset we observe
a greater performance for the end-to-end models compared to the CNN. This is
an evidence that context is being used since in the CNN approach there is the
advantage that an explicit perfect segmentation is given. In the case of WR we
observe an even greater boost of performance when using the context, specially
the bi-dimensional one (setup A). We attribute this to the inherent layout
pattern contained in the dataset as it can be intuited observing Figure 4. We
also assume that predictions were based on the layout due to the large amount
of out of vocabulary words, which would make it difficult to predict the word
category based on a known vocabulary. sGMB is clearly the most difficult one
since it has the sparsest distribution of entities as it can be seen in Table
4. With this dataset we also see a very substantial increase when using the
context, concretely, the sequential one (setups B and C). This makes sense as
the type of text is natural language, which means that it has a sequential
structure but lacks the bi-dimensional layout structure of registration forms
or marriage records. Consequently, sequential patterns existing in natural
language are more suitable to recognize entities.

Table 5: Performance of the different method variations on each dataset. Method | IEHHR | WR | sGMB
---|---|---|---
Text localization (AP)
A: triple task | 0.97 | 0.976 | 0.994
B: triple task seq | 0.972 | 0.973 | 0.994
C: Det+ner seq | 0.969 | 0.975 | 0.997
D: det+htr | 0.974 | 0.981 | 0.996
Text recognition CER (%)
A: Triple task | 6.1 | 23.7 | 2.3
B: Triple task seq | 6.3 | 28.7 | 2.6
D: Det+HTR | 6.5 | 27.5 | 2.5
Named entity recognition (F1)
A: Triple task | 0.797 | 0.975 | 0.347
B: Triple task seq | 0.806 | 0.924 | 0.535
C: Det+NER seq | 0.796 | 0.963 | 0.510
CNN classifier | 0.700 | 0.821 | 0.382

##  6 Discussion and Conclusion

In this paper we have presented a unified neural model to extract information
from semi-structured documents. Our method shows the strengths of the pairwise
interaction of some of the tasks, such as localization and transcription and
also for localization and named entity recognition when the spatial
information or the neighbourhood (geometric context) of a text entity
influences the value to predict. Nevertheless observing the performance of
triple task neural model variations, it must be noted that a unified model can
be limited in performance in cases where one specific task is much harder and
unrelated to the others. In such a case, a separate approach would allow us to
use specific techniques for this difficult unrelated task. For example, named
entity recognition performance is limited by the fact that it is very
difficult to generate semantically meaningful word embedding vectors (e.g.
word2vec, glove) when the model input is a page image.

In summary, we conclude that a joint model is suitable for cases in which
there is a strong task interdependence, but not for unstructured documents
where the main difficulty is on one independent single task.

Fig. 7: Word localizations, transcriptions and semantic annotations on an
unseen page of the IEHHR dataset. The model learns to detect and classify
words based not only on its appearance but also on its context. The colors
illustrate the different type of named entities.

## Acknowledgments

This work has been partially supported by the Spanish project
RTI2018-095645-B-C21, the European Commission H2020 SME Instrument program,
under Grant Agreement no. 849628, project OMNIUS, the grant 2016-DI-095 from
the Secretaria d’Universitats i Recerca del Departament d’Economia i
Coneixement de la Generalitat de Catalunya, the Ramon y Cajal Fellowship
RYC-2014-16831 and the CERCA Programme / Generalitat de Catalunya.

## References

  * [1] J. Ignacio Toledo, Manuel Carbonell, Alicia Fornés, and Josep Lladós.  Information extraction from historical handwritten document images with a context-aware neural model.  Pattern Recognition, 86:27–36, 2019.
  * [2] Rasmus Berg Palm, Florian Laws, and Ole Winther.  Attend, copy, parse - end-to-end information extraction from documents.  International Conference on Document Analysis and Recognition (ICDAR), 2019.
  * [3] Manuel Carbonell, Mauricio Villegas, Alicia Fornés, and Josep Lladós.  Joint recognition of handwritten text and named entities with a neural end-to-end model.  In International Workshop on Document Analysis Systems, pages 399–404, 04 2018.
  * [4] Manuel Carbonell, Joan Mas, Mauricio Villegas, Alicia Fornés, and Josep Lladós.  End-to-end handwritten text detection and transcription in full pages.  International Conference on Document Analysis and Recognition Workshops, 2019.
  * [5] J. A. Sánchez, V. Romero, A. H. Toselli, and E. Vidal.  Icfhr2014 competition on handwritten text recognition on transcriptorium datasets (htrts).  In 2014 14th International Conference on Frontiers in Handwriting Recognition, pages 785–790, Sept 2014.
  * [6] J.R.R. Uijlings, K.E.A. van de Sande, T. Gevers, and A.W.M. Smeulders.  Selective search for object recognition.  International Journal of Computer Vision, 2013.
  * [7] Ross B. Girshick.  Fast R-CNN.  CoRR, abs/1504.08083, 2015.
  * [8] Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott E. Reed, Cheng-Yang Fu, and Alexander C. Berg.  SSD: single shot multibox detector.  CoRR, abs/1512.02325, 2015.
  * [9] Joseph Redmon, Santosh Kumar Divvala, Ross B. Girshick, and Ali Farhadi.  You only look once: Unified, real-time object detection.  CoRR, abs/1506.02640, 2015.
  * [10] Tsung-Yi Lin, Priya Goyal, Ross B. Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  CoRR, abs/1708.02002, 2017.
  * [11] Théodore Bluche, Jérôme Louradour, and Ronaldo O. Messina.  Scan, attend and read: End-to-end handwritten paragraph recognition with mdlstm attention.  2017 14th IAPR International Conference on Document Analysis and Recognition (ICDAR), 01:1050–1055, 2017.
  * [12] Joan Puigcerver.  Are multidimensional recurrent layers really necessary for handwritten text recognition?  In 2017 14th IAPR International Conference on Document Analysis and Recognition (ICDAR), volume 1, pages 67–72. IEEE, 2017.
  * [13] Curtis Wigington, Chris Tensmeyer, Brian Davis, William Barrett, Brian Price, and Scott Cohen.  Start, follow, read: End-to-end full-page handwriting recognition.  In The European Conference on Computer Vision (ECCV), September 2018\.
  * [14] Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer.  Neural architectures for named entity recognition.  In HLT-NAACL, 2016.
  * [15] Xuezhe Ma and Eduard Hovy.  End-to-end sequence labeling via bi-directional LSTM-CNNs-CRF.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1064–1074, Berlin, Germany, August 2016. Association for Computational Linguistics.
  * [16] Alan Akbik, Duncan Blythe, and Roland Vollgraf.  Contextual string embeddings for sequence labeling.  In Proceedings of the 27th International Conference on Computational Linguistics, pages 1638–1649, Santa Fe, New Mexico, USA, August 2018. Association for Computational Linguistics.
  * [17] J. Ignacio Toledo, Sebastian Sudholt, Alicia Fornés, Jordi Cucurull, Gernot A. Fink, and Josep Lladós.  Handwritten word image categorization with convolutional neural networks and spatial pyramid pooling.  In Antonio Robles-Kelly, Marco Loog, Battista Biggio, Francisco Escolano, and Richard Wilson, editors, Structural, Syntactic, and Statistical Pattern Recognition, pages 543–552, Cham, 2016. Springer International Publishing.
  * [18] Vijay Rowtula, Praveen Krishnan, and C.V. Jawahar.  Pos tagging and named entity recognition on handwritten documents.  15th International Conference on NaturalLanguage Processing, 2018\.
  * [19] Curtis Wigington, Brian Price, and Scott Cohen.  Multi-label connectionist temporal classification.  In 2019 15th IAPR International Conference on Document Analysis and Recognition (ICDAR). IEEE, 2019.
  * [20] Alex Graves, Santiago Fernández, Faustino Gomez, and Jürgen Schmidhuber.  Connectionist temporal classification: Labelling unsegmented sequence data with recurrent neural networks.  In Proceedings of the 23rd International Conference on Machine Learning, ICML ’06, pages 369–376, New York, NY, USA, 2006. ACM.
  * [21] He Ping Guo, Xiameng Qin, Jiaming Liu, Junyu Han, Jingtuo Liu, and Errui Ding.  Eaten: Entity-aware attention for single shot visual text extraction.  ArXiv, abs/1909.09380, 2019.
  * [22] Tsung-Yi Lin, Piotr Dollár, Ross B. Girshick, Kaiming He, Bharath Hariharan, and Serge J. Belongie.  Feature pyramid networks for object detection.  CoRR, abs/1612.03144, 2016.
  * [23] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  CoRR, abs/1512.03385, 2015.
  * [24] Urs-Viktor Marti and Horst Bunke.  The iam-database: an english sentence database for offline handwriting recognition.  International Journal on Document Analysis and Recognition, 5:39–46, 2002.
  * [25] Vincent Dumoulin and Francesco Visin.  A guide to convolution arithmetic for deep learning.  ArXiv, abs/1603.07285, 2016.
  * [26] Johan Bos, Valerio Basile, Kilian Evang, Noortje Venhuizen, and Johannes Bjerva.  The groningen meaning bank.  In Nancy Ide and James Pustejovsky, editors, Handbook of Linguistic Annotation, volume 2, pages 463–496. Springer, 2017.
  * [27] Sebastian Ruder.  An overview of multi-task learning in deep neural networks.  CoRR, abs/1706.05098, 2017.