LATIN '92

1. Front Matter

   PDF

2. Linear time algorithms for liveness and boundedness in conflict-free Petri nets

   • Paola Alimonti, Esteban Feuerstein, Umberto Nanni

   Pages 1-14

3. q-Regular sequences and other generalizations of q-automatic sequences

   • Jean-Paul Allouche

   Pages 15-23

4. Complex polynomials and circuit lower bounds for modular counting

   • David A. Mix Barrington, Howard Straubing

   Pages 24-31

5. A decidability result about convex polyominoes

   • Danièle Beauquier, Michel Latteux, Karine Slowinski

   Pages 32-45

6. Edge insertion for optimal triangulations

   • M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, T. S. Tan

   Pages 46-60

7. Simulating permutation networks on hypercubes

   • Said Bettayeb, Bin Cong, Mike Girou, I. Hal Sudborough

   Pages 61-70

8. Universal statistical tests

   • Manuel Blum

   Pages 71-75

9. Automata and pattern matching in planar directed acyclic graphs

   • F. Bossut, B. Warin

   Pages 76-86

10. Regular expressions into finite automata

    • Anne Brüggemann-Klein

    Pages 87-98

11. Automata and codes with bounded deciphering delay

    • Véronique Bruyère

    Pages 99-107

12. Parallel complexity of heaps and min-max heaps

    • Svante Carlsson, Jingsen Chen

    Pages 108-116

13. On the complexity of some problems for the Blum, Shub & Smale model

    • Felipe Cucker, Francesc Rosselló

    Pages 117-129

14. Average case analysis of a greedy algorithm for the minimum hitting set problem

    • W. Fernandez de la Vega, V. Th. Paschos, R. Saad

    Pages 130-138

15. Achieving optimality for gate matrix layout and PLA folding: A graph theoretic approach

    • Afonso G. Ferreira, Siang W. Song

    Pages 139-153

16. How to write integers in non-integer base

    • Christiane Frougny

    Pages 154-164

17. A simple randomized parallel algorithm for maximal f-matchings

    • Oscar Garrido, Stefan Jarominek, Andrzej Lingas, Wojciech Rytter

    Pages 165-176

18. On the number of components of a recursive graph

    • William I. Gasarch, Katia S. Guimarães

    Pages 177-190

19. Factoring in skew-polynomial rings

    • Mark Giesbrecht

    Pages 191-203

20. Leaders election without conflict resolution rule

    • Joseph Gil, Yossi Matias

    Pages 204-218

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.

• Algorithms
• Automat
• algorithm
• automata
• complexity
• complexity theory
• computability
• computational geometry
• computer
• computer science
• data structure
• data structures
• formal language
• formal languages
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics