A Kleene Theorem for Regular Picture Languages

to full text (292 kB)   ZIP
involved person(s) / institution(s)author :
datePublished :
  • February 2007
size25 S.

We consider the class of regular picture languages, which is the two-dimensional analog to the well-known class of regular (word) languages as defined by regular expressions. We present an automaton model that characterizes the class of regular picture languages, similar to the famous Kleene theorem that characterizes the class of regular picture languages by non-deterministic finite state automata. The two concatenations (called "row"- and "column"-concatenation) for picture languages are partial because they require matching height or width, respectively. However, we show that for the definition of regular picture languages, the partialness of the concatenations is irrelevant in the sense that every regular expression can be converted into a regular expression during whose evaluation no picture gets discarded because of that partialness. We conclude that for every regular picture languages, its "front" (i.e., the set of top rows of its pictures) is a regular word language.
Static URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000118
IDNumber of report :
  • TR_0703