\documentclass[final]{beatcs} \begin{document} \beatcsReport{DCFS'2003} {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}. \medskip {DCFS'2003} was attended by 35 participants from 12 countries as given below \begin{center} \begin{tabular}{|lr|lr|lr|lr|lr|lr|lr|} \hline D & 11 & CDN & 3 & I & 3 & E & 2 & IND & 1 & RO & 1 \\ I & 5 & H & 3 & A & 2 & F & 2 & MD & 1 & SK & 1 \\ \hline \end{tabular} \end{center} 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): \begin{center} \begin{tabular}{||l|r|rc|rc||l|r|rc|rc||l|r|rc|rc||} \hline C & I & R & & S & & C & I & R & & S & & C & I & R & & S & \\ \hline 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] \hline \end{tabular} \end{center} {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. \smallskip 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}. \smallskip 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'}). {\sloppy 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. \smallskip 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. \medskip {\sloppy 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} \bigskip 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}. \medskip 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. \medskip 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. \end{document} |