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 of local languages Locn over an alphabet of n greater than 1 symbol, 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 Locn. We point out some undecidable problems which arise in studying the lattices Locn. We study in some detail atoms and chains of Loc2. Finally we examine the lattice of local string languages Loc2h, 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

Lattices of local two-dimensional languages / F. De Carli; A. Frosini; S. Rinaldi; A. Sorbi. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 410:(2009), pp. 2701-2713. [10.1016/j.tcs.2009.03.025]

Lattices of local two-dimensional languages

FROSINI, ANDREA
;
2009

Abstract

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 of local languages Locn over an alphabet of n greater than 1 symbol, 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 Locn. We point out some undecidable problems which arise in studying the lattices Locn. We study in some detail atoms and chains of Loc2. Finally we examine the lattice of local string languages Loc2h, 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
2009
410
2701
2713
F. De Carli; A. Frosini; S. Rinaldi; A. Sorbi
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/397037
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact