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 in REC and 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. (c) 2005 Elsevier B.V. All rights reserved.
Anselmo, M., Giammarresi, D., & Madonia, M. (2005). New operations and regular expressions for two-dimensional languages over one-letter alphabet. THEORETICAL COMPUTER SCIENCE, 340(2), 408-431.
Tipologia: | Articolo su rivista |
Citazione: | Anselmo, M., Giammarresi, D., & Madonia, M. (2005). New operations and regular expressions for two-dimensional languages over one-letter alphabet. THEORETICAL COMPUTER SCIENCE, 340(2), 408-431. |
IF: | Con Impact Factor ISI |
Lingua: | English |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Revisione (peer review): | Sì, ma tipo non specificato |
Tipo: | Articolo |
Rilevanza: | Rilevanza internazionale |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.tcs.2005.03.031 |
Stato di pubblicazione: | Pubblicato |
Data di pubblicazione: | 2005 |
Titolo: | New operations and regular expressions for two-dimensional languages over one-letter alphabet |
Autori: | |
Autori: | Anselmo, M; Giammarresi, D; Madonia, M |
Appare nelle tipologie: | 01 - Articolo su rivista |