|
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
Topics
Program committee
Invited speakers
Program
Proceedings - Instructions for authors
Important dates
Contact
Registration information
Hotel information
Travel information
Map of Budapest
Interesting links
Topics
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,
|   | csuhaj@sztaki.hu
|
Chandra Kintala (Basking Ridge, USA), co-chair,
|   | cmk@avaya.com
|
Detlef Wotschke (Frankfurt am Main, Germany), co-chair,
|   | wotschke@psc.informatik.uni-frankfurt.de
|
Cristian Calude (Auckland, New Zealand),
|   | cristian@cs.auckland.ac.nz
|
Jürgen Dassow (Magdeburg, Germany),
|   | dassow@iws.cs.uni-magdeburg.de
|
Jonathan Goldstine (University Park, USA),
|   | goldstin@cse.psu.edu
|
Juris Hartmanis (Ithaca, USA),
|   | jh@cs.cornell.edu
|
Juraj Hromkovic (Aachen, Germany),
|   | jh@i1.informatik.rwth-aachen.de
|
Helmut Jürgensen
(London, Canada and Potsdam, Germany),
|   | helmut@csd.uwo.ca
|
Lila Kari (London, Canada),
|   | lila@csd.uwo.ca
|
Carlos Martín-Vide (Tarragona, Spain),
|   | cmv@astor.urv.es
|
Dale Miller (Palaiseau, France),
|   | dale.miller@inria.fr
|
Catuscia Palamidessi (University Park, USA),
|   | catuscia@cse.psu.edu
|
Gheorghe Paun (Bucharest, Romania / Tarragona, Spain),
|   | gp@correu.urv.es
|
Kai Salomaa (Kingston, Canada),
|   | ksalomaa@cs.queensu.ca
|
Jeffrey Shallit (Waterloo, Canada),
|   | shallit@graceland.uwaterloo.ca
|
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
Program
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.00 | Jozef Gruska (Brno, Czech Republic), invited talk:
Succinctness in quantum information processing
|
15.00 - 15.30 | Andreas 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.40 | Pá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.40 | Mario. 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.00 | Mark 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.40 | Ralf 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 dcfs03@sztaki.hu 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
Contact
For more information, you can write to the address:
dcfs03@sztaki.hu
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.
Hotels
|
Room rates(*)
per night
|
Access to
the venue
|
|
Single
|
Double
|
|
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;
e-mail: reserve@hotelgriff.hunguesthotels.hu
|
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, e-mail: imre.frittmann@bkae.hu
(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 http://www.travelport.hu/
or http://www.budapesthotelguide.com/
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.
|