%0 Journal Article %1 anselmo2005operations %A Anselmo, Marcella %A Giammarresi, Dora %A Madonia, Maria %D 2005 %J Theoretical Computer Science %K 3d expressions languages regular %N 2 %P 408 - 431 %R 10.1016/j.tcs.2005.03.031 %T New operations and regular expressions for two-dimensional languages over one-letter alphabet %U http://www.sciencedirect.com/science/article/pii/S030439750500160X %V 340 %X 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.

@article{anselmo2005operations, 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 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. }, added-at = {2013-07-08T19:40:18.000+0200}, author = {Anselmo, Marcella and Giammarresi, Dora and Madonia, Maria}, biburl = {https://www.bibsonomy.org/bibtex/2c5341778a58771e0f8b1f543b66a5648/ripe}, doi = {10.1016/j.tcs.2005.03.031}, interhash = {e4eda89bea07c2842ce4d3c113ed1cfd}, intrahash = {c5341778a58771e0f8b1f543b66a5648}, issn = {0304-3975}, journal = {Theoretical Computer Science }, keywords = {3d expressions languages regular}, note = {The Art of Theory <xocs:full-name>The Art of Theory</xocs:full-name> }, number = 2, pages = {408 - 431}, timestamp = {2013-07-08T19:40:18.000+0200}, title = {New operations and regular expressions for two-dimensional languages over one-letter alphabet }, url = {http://www.sciencedirect.com/science/article/pii/S030439750500160X}, volume = 340, year = 2005 }