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 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 of local languages over an alphabet of n≥2 symbols, we show that is not semimodular, and we exhibit sublattices isomorphic to M5 and N5. We characterize the meet-irreducible elements, the coatoms, and the join-irreducible elements of . We point out some undecidable problems which arise in studying the lattices , n≥2. We study in some detail atoms and chains of . Finally we examine the lattice of local string languages, i.e. the local languages over the binary alphabet consisting of objects of only one row. is an ideal of . As a lattice, it is not semimodular but satisfies the Jordan–Dedekind condition.