Representation of Scenarios in Finite Two-Dimensional Automata

Gheorghe Stefanescu
Professor and Director of the Computer Science Department
University of Bucharest
SERC 306
Tuesday, August 11, 2015 - 11:00
The talk has two parts. In the first part, we will seek an answer to the question: What type of 2-dimensional patters may be obtained by tiling transitions of finite two-dimensional automata assuming a specific state on each west-north-east-south border? To address the problem, we introduce a formalism using systems of recursive equations built on top of new classes of two-dimensional regular expressions. Then, we propose a research programme for getting structural characterizations for 2-dimensional languages generated by finite two-dimensional automata. We show that, enriched with spatial and temporal data attached to tiles, the formalism leads to a natural model for interactive, distributed programs. Finally, we comment on a few classes of applications: (1) lifting problems, results, and implementation packages from strings to images; (2) specification and verification of interactive, parallel, distributed programs; and (3) considering new data-types for programming languages (generalized arrays) in order to handle 2-dimensional words and their extension to other dimensions.

In the second part, I will introduce the Computer Science Department at the University of Bucharest.