| Wednesday, August 21, 2002 | |
|---|---|
| 16:00-20:00 | Reception / Wine and Cheese |
| Thursday, August 22, 2002 | |
|---|---|
| 09:00-10:00 | Invited Lecture:
J. Hartmanis (Ithaca, New York, USA):
The Separation Problems and Descriptional Complexity |
| 10:00-10:30 | Coffee Break |
| 10:30-11:00 |
C. Grozea (Bucharest, Romania):
NP Predicates Computable in the Weakest Level of the Grzegorczyck Hierarchy |
| 11:00-11:30 |
J.-M. Champarnaud, G. Hansel, T. Paranthoën, D. Ziadi
(Rouen, France):
NFAs Bitstream-Based Random Generation |
| 11:30-12:00 |
M.-J. Nederhof (Groningen, The Netherlands), G. Satta
(Padova, Italy):
Probabilistic Parsing Strategies |
| 12:00-12:30 |
L. Kari (London, Ontario, Canada), S. Konstantinidis (Halifax, Nova Scotia, Canada):
Descriptional Complexity of Error/Edit Systems |
| 12:30-14:00 | Lunch |
| 14:00-15:00 | Invited Lecture:
K. Ellul, J. Shallit, M.-W. Wang (Waterloo, Ontario, Canada):
Regular Expressions: New Results and Open Problems |
| 15:00-15:15 | Coffee Break |
| 15:15-15:45 |
A. Martinez (Waterloo, Ontario, Canada):
Efficient Computation of Regular Expressions from Unary NFAs |
| 15:45-16:15 |
A. Okhotin (Kingston, Ontario, Canada):
State Complexity of Linear Conjunctive Languages |
| 16:15-16:45 |
M. Domaratzki, K. Salomaa (Kingston, Ontario, Canada):
State Complexity of Shuffle on Trajectories |
| 16:45-17:15 |
H. Bordihn (Potsdam, Germany), M. Holzer (Munich, Germany),
M. Kutrib (Giessen, Germany):
Economy of Description for Basic Constructions on Rational Transductions |
| 17:30-18:30 | Business Meeting of IFIP Working Group 1.2 Descriptional Complexity |
| Friday, August 23, 2002 | |
|---|---|
| 09:00-10:00 | Invited Lecture:
M. Kappes (Basking Ridge, New Jersey, USA):
On Possible Extensions and Relationships Between Software Reliability, Software Metrics and Descriptional Complexity |
| 10:00-10:25 | Discussion - chaired by C. Kintala |
| 10:25-10:45 | Coffee Break |
| 10:45-11:35 | Invited Tutorial:
E. Csuhaj-Varju (Budapest, Hungary):
Descriptional Complexity Issues in Grammar Systems |
| 11:35-12:05 |
M. Madhu (Madras, India):
Complexity Issues in Rewriting P Systems |
| 14:00 | Excursion / Barbecue |
| Saturday, August 24, 2002 | |
|---|---|
| 09:00-10:00 | Invited Lecture:
L. Kari (London, Ontario, Canada):
Self-Assembly and Computation |
| 10:00-10:30 | Coffee Break |
| 10:30-11:00 |
A. Malcher (Frankfurt, Germany):
On One-Way Cellular Automata With a Fixed Number of Cells |
| 11:00-11:30 |
M. G. Eramian (London, Ontario, Canada):
Efficient Simulation of Nondeterministic Weighted Finite Automata |
| 11:30-12:00 |
I. McQuillan (London, Ontario, Canada):
Descriptional Complexity of Block-Synchronization Context-Free Grammars |
| 12:00-12:30 |
F. Nießner (Frankfurt, Germany):
Büchi Automata and Their Degrees of Nondeterminism and Ambiguity |
| 12:30-14:00 | Lunch |
| 14:00-15:00 | Invited Lecture:
S. Yu (London, Ontario, Canada):
Repetition Complexity of Words |
| 15:00-15:15 | Coffee Break |
| 15:15-15:45 |
C. Câmpeanu (Charlottetown, Prince Edward Island, Canada):
How Many States Can a Minimal DFA Have That Accepts Words of Length Less Than or Equal to l ? |
| 15:45-16:15 |
M. Sakthi Balan (Madras, India):
Complexity Issues in Binding-Blocking Automata |
| 16:15-16:45 |
T. Y. Nishida (Toyama, Japan):
Descriptional Complexities of Grammars Over Alphabets With Finite Parameters |
| 16:45-17:15 |
C. L. Miller (London, Ontario, Canada):
Context Derivation Sets and Context-Free Normal Forms |
| DCFS 2002 Homepage |
| Magdeburg, July 11, 2002 |