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.
%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
}