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.
-