From: stacs@informatik.uni-wuerzburg.de (Stacs Conference Account)
Subject: STACS'93: Program & Registration form
Organization: Universitaet Wuerzburg
Date: Thu, 12 Nov 1992 15:23:09 GMT

Dear Colleagues,

below please find an ascii-version of the program and registration form
for STACS'93, Wuerzburg.
A Postscript file is availabe via anonymous ftp from
	haegar.informatik.uni-wuerzburg.de (132.187.101.41)

Looking forward to seeing you in Wuerzburg in February

--The Organizing Commitee of STACS'93




===========================================================================
%cut here!


_G_I                                                                _a_f_c_e_t


     SSSS   TTTTTTTTT     A         CCCC    SSSS     '  9999   3333  
    S    S      T        A A       C    C  S    S   '  9    9 3    3
    S           T       A   A     C        S           9    9      3  
     SS         T      A     A    C         SS         9    9    33  
       SS       T     AAAAAAAAA   C           SS        9999     33
         S      T    A         A  C             S         9        3
    S    S      T   A           A  C    C  S    S        9    3    3   
     SSSS       T  A             A  CCCC    SSSS        9      3333    



10th _Symposium on _Theoretical _Aspects of _Computer _Science '_9_3


		  February, 25--27
		  Congress Centrum
		 Wuerzburg, Germany


_P_r_o_g_r_a_m_ _C_o_m_m_i_t_t_e_e_:

    H. Bodlaender (Utrecht)
    M. Crochemore (Paris)
    P. Enjalbert (Caen, co-chair)
    A. Finkel (Cachan, co-chair)
    D. Gouyou-Beauchamps (Paris)
    J. Karhumaeki (Turku)
    A. de Luca (Roma)
    M. Rusinowitch (Villers-Les-Nancy)
    A. Salwicki (Pau)
    E. Shamir (Jerusalem)
    P. Starke (Berlin)
    K.W. Wagner (Wuerzburg, chair)
    E. Welzl (Berlin)
    P. Widmayer
    M. Wirsing


_O_r_g_a_n_i_z_i_n_g_ _C_o_m_m_i_t_t_e_e_:

    J. Albert
    G. Buntrock
    D. Emme
    S. Frank
    U. Hertrampf
    H. Vollmer
    K.W. Wagner
    J. Wolff v. Gudenberg (chair).









_G_I                                = 1 =                                 _a_f_c_e_t

_G_I                             STACS '93                                _a_f_c_e_t


		        _R_e_g_i_s_t_r_a_t_i_o_n_ _F_o_r_m

Registration fee includes the proceedings and the wine tasting party
(except for students). Full payment in DM without any bank transfer
charges must accompany registration.  (No checks please!)

	                   ___________________________________
	 		   |   by Jan 15   |  after Jan 15   |
	___________________|_______________|_________________|
	| AFCET--GI member |     170       |       210       |
	| Non-member	   |     220       |       260       |
	| Student          |      50       |        70       |
        ______________________________________________________

Please transfer money to Castell Bank Wuerzburg, (BLZ 790 300 01),
Account Wolff v. Gudenberg, keyword STACS '93, #020 037 99.

Reduced hotel rates can be arranged _b_e_f_o_r_e_ _D_e_c_e_m_b_e_r_ _1_1_,_ _1_9_9_2. All
prices are per room and night and include breakfast.  (Do not
transfer money for hotel reservation.)

	    _____________________________________________
	    |   Hotel      |  sgl  |  dbl  | shared dbl |
	    _____________________________________________
	    |   Strauss    |   90  |  130  |     65     |
	    |   Residence  |  110  |  140  |     70     |
	    |   Rebstock   |  143  |  226  |    113     |
	    |   Maritim    |  200  |  280  |    140     |
	    _____________________________________________


Name:_________________________________________________________________
First name:___________________________________________________Sex: f/m
Organization:_________________________________________________________
Mailing address:______________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
E-Mail address:_______________________________________________________
Phone/FAX:____________________________________________________________
GI--AFCET No.:________________________________________________________
Registration fee:                                     DM______________
Add. party tickets (DM 60) No:___________             DM______________
Total (Registration fee + party tickets):             DM______________
Desired hotel:________________________________________________________
From:_____________To:_____________(sgl/dbl/shared dbl)________________
Sharing double with:__________________________________________________

Date:_______________________ Signature:_______________________________

Return the registration form to

	Prof.Dr. J. Wolff v. Gudenberg
	Institut fuer Informatik
	Universitaet Wuerzburg
	Am Hubland
	D-8700 Wuerzburg

_G_I                                = 2 =                                 _a_f_c_e_t

_G_I                             STACS '93                                _a_f_c_e_t


		     _C_o_n_f_e_r_e_n_c_e_ _I_n_f_o_r_m_a_t_i_o_n


_L_o_c_a_t_i_o_n_:  _W_u_e_r_z_b_u_r_g_,_ _G_e_r_m_a_n_y

Wuerzburg is a city of about 130,000 inhabitants located in
Franconia, northern Bavaria, one of the most famous wine regions of
Europe.

Wuerzburg was founded by Franconian dukes nearly 1300 years ago and
became a rich and important town during the middle ages. The
University of Wuerzburg is one of the oldest in Europe. It was
founded in 1402.

Wuerzburg was one of the cultural centers of Germany in the baroque
epoch.  Even today, Wuerzburg has a baroque atmosphere, caused by
lots of well-preserved buildings from that time; the most famous of
which is probably the former bishop residence, a palace built by the
ingenious architect Balthasar Neumann.  The famous staircase of the
"Residenz" can be found on the back side of the DM 50 bill.

_W_u_e_r_z_b_u_r_g_ _C_l_i_m_a_t_e

Typical February weather is cold and wet, ranging from -5C to +5C
(23F to 41F). Snow or rain is likely.

_H_o_u_s_i_n_g

Reservations can be made in 4 hotels at prearranged reduced prices:

*   Hotel Maritim, a part of the Congress Centrum Wuerzburg,
    where the conference will take place, a first class hotel.
    (Unfortunately, only few reservations are possible in this
    hotel.)

*   Hotel Residence, Juliuspromenade 1, a five minute walk to
    the Congress Centrum.

*   Hotel Strauss, Juliuspromenade 5, a five minute walk to the
    Congress Centrum, with moderate prices.

*   Hotel Rebstock, Neubaustrasse 7, a 10 minute ride by tram
    line 4, direction "Zellerau". Get off at the "Congress
    Centrum" stop.


If you want to stay in one of these hotels, indicate as such on your
registration form. If you register early, _b_e_f_o_r_e_ _D_e_c_e_m_b_e_r_ _1_1, your
wish can probably be fullfilled. Every attempt will be made to
accommodate late registrations, but rooms and rates cannot be
guaranteed.







_G_I                                = 3 =                                 _a_f_c_e_t

_G_I                             STACS '93                                _a_f_c_e_t

                       _C_o_n_f_e_r_e_n_c_e_ _L_o_c_a_t_i_o_n

The Conference will take place in the Congress Centrum Wuerzburg,
Pleichertorstrasse.

_B_a_n_q_u_e_t

There will be a guided tour of the "Residenz" starting at 17:30 on
Friday 26th. Afterwards a wine tasting party in the "Residenz" wine
cellar accompanied by a typical Franconian "Haeckerbrotzeit" will
take place.

Additional tickets for the wine tasting party are available.  Please
indicate on the registration form.

_G_e_t_t_i_n_g_ _T_h_e_r_e

If you arrive by plane, there are direct trains from Frankfurt/Main
Airport to Wuerzburg, leaving every 60 min. or less.  The train ride
lasts about 100 min.

When you arrive at Wuerzburg Central Station, take the following
tram lines to reach your hotel:

*   Hotel Maritim, line 2 direction "Zellerau". Get off at
    "Congress Centrum" stop.

*   Hotel Residence or Strauss, line 2 direction "Zellerau". Get
    off at "Alter Kranen" stop.

*   Hotel Rebstock, line 3 direction "Heidingsfeld" or line 5
    direction "Heuchelhof". (Be sure the direction is correct!)
    Get off at "Neubaustrasse" stop.


_M_e_s_s_a_g_e_s_ _a_n_d_ _A_d_d_i_t_i_o_n_a_l_ _I_n_f_o_r_m_a_t_i_o_n

In the event that you need to be contacted at the conference,
messages can be left with Prof.Dr. K.W. Wagner, Lehrstuhl fuer
Theoretische Informatik, Am Exerzierplatz 3, Phone +49.931.88 78
10.  At this location there is also a world wide internet site
         haegar.informatik.uni-wuerzburg.de (132.187.101.41)
with anonymous ftp access and during the conference you will be able
to use e-mail.  Here you can get the map in PostScript format that is
mentioned in this program.

Further questions can be addressed by e-mail to

    stacs@informatik.uni-wuerzburg.de

or by letter to

	Prof.Dr. J. Wolff v. Gudenberg
	Institut fuer Informatik
	Universitaet Wuerzburg
	Am Hubland
	D-8700 Wuerzburg

_G_I                                = 4 =                                 _a_f_c_e_t

_G_I                             STACS '93                                _a_f_c_e_t

			Thursday, February 25
			=====================

9:00-9:15	Opening
		
9:15-10:00	Invited Lecture: Ilaria Castellani (Valbonne):
		Causal and Distributed Semantics for Concurrent Processes
-------------------------------------------------------------------------
10:00-10:30	Coffee Break
-------------------------------------------------------------------------
		    _B_a_l_t_h_a_s_a_r_-_N_e_u_m_a_n_n_-_S_a_a_l  (A-Sessions)

_S_e_s_s_i_o_n_ _1_A: COMPUTATIONAL COMPLEXITY
	(Thursday Morning, 10:30-12:10)
Chair: Klaus W. Wagner (Wuerzburg)

10:30	B. von Braunmuehl (Bonn):
	Alternation for two-way machines with sublogarithmic space.
10:55	M. Liskiewicz, R. Reischuk (Darmstadt):
	Separating the lower levels of the sublogarithmic space hierarchy.
11:20	J. Koebler (Ulm):
	Locating P/poly optimally in the extended low hierarchy.
11:45	J.. Lutz (Ames), E. Mayordomo Barcelona):
	Measure,stochasticity,and the density of hard languages.
-------------------------------------------------------------------------
12:10-13:40	Lunch
-------------------------------------------------------------------------
_S_e_s_s_i_o_n_ _2_A: EFFICIENT ALGORITHMS
	(Thursday  Early Afternoon, 13:40-15:20)
Chair: Peter Widmayer (Zuerich)

13:40   T. Kloks (Utrecht), D. Kratsch (Jena):
	Treewidth of chordal bipartite graphs.
14:05   U. Huckenbeck (Wuerzburg):
	On paths in networks with valves.
14:30   S. Sunder, X. He (Buffalo):
	Scheduling interval ordered tasks in parallel.
14:55   A. Pietracaprina, F.P. Preparata (Providence):
	An O(sqrt(n)log n)-worst case time solution to the
	granularity problem.
-------------------------------------------------------------------------
15:20-15:50	Coffee Break
-------------------------------------------------------------------------
_S_e_s_s_i_o_n_ _3_A: COMPUTATIONAL COMPLEXITY
	(Thursday Late Afternoon, 15:50-17:30)
Chair: Hans Bodlaender (Utrecht)

15:50   E. Allender (New Brunswick), J. Balcazar (Barcelona), N.
	Immerman (Amherst):
	A first-order isomorphism theorem.
16:15   H. Buhrmann (Amsterdam), A. Hoene (Berlin), L. Torenvliet
	(Amsterdam):
	Splitting,robustness and structure of complete sets.
16:40   L.A. Hemachandra, S.K. Jha (Rochester):
	Defying upward and downward separation.
17:05   A. Hoene, A. Nickelsen (Berlin):
	Counting,selecting,and sorting by query-bounded machines.
-------------------------------------------------------------------------
_G_I                                = 5 =                                 _a_f_c_e_t

_G_I                            STACS '93                               _a_f_c_e_t






_T_i_e_p_o_l_o_-_S_a_a_l  (B-Sessions)

-------------------------------------------------------------------------
_S_e_s_s_i_o_n_ _1_B: LOGIC IN COMPUTER SCIENCE
	(Thursday Morning, 10:30-12:10)
Chair: Michael Rusinowitch (Nancy)

10:30   P. Devienne, P. Lebegue, J.-C. Routier (Lille):
	Halting problem of one binary Horn clause is undecidable.
10:55   Z. Chaochen, M.R. Hansen, P. Sestoft (Lyngby):
	Decidability results for duration calculus.
11:20   P. de Groote (Louvain):
	Defining lambda-typed calculi by axiomatizing the typing
	relation.
11:45   T. Eiter, G. Gottlob (Vienna):
	The complexity of logic-based abduction.

-------------------------------------------------------------------------
12:10-13:40	Lunch
-------------------------------------------------------------------------
_S_e_s_s_i_o_n_ _2_B: PARALLEL AND DISTRIBUTED COMPUTATION
	(Thursday  Early Afternoon, 13:40-15:20)
Chair: Peter Starke (Berlin)

13:40   J. Desel, W. Reisig (Munich):
	The synthesis problem of Petri nets.
14:05   E. Best (Hildesheim), R. Devillers (Brussels), J. Esparza
	(Hildesheim):
	General refinement and recursion operators for the Petri
	box calculus.
14:30   M.P. Bonacina, J. Hsiang (Stony Brook):
	On fairness in distributed automated deduction.
14:55   E.W. Mayr, R. Werchner (Frankfurt):
	Divide-and-conquer algorithms on the hypercube.

-------------------------------------------------------------------------
15:20-15:50	Coffee Break
-------------------------------------------------------------------------
_S_e_s_s_i_o_n_ _3_B: LANGUAGE THEORY
	(Thursday Late Afternoon, 15:50-17:30)
Chair: Juhani Karhumaeki (Turku)

15:50   M. Jantzen, H. Petersen (Hamburg):
	Cancellation in context-free languages: enrichment by
	reduction.
16:15   J. Cassaigne (Paris):
	Counting overlap-free binary words.
16:40   P. Narbel (Paris):
	The limit set of recognizable substitution systems.
17:05   D. Krob (Rouen), P. Lalonde (Massachusets):
	Partially commutative Lyndon words.
-------------------------------------------------------------------------

_G_I                                = 6 =                                 _a_f_c_e_t

_G_I                            STACS '93                               _a_f_c_e_t

                       Friday, February 26
                       ===================
8:30-9:15	Invited Lecture: Burkhard Monien (Paderborn):
		Parallel Architecture: Design and Efficient Use
-------------------------------------------------------------------------
9:15-9:45	Coffee Break
-------------------------------------------------------------------------
_B_a_l_t_h_a_s_a_r_-_N_e_u_m_a_n_n_-_S_a_a_l  (A-Sessions)

_S_e_s_s_i_o_n_ _4_A: COMPUTATIONAL GEOMETRY
	(Friday Morning, 9:45-11:50)
Chair: Emo Welzl (Berlin)

9:45	M. Formann (Berlin):
	Weighted closest pairs.
10:10	S. Schuierer (Freiburg):
	Rectilinear path queries in a simple rectilinear polygon.
10:35	A. Czumaj (Warsaw):
	Parallel algorithm for the matrix chain product and the
	optimal triangulation problem.
11:00	A. Dessmark, A. Lingas (Lund), A. Maheshwari (Bombay):
	Multi-list ranking: complexity and applications.
11:25   L. Kucera, K. Mehlhorn, B. Preis, E. Schwarzenecker (Saarbruecken):
	Exact algorithms for a geometric packing problem.
-------------------------------------------------------------------------
11:50-13:20     Lunch
-------------------------------------------------------------------------
_S_e_s_s_i_o_n_ _5_A: COMPUTATIONAL COMPLEXITY
	(Friday Early Afternoon, 13:20-15:00)
Chair: Maxime Crochemore (Paris)

13:20   K.A. Abrahamson (Pullman), R.G. Downey (Wellington), M.R.
	Fellows (Victoria):
	Fixed-parameter intractability II.
13:45   F.E. Fich, R. Impagliazzo, B. Kapron, V. King (Toronto),
	M. Kutylowski (Paderborn):
	Limits on the power of parallel random access machines
	with weak forms of write conflict resolution.
14:10   S. Fenner (Gorham), S. Homer (Boston), M. Ogiwara (Tokyo),
	A.L. Selman (Buffalo):
	On using oracles that compute values.
14:35   R. Gengler (Bonn):
	Multicounter automata with sublogarithmic reversal
	bounds.
-------------------------------------------------------------------------
15:00-15:20     Coffee Break
-------------------------------------------------------------------------
_S_e_s_s_i_o_n_ _6_A: COMPUTATIONAL COMPLEXITY
	(Friday Late Afternoon, 15:20-16:35)
Chair: Dominique Gouyou-Beauchamps (Orsay)

15:20   K. Luerwer-Brueggemeier, F. Meyer auf der Heide (Paderborn):
	Capabilities and complexity of computations with integer division.
15:45   R. Niedermeier, P. Rossmanith (Munich):
	Extended locally definable acceptance types.
16:10   S. Fenner (Gorham), L. Fortnow, L. Li (Chicago):
	Gap-definability as a closure property.
-------------------------------------------------------------------------
_G_I                                = 7 =                                 _a_f_c_e_t

_G_I                            STACS '93                               _a_f_c_e_t




_T_i_e_p_o_l_o_-_S_a_a_l  (B-Sessions)
-------------------------------------------------------------------------
_S_e_s_s_i_o_n_ _4_B: AUTOMATA THEORY
	(Friday Morning, 9:45-11:50)
Chair: Alain Finkel (Cachan)
-------------------------------------------------------------------------

9:45	O. Maler (Rennes):
        A decomposition theorem for probabilistic transition systems.
10:10	R. Montalbano (Palermo):
	Local automata and completion.
10:35	K. Culik II, S. Dube (Columbia):
	Implementing wavelet transform with automata and
	application to data compression.
11:00   O.H. Ibarra (Santa Barbara), T. Jiang (Ontario), N. Tran,
	H. Wang (Santa Barbara):
	On the equivalence of two-way pushdown automata and
	counter machines over bounded languages.
11:25   M. Cosnard, M. Garzon, P. Koiran (Lyon):
	Computability properties of low-dimensional dynamical
	systems.
-------------------------------------------------------------------------
11:50-13:20     Lunch
-------------------------------------------------------------------------
_S_e_s_s_i_o_n_ _5_B SEMANTICS AND LOGICS OF PROGRAMMING LANGUAGES
	(Friday Early Afternoon, 13:20-15:00)
Chair: Martin Wirsing (Munich)

13:20	A.C. Uselton (Stony Brook):
	Structured operational semantics for concurrency and
	hierarchy.
13:45	H. Hungar (Oldenburg):
	The complexity of verifying functional programs.
14:10	P.J.A. Lentfert, S.D. Swierstra (Utrecht):
	Towards the formal design of self-stabilizing distributed
	algorithms.
14:35	W. Penczek (Warsaw):
	Axiomatizations of temporal logics on trace systems.
-------------------------------------------------------------------------
15:00-15:20     Coffee Break
-------------------------------------------------------------------------
_S_e_s_s_i_o_n_ _6_B: AUTOMATA THEORY AND LOGIC
Chair: Patrice Enjalbert (Caen)
	(Friday Early Afternoon, 15:20-16:35)

15:20	C. Choffrut, L. Guerra (Paris):
	On the logical definability of some rational trace language.
15:45	R. Gilleron, S. Tison, M. Tommasi (Lille):
	Solving systems of set constraints using tree automata.
16:10	D. Lugiez, J.L. Moysset (Nancy):
	Complement problems and tree automata in AC-like theories.
-------------------------------------------------------------------------
17:30-23:00     Guided tour of the "Residenz", chamber concert, wine
		tasting party
-------------------------------------------------------------------------
_G_I                                = 8 =                                 _a_f_c_e_t

_G_I                            STACS '93                               _a_f_c_e_t


			  Saturday, February 27
			  =====================

8:30-9:15	Invited Lecture: Laszlo Babai (Chicago):
		Transparent Proofs
-------------------------------------------------------------------------
9:15-9:45	Coffee Break
-------------------------------------------------------------------------
_B_a_l_t_h_a_s_a_r_-_N_e_u_m_a_n_n_H-_HS_a_a_l  (A-Sessions)

_S_e_s_s_i_o_n_ _7_A: CIRCUIT COMPLEXITY
	(Saturday Morning, 9:45-11:50)
Chair: Andrzej Salwicki (Pau)

9:45    Z.-L. Zhang, D.A. Mix Barrington (Amherts), J. Tarui
	(Warwick):
	Computing symmetric functions with AND/OR circuits and a
	single majority gate.
10:10	A. Maciel, D. Therien (Montreal):
	Threshold circuits for iterated multiplication: using AC0
	for free.
10:35	M. Beaudry (Sherbrooke), P. McKenzie, P. Peladeau (Montreal):
	Circuits with monoidal gates.
11:00	S. Istrail, D. Zivkovic (Middleton):
	A non probabilistic switching lemma for the Sipser function.
11:25	J. Gergov, C. Meinel (Trier):
	Frontiers of feasible and probabilistic feasible boolean
	manipulation with branching programs.
-------------------------------------------------------------------------
11:50-13:20     Lunch
-------------------------------------------------------------------------
_S_e_s_s_i_o_n_ _8_A: NON-CLASSICAL COMPLEXITY
	(Saturday Early Afternoon, 13:20-14:35)
Chair: Juergen Albert (Wuerzburg)

13:20	S. Sairam, J.S. Vitter, R. Tamassia (Providence):
	A complexity theoretic approach to incremental computation.
13:45	R. Reischuk, C. Schindelhauer (Darmstadt):
	Precise average case complexity.
14:10	P.B. Miltersen (Aarhus):
	The bit probe complexity measure revisited.
-------------------------------------------------------------------------















_G_I                                = 9 =                                 _a_f_c_e_t

_G_I                            STACS '93                               _a_f_c_e_t





_T_i_e_p_o_l_o_-_S_a_a_l  (B-Sessions)
_S_e_s_s_i_o_n 2: The Chair is to be elected                      
-------------------------------------------------------------------------
_S_e_s_s_i_o_n_ _7_B: w-AUTOMATA
Chair: Aldo de Luca (Rome)
	(Saturday Morning, 13:20-15:00)

9:45	O. Maler (Rennes), L. Staiger (Siegen):
	On syntactic congruences for w-languages.
10:10	S. Varricchio (L'Aquila):
	A polynomial time algorithm for the equivalence of two
	morphisms on w-regular languages.
10:35	T. Wilke (Kiel):
	Locally threshold testable languages of infinite words.
11:00	V. Diekert, A. Muscholl (Stuttgart):
	Deterministic asynchronous automata for infinite traces.
11:25	L. Staiger (Siegen):
	Recursive automata on infinite words.
-------------------------------------------------------------------------
11:50-13:20     Lunch
-------------------------------------------------------------------------
_S_e_s_s_i_o_n_ _8_B: LEARNING THEORY AND CRYPTOGRAPHY
	(Saturday Early Afternoon, 13:20-14:35)
Chair: Eli Shamir (Jerusalem)

13:20	G. Baliga, J. Case, S. Jain (Newark):
	Language learning with some negative information.
13:45	S. Lange (Leipzig), T. Zeugmann (Darmstadt):
	Language learning with a bounded number of mind changes.
14:10	C. Blundo, A. De Santis, U. Vaccaro (Salerno):
	Efficient sharing of many secrets.
-------------------------------------------------------------------------
14:35	End of STACS '93
-------------------------------------------------------------------------





_A_c_k_n_o_w_l_e__d_g_e_m_e_n_t_s

We wish to thank all sponsors for their support. We gratefully
acknowledge the help of Vogel Verlag Wuerzburg for printing the "call
for papers", the poster and the program free of charge.

			 Sponsored by
	       Deutsche Forschungsgemeinschaft
    Bayerische Julius-Maximilians-Universitaet Wuerzburg
			 Vogel Verlag
		       IBM Deutschland
		 Fremdenverkehrsamt Wuerzburg
		 Universitaetsbund  Wuerzburg
		    Castell Bank Wuerzburg
	     Keupp, Faber-Castell, Staedtler-Mars

_G_I                                    = 10 =                                _a_f_c_e_t
Newsgroups: comp.theory,sci.math