From is Thu Jan 16 20:53 BRD 1992 LATIN'92 Latin American Theoretical INformatics Sao Paulo, April 6-10, 1992 Conference Auditorium of the University of Sao Paulo PRELIMINARY PROGRAM (*=invited speaker) Monday, April 6 9:00-9:30 Opening ceremony 9:30-10:45 Session 1: Claudio L. Lucchesi (Campinas) 9:30 Vaughan Pratt* (Stanford) Arithmetic + Logic + Geometry = Concurrency 10:20 Esther Jennings (Lund) and Lenka Motyckova (Brno Inst. of Tech.) A distributed algorithm for finding all maximal cliques in a network graph 10:45-11:15 Coffee break 11:15-12:30 Session 2: Arnaldo V. Moura (IBM, Rio de Janeiro) 11:15 Paola Alimonti (Roma `La Sapienza'), Esteban Feuerstein (Roma `La Sapienza' and ESLAI, Buenos Aires) and Umberto Nanni (L'Aquila) Linear time algorithms for liveness and boundedness in conflict-free Petri nets 11:40 Anne Bruggemann-Klein (Freiburg) Regular expressions into finite automata 12:05 F. Bossut and B. Warin (Lille) Automata and pattern matching in planar directed acyclic graphs 12:30-14:30 Lunch break 14:30-15:45 Session 3: Ricardo Baeza-Yates (U. Chile) 14:30 Gene Myers* (U. of Arizona) Approximate matching of network expressions with spacers 15:20 Veronique Bruyere (Mons-Hainaut) Automata and codes with bounded deciphering delay 15:45-16:15 Coffee break 16:15-17:30 Session 4: Eric Goles (U. Chile) 16:15 Alistair Sinclair (Edinburgh) Improved bounds for mixing rates of Markov chains and multicommodity flow 16:40 W. Fernandez de la Vega (Paris XI), V.Th. Paschos (Paris I and XI) and R. Saad (Paris XI) Average case analysis of a greedy algorithm for the minimum hitting set problem 17:05 Felipe Cucker (Politecnica de Catalunya) and Francesc Rossello (Illes Balears) On the complexity of some problems for the Blum, Shub & Smale model Tuesday, April 7 9:30-10:45 Session 5: Joel Seiferas (Rochester) 9:30 Manuel Blum* (Berkeley) Universal statistical tests 10:20 William I. Gasarch (Maryland) and Katia S. Guimaraes (Maryland and Recife) On the number of components of a recursive graph 10:45-11:15 Coffee break 11:15-12:30 Session 6: Walter Cunto (IBM, Caracas) 11:15 Joseph Gil (British Columbia) and Yossi Matias (Maryland and Tel Aviv) Leaders election without conflict resolution rules---fast and efficient randomized simulations among CRCW PRAMs 11:40 Said Bettayeb (Louisiana State), Bin Cong, Mike Girou and I. Hal Sudborough (U. of Texas at Dallas) Simulating permutation networks on hypercubes 12:05 Afonso G. Ferreira (Sao Paulo and Lyon) and Siang W. Song (Sao Paulo) Achieving optimality for gate matrix layout and PLA folding: a graph theoretic approach 12:30-14:30 Lunch break 14:30-15:45 Session 7: Juhani Karhumaki (Turku) 14:30 Kosaburo Hashiguchi* (Toyohashi) The double reconstruction conjectures about colored hypergraphs and colored directed graphs 15:20 Jacques Sakarovitch (Paris VI and Blaise Pascal) The "last" decision problem for rational trace languages 15:45-16:15 Coffee break 16:15-17:30 Session 8: Jayme Szwarcfiter (UFRJ, Rio de Janeiro) 16:15 Oscar Garrido (Lund), Stefan Jarominek (Warsaw), Andrzej Lingas (Lund), and Wojciech Rytter (Warsaw) A simple randomized parallel algorithm for maximal f-matchings 16:40 Oscar Porto (PUC, Rio de Janeiro) Even induced cycles in planar graphs 17:05 X. Zhou, S. Nakano, H. Suzuki and T. Nishizeki (Tohoku) An efficient algorithm for edge-coloring series-parallel multigraphs Wednesday, April 8 9:00-10:15 Session 9: Imre Simon (Sao Paulo) 9:00 Aldo de Luca* (Roma `La Sapienza') and Stefano Varricchio (L'Aquila) Some regularity conditions based on well quasi-orders 9:50 Alair Pereira do Lago (Sao Paulo) On the Burnside semigroups x^n=x^{n+m} 10:15-10:45 Coffee break 10:45-12:00 Session 10: Martin Grotschel (Berlin) 10:45 Daniel D. Sleator* (Carnegie Mellon) Data structures and terminating Petri nets 11:35 M. Bern (Xerox, Palo Alto), Herbert Edelsbrunner (U. of Illinois at Urbana), D. Eppstein (U. of California at Irvine), S. Mitchell (Cornell) and T.S. Tan (U. of Illinois at Urbana) Edge-insertion for optimal triangulations 12:00-18:00 Excursion, barbecue or `feijoada' (details to be announced later) Thursday, April 9 9:30-10:45 Session 11: Jeff Shallit (Waterloo) 9:30 Jean-Paul Allouche* (Bordeaux I) q-Regular sequences and other generalizations of q-automatic sequences 10:20 Christiane Frougny (Paris VIII and Blaise Pascal) How to write integers in non-integer bases 10:45-11:15 Coffee break 11:15-12:30 Session 12: Paulo Feofiloff (Sao Paulo) 11:15 Joachim Hollman (Royal Inst. of Tech., Stockholm) On the computation of the Hilbert series 11:40 Mark Giesbrecht (Toronto) Factoring in skew-polynomial rings 12:05 Jaime Gutierrez and Tomas Recio (Cantabria) Rational function decomposition and Groebner bases in the parameterization of plane curves 12:30-14:30 Lunch break 14:30-15:45 Session 13: Siang W. Song (Sao Paulo) 14:30 Michel Cosnard*, Pascal Koiran and Helene Paugam-Moisy (Lyon) Complexity issues in neural network computations 15:20 Eric Goles and Marcos A. Kiwi (U. Chile) Dynamics of sand-piles games on graphs 15:45-16:15 Coffee break 16:15-17:30 Session 14: Jozef Gruska (Bratislava and Hamburg) 16:15 Rolf Niedermeier and Peter Rossmanith (Munchen) Unambiguous simulations of auxiliary pushdown automata and circuits 16:40 Nami Kobayashi (Sao Paulo) Properties of recognizable M-subsets of a free monoid 17:05 Andreas Weber (Frankfurt) Decomposing a k-valued transducer into k unambiguous ones 19:00 Symposium Dinner Friday, April 10 9:00-10:15 Session 15: William T. Trotter (Bellcore) 9:00 Arjen K. Lenstra* (Bellcore) Massively parallel computing and factoring 9:50 Svante Carlsson (Lulea) and Jingsen Chen (Lund) Parallel complexity of heaps and min-max heaps 10:15-10:45 Coffee break 10:45-12:00 Session 16: Joachim von zur Gathen (Toronto) 10:45 Erich Kaltofen* (Rensselaer Polytechnic) A decade of research on polynomial factorization 11:35 Denis Therien (McGill) Circuits constructed with MOD_q gates cannot compute AND in sublinear size 12:00-14:00 Lunch break 14:00-15:15 Session 17: Dominique Perrin (Paris VII and Blaise Pascal) 14:00 Jean-Eric Pin* (Bull Research and Development) On reversible automata 14:50 David A. Mix Barrington (U. of Massachusetts at Amherst) and Howard Straubing (Boston College) Complex polynomials and circuit lower bounds for modular counting 15:15-15:45 Coffee break 15:45-17:00 Session 18: Janos Simon (Chicago) 15:45 Ulrich Hertrampf (Wuerzburg) Locally definable acceptance types---the three-valued case 16:10 Jose D.P. Rolim (Geneve) On the density and core of the complexity classes 16:35 Daniele Beauquier (Paris VI and Blaise Pascal), Michel Latteux and Karine Slowinski (Lille) A decidability result about convex polyominoes ______________________________________________________________________ ******** PLEASE POST A COPY OF THIS FORM ******** NB A TeX source file for the program and the registration form for LATIN'92 may be obtained by sending an e-mail message to asking for a copy. Do not hesitate to get in touch with us!