Lattices of local two-dimensional languages

The aim of this paper is to study local two-dimensional languages from an algebraic point of view. We show that local two-dimensional languages over a finite alphabet, with the usual relation of set inclusion, form a lattice. The simplest case $\Loc_1$ of local languages defined over the alphabet consisting of one element yields a distributive lattice, which can be easily described. In the general case of the lattice $\Loc_n$ of local languages over an alphabet of $n\ge 2$ symbols, we show that $\Loc_n$ is not semimodular, and we exhibit sublattices isomorphic to $\mathfrak{M}_5$ and $\mathfrak{N}_5$. We characterize the meet-irreducible elements, the coatoms, and the join-irreducible elements of $\Loc_n$. We point out some undecidable problems which arise in studying the lattices $\Loc_n$, $n\ge 2$. We study in some detail atoms and chains of $\Loc_2$. Finally we examine the lattice $\Loc^h_2$ of local string languages, i.e. the local languages over the binary alphabet consisting of objects of only one row. $\Loc^h_2$ is an ideal of $\Loc_2$. As a lattice, it is not semimodular but satisfies the Jordan-Dedekind condition.