James Abello, Krishna Kumar (auth.), Ricardo Baeza-Yates, Eric Goles, Patricio V. Poblete (eds.)3540591753, 9783540591757
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.
Table of contents :
Visibility graphs of 2-spiral polygons (Extended abstract)….Pages 1-15
Random generation of colored trees….Pages 16-35
Space filling curves and their use in the design of geometric data structures….Pages 36-48
Tight bounds for finding degrees from the adjacency matrix….Pages 49-59
Lower bounds for modular counting by circuits with modular gates….Pages 60-71
On the relation between BDDs and FDDs….Pages 72-83
On dynamical properties of generalized toggle automata….Pages 84-98
Free shuffle algebras in language varieties extended abstract….Pages 99-111
Lower bounds for the matrix chain ordering problem….Pages 112-130
Off-line electronic cash based on secret-key certificates….Pages 131-166
Recognizable sets of numbers in nonstandard bases….Pages 167-179
On weak growing context-sensitive grammars….Pages 180-194
Logic of plotkin continuous domain….Pages 195-206
(Probabilistic) recurrence relations revisited….Pages 207-219
On linear-time alphabet-independent 2-dimensional pattern matching….Pages 220-229
Reversible cellular automaton able to simulate any other reversible one using partitioning automata….Pages 230-244
Nearest neighbour graph realizability is NP-hard….Pages 245-256
Linear-time algorithms for parametric minimum spanning tree problems on planar graphs….Pages 257-271
Paging more than one page….Pages 272-285
On edge-colouring indifference graphs….Pages 286-299
On the approximability of some maximum spanning tree problems….Pages 300-310
Gauss periods and fast exponentiation in finite fields….Pages 311-322
Unbounded search and recursive graph problems….Pages 323-331
On the complexity of computing the greatest common divisor of several univariate polynomials….Pages 332-345
State complexity of SBTA languages….Pages 346-357
Pushdown automata with bounded nondeterminism and bounded ambiguity….Pages 358-370
Multihead two-way probabilistic finite automata….Pages 371-385
Non-erasing turing machines: A new frontier between a decidable halting problem and universality….Pages 386-397
Cyclic automata networks on finite graphs….Pages 398-410
Multiple alignment of biological sequences with gap flexibility….Pages 411-426
Lower bounds for the modular communication complexity of various graph accessibility problems….Pages 427-435
On monotonous oracle machines….Pages 436-448
On using learning automata for fast graph partitioning….Pages 449-460
Solution of a problem of yekutieli and mandelbrot….Pages 461-468
A rewrite approach for constraint logic programming….Pages 469-482
Simulations between cellular automata on cayley graphs….Pages 483-493
A temporal logic for real-time partial-ordering with named transactions….Pages 494-508
A new approach for routing in arrangement graphs and its performance evaluation….Pages 509-523
Reviews
There are no reviews yet.