{5th Workshop on Descriptional Complexity of Formal Systems\\
   Budapest, Hungary, July 12 -- 14, 2003}
  {Manfred Kudlek} 

{\bf DCFS'2003}, the ${5}^{th}$ workshop in this series, was held at
{Budapest} from July 12 to 14, 2003.
It took place at {\it MTA SZTAKI}
({\it Magyar Tudom\'{a}nyos Akad\'{e}mia - Sz\'{a}mit\'{a}stechnikai
 \'{e}s Kutat\'{o}intezet}, {Computer and Automation Research
 Institute of the Hugarian Academy of Sciences}),
 and was organized by {\bf Erzs\'{e}bet Csuhaj-Varj\'{u}}, 
 {\bf Mariann Kindl}, and {\bf Gy\"{o}rgy Vaszil}.


{DCFS'2003} was attended by 35 participants from 12 countries as given
D & 11 & CDN & 3 & I & 3 & E & 2 & IND & 1 & RO & 1 \\
I & 5 & H & 3 & A & 2 & F & 2 & MD & 1 & SK & 1 \\

 The scientific program consisted of 5 invited lectures and 21
 contributions (13 regular and 8 short) from 14 countries, as given in
 the following table ($C,I,R,S$ for country, invited talk, and
 regular, short paper, respectively): 
C & I & R & & S & & C & I & R & & S & & C & I & R & & S & \\
A & & & $\frac{2}{3}$ & & & F & & 2 & & & $\frac{1}{2}$ &
 MD & & & & & $\frac{1}{4}$ \\[1pt]
CDN & & & $\frac{1}{6}$ & 2 & & H & & 1 & & & $\frac{1}{2}$ &
 RO & 1 & & & & $\frac{5}{8}$ \\[1pt]
CZ & 2 & & $\frac{1}{6}$ & 1 & $\frac{1}{6}$ & I & & 1 & & & &
 SK & & 1 & & & \\[1pt]
D & 1 & 5 & $\frac{1}{2}$ & 1 & $\frac{1}{3}$ & IND & & 1 & & & &
 USA & & & $\frac{1}{2}$ & & \\[1pt]
E & 1 & & & 1 & $\frac{1}{8}$ & J & & & & & $\frac{1}{2}$ &
 & & & & & \\[1pt]

{DCFS'2003} was opened on Saturday morning by 
 {\bf Erzs\'{e}bet Csuhaj-Varj\'{u}}, speaking on the workshop, and
 thanking all speakers and the program committee. On Monday she also
 asked us not to enter {SZTAKI} dressed with shorts, according to the
 rules of the institute.


 All talks were presented by one of the authors. The program of
 {DCFS'2003} can be found at \url{http://www.sztaki.hu/mms/dcfs03}.


An excellent first invited lecture {\it `Some Complexity Aspects
of Hybrid Networks of Evolutionary Processors'} was presented by
{\bf Victor Mitrana}. It was a uniform and systematic survey
 on the complexity of generating, accepting, and problem solving devices,
as well as size of languages, also stating a number of open problems.

Another excellent and very interesting presentation was the second
invited talk {\it `Succinctness in Quantum Information Processing'} by
{\bf Jozef Gruska}, on the development of new information
technology, usable techniques, paradigms, concepts, the laws and goals of
physics and informatics, quantum computing, and Kolmogorov complexity.

{\bf Markus Holzer}, in his traditional conference shirt, presented
another excellent one with the third invited talk {\it `Aspects on
the Descriptional Complexity of Finite Automata'}. It was his first
beamer talk, having scanned all his nice slides known
from former conferences, on finite automata, descriptional complexity, and
applications ({\it `A very ambitious title'}).

 The fourth invited lecture {\it `Descriptional Complexity Issues in
Membrane Computing'} by {\bf Gheorghe P\u{a}un} was also an excellent
and very interesting one on universality, polynomial solutions of hard
problems, normal forms, decidability, implementation, application, and
descripyion by multisets.  The brainstorm in February and {\bf
  WMC'2003} in {Tarragona} was mentioned, too 
({\it `Nature has arranged something at all levels'}). 
 It was finished with 
{\it `Small is beautiful but big is necessary'}.\par}

The fifth invited talk {\it `Descriptional Complexity of Eco-grammar
systems'} by {\bf Alica Kelemenov\'{a}} was a good tutorial and survey
on the history, development and power of eco-grammar systems.


Only some personal impressions can be given on the contributions.

{\bf Andreas Malcher} gave good talk with nice results on 2-way
communications in cellular automata, {\bf Martin Kutrib} another
good and interesting one the hierarchy of FA's, non-recursive trade-offs,
and open problems for 2-way FA's. {\bf Filippo Mora} gave a good presentation
on the number of states of NFA's to accept the complement of a language.
An interesting talk on reliability was given by {\bf Frank Niessner} ({\it
`It may pay off to make errors'}).

{\bf Franti\v{s}ek Mr\'{a}z} gave a nice presentation on 2-way
restarting automata, motivated by linguistics, and
{\bf Holger Petersen}, who also asked the previous speaker, a very good one on
complexity results for prefix grammars.
{\bf S\'{a}ndor Horv\'{a}th} had a good presentation (dedicated to
the birthday of the author of this report, but with some delay of more than
two years) on primitive words and palindromes.
 {\bf Alexander Okhotin}, using
two projectors, had a good, interesting, and fast presentation on
linear conjunctive grammars, and different equivalent devices.

{\bf Marion Oswald} presented a nice talk on register machines,
 {\bf Sergey Verlan} a good and interesting one on splicing
 ({\it `because you are still tired from axiom I'll be short'}),
and {\bf Yuri Rogozhin} an interesting one on insertion and deletion.

Good and interesting talks were also presented by {\bf Ian McQuillan}
on ciliates, by {\bf Henning Bordihn} on the number of components in
distributed grammar systems, by {\bf Ralf Stiebe} on positive valence grammars, and by
{\bf Gy\"{o}rgy Vaszil} on permitting and forbidding conditions in
simple semi-conditional grammars.


 The proceedings, edited by {\bf Erzs\'{e}bet Csuhaj-Varj\'{u}},
 {\bf Chandra Kintala}, {\bf Gy\"{o}rgy Vaszil,} and 
 {\bf Detlef Wotschke}, containing all invited talks and
 contributions, have been published as a report of {SZTAKI}.\par}


In the breaks coffee, tea, mineral water, and cakes were available.
On Saturday we had lunch in {Kisborosty\'{a}n},
 on Monday it was served in the restaurant of
{SZTAKI}, both about 50 m from the institute.
Most participants stayed in {Professor's Guest House}, some also in
{Summer Hotel Hill} and in {Congress Park Hotel Flamenco},
all within 10 minutes walk distance from {SZTAKI}.


The social program on Sunday started at 15.30 with a sightseeing tour
through {Budapest}. The guide, {Attila}, explained us many
facts about the town. We passed by {\it N\'{e}pstadion},
the diplomats' quarter, stopped at {\it H\H{o}s\"{o}k T\'{e}re},
continued to pass the cathedral and  parlament, before we reached
{\it Buda v\'{a}r} where we walked to {\it Hal\'{a}sz b\'{a}stya}.
It offered a nice view over {\it Pest}, but
we nearly lost {\bf Giuditta Franco} and her brother.
 The next stop was at the {\it Citadella}
on {\it Gell\'{e}rt hegy}, with another
beautiful view over {Budapest}. The tour ended at {Rakpart 3}
on the Danube quay. There we had to wait a little bit
until 19 h before we could enter the boat {Attila}.

The boat trip on Danube went northwards until 
{\it\'{U}pesti vas\'{u}ti h\'{\i}d}
(a railway bridge) and then southwards until another bridge
{\it L\'{a}gymanyosi h\'{\i}d}. When entering the boat we got 
{\it p\'{a}linka}, champagne, and mineral water. The workshop dinner
consisted of a buffet with bread, cheese, sausages, salads, cakes,
`{r\'{e}tesek}' (strudel), as well as soup, fish, rice, meat, and
potatoes. White {D\'{e}l Balatoni Cuv\'{e}c 2001}, and red
{Egri K\'{e}kfrankos 2001}, both dry wines, were also served.
{Erzs\'{e}bet Csuhaj-Varj\'{u}} wished us {\it `Enjoy the trip!'}
During the boat trip we could enjoy nice views on both sides of the Danube.
It was by 22 h when we returned to the starting place.


Weather was fine, sunny and with highest temperatures between
$25$ and $30{}^{\circ}$ C.
{DCFS'2003} was a successful workshop, well organized and in
a nice atmosphere.

e-max.it: your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.