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
<latin92@ime.usp.br> asking for a copy. Do not hesitate
to get in touch with us!