home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / 2398 < prev    next >
Encoding:
Text File  |  1992-11-12  |  23.7 KB  |  651 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!sun-barr!cs.utexas.edu!uwm.edu!zaphod.mps.ohio-state.edu!darwin.sura.net!jvnc.net!yale.edu!ira.uka.de!fauern!dec16!stacs
  3. From: stacs@informatik.uni-wuerzburg.de (Stacs Conference Account)
  4. Subject: STACS'93: Program & Registration form
  5. Message-ID: <1992Nov12.152309.20029@informatik.uni-wuerzburg.de>
  6. Sender: news@informatik.uni-wuerzburg.de (USENET News account)
  7. Organization: Universitaet Wuerzburg
  8. Date: Thu, 12 Nov 1992 15:23:09 GMT
  9. Lines: 640
  10.  
  11. Dear Colleagues,
  12.  
  13. below please find an ascii-version of the program and registration form
  14. for STACS'93, Wuerzburg.
  15. A Postscript file is availabe via anonymous ftp from
  16.     haegar.informatik.uni-wuerzburg.de (132.187.101.41)
  17.  
  18. Looking forward to seeing you in Wuerzburg in February
  19.  
  20. --The Organizing Commitee of STACS'93
  21.  
  22.  
  23.  
  24.  
  25. ===========================================================================
  26. %cut here!
  27.  
  28.  
  29. _G_I                                                                _a_f_c_e_t
  30.  
  31.  
  32.      SSSS   TTTTTTTTT     A         CCCC    SSSS     '  9999   3333  
  33.     S    S      T        A A       C    C  S    S   '  9    9 3    3
  34.     S           T       A   A     C        S           9    9      3  
  35.      SS         T      A     A    C         SS         9    9    33  
  36.        SS       T     AAAAAAAAA   C           SS        9999     33
  37.          S      T    A         A  C             S         9        3
  38.     S    S      T   A           A  C    C  S    S        9    3    3   
  39.      SSSS       T  A             A  CCCC    SSSS        9      3333    
  40.  
  41.  
  42.  
  43. 10th _Symposium on _Theoretical _Aspects of _Computer _Science '_9_3
  44.  
  45.  
  46.           February, 25--27
  47.           Congress Centrum
  48.          Wuerzburg, Germany
  49.  
  50.  
  51. _P_r_o_g_r_a_m_ _C_o_m_m_i_t_t_e_e_:
  52.  
  53.     H. Bodlaender (Utrecht)
  54.     M. Crochemore (Paris)
  55.     P. Enjalbert (Caen, co-chair)
  56.     A. Finkel (Cachan, co-chair)
  57.     D. Gouyou-Beauchamps (Paris)
  58.     J. Karhumaeki (Turku)
  59.     A. de Luca (Roma)
  60.     M. Rusinowitch (Villers-Les-Nancy)
  61.     A. Salwicki (Pau)
  62.     E. Shamir (Jerusalem)
  63.     P. Starke (Berlin)
  64.     K.W. Wagner (Wuerzburg, chair)
  65.     E. Welzl (Berlin)
  66.     P. Widmayer
  67.     M. Wirsing
  68.  
  69.  
  70. _O_r_g_a_n_i_z_i_n_g_ _C_o_m_m_i_t_t_e_e_:
  71.  
  72.     J. Albert
  73.     G. Buntrock
  74.     D. Emme
  75.     S. Frank
  76.     U. Hertrampf
  77.     H. Vollmer
  78.     K.W. Wagner
  79.     J. Wolff v. Gudenberg (chair).
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89. _G_I                                = 1 =                                 _a_f_c_e_t
  90.  
  91. _G_I                             STACS '93                                _a_f_c_e_t
  92.  
  93.  
  94.                 _R_e_g_i_s_t_r_a_t_i_o_n_ _F_o_r_m
  95.  
  96. Registration fee includes the proceedings and the wine tasting party
  97. (except for students). Full payment in DM without any bank transfer
  98. charges must accompany registration.  (No checks please!)
  99.  
  100.                        ___________________________________
  101.                 |   by Jan 15   |  after Jan 15   |
  102.     ___________________|_______________|_________________|
  103.     | AFCET--GI member |     170       |       210       |
  104.     | Non-member       |     220       |       260       |
  105.     | Student          |      50       |        70       |
  106.         ______________________________________________________
  107.  
  108. Please transfer money to Castell Bank Wuerzburg, (BLZ 790 300 01),
  109. Account Wolff v. Gudenberg, keyword STACS '93, #020 037 99.
  110.  
  111. 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
  112. prices are per room and night and include breakfast.  (Do not
  113. transfer money for hotel reservation.)
  114.  
  115.         _____________________________________________
  116.         |   Hotel      |  sgl  |  dbl  | shared dbl |
  117.         _____________________________________________
  118.         |   Strauss    |   90  |  130  |     65     |
  119.         |   Residence  |  110  |  140  |     70     |
  120.         |   Rebstock   |  143  |  226  |    113     |
  121.         |   Maritim    |  200  |  280  |    140     |
  122.         _____________________________________________
  123.  
  124.  
  125. Name:_________________________________________________________________
  126. First name:___________________________________________________Sex: f/m
  127. Organization:_________________________________________________________
  128. Mailing address:______________________________________________________
  129. ______________________________________________________________________
  130. ______________________________________________________________________
  131. ______________________________________________________________________
  132. E-Mail address:_______________________________________________________
  133. Phone/FAX:____________________________________________________________
  134. GI--AFCET No.:________________________________________________________
  135. Registration fee:                                     DM______________
  136. Add. party tickets (DM 60) No:___________             DM______________
  137. Total (Registration fee + party tickets):             DM______________
  138. Desired hotel:________________________________________________________
  139. From:_____________To:_____________(sgl/dbl/shared dbl)________________
  140. Sharing double with:__________________________________________________
  141.  
  142. Date:_______________________ Signature:_______________________________
  143.  
  144. Return the registration form to
  145.  
  146.     Prof.Dr. J. Wolff v. Gudenberg
  147.     Institut fuer Informatik
  148.     Universitaet Wuerzburg
  149.     Am Hubland
  150.     D-8700 Wuerzburg
  151.  
  152. _G_I                                = 2 =                                 _a_f_c_e_t
  153.  
  154. _G_I                             STACS '93                                _a_f_c_e_t
  155.  
  156.  
  157.              _C_o_n_f_e_r_e_n_c_e_ _I_n_f_o_r_m_a_t_i_o_n
  158.  
  159.  
  160. _L_o_c_a_t_i_o_n_:  _W_u_e_r_z_b_u_r_g_,_ _G_e_r_m_a_n_y
  161.  
  162. Wuerzburg is a city of about 130,000 inhabitants located in
  163. Franconia, northern Bavaria, one of the most famous wine regions of
  164. Europe.
  165.  
  166. Wuerzburg was founded by Franconian dukes nearly 1300 years ago and
  167. became a rich and important town during the middle ages. The
  168. University of Wuerzburg is one of the oldest in Europe. It was
  169. founded in 1402.
  170.  
  171. Wuerzburg was one of the cultural centers of Germany in the baroque
  172. epoch.  Even today, Wuerzburg has a baroque atmosphere, caused by
  173. lots of well-preserved buildings from that time; the most famous of
  174. which is probably the former bishop residence, a palace built by the
  175. ingenious architect Balthasar Neumann.  The famous staircase of the
  176. "Residenz" can be found on the back side of the DM 50 bill.
  177.  
  178. _W_u_e_r_z_b_u_r_g_ _C_l_i_m_a_t_e
  179.  
  180. Typical February weather is cold and wet, ranging from -5C to +5C
  181. (23F to 41F). Snow or rain is likely.
  182.  
  183. _H_o_u_s_i_n_g
  184.  
  185. Reservations can be made in 4 hotels at prearranged reduced prices:
  186.  
  187. *   Hotel Maritim, a part of the Congress Centrum Wuerzburg,
  188.     where the conference will take place, a first class hotel.
  189.     (Unfortunately, only few reservations are possible in this
  190.     hotel.)
  191.  
  192. *   Hotel Residence, Juliuspromenade 1, a five minute walk to
  193.     the Congress Centrum.
  194.  
  195. *   Hotel Strauss, Juliuspromenade 5, a five minute walk to the
  196.     Congress Centrum, with moderate prices.
  197.  
  198. *   Hotel Rebstock, Neubaustrasse 7, a 10 minute ride by tram
  199.     line 4, direction "Zellerau". Get off at the "Congress
  200.     Centrum" stop.
  201.  
  202.  
  203. If you want to stay in one of these hotels, indicate as such on your
  204. registration form. If you register early, _b_e_f_o_r_e_ _D_e_c_e_m_b_e_r_ _1_1, your
  205. wish can probably be fullfilled. Every attempt will be made to
  206. accommodate late registrations, but rooms and rates cannot be
  207. guaranteed.
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215. _G_I                                = 3 =                                 _a_f_c_e_t
  216.  
  217. _G_I                             STACS '93                                _a_f_c_e_t
  218.  
  219.                        _C_o_n_f_e_r_e_n_c_e_ _L_o_c_a_t_i_o_n
  220.  
  221. The Conference will take place in the Congress Centrum Wuerzburg,
  222. Pleichertorstrasse.
  223.  
  224. _B_a_n_q_u_e_t
  225.  
  226. There will be a guided tour of the "Residenz" starting at 17:30 on
  227. Friday 26th. Afterwards a wine tasting party in the "Residenz" wine
  228. cellar accompanied by a typical Franconian "Haeckerbrotzeit" will
  229. take place.
  230.  
  231. Additional tickets for the wine tasting party are available.  Please
  232. indicate on the registration form.
  233.  
  234. _G_e_t_t_i_n_g_ _T_h_e_r_e
  235.  
  236. If you arrive by plane, there are direct trains from Frankfurt/Main
  237. Airport to Wuerzburg, leaving every 60 min. or less.  The train ride
  238. lasts about 100 min.
  239.  
  240. When you arrive at Wuerzburg Central Station, take the following
  241. tram lines to reach your hotel:
  242.  
  243. *   Hotel Maritim, line 2 direction "Zellerau". Get off at
  244.     "Congress Centrum" stop.
  245.  
  246. *   Hotel Residence or Strauss, line 2 direction "Zellerau". Get
  247.     off at "Alter Kranen" stop.
  248.  
  249. *   Hotel Rebstock, line 3 direction "Heidingsfeld" or line 5
  250.     direction "Heuchelhof". (Be sure the direction is correct!)
  251.     Get off at "Neubaustrasse" stop.
  252.  
  253.  
  254. _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
  255.  
  256. In the event that you need to be contacted at the conference,
  257. messages can be left with Prof.Dr. K.W. Wagner, Lehrstuhl fuer
  258. Theoretische Informatik, Am Exerzierplatz 3, Phone +49.931.88 78
  259. 10.  At this location there is also a world wide internet site
  260.          haegar.informatik.uni-wuerzburg.de (132.187.101.41)
  261. with anonymous ftp access and during the conference you will be able
  262. to use e-mail.  Here you can get the map in PostScript format that is
  263. mentioned in this program.
  264.  
  265. Further questions can be addressed by e-mail to
  266.  
  267.     stacs@informatik.uni-wuerzburg.de
  268.  
  269. or by letter to
  270.  
  271.     Prof.Dr. J. Wolff v. Gudenberg
  272.     Institut fuer Informatik
  273.     Universitaet Wuerzburg
  274.     Am Hubland
  275.     D-8700 Wuerzburg
  276.  
  277. _G_I                                = 4 =                                 _a_f_c_e_t
  278.  
  279. _G_I                             STACS '93                                _a_f_c_e_t
  280.  
  281.             Thursday, February 25
  282.             =====================
  283.  
  284. 9:00-9:15    Opening
  285.         
  286. 9:15-10:00    Invited Lecture: Ilaria Castellani (Valbonne):
  287.         Causal and Distributed Semantics for Concurrent Processes
  288. -------------------------------------------------------------------------
  289. 10:00-10:30    Coffee Break
  290. -------------------------------------------------------------------------
  291.             _B_a_l_t_h_a_s_a_r_-_N_e_u_m_a_n_n_-_S_a_a_l  (A-Sessions)
  292.  
  293. _S_e_s_s_i_o_n_ _1_A: COMPUTATIONAL COMPLEXITY
  294.     (Thursday Morning, 10:30-12:10)
  295. Chair: Klaus W. Wagner (Wuerzburg)
  296.  
  297. 10:30    B. von Braunmuehl (Bonn):
  298.     Alternation for two-way machines with sublogarithmic space.
  299. 10:55    M. Liskiewicz, R. Reischuk (Darmstadt):
  300.     Separating the lower levels of the sublogarithmic space hierarchy.
  301. 11:20    J. Koebler (Ulm):
  302.     Locating P/poly optimally in the extended low hierarchy.
  303. 11:45    J.. Lutz (Ames), E. Mayordomo Barcelona):
  304.     Measure,stochasticity,and the density of hard languages.
  305. -------------------------------------------------------------------------
  306. 12:10-13:40    Lunch
  307. -------------------------------------------------------------------------
  308. _S_e_s_s_i_o_n_ _2_A: EFFICIENT ALGORITHMS
  309.     (Thursday  Early Afternoon, 13:40-15:20)
  310. Chair: Peter Widmayer (Zuerich)
  311.  
  312. 13:40   T. Kloks (Utrecht), D. Kratsch (Jena):
  313.     Treewidth of chordal bipartite graphs.
  314. 14:05   U. Huckenbeck (Wuerzburg):
  315.     On paths in networks with valves.
  316. 14:30   S. Sunder, X. He (Buffalo):
  317.     Scheduling interval ordered tasks in parallel.
  318. 14:55   A. Pietracaprina, F.P. Preparata (Providence):
  319.     An O(sqrt(n)log n)-worst case time solution to the
  320.     granularity problem.
  321. -------------------------------------------------------------------------
  322. 15:20-15:50    Coffee Break
  323. -------------------------------------------------------------------------
  324. _S_e_s_s_i_o_n_ _3_A: COMPUTATIONAL COMPLEXITY
  325.     (Thursday Late Afternoon, 15:50-17:30)
  326. Chair: Hans Bodlaender (Utrecht)
  327.  
  328. 15:50   E. Allender (New Brunswick), J. Balcazar (Barcelona), N.
  329.     Immerman (Amherst):
  330.     A first-order isomorphism theorem.
  331. 16:15   H. Buhrmann (Amsterdam), A. Hoene (Berlin), L. Torenvliet
  332.     (Amsterdam):
  333.     Splitting,robustness and structure of complete sets.
  334. 16:40   L.A. Hemachandra, S.K. Jha (Rochester):
  335.     Defying upward and downward separation.
  336. 17:05   A. Hoene, A. Nickelsen (Berlin):
  337.     Counting,selecting,and sorting by query-bounded machines.
  338. -------------------------------------------------------------------------
  339. _G_I                                = 5 =                                 _a_f_c_e_t
  340.  
  341. _G_I                            STACS '93                               _a_f_c_e_t
  342.  
  343.  
  344.  
  345.  
  346.  
  347.  
  348. _T_i_e_p_o_l_o_-_S_a_a_l  (B-Sessions)
  349.  
  350. -------------------------------------------------------------------------
  351. _S_e_s_s_i_o_n_ _1_B: LOGIC IN COMPUTER SCIENCE
  352.     (Thursday Morning, 10:30-12:10)
  353. Chair: Michael Rusinowitch (Nancy)
  354.  
  355. 10:30   P. Devienne, P. Lebegue, J.-C. Routier (Lille):
  356.     Halting problem of one binary Horn clause is undecidable.
  357. 10:55   Z. Chaochen, M.R. Hansen, P. Sestoft (Lyngby):
  358.     Decidability results for duration calculus.
  359. 11:20   P. de Groote (Louvain):
  360.     Defining lambda-typed calculi by axiomatizing the typing
  361.     relation.
  362. 11:45   T. Eiter, G. Gottlob (Vienna):
  363.     The complexity of logic-based abduction.
  364.  
  365. -------------------------------------------------------------------------
  366. 12:10-13:40    Lunch
  367. -------------------------------------------------------------------------
  368. _S_e_s_s_i_o_n_ _2_B: PARALLEL AND DISTRIBUTED COMPUTATION
  369.     (Thursday  Early Afternoon, 13:40-15:20)
  370. Chair: Peter Starke (Berlin)
  371.  
  372. 13:40   J. Desel, W. Reisig (Munich):
  373.     The synthesis problem of Petri nets.
  374. 14:05   E. Best (Hildesheim), R. Devillers (Brussels), J. Esparza
  375.     (Hildesheim):
  376.     General refinement and recursion operators for the Petri
  377.     box calculus.
  378. 14:30   M.P. Bonacina, J. Hsiang (Stony Brook):
  379.     On fairness in distributed automated deduction.
  380. 14:55   E.W. Mayr, R. Werchner (Frankfurt):
  381.     Divide-and-conquer algorithms on the hypercube.
  382.  
  383. -------------------------------------------------------------------------
  384. 15:20-15:50    Coffee Break
  385. -------------------------------------------------------------------------
  386. _S_e_s_s_i_o_n_ _3_B: LANGUAGE THEORY
  387.     (Thursday Late Afternoon, 15:50-17:30)
  388. Chair: Juhani Karhumaeki (Turku)
  389.  
  390. 15:50   M. Jantzen, H. Petersen (Hamburg):
  391.     Cancellation in context-free languages: enrichment by
  392.     reduction.
  393. 16:15   J. Cassaigne (Paris):
  394.     Counting overlap-free binary words.
  395. 16:40   P. Narbel (Paris):
  396.     The limit set of recognizable substitution systems.
  397. 17:05   D. Krob (Rouen), P. Lalonde (Massachusets):
  398.     Partially commutative Lyndon words.
  399. -------------------------------------------------------------------------
  400.  
  401. _G_I                                = 6 =                                 _a_f_c_e_t
  402.  
  403. _G_I                            STACS '93                               _a_f_c_e_t
  404.  
  405.                        Friday, February 26
  406.                        ===================
  407. 8:30-9:15    Invited Lecture: Burkhard Monien (Paderborn):
  408.         Parallel Architecture: Design and Efficient Use
  409. -------------------------------------------------------------------------
  410. 9:15-9:45    Coffee Break
  411. -------------------------------------------------------------------------
  412. _B_a_l_t_h_a_s_a_r_-_N_e_u_m_a_n_n_-_S_a_a_l  (A-Sessions)
  413.  
  414. _S_e_s_s_i_o_n_ _4_A: COMPUTATIONAL GEOMETRY
  415.     (Friday Morning, 9:45-11:50)
  416. Chair: Emo Welzl (Berlin)
  417.  
  418. 9:45    M. Formann (Berlin):
  419.     Weighted closest pairs.
  420. 10:10    S. Schuierer (Freiburg):
  421.     Rectilinear path queries in a simple rectilinear polygon.
  422. 10:35    A. Czumaj (Warsaw):
  423.     Parallel algorithm for the matrix chain product and the
  424.     optimal triangulation problem.
  425. 11:00    A. Dessmark, A. Lingas (Lund), A. Maheshwari (Bombay):
  426.     Multi-list ranking: complexity and applications.
  427. 11:25   L. Kucera, K. Mehlhorn, B. Preis, E. Schwarzenecker (Saarbruecken):
  428.     Exact algorithms for a geometric packing problem.
  429. -------------------------------------------------------------------------
  430. 11:50-13:20     Lunch
  431. -------------------------------------------------------------------------
  432. _S_e_s_s_i_o_n_ _5_A: COMPUTATIONAL COMPLEXITY
  433.     (Friday Early Afternoon, 13:20-15:00)
  434. Chair: Maxime Crochemore (Paris)
  435.  
  436. 13:20   K.A. Abrahamson (Pullman), R.G. Downey (Wellington), M.R.
  437.     Fellows (Victoria):
  438.     Fixed-parameter intractability II.
  439. 13:45   F.E. Fich, R. Impagliazzo, B. Kapron, V. King (Toronto),
  440.     M. Kutylowski (Paderborn):
  441.     Limits on the power of parallel random access machines
  442.     with weak forms of write conflict resolution.
  443. 14:10   S. Fenner (Gorham), S. Homer (Boston), M. Ogiwara (Tokyo),
  444.     A.L. Selman (Buffalo):
  445.     On using oracles that compute values.
  446. 14:35   R. Gengler (Bonn):
  447.     Multicounter automata with sublogarithmic reversal
  448.     bounds.
  449. -------------------------------------------------------------------------
  450. 15:00-15:20     Coffee Break
  451. -------------------------------------------------------------------------
  452. _S_e_s_s_i_o_n_ _6_A: COMPUTATIONAL COMPLEXITY
  453.     (Friday Late Afternoon, 15:20-16:35)
  454. Chair: Dominique Gouyou-Beauchamps (Orsay)
  455.  
  456. 15:20   K. Luerwer-Brueggemeier, F. Meyer auf der Heide (Paderborn):
  457.     Capabilities and complexity of computations with integer division.
  458. 15:45   R. Niedermeier, P. Rossmanith (Munich):
  459.     Extended locally definable acceptance types.
  460. 16:10   S. Fenner (Gorham), L. Fortnow, L. Li (Chicago):
  461.     Gap-definability as a closure property.
  462. -------------------------------------------------------------------------
  463. _G_I                                = 7 =                                 _a_f_c_e_t
  464.  
  465. _G_I                            STACS '93                               _a_f_c_e_t
  466.  
  467.  
  468.  
  469.  
  470. _T_i_e_p_o_l_o_-_S_a_a_l  (B-Sessions)
  471. -------------------------------------------------------------------------
  472. _S_e_s_s_i_o_n_ _4_B: AUTOMATA THEORY
  473.     (Friday Morning, 9:45-11:50)
  474. Chair: Alain Finkel (Cachan)
  475. -------------------------------------------------------------------------
  476.  
  477. 9:45    O. Maler (Rennes):
  478.         A decomposition theorem for probabilistic transition systems.
  479. 10:10    R. Montalbano (Palermo):
  480.     Local automata and completion.
  481. 10:35    K. Culik II, S. Dube (Columbia):
  482.     Implementing wavelet transform with automata and
  483.     application to data compression.
  484. 11:00   O.H. Ibarra (Santa Barbara), T. Jiang (Ontario), N. Tran,
  485.     H. Wang (Santa Barbara):
  486.     On the equivalence of two-way pushdown automata and
  487.     counter machines over bounded languages.
  488. 11:25   M. Cosnard, M. Garzon, P. Koiran (Lyon):
  489.     Computability properties of low-dimensional dynamical
  490.     systems.
  491. -------------------------------------------------------------------------
  492. 11:50-13:20     Lunch
  493. -------------------------------------------------------------------------
  494. _S_e_s_s_i_o_n_ _5_B SEMANTICS AND LOGICS OF PROGRAMMING LANGUAGES
  495.     (Friday Early Afternoon, 13:20-15:00)
  496. Chair: Martin Wirsing (Munich)
  497.  
  498. 13:20    A.C. Uselton (Stony Brook):
  499.     Structured operational semantics for concurrency and
  500.     hierarchy.
  501. 13:45    H. Hungar (Oldenburg):
  502.     The complexity of verifying functional programs.
  503. 14:10    P.J.A. Lentfert, S.D. Swierstra (Utrecht):
  504.     Towards the formal design of self-stabilizing distributed
  505.     algorithms.
  506. 14:35    W. Penczek (Warsaw):
  507.     Axiomatizations of temporal logics on trace systems.
  508. -------------------------------------------------------------------------
  509. 15:00-15:20     Coffee Break
  510. -------------------------------------------------------------------------
  511. _S_e_s_s_i_o_n_ _6_B: AUTOMATA THEORY AND LOGIC
  512. Chair: Patrice Enjalbert (Caen)
  513.     (Friday Early Afternoon, 15:20-16:35)
  514.  
  515. 15:20    C. Choffrut, L. Guerra (Paris):
  516.     On the logical definability of some rational trace language.
  517. 15:45    R. Gilleron, S. Tison, M. Tommasi (Lille):
  518.     Solving systems of set constraints using tree automata.
  519. 16:10    D. Lugiez, J.L. Moysset (Nancy):
  520.     Complement problems and tree automata in AC-like theories.
  521. -------------------------------------------------------------------------
  522. 17:30-23:00     Guided tour of the "Residenz", chamber concert, wine
  523.         tasting party
  524. -------------------------------------------------------------------------
  525. _G_I                                = 8 =                                 _a_f_c_e_t
  526.  
  527. _G_I                            STACS '93                               _a_f_c_e_t
  528.  
  529.  
  530.               Saturday, February 27
  531.               =====================
  532.  
  533. 8:30-9:15    Invited Lecture: Laszlo Babai (Chicago):
  534.         Transparent Proofs
  535. -------------------------------------------------------------------------
  536. 9:15-9:45    Coffee Break
  537. -------------------------------------------------------------------------
  538. _B_a_l_t_h_a_s_a_r_-_N_e_u_m_a_n_n_H-_HS_a_a_l  (A-Sessions)
  539.  
  540. _S_e_s_s_i_o_n_ _7_A: CIRCUIT COMPLEXITY
  541.     (Saturday Morning, 9:45-11:50)
  542. Chair: Andrzej Salwicki (Pau)
  543.  
  544. 9:45    Z.-L. Zhang, D.A. Mix Barrington (Amherts), J. Tarui
  545.     (Warwick):
  546.     Computing symmetric functions with AND/OR circuits and a
  547.     single majority gate.
  548. 10:10    A. Maciel, D. Therien (Montreal):
  549.     Threshold circuits for iterated multiplication: using AC0
  550.     for free.
  551. 10:35    M. Beaudry (Sherbrooke), P. McKenzie, P. Peladeau (Montreal):
  552.     Circuits with monoidal gates.
  553. 11:00    S. Istrail, D. Zivkovic (Middleton):
  554.     A non probabilistic switching lemma for the Sipser function.
  555. 11:25    J. Gergov, C. Meinel (Trier):
  556.     Frontiers of feasible and probabilistic feasible boolean
  557.     manipulation with branching programs.
  558. -------------------------------------------------------------------------
  559. 11:50-13:20     Lunch
  560. -------------------------------------------------------------------------
  561. _S_e_s_s_i_o_n_ _8_A: NON-CLASSICAL COMPLEXITY
  562.     (Saturday Early Afternoon, 13:20-14:35)
  563. Chair: Juergen Albert (Wuerzburg)
  564.  
  565. 13:20    S. Sairam, J.S. Vitter, R. Tamassia (Providence):
  566.     A complexity theoretic approach to incremental computation.
  567. 13:45    R. Reischuk, C. Schindelhauer (Darmstadt):
  568.     Precise average case complexity.
  569. 14:10    P.B. Miltersen (Aarhus):
  570.     The bit probe complexity measure revisited.
  571. -------------------------------------------------------------------------
  572.  
  573.  
  574.  
  575.  
  576.  
  577.  
  578.  
  579.  
  580.  
  581.  
  582.  
  583.  
  584.  
  585.  
  586.  
  587. _G_I                                = 9 =                                 _a_f_c_e_t
  588.  
  589. _G_I                            STACS '93                               _a_f_c_e_t
  590.  
  591.  
  592.  
  593.  
  594.  
  595. _T_i_e_p_o_l_o_-_S_a_a_l  (B-Sessions)
  596. _S_e_s_s_i_o_n 2: The Chair is to be elected                      
  597. -------------------------------------------------------------------------
  598. _S_e_s_s_i_o_n_ _7_B: w-AUTOMATA
  599. Chair: Aldo de Luca (Rome)
  600.     (Saturday Morning, 13:20-15:00)
  601.  
  602. 9:45    O. Maler (Rennes), L. Staiger (Siegen):
  603.     On syntactic congruences for w-languages.
  604. 10:10    S. Varricchio (L'Aquila):
  605.     A polynomial time algorithm for the equivalence of two
  606.     morphisms on w-regular languages.
  607. 10:35    T. Wilke (Kiel):
  608.     Locally threshold testable languages of infinite words.
  609. 11:00    V. Diekert, A. Muscholl (Stuttgart):
  610.     Deterministic asynchronous automata for infinite traces.
  611. 11:25    L. Staiger (Siegen):
  612.     Recursive automata on infinite words.
  613. -------------------------------------------------------------------------
  614. 11:50-13:20     Lunch
  615. -------------------------------------------------------------------------
  616. _S_e_s_s_i_o_n_ _8_B: LEARNING THEORY AND CRYPTOGRAPHY
  617.     (Saturday Early Afternoon, 13:20-14:35)
  618. Chair: Eli Shamir (Jerusalem)
  619.  
  620. 13:20    G. Baliga, J. Case, S. Jain (Newark):
  621.     Language learning with some negative information.
  622. 13:45    S. Lange (Leipzig), T. Zeugmann (Darmstadt):
  623.     Language learning with a bounded number of mind changes.
  624. 14:10    C. Blundo, A. De Santis, U. Vaccaro (Salerno):
  625.     Efficient sharing of many secrets.
  626. -------------------------------------------------------------------------
  627. 14:35    End of STACS '93
  628. -------------------------------------------------------------------------
  629.  
  630.  
  631.  
  632.  
  633.  
  634. _A_c_k_n_o_w_l_e__d_g_e_m_e_n_t_s
  635.  
  636. We wish to thank all sponsors for their support. We gratefully
  637. acknowledge the help of Vogel Verlag Wuerzburg for printing the "call
  638. for papers", the poster and the program free of charge.
  639.  
  640.              Sponsored by
  641.            Deutsche Forschungsgemeinschaft
  642.     Bayerische Julius-Maximilians-Universitaet Wuerzburg
  643.              Vogel Verlag
  644.                IBM Deutschland
  645.          Fremdenverkehrsamt Wuerzburg
  646.          Universitaetsbund  Wuerzburg
  647.             Castell Bank Wuerzburg
  648.          Keupp, Faber-Castell, Staedtler-Mars
  649.  
  650. _G_I                                    = 10 =                                _a_f_c_e_t
  651.