Descriptional Complexity of Formal Systems
DCFS 2003

5th Workshop, July 12-14, 2003, Budapest, Hungary

Computer and Automation Research Institute (SZTAKI) of
the Hungarian Academy of Sciences (MTA)

Address: H-1111 Budapest, Kende utca 13-17.

The Workshop

    DCFS is the successor workshop to and the merger of

      DCAGRS - Descriptional Complexity of Automata, Grammars and Related Structures, and

      FDSR - Formal Descriptions and Software Reliability.

    DCAGRS was previously held in Magdeburg (1999), London, Ontario (2000), and Vienna (2001). FDSR was previously held in Paderborn (1998), Boca Raton (1999), and San Jose (2000).

    DCFS was first held in London, Ontario (2002).

    DCFS 2003 will be jointly organized by the IFIP Working Group 1.2 on Descriptional Complexity and the Computer and Automation Research Institute of the Hungarian Academy of Sciences.

    It will take place in Budapest, immediately after

      DLT 03 - 7th International Conference "Developments in Language Theory"
      Szeged, Hungary, July 7-11, 2003.

Contents of this page


    Program committee

    Invited speakers


    Proceedings - Instructions for authors

    Important dates


    Registration information

    Hotel information

    Travel information

    Map of Budapest

    Interesting links


    Submissions for DCFS 2003 are invited, concerning the descriptional complexity of formal systems and structures (and its applications). Topics include, but are not limited to:

    • various measures of descriptional complexity of automata, grammars, languages and of related systems

    • trade-offs between descriptional complexity and mode of operation

    • circuit complexity of Boolean functions and related measures

    • succinctness of description of (finite) objects

    • descriptional complexity in resource-bounded or structure-bounded environments

    • structural complexity

    • descriptional complexity of formal systems for applications (e.g. software reliability, software and hardware testing, modelling of natural languages)

    • descriptional complexity aspects of nature-motivated (bio- inspired) architectures and unconventional models of computing

Program Committee

    Erzsébet Csuhaj-Varjú (Budapest, Hungary), co-chair,
    Chandra Kintala (Basking Ridge, USA), co-chair,
    Detlef Wotschke (Frankfurt am Main, Germany), co-chair,
    Cristian Calude (Auckland, New Zealand),
    Jürgen Dassow (Magdeburg, Germany),
    Jonathan Goldstine (University Park, USA),
    Juris Hartmanis (Ithaca, USA),
    Juraj Hromkovic (Aachen, Germany),
    Helmut Jürgensen (London, Canada and Potsdam, Germany),
    Lila Kari (London, Canada),
    Carlos Martín-Vide (Tarragona, Spain),
    Dale Miller (Palaiseau, France),
    Catuscia Palamidessi (University Park, USA),
    Gheorghe Paun (Bucharest, Romania / Tarragona, Spain),
    Kai Salomaa (Kingston, Canada),
    Jeffrey Shallit (Waterloo, Canada),

Invited speakers

    Jozef Gruska (Brno, Czech Republic)
    Title of the talk: Succinctness in quantum information processing

    Markus Holzer (Münich, Germany)
    Title of the talk: Aspects on the descriptional complexity of finite automata

    Alica Kelemenová (Opava, Czech Republic)
    Title of the talk: Descriptional complexity of eco-grammar systems

    Victor Mitrana (Bucharest, Romania / Tarragona, Spain)
    Title of the talk: Some complexity aspects of hybrid networks of evolutionary processors

    Gheorghe Paun (Bucharest, Romania / Tarragona, Spain)
    Title of the talk: Descriptional complexity issues in membrane computing


    The workshop is held at the Computer and Automation Research Institute of the Hungarian Academy of Sciences (MTA SZTAKI), at the address 1111 Budapest, Kende utca 13-17.

    The lectures take place in the so called "nagytanácsterem", the lecture room in the basement of the building.

    For more information on the location of the conference sight, see the maps below.

    Saturday, July 12

    10.00 - 11.00 Registration and welcome coffee
    11.00 - 11.05 Opening
    11.05 - 12.00 Victor Mitrana (Bucharest, Romania / Tarragona, Spain), invited talk: Some complexity aspects of hybrid networks of evolutionary processors
    12.00 - 14.00 Lunch
    14.00 - 15.00Jozef Gruska (Brno, Czech Republic), invited talk: Succinctness in quantum information processing
    15.00 - 15.30Andreas Malcher (Frankfurt am Main, Germany): On two-way communication in cellular automata with a fixed number of cells
    15.30 - 16.00 Break
    16.00 - 16.30 Martin Kutrib (Giessen, Germany): On the descriptional power of heads, counters, and pebbles
    16.30 - 17.00 Filippo Mera, Giovanni Pighizzini (Milan, Italy): Complementing unary nondeterministic automata
    17.00 - 17.30 Galina Jirásková (Kosice, Slovakia): State complexity of some operations on regular languages
    17.30 Business meeting of the IFIP Working Group 1.2 Descriptional Complexity

    Sunday, July 13

    9.00 - 10.00 Markus Holzer (Munich, Germany), invited talk: Aspects on the descriptional complexity of finite automata
    10.00 - 10.30 Martin Kappes (Basking Ridge, New Jersey, USA), Frank Niessner (Frankfurt am Main, Germany): Succinct representation of languages by DFA with different levels of reliability
    10.30 - 10.50 Break
    10.50 - 11.20 J-M. Champarnaud, T. Paranthoen (Rouen, France): Random DFAs over a non-unary alphabet
    11.20 - 11.40 Martin Plátek (Prague, Czech Republic), Friedrich Otto (Kassel, Germany), Frantisek Mráz (Prague, Czech Republic): Restarting automata and variants of j-monotonicity
    11.40 - 12.00 Holger Petersen (Stuttgart, Germany): Complexity results for prefix grammars
    12.00 - 12.20 Break
    12.20 - 12.40Pál Dömösi (Debrecen, Hungary), Sándor Horváth (Budapest, Hungary), Masami Ito, Masahi Katsura (Kyoto, Japan): Some remarks on primitive words and palindromes
    12.40 - 13.00 Radu Gramatovici (Bucharest, Romania), Martin Plátek (Prague, Czech Republic): Proper dependency grammars
    13.00 - 13.20 Alexander Okhotin (Kingston, Ontario, Canada): On the number of nonterminals in linear conjunctive grammars
    15.30 - 19.00 Sightseeing tour. The bus departs from Kende utca, from the building of the institute.
    19.00 - 22.00 Boat trip with the conference dinner. The name of the boat is ``Halászbástya'', it leaves from port no. 3 at Jászai Mari tér square, where the sightseeing tour ends.

    Monday, July 14

    9.00 - 10.00 Gheorghe Paun (Bucharest, Romania / Tarragona, Spain) invited talk: Descriptional complexity issues in membrane computing
    10.00 - 10.30 Rudolf Freund, Marion Oswald (Vienna, Austria), Petr Sosík (Opava, Czech Republic / London, Ontario, Canada): Reducing the number of catalysts needed in computationally universal P systems without priorities
    10.30 - 11.00 Break
    11.00 - 11.30 Sergey Verlan (Metz, France): A frontier result on enhanced time-varying distributed H systems with parallel computation
    11.30 - 12.00 K. Lakshmanan, R. Rama (Chennay /Madras/, India): Descriptional complexity of rewriting tissue P systems
    12.00 - 14.00 Lunch
    14.00 - 14.20 Maurice Margenstern (Metz, France), Gheorghe Paun (Bucharest, Romania / Tarragona, Spain), Yurii Rogozhin (Chisinau, Moldova), Sergey Verlan (Metz, France): Context-free insertion-deletion systems
    14.20 - 14.40Mario. J. Pérez Jiménez, Álvaro Romero Jiménez, Fernando Sancho Caparrini (Sevilla, Spain): A polynomial complexity class in P systems using membrane division
    14.40 - 15.00Mark Daley (Saskatoon, Saskatchewan, Canada), Ian McQuillian (London, Ontario, Canada): Template-guided DNA Recombination
    15.00 - 15.20 Break
    15.20 - 16.10 Alica Kelemenová (Opava, Czech Republic), invited tutorial: Descriptional complexity of eco-grammar systems
    16.10 - 16.30 Henning Bordihn (Potsdam, Germany): On the number of components in cooperating distributed grammar systems
    16.30 - 16.50 Bettina Sunckel (Frankfurt am Main, Germany): On the descriptional complexity of external hybrid cooperating distributed grammar systems
    16.50 - 17.10 Break
    17.10 - 17.40Ralf Stiebe (Magdeburg, Germany): Positive valence grammars
    17.40 - 18.00 György Vaszil (Budapest, Hungary): On the number of conditional productions in simple semi-conditional grammars
    18.00 Closing

Proceedings - Instructions for authors

    Proceedings containing all accepted papers will be available at the workshop.

    Authors should send the final version of their contribution as a plain LaTeX source file to the e-mail address not later than June 15, 2003.

    For more information on the preparation of manuscripts follow the link below.

    >>> Instructions for authors <<<

    Selected papers of the workshop, after the standard refereeing process of the journal, will be published in a special issue of Theoretical Computer Science.

Important Dates

    The DCFS 2003 deadlines are as follows:

      Deadline for submission:  April 9, 2003
      Notification of acceptance or rejection:  May 9, 2003
      Final copy for the proceedings and early registration:  June 15, 2003
      Workshop:  July 12-14, 2003

Organizing Committee

    Erzsébet Csuhaj-Varjú,
    György Vaszil,
    Mariann Kindl,


    For more information, you can write to the address:

    For the IFIP Working Group on Descriptional Complexity, contact Helmut Jürgensen, Vice Chairman, Chandra Kintala, Vice Chairman, Detlef Wotschke, Chairman.

    For the Computer and Automation Research Institute of the Hungarian Academy of Sciences, contact Erzsébet Csuhaj-Varjú.

Registration information

    The registration fee is EUR 150 for participants registering before June 15, 2003, or EUR 200 if registering after that date.

    This fee includes a copy of the proceedings, refreshments during coffee breaks, a Budapest sight-seeing tour, and the workshop dinner.

    For additional information and online registration visit our online registration page by following the link below.

    >>> Online Registration <<<

Hotel information

    Hotel reservation should be made directly to the hotel. Please give "DCFS 2003" as a reference to receive the reduced price agreed with the hotels below.


    Room rates(*) per night

    Access to the venue




    Congress Park Hotel Flamenco ****
    1113 Budapest, Tas vezér u.7.
    Fax: +36-1-365 8007; Tel: +36-1-372 2000

    EUR 78

    EUR 78

    10 min. walk

    Best Western Hotel Orion ***
    1013 Budapest, Döbrentei u. 13.
    Fax: +36-1-375 5418; Tel: +36-1-356 8583

    EUR 74 EUR 94

    15 min. by bus or tram

    Professors' Guest House
    1111 Budapest, Stoczek u. 5-7/Floor 7
    Fax: +36-1-463 3936; Tel: +36-1-463 4103
    (limited number of rooms)

    EUR 56

    EUR 60

    5 min. walk    

    Hotel Griff***
    H-1113 Budapest, Bartók B. u. 152.
    Fax: +36-1-204 0062 Tel: +36-1-204 0046;

    EUR 50
    EUR 60
    20 min. by tram
    Summer Hotel Hill (student hostel)(**)
    1118 Budapest, Menesi ut 5.
    Fax: 36-1-386 9429; Tel: 36-1-386 9908,
    (very limited number of rooms)
    EUR 23
    EUR 26

    5 min. walk

    (*) Room rates include breakfast and all taxes.

    (**) Summer Hotel Hill  - student hostel. Breakfast is not included!

    Parking information:

      Hotel Griff 1. There are free places for hotel guests in front of the building, unless the hotel is very crowded, it is usually possible to park there easily. 2. There is a guarded and closed parking area for hotel guests which costs HUF 1600/night (EUR 6,5).
      Professors Guest House There is a guarded parking place where they can reserve places for guests, it costs HUF 1200/night (EUR 5), and they ask to tell them in advance (when making the reservation) that you will need the parking place, because they also make the reservation in this parking area in advance.
      Hotel Orion There is no separate parking place, but the street of the hotel is a free parking area. (Not the surrounding side streets, only the one that the hotel is located on.) According to the people at the reception, it is usually possible to park on that street easily.
      Hotel Flamenco They have two separate parking places for guests. One is open air, it costs HUF 1500/night (EUR 6), the other is inside a buliding, it costs HUF 3000/night (EUR 12).

    In case you wish to stay in an other hotel, feel free to visit the web pages or

Travel information

    The lectures are held at the Computer and Automation Research Institute of the Hungarian Academy of Sciences (MTA SZTAKI), at the address 1111 Budapest, Kende utca 13-17. For more information on the location of the conference sight, see the maps below.

    After arriving at Ferihegy airport, Budapest, you can use the minibus service to reach the center of the city. The Airport minibus service will take you anywhere in Budapest. Information desk (operator) for the minibus service is found in the centre of the arrival lobby. You can order this service inside the baggage claim area from 5 am in the morning until 1 am in the night. The price is HUF 2100 (EUR 8.5) in one direction, return tickets are also available for HUF 3600 (EUR 14.5).

    Airport taxis are in front of the arrival lobby. Fare depends on the destination, and often changes, but usually considerably more expensive then the minibus service. Most companies have a so called "airport transfer" service, with fixed prices to the left or to the right side of the Duna river (Buda - this should be more expensive and this is what you need to the hotels, or Pest). If you decide to take a taxi you should choose one which offers this service. For example, the company "6x6 Taxi" charges a fixed rate of HUF 3800 (EUR 15) for Buda. For this company you should call the number 266-6666, or 466-6666 from Budapest (the airport is in Budapest) or +36-1-266-6666, +36-1-466-6666 from abroad.

    When travelling from Szeged to Budapest, the trains arrive at the Nyugati Pályaudvar railway station which is on the Pest side of the river. The tram 6 to "MÓRICZ ZSIGMOND KÖRTÉR"  square might be used to reach the neighbourhood of the conference site and the hotels. When taking a taxi, it is a general rule that the fares are lower if the car was ordered by telephone. The numbers of the company "6x6 Taxi" are given above.

Map of Budapest

    The map of Budapest is available in two versions. An overview with the most important streets of the city, and a more deatiled street map marked at the locations of our institute, and the hotels.

    To reach the institute from Hotel Flamenco, you can take the bus 7 from "KOSZTOLÁNYI DEZSŐ TÉR" square in direction "BOSNYÁK TÉR VÁ.". You should get off at the first stop called "MÓRICZ ZSIGMOND KÖRTÉR".

    To reach the institute from Hotel Orion, you can take the tram 19 in direction "ETELE TÉR, KELENFÖLDI PÁLYAUDVAR VÁ." or the tram 18 in direction "ALBERTFALVA, KITÉRÖ VÁ." The station close to Hotel Orion is "Döbrentei tér", get off at the second stop called "Bertalan Lajos utca".

    To reach the institute from Hotel Griff, you can take the tram 19 in direction "BATTHYÁNY TÉR VÁ." or the tram 49 in direction "DEÁK FERENC TÉR VÁ." You should get off at the station "MÓRICZ ZSIGMOND KÖRTÉR" or "BERTALAN LAJOS UTCA".

    Tickets for trams and buses should be purchased in advance for HUF 125 (EUR 0.5).

Interesting links

    A Guide to Budapest on the web-pages of our institute containing information on arriving at the airport, using the airport shuttle service, taxis, telephones, etc.

    A live web-cam image of Budapest from the top of the Gellért hegy.

    An other page about Budapest with information and facts about the city and Hungary.

    About the weather in Hungary.

    A photo album with pictures organized in several categories on the page of the Budapest Tourism Office.

    The page of the Hungarian National Tourist Office.

Updated on July 3, 2003. With questions or comments about this page, write to György Vaszil.