LATIN'95: Latin American Theoretical INformatics II South American Workshop on String Processing PRELIMINARY CALL FOR PARTICIPATION April 3--7, 1995 Univ. T'ecnica Federico Santa Mar'ia Valpara'iso, CHILE Welcome to Chile! The Second International Symposium of Latin American Theoretical Informatics, LATIN'95 is to take place in Valpara'iso, Chile, a legendary port on the Pacific Ocean. This conference, first held at Sao Paulo, Brazil in 1992, has become the main international conference on the region in the field of theoretical computer science. This year the conference is organized by the University of Chile at Santiago and the Univ. T'ecnica Federico Santa Mar'ia (UTFSM) at Valpara'iso/Vi~na del Mar, with the cooperation of the P. Univ. Cat'olica at Santiago. In addition, the Second South American Workshop on String Processing will take place jointly with LATIN'95. This workshop started on Belo Horizonte, Brazil, on 1993, having as main goal to be a place of encounter for researchers on text algorithms and computational biology. This year is organized by the University of Chile. Other workshops for Friday, April 7 are being planned. Plan now to attend this unique event! Location. Valpara'iso is located 110 kms. west of Santiago, the capital city of Chile. Close to Valpara'isois Vi~na del Mar, one of the main beach resorts ofChile. Together, they have more than a million inhabitants, being the third largest urban area in the country. Valpara'iso is a picturesque city with houses and cable cars climbing the hills that surround the bay. Valpara'iso hosts the National Congress and is one of the two busiest ports in Chile. On the other hand, Vi~na del Mar, ``the Garden City'', is one of the main turistic attractions in Chile with nice beaches, green areas, a casino, hotels and many restaurants. Conference Information Conference Site. The conference will be held at the Universidad T'ecnica Federico Santa Mar'ia (UTFSM), which is located in Valpara'iso beside the sea on the boundary with Vi~na del Mar. The address is Avda. Espa~na 1680, and the conference room, Auditorio, is located beside the main building of the university (Edificio A). The hotels offered are located in Vi~na del Mar within a few minutes by bus or taxi to the conference location. Registration. The registration office will open Monday, April 3 at 9AM giving the attendees enough time to locate the conference site before the conference starts at noon. The normal registration fee allows to attend both conferences and the social events, but includes only LATIN'95 proceedings (published by Lecture Notes in Computer Science). Members of institutional supporters have a discounted fee. Certified students have a special fee which does not include the proceedings. If you want extra copies of LATIN'95 proceedings or copies of the workshop proceedings, they should be ordered in advance as the number of them is limited. Scholarships. A limited number of scholarships covering the registration fee, local expenses and partial travel will be provided by UNESCO and available to Latin American students presenting a paper. Scholarships for student registration fees and partial fees for Chilean researchers will be available from CONICYT and Fundaci'on Andes. In both cases, requests should be made tothe conference chairs through e-mail (latin95@dcc.uchile.cl) justifying the need for the scholarship and certifying in the registration form your student condition. Instructions for Authors. Every presentation should take at most 20 minutes, plus 5 minutes for questions. If you need special equipment in addition to overhead projectors please contact the local secretary. Upon your arrival please contact the chair of your technical session to let him know which of the authors will present the paper. The Workshop on String Processing has an open problem session. If you want to participate in it giving a 10 minute talk, contact Ricardo Baeza-Yates via e-mail (rbaeza@dcc.uchile.cl). Social Program. The technical program is enhanced by a conference banquet on Thursday night. We are also planning a tour for Wednesday afternoon, possibly a city tour of Valpara'iso. All these events are included in the regular registration fee. Conference lunches will be provided inside campus at US$5 per person (approx.). Local Information Currency. The local currency is the peso ($). The exchange rate is, approximately, US$1 = $400. US dollars can be exchanged freely at banks and money exchange offices. Weather in April. April is early Autumm in Vi~na del Mar. Temperatures range from a low of 5C to a high of 25C, with an average of 15C. You should come prepared for an occasional shower or windy day. Transportation. The main entrance point to Chile is Santiago, the capital. Santiago can be reached by most major airlines, and its international airport boasts a brand new terminal for international flights. >From there, there are flights to Vi~na del Mar on one of the Chilean airlines, Ladeco, which takes 10 minutes (one per day). Also, Lan Chile, the other main Chilean airline offers buses that go directly to Vi~na del Mar atno cost for their passengers. Otherwise, from any of the two suburban bus stations located between the airport and downtown Santiago, you can take a bus which will take you in less than two hours to Vi~na del Mar for US$5 (round trip) or US$3 (one way). Bus service from the airport todowntown Santiago costs US$2. A shared minivan ride to any place in the city costs US$7, and a taxi ride to downtown approximately US$23 or less. To get around in Valpara'isoor Vi~na del Mar you can walk or use city transportation. Taxis are also abundant and at a reasonable price. Travel Agencies and Tours. The official travel agent for the conference is Turismo Bancard . Contact them for pre- and post-conference tours, special accommodation arrangements and/or local air tickets. To some places itcould be cheaper to buy a ticket in Chile rather than in your country of origin (that is the case for most European countries). The same is true for local flights. During the conference a local travel agency (see below) will offer city tours for at most US$20 (Valpara'iso, Vi~na del Mar, or both), as well as other local tours with prices ranging from US$25 to US$40 and taking 8 hours (Isla Negra - in the coast to the south - where the famous house of Pablo Neruda is located; Neruda is one of the Chilean Nobel Prize winners in literature; Zapallar - an old and traditional beach to the north; Olmu'e - a trip to the countryside where you can see typical traditions.) Turismo Bancard Turismo Nuevo Centro Attn: Silvia Araya Attn: Maria Isabel Sandoval Avda. Suecia 0150 Avda. Libertad 17 - Local 4 Santiago, Chile Vi~na del Mar Tel/Fax: (+56 2) 233-9660 (please ask Fax: (+56 32) 971539, for fax tone) Tel: (+56-32) 973331 E-mail: bancard@dcc.uchile.cl Accommodation. Special fares have been arranged at three hotels in Vi~na del Marwith different levels of comfort and all located in the downtown area near by the sea. Foreigners paying for their hotel accommodations inUS dollars (cash or credit card) are exempt from the 18% sales tax. Reservations should be made directly to the hotels mentioning LATIN'95. Special arrangements can be requested for inexpensive accommodation for students through the local arrangements secretary (approximate cost of US$6 per day in shared rooms at the guest house of the Physical Education department of the UTFSM.) o Hotel San Mart'in (* * * *) Rates: US$50 (single), US$70 (double), rates include breakfast. Address: Av. San Mart'in 667. Tel.: +56-32-689-191. Fax: +56-32-689-195. o Hotel Castell'on (* * *) Rates: US$45 (single or double), US$55 (triple), rates include breakfast. Address: Viana 135. Tel.: +56-32-687-688. Fax: +56-32-977-019. o Hotel Alc'antara (* * *) Rates: US$35 (single), US$45 (double), US$55 (triple), rates include breakfast. Address: Viana 575. Tel.: +56-32-680-986. Fax: +56-32-680-202. Additional Information. Further information can be obtained from: LATIN'95 Symposium Tel: (+56 2) 689 2736, Fax: (+56 2) 689 5531 Universidad de Chile E-mail: latin95@dcc.uchile.cl Blanco Encalada 2120 Gopher: gopher.dcc.uchile.cl Santiago, Chile WWW: http://www.dcc.uchile.cl/ For further information on local arrangements (student accommodation, special presentation requirements, etc.) contact: LATIN'95 Symposium Tel: (+56 32) 626 364, x. 431 Mar'ia Isabel Ovando E-mail: latin95@inf.utfsm.cl UTFSM, Avda. Espa~na 1680, Fax: (+56 32) 625-217 Casilla 110-V, Valpara'iso, Chile Organizing Committee Ricardo Baeza-Yates, Univ. de Chile (Co-chair) Leopoldo Bertossi, P. Univ. Cat'olica de Chile Horst von Brand, Univ. Tec. Federico Santa Mar'ia Alvaro Campos, P. Univ. Cat'olica de Chile Eric Goles, Univ. de Chile (Co-chair) R'aul Monge, Univ. Tec. Federico Santa Mar'ia Patricio Poblete, U. de Chile Imre Simon, Univ. de S~ao Paulo Marcello Visconti, Univ. Tec. Federico Santa Mar'ia Program Committee Ricardo Baeza-Yates (U. of Chile, Co-chair) Arnaldo Moura (IBM, Brazil) Leopoldo Bertossi (Catholic Univ., Chile) J.Ian Munro (Waterloo, Canada) Svante Carlsson (Lulea, Sweden) Gene Myers (Arizona, USA) Walter Cunto (IBM, Venezuela) Maurice Nivat (Paris, France) Josep Diaz (Barcelona, Spain) Andrew Odlyzko (Bell Labs, USA) Volker Diekert (Stuttgart, Germany) Ren'e Peralta (Wisconsin, USA) Vladimir Estivill-Castro (LANIA, Mexico) Dominique Perrin (Paris, France) Joachim von zur Gathen (Toronto, Canada) Patricio Poblete (U. of Chile) Eric Goles (U. of Chile, Co-chair) Gregory Rawlins (Indiana, USA) Gast'on Gonnet (ETH, Switzerland) Antonio Restivo (Palermo, Italy) Jozef Gruska (Bratislava, Slovakia) Grzegorz Rozenberg (Leiden, Netherlands ) Jan van Leeuwen (Utrecht, Netherlands) Isaac Scherson (Irvine, USA) Tom Leighton (MIT, USA) Imre Simon (S~ao Paulo, Brazil) Andrzej Lingas (Lund, Sweden) Godfried Toussaint (McGill, Canada) Laszlo Lovasz (Yale, USA) Nivio Ziviani (Minas Gerais, Brazil) Sponsors Supporters AFP PROVIDA ACM/SIGACT CONICYT Chile CENTRO LATINOAMERICANO DE ESTUDIOS EN INFORMATICA (CLEI) FUNDACION ANDES EUROPEAN ASSOCIATION FOR THEORETICAL IFIP SGFCS COMPUTER SCIENCE (EATCS) RED IBEROAMERICANA DEPTO. DE CIENCIAS DE LA COMPUTACION DE TECNOLOGIA DE DEPTO. DE INGENIERIA MATEMATICA SOFTWARE (RITOS - CYTED) U. DE CHILE UNESCO DEPTO. DE INGENIERIA INFORMATICA REGIONAL OFFICE FOR UNIV. TECNICA FEDERICO SANTA MARIA SCIENCE AND TECHNOLOGY _____ DEPTO. DE CIENCIAS DE LA COMPUTACION ____ __ P. UNIV. CATOLICA DE CHILE ______ _______ ____________________ IEEE TCMFC _______________ _________________ SOCIEDAD CHILENA DE ________________ CIENCIA DE LA COMPUTACI'ON (SCCC) ______________ ____________ SOCIEDAD BRASILEIRA DE __________ COMPUTACAO (SBC) ________ _______ _____ _____ ___ ___ ___ Conference Program Monday, April 3 LATIN'95 09:00-11:30 Registration 11:30-12:00 Break 12:00-13:00 Invited Talk o NC Approximations, Josep Diaz - Spain 13:00-14:30 Lunch 14:30-16:10 Complexity Theory (Chair: Josep Diaz) o On the Approximability of some Maximum Spanning Tree Problems, Giulia Galbiati, F. Maffioli, A. Morzenti - Italy o Nearest Neighbor Graph Realizability is NP-hard, Peter Eades, Sue Whitesides - Australia & Canada o Unbounded Search and Recursive Graph Problems, William I. Gasarch, Katia S. Guimaraes - USA & Brazil o Cyclic Automata Networks on Finite Graphs, Eric Goles, Martin Matamala - Chile 16:10-16:30 Break 16:30-17:45 Cellular Automata (Chair: Jozef Gruska) o On dynamical properties of generalized toggle automata, F. Blanchard, Alejandro Maas - Chile o Simulations between cellular automata on Cayley graphs, Zsuzsanna Roka - France o Reversible Cellular automaton Able to Simulate Any Other Reversible One Using Partitioning Automata, Jerome Durand-Lose - Chile Tuesday, April 4 LATIN'95 09:00-10:00 Invited Talk o Load Balancing in Distributed Systems, Isaac Scherson - USA 10:10-11:00 Networks (Chair: Isaac Scherson) o Lower Bounds for the Modular Communication Complexity of Various Graph Accessibility Problems, Christoph Meinel, Stephan Waack - Germany o A New approach for Routing in arrangement Graphs and its Performance Evaluation, Hiroyuki Ebara, Hideo Nakanoo, Peter M. Yamakawa - Japan 11:10-11:30 Break 11:30-13:10 Symbolic Computation (Chair: Walter Cunto) o Gauss Periods and Primitive Normal Bases in Finite Fields, Shuhong Gao, Joachim von zur Gathen, Daniel Panario - Canada o On the complexity of computing the greatest common divisor of several univariate polynomials, Laureano Gonzalez-Vega - Spain o (Probabilistic) Recurrence Relations Revisited, Shiva Chaudhuri, Devdatt Dubhashi - Germany o Recognizable Set of Numbers in Nonstandard Bases, Veronique Bruyere, Georges Hansel - Belgium & France 13:10-14:30 Lunch 14:30-16:10 Automata Theory (Chair: Dominique Perrin) o Multihead two-way probabilistic finite automata, Ioan I. Macarie - USA o Pushdown Automata with Bounded Nondeterminism and Bounded Ambiguity, Christian Herzog - Germany o Non-erasing Turing machines: a new frontier between a decidable halting problem and universality, Maurice Margenstern - France o On monotonous oracle machines, M. Mundhenk - Germany 16:10-16:30 Break 16:30-17:45 Formal Languages (Chair: Volkert Diekert) o State Complexity of Systolic Binary Tree Automata Languages, Jozef Gruska, Angelo Monti, Margherita Napoli, Domenico Parente - Slovakia & Italy o Free Shuffe Algebras in Language Varieties, Stephen L. Bloom, Zoltan Esik - USA & Hungary o On Weak Growing Context-Sensitive Grammars, Gerhard Buntrock, Gundula Niemann - Germany Wednesday, April 5 LATIN'95 09:00-10:00 Invited Talk o Fast, Space Efficient Data Structures, J.Ian Munro - Canada 10:10-11:00 Data Structures (Chair: J.Ian Munro) o Space Filling curves and Their Use in the Design of Geometric Data Structures, Tetsuo Asano, Desh Ranjan, Thomas Roos, Emo Welzl, Peter Widmayer - Switzerland o On the Relation Between BDDs and FDDs, Bernd Becker, Rolf Drechsler, Ralph Werchner - Germany 11:10-11:30 Break 11:30-13:10 Graph Problems (Chair: Vladimir Estivill-Castro) o Graph Partitioning Using Learning Automata, B. John Oommen, Edward V. de St. Croix - Canada o Linear-Time Algorithms for Parametric Minimum Spanning Tree Problems on Planar Graphs, David Fernandez-Baca, Giora Slutzki, USA o On Edge-Colouring Indifference Graphs, Celina Herrera de Figuereido, Joao Meidanis, Celia Picinin de Mello - Brazil o Visibility Graphs and Oriented Matroids, James Abello, Krishna Kumar - USA 13:10-14:30 Lunch 14:30-18:30 Conference Excursion Thursday, April 6 LATIN'95 09:00-10:00 Invited Talk o The String Statistics Problem, Alberto Apostolico - Italy & USA 10:10-11:00 Pattern Matching (Chair: Gene Myers) o On Linear-Time Alphabet-Independent 2-Dimensional Pattern Matching, Maxime Crochemore, Wojciech Rytter - France & Poland o Multiple Alignment of DNA Sequences with Gap Flexibility, Joao Meidanis, Joao C. Setubal - Brazil 11:10-11:30 Break 11:30-13:10 Algorithms (Chair: Nivio Ziviani) o Paging more than one page, Esteban Feuerstein - Italy o Tight Bounds for Finding Degrees from the Adjacency Matrix, R. Balasubramanian, Venkatesh Raman, G. Srinivasaraghavan - India o On Lower Bounds for the Matrix Chain Ordering Problem, Phillip G. Bradford, Venkatesh Choppella, Gregory J. E. Rawlins - Germany & USA o Random Generation of Colored Trees, L. Alonso, R. Schott - France 13:10-14:30 Lunch 14:30-15:45 Miscelaneous (Chair: Patricio Poblete) o Off-Line Digital Cash, Stefan Brands - Nederlands o Solution of a problem of Yecutieli and Mandelbrot, Helmut Prodinger - Austria o Lower Bounds for Modular Counting by Circuits with Modular Gates, David Mix Barrington, Howard Straubing - USA 15:45-16:00 Break 16:00-17:15 Logic (Chair: Leopoldo Bertossi) o A Rewrite Approach of Constraint Logic Programming, Gilles Richard, Frederic Saubion - France o A Temporal Logic for Real-Time Partial-Ordering with Named Transactions, Farn Wang - Rep. of China o Logic of Plotkin Continuous Domain, Benjamin Callejas Bedregal, Benedito Melo Acioly - Brazil 17:20-17:45 Closure of LATIN'95: Announcement for LATIN'97? 20:00-open Conference & Workshops Banquet at Hotel San Mart'in Friday, April 7 Workshop on String Processing 10:00-11:00 Invited Talk o Probability Distributions for Sequence Alignment Scores Mike Waterman - USA 11:00-11:30 Break 11:30-13:10 Text Searching (Chair: Alberto Apostolico) o From Partial to Full Inverted Lists for Text Searching, Eduardo F. Barbosa, Nivio Ziviani - Brazil o Two-Dimensional Pattern Matching, Fei Shi - Switzerland o Optimized Indirect Binary Search and Text Retrieval, E. Barbosa, G. Navarro, C. Perleberg, R. Baeza-Yates, N. Ziviani, Brazil & Chile 13:30-14:30 Lunch 14:30-16:40 Approximate Pattern Matching (Chair: Mike Waterman) o Approximate comparison of sequences with transpositions, Liisa Raiha - Finland o Block Edit Models for Approximate String Matching, Daniel Lopresti, Andrew Tomkins - USA o Aproximately Matching Context-Free Languages, Gene Myers - USA o Searching For Repeated Words in a Text Allowing For Mismatches and Gaps, Marie-France Sagot, Vincent Escalier, Alain Viari - France o Distance and Similarity in the Presence of Nonincreasing-Gap- Weighting Functions, Joao Meidanis - Brazil 16:40-17:00 Break 17:00-17:45 Open Problem Session (Chair: Maxime Crochemore) ============================================================================= II SYMPOSIUM ON LATINAMERICAN THEORETICAL INFORMATICS II South American Workshop on String Processing April 3-7, 1995 Univ. T'ecnica Federico Santa Mar'ia Valpara'iso, CHILE REGISTRATION FORM Please type or print clearly. Last Name:___________ First Name:____________ Affiliation:________________________________________________________________ Mailing Address:____________________________________________________________ ____________________________________________________________ ____________________________________________________________ Tel:__________________________________ Fax:_________________________________ E-mail:_____________________________________________________________________ Registration Fees(Please circle applicable fees): Before January 31st After January 31st Regular registration fee US$160 US$200 ACM/IEEE/SCCC/SBC Members US$140 US$170 Student registration fee US$40 US$50 Extra LATIN'95 proceedings US$35 US$40 Workshop proceedings US$15 US$20 Extra Banquet Ticket US$25 US$25 Total amount enclosed: US$:________ (or equivalent in Chilean pesos at the day of payment) Tobe allowed to pay the reduced registration fee, this form should be signed by the student's advisor: Advisor's signature:________________________________________________________ Advisor's name:_____________________________________________________________ Payment should be made by check or money order in US dollars payable to U.de Chile/LATIN'95, or by credit card. If paying by credit card, please specify the following: 2 Visa 2 Mastercard 2 Diners Club Credit Card number:_________________________________ Exp. Date:____________ Cardholder's name:__________________________________________________________ Signature:__________________________________________________________________ If paying by check or money order, please mail this registration form, with payment enclosed, to the following address. If paying by credit card, this registration form may be mailed to the same address, or sent by fax. LATIN'95 Secretariat U. de Chile, D.C.C. Avda. Blanco Encalada 2120, Of. 106, Fax: +56-2-689-5531