# Invited Speakers

- Javier Esparza (Technische Universität München,
Germany)

**A Generic Solver for Fixed Point Equations on Semirings** - Friedrich Otto (Universität Kassel, Germany)

**Restarting Automata for Picture Languages: A Survey on Recent Developments**

Since many years a lot of work has been done to define classes of picture languages that would correspond to the classes of the Chomsky hierarchy for string languages. Various models of automata have been carried over to the two-dimensional setting, and finally the class REC of recognizable picture languages has been agreed on as being the class that corresponds to the "regular string languages". Indeed, REC has several nice characterizations in terms of regular expressions, tiling automata, and on-line tesselation automata, and it has nice closure properties, but it also has two main drawbacks: all its characterizations are highly nondeterministic in nature, and it contains languages that are NP-complete, that is, the picture languages in REC are in general much more complex than the regular string languages. Correspondingly, there have been attempts to come up with a deterministic version of REC, and indeed, various different deterministic subclasses of REC have been defined. Mainly, however, these definitions are quite complex, and it is not clear which of the resulting classes should be considered as "the" class of deterministic recognizable picture languages.

Here we present some recent developments that were obtained from a research project that has the aim of finding a deterministic model of a two-dimensional automaton that has the following desirable properties:

- the automata should be conceptually simple, so that basic tasks can be easily implemented,
- the class of languages accepted should be as large as possible,
- the membership problem for each of these languages should be solvable in polynomial time,
- when restricted to one-row pictures (that is, strings), only the regular languages should be accepted,
- and the class of languages should have nice closure properties.

In the course of the project, several types of two-dimensional automata have been defined and investigated:

- he Sgraffito automaton and its deterministic restriction,
- the restarting tiling automaton,
- the ordered restarting automaton,
- the deterministic two-dimensional three-way ordered restarting automaton, and
- the deterministic two-dimensional extended two-way ordered restarting automaton.

Here these types of automata and the classes of picture languages accepted by them are compared to each other and to the classes mentioned above, and their closure properties and algorithmic properties are considered. The presentation ends by listing a couple of open problems for future research related to the expressive power of the various models and to their descriptional complexity. - Giovanni Pighizzini (Università degli studi di
Milano, Italy)

**Some Investigations on Automata and Languages Over a Unary Alphabet**

The investigation of automata and languages defined over a one letter alphabet shows interesting differences with respect to the case of alphabets with at least two letters. Probably, the oldest example emphasizing one of these differences is the collapse of the classes of regular and context-free languages in the unary case, proved by Ginsburg and Rice in 1962.

Many differences have been proved concerning the state costs of the simulations between different variants of finite state unary automata. Many other results related to the unary case are presented in the literature.

In this talk we will discuss some of them. We will emphasize the fact that the unary case is interesting not only by itself, but even for the connections with some general questions, as for instance the problem of power of the nondeterminism in logarithmic space bounded computations. - Georgios Sirakoulis (Democritus University of Thrace,
Greece)

**Cellular Automata for Crowd Dynamics**

Cellular Automata (CAs) as bio-inspired parallel computational models

suitable for simulating physical systems and solving scientific problems

have been introduced several decades ago. CAs as formal models of

self-reproducing organisms can capture the essential features of systems

where global behaviour arises from the collective effect of simple

components which interact locally. Nontrivial CAs are obtained whenever

the dependence on the values at each site is nonlinear. As a result, any

physical system satisfying differential equations may be approximated by

a CA, by introducing finite differences and discrete variables. In this

aspect, CAs have been considered as a fine candidate to solve

efficiently several scientific problems and, among others, to model

pedestrian behavior and crowd dynamics in a fine manner. In specific,

for crowd modeling, the CA models show evidence of a macroscopic nature

with microscopic extensions, i.e. they provide adequate details in the

description of human behavior and interaction, whilst they retain the

computational cost at low levels. Nevertheless, evacuation process is

inherently complex, i.e. a system multi-parameterized and its response

cannot be easily estimated since exist interactions among pedestrians,

buildings and environment and there are also socio-psychological

parameter. Consequently, evacuation could be defined as a non-linear

problem with many factors affecting it and can be approached by systems

of partial differential equations. In this presentation several CA

models for crowd evacuation taking into consideration different modeling

principles, like floor fields methods, potential fields techniques,

follow-the-leader principles, grouping behavior, etc. will be presented

in an attempt to accomplish efficient crowd evacuation simulation.

Moreover, an integrated system based on CAs that operates as an

anticipative crowd management tool in cases of medium density crowd

evacuation for indoor and outdoor environments will be also presented.

Several real world cases and different environments will be examined and

the presented results will prove the efficiency of the proposed CA based

anticipative system under different circumstances. Furthermore, having

in mind that, in the field of robotics research, CAs have been proven

efficient to accomplish different complex tasks, we will present robot

guided evacuation with the help of CAs. This evacuation system based on

an accurate CA model capable of assessing the human behavior during

emergency situations takes advantage of the simulation output to provide

sufficient information to a mobile robotic guide, which in turn guides

people towards a less congestive exit at a time. Last, the performance

of the proposed robot guided evacuation will be examined in real world

scenarios exhibiting significant performance improvement during the

crucial first response time window. -