LATIN '95: Theoretical Informatics: Second Latin American Symposium, Valparaiso, Chile, April 3 - 7, 1995. Proceedings

Front Cover
Ricardo Baeza-Yates, Eric Goles, Patricio V. Poblete
Springer Science & Business Media, Mar 20, 1995 - Computers - 530 pages
This volume constitutes the proceedings of the Second International Symposium, Latin American Theoretical Informatics, LATIN '95, held in Valparaiso, Chile in April 1995.
The LATIN symposia are intended to be comprehensive events on the theory of computing; they provide a high-level forum for theoretical computer science research in Latin America and facilitate a strong and healthy interaction with the international community. The 38 papers presented in this volume were carefully selected from 68 submissions. Despite the intended broad coverage there are quite a number of papers devoted to computational graph theory; other topics strongly represented are complexity, automata theory, networks, symbolic computation, formal languages, data structures, and pattern matching.
 

Contents

Visibility Graphs of 2Spiral Poygons
1
Random Generation of Colored Trees
16
Space Filling Curves and Their Use in the Design of Geometric Data Structures
36
Tight Bounds for Finding Degrees from the Adjacency Matrix
49
Lower Bounds for Modular Counting by Circuits with Modular Gates
60
On the Relation Between BDDs and FDDs
72
On dynamical properties of generalized toggle automata
84
Free Shuffle Algebras in Language Varieties Extended Abstract
99
On the Approximability of some Maximum Spanning Tree Problems
300
Gauss periods and fast exponentiation in finite fields
311
Unbounded Search and Recursive Graph Problems
323
On the complexity of computing the greatest common divisor of several univariate polynomials
332
State Complexity of SBTA Languages
346
Pushdown Automata with Bounded Nondeterminism and Bounded Ambiguity
358
Multihead twoway probabilistic finite automata
371
A New Frontier Between a Decidable Halting Problem and Universality
386

Lower Bounds for the Matrix Chain Ordering Problem
112
OffLine Electronic Cash Based on SecretKey Certificates
131
Recognizable Sets of Numbers in Nonstandard Bases
167
On Weak Growing ContextSensitive Grammars
180
Logic of Plotkin Continuous Domain
195
Probabilistic Recurrence Relations Revisited
207
On LinearTime AlphabetIndependent 2Dimensional Pattern Matching
220
Reversible Cellular Automaton Able to Simulate Any Other Reversible One Using Partitioning Automata
230
Nearest Neighbour Graph Realizability is NPhard
245
LinearTime Algorithms for Parametric Minimum Spanning Tree Problems on Planar Graphs
257
Paging more than one page
272
On EdgeColouring Indifference Graphs
286
Cyclic Automata Networks on Finite Graphs
398
Multiple Alignment of Biological Sequences with Gap Flexibility
411
Lower Bounds for the Modular Communication Complexity of Various Graph Accessibility Problems
427
On monotonous oracle machines
436
On Using Learning Automata for Fast Graph Partitioning
449
Solution of a Problem of Yekutieli and Mandelbrot
461
A Rewrite Approach for Constraint Logic Programming
469
Simulations Between Cellular Automata on Cayley Graphs
483
A Temporal Logic for RealTime PartialOrdering with Named Transactions
494
A New Approach for Routing in Arrangement Graphs and its Performance Evaluation
509
Author Index
Copyright

Common terms and phrases

Bibliographic information