AFL 2008

The 12th International Conference on
Automata and Formal Languages
May 27-30, 2008, Balatonfüred, Hungary

Challenges in Computing and Complexity
May 27, 2008, Balatonfüred

Special Event related to AFL 2008

jointly organized by the

Computer and Automation Research Institute of the Hungarian Academy of Sciences, Theoretical Computer Science Research Group,

Eötvös Loránd University, eScience Regional Knowledge Centre,

Eötvös Loránd University, Faculty of Informatics, Department of Algorithms and Their Applications and Department of Information Systems.

Venue: Hotel Uni, H-8230 Balatonfüred, Széchenyi u. 10. Click here for a map


Contemporary computer science faces an enormous number of challenges, ranging from problems concerning the fundamentals of computation, to interpreting concepts and ideas that have penetrated into computer science from other scientific areas as biology, physics, social sciences, only to mention a few. Unconventional computing, bio-inspired computing, nano-scale computing, ubiquitous computing, quantum computing are examples for scientific fields emerged from this interaction. One of the main challenges occuring in all these areas is the understanding of complexity, interpreted in different disciplines in different manner, from computational complexity in computer science, to the theory of complex dynamical systems. Problems and challenges in computer science are approached by a wide range of tools of mathematics, among them automata and formal language theory, a traditional, classic area of theoretical computer science.

The aim of this session consisting of invited talks is to demonstrate some recent challenges and fundamental problems in new fields of computer science, in particular related to complexity, in order to inspire and possibly open new horizons for research in the boundaries of these areas and formal language and automata theory.

The event will be held on May 27, 2008, just before the regular program of AFL 2008.


  Gheorghe Paun  (Mathematical Institute, Romanian Academy, Bucharest, Romania):

Membrane Computing: Recent Developments and Applications

Abstract: Membrane computing is a branch of natural computing whose initial aim was to abstract computing models from the structure and the functioning of living cells and from the cell cooperation in tissues, colonies, nerve nets, or other cell populations. Many classes of computing devices (called P systems) were introduced in this framework and vividly investigated in the almost ten years since this area was initiated. The main investigated issues were the computing power and the possibility of solving computationally hard problems in a feasible time. Later, membrane computing became a framework for devising models, first for biological processes, then for approaching a variety of issues, for instance, in linguistics, economics, computer graphics, approximate optimization, etc. Several software products were realized and used in these applications. Recently, a lab implementation was started in Technion, Haifa-Israel. The talk will provide a glimpse to all this landscape, as a general, non-technical introduction to membrane computing, with emphasis on recent directions of research and applications. Comprehensive details can be found at the domain webpage, at


  Tamás Roska  (Computer and Automation Research Institute, Hungarian Academy of Sciences, and Pázmány Péter Catholic University, Budapest, Hungary):

Cellular Wave Computers - Algorithms for million processor computers

Abstract: Since a few years, hundreds or thousands of processors are placed on a sigle chip and the trend is continuing in this direction. The underlying physical constraints support a new way of thinking about computing and computers. The Cellular Wave Computer architecture emerged in this line of development. This architecture, the accompanying algorithmic definition, the alpha-recursive function, as well as some algorithmic principles will be presented. The biological relevance is shown via a retinal model and the theoretical impact toward a non-Boolean spatial-temporal logic will be outlined.


  Eörs Szathmáry  (Eötvös Loránd University, and Collegium Budapest, Institute for Advanced Study, Budapest, Hungary):

In silico Evolutionary Developmental Neurobiology and the Origin of Natural Language

Abstract: It is justified to assume that part of our genetic endowment contributes to our language skills, yet it is impossible to tell at this moment exactly how genes affect the language faculty. We complement experimental biological studies by an in silico approach in that we simulate the evolution of neuronal networks under selection for language-related skills. At the heart of this project is the Evolutionary Neurogenetic Algorithm (ENGA) that is deliberately biomimetic. The design of the system was inspired by important biological phenomena such as brain ontogenesis, neuron morphologies, and indirect genetic encoding. Neuronal networks were selected and were allowed to reproduce as a function of their performance in the given task. The selected neuronal networks in all scenarios were able to solve the communication problem they had to face. The most striking feature of the model is that it works with highly indirect genetic encoding-just as brains do.


Program chairs:

András Benczúr (eScience Regional Knowledge Centre, Eötvös Loránd University, and Department of Information Systems, Eötvös Loránd University, Budapest, Hungary)

Erzsébet Csuhaj-Varjú (Computer and Automation Research Institute, Hungarian Academy of Sciences and Department of Algorithms and Applications, Eötvös Loránd University, Budapest, Hungary)







Maintained by the author.