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 LOC1, 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 LOC1 of local languages over an alphabet of n >= 2 symbols, we show that LOCn is not semimodular, and we exhibit sublattices isomorphic to m(5) and n(5). We characterize the meet-irreducible elements, the coatoms, and the join-irreducible elements of LOCn. We point out some undecidable problems which arise in studying the lattices LOCn, n >= 2. We study in some detail atoms and chains of LOC2. Finally we examine the lattice LOC2h of local string languages, i.e. the local languages over the binary alphabet consisting of objects of only one row. LOC2h is an ideal of LOC2. As a lattice, it is not semimodular but satisfies the Jordan-Dedekind Condition. (C) 2009 Published by Elsevier B.V.