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

摘要

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.