LATIN ’92: 1st Latin American Symposium on Theoretical Informatics São Paulo, Brazil, April 6–10, 1992 Proceedings

Paola Alimonti, Esteban Feuerstein, Umberto Nanni (auth.), Imre Simon (eds.)3540552847, 9783540552840

This volume contains the proceedings of LATIN ’92, a theoretical computer science symposium (Latin American Theoretical Informatics) held in S o Paulo, Brazil in April 1992. LATIN is intended to be a comprehensive symposium in the theory of computing, but for this first meeting the following areas were chosen for preferential coverage: algorithms and data structures, automata and formal languages, computability and complexity theory, computational geometry, cryptography, parallel and distributed computation, symbolic and algebraic computation, and combinatorial and algebraic aspects of computer science. The volume includesfull versions of the invited papers by 11 distinguished guest lecturers as well as 32 contributed papers selected from 66 submissions from authors with affiliations in 26 countries.

---

Table of contents :
Linear time algorithms for liveness and boundedness in conflict-free Petri nets….Pages 1-14
q -Regular sequences and other generalizations of q -automatic sequences….Pages 15-23
Complex polynomials and circuit lower bounds for modular counting….Pages 24-31
A decidability result about convex polyominoes….Pages 32-45
Edge insertion for optimal triangulations….Pages 46-60
Simulating permutation networks on hypercubes….Pages 61-70
Universal statistical tests….Pages 71-75
Automata and pattern matching in planar directed acyclic graphs….Pages 76-86
Regular expressions into finite automata….Pages 87-98
Automata and codes with bounded deciphering delay….Pages 99-107
Parallel complexity of heaps and min-max heaps….Pages 108-116
On the complexity of some problems for the Blum, Shub & Smale model….Pages 117-129
Average case analysis of a greedy algorithm for the minimum hitting set problem….Pages 130-138
Achieving optimality for gate matrix layout and PLA folding: A graph theoretic approach….Pages 139-153
How to write integers in non-integer base….Pages 154-164
A simple randomized parallel algorithm for maximal f -matchings….Pages 165-176
On the number of components of a recursive graph….Pages 177-190
Factoring in skew-polynomial rings….Pages 191-203
Leaders election without conflict resolution rule….Pages 204-218
Dynamics of sand-piles games on graphs….Pages 219-230
Rational function decomposition and Gröbner bases in the parameterization of plane curves….Pages 231-245
The double reconstruction conjectures about colored hypergraphs and colored directed graphs….Pages 246-261
Locally definable acceptance types — The three-valued case….Pages 262-271
On the computation of the Hilbert series….Pages 272-280
A distributed algorithm for finding all maximal cliques in a network graph….Pages 281-293
Polynomial factorization 1987–1991….Pages 294-313
Properties of recognizable $$mathcal{M}$$ -subsets of a free monoid….Pages 314-328
On the Burnside semigroups x n = x n+m ….Pages 329-343
Massively parallel computing and factoring….Pages 344-355
Some regularity conditions based on well quasi-orders….Pages 356-371
Approximate matching of network expressions with spacers….Pages 372-386
Unambiguous simulations of auxiliary pushdown automata and circuits….Pages 387-400
On reversible automata….Pages 401-416
Even induced cycles in planar graphs….Pages 417-429
Arithmetic + logic + geometry = concurrency….Pages 430-447
On the density and core of the complexity classes….Pages 448-459
The “last” decision problem for rational trace languages….Pages 460-473
Improved bounds for mixing rates of Markov chains and multicommodity flow….Pages 474-487
Data structures and terminating Petri nets….Pages 488-497
Circuits constructed with MOD q gates cannot compute AND in sublinear size….Pages 498-502
Decomposing a k -valued transducer into k unambiguous ones….Pages 503-515
An efficient algorithm for edge-coloring series parallel multigraphs….Pages 516-529
Complexity issues in neural network computations….Pages 530-544