Akademie Greifswald
129
Arbeitsgruppe 2
Formal Language Theory, Complexity, and the Web
Leitung
Prof. Dr. WimMartens
Arbeitsgruppe Theoretische Informatik, Universität Bayreuth
Dr. Wojciech Czerwi
ń
ski
Institute of Informatics, Universität Warschau
Teilnehmer
Studierende der Informatik oder Mathematik
The World Wide Web has gone through a very impressive evolution in the last years. This
evolution has been due to more content, a constant improvement of search engines, but
also due to a revolution in how content is shared between different sites. The latter deve-
lopment is largely due to the efforts of the World Wide Web Consortium, which standar-
dizes how documents and information in the Web can be presented and processed. Many
of these standards are built on foundations from theoretical computer science, such as
regular languages, regular expressions, and finite automata. This means that many types
of ‘classical’ formal language theory questions of have again been topics of active research
with immediate practical relevance. Furthermore, the new applications of regular langua-
ges have generated many interesting new questions and new fundamental results.
We intend to discuss various questions regarding finite automata, formal languages, de-
cision problems, and their complexity. Therefore, the main theme in this working group
will be of a theoretical flavour. However, we will also discuss links between theory and
practice, with an emphasis on the Web.
