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.