We consider the problem of defining regular expressions to characterize the class of recognizable picture languages in the case of a one-letter alphabet.We define a diagonal concatenation and its star and consider two different families, L(D) and L(CRD), of languages denoted by regular expressions involving such operations plus classical operations. L(D) is characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. L(CRD) is included inRECand contains languages defined by three-way automata while languages in L(CRD) necessarily satisfy some regularity conditions. Finally, we introduce new definitions of advanced stars expressing the necessity of conceptually different definitions for iteration.

New operations and regular expressions for two-dimensional languages over one-letter alphabet

ANSELMO, Marcella;
2005

Abstract

We consider the problem of defining regular expressions to characterize the class of recognizable picture languages in the case of a one-letter alphabet.We define a diagonal concatenation and its star and consider two different families, L(D) and L(CRD), of languages denoted by regular expressions involving such operations plus classical operations. L(D) is characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. L(CRD) is included inRECand contains languages defined by three-way automata while languages in L(CRD) necessarily satisfy some regularity conditions. Finally, we introduce new definitions of advanced stars expressing the necessity of conceptually different definitions for iteration.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/1063563
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 13
social impact