Institute of Computer Languages
Compilers and Languages Group

Talks 2004 - Adriana Popovici

The Compilers and Languages Group invites you to a talk given by

Dr. Adriana Popovici

(Universitatea de Vest din Timisoara) on

Real-Time Cellular Automata Recognizers

Date:	Wednesday, February 18, 2004
Time:	14:15
Location:	TU Wien, Reithofer Hörsaal, Gußhausstraße 25-29, 2nd upper floor

Abstract:

Cellular automata (CA) appear to be a relevant model for massively parallel computation. Language recognition is a powerful tool to evaluate the computational power of devices. Therefore, a lot of interest has been devoted to one-dimensional cellular acceptors (1-D CA). For example, as concerning real-time CA: regular languages (R) are accepted by real-time one-way cellular automata (ROCA); linear context-free languages (LCF) are accepted by ROCA; there is no link between context-free languages (CF) and ROCA; ROCA languages are real-time CA languages (RCA) - the converse inclusion is false; RCA languages are linear CA languages (LCA); ROCA languages form a subclass of LOCA languages which are exactly the RCA languages.

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.

About Dr. Adriana Popovici:

Dr. Adriana Popovici is an assistant professor at the Universitatea de Vest din Timisoara. From December 2003 to Mai 2004 she is visiting the Compiler and Languages Group of the Institute of Computer Languages at the TU Vienna.