Institute of Computer Languages
Compilers and Languages Group
|Date:||Wednesday, February 18, 2004|
|Location:||TU Wien, Reithofer Hörsaal, Gußhausstraße 25-29, 2nd upper floor|
Languages on 2-D CA can be understood either as sets of 2-D patterns (also often called images) or as standard languages of finite words. Actually, although some work has been done on images, we will here restrict the matter to the latter ones.
In the frame of 2-D CA, input and output problems naturally become a little more involved, but, moreover, a new one may arise because the standard neighborhood of dimension one splits into von Neumann's and Moore's neighborhoods. In this framework real-time means, as usual, the minimal time necessary to the accepting cell to know the whole input.
In two dimensions, CA with von Neumann neighborhood are strictly more powerful than analogous OCA. It is not known whether 2-D OCA are more powerful than 1-D OCA, nor whether there exists some relation between 2-D OCA and 1-D CA. Also, the famous problem RCA=CA can be transposed in this generality.
The power capabilities of real-time recognition are discussed with a comparison between the two cases above.