Volume 134, Number 1, 7 November 1994

Selected Papers of the Second International Colloquium on Words, Languages and Combinatorics, Kyoto, Japan, August 25-28, 1992

• 
  J. A. Anderson: Semiretracts of a Free Monoid. 3-11
• 
  Danièle Beauquier, Andreas Podelski: Rabin Tree Automata and Finite Monoids. 13-25
• 
  Agnès Bonnier-Rigny, Daniel Krob: A Complete System of Identities for One-Letter Rational Expressions with Multiplicities in the Tropical Semiring. 27-50
• 
  Fernanda Botelho, Max H. Garzon: Boolean Neural Nets are Observable. 51-61
• 
  Renato M. Capocelli, Luisa Gargano, Ugo Vaccaro: A Fast Algorithm for the Unique Decipherability of Multivalued Encodings. 63-78
• 
  Sinisa Crvenkovic, Rozália Sz. Madarász: On Dynamic Algebras. 79-86
• 
  Volker Diekert: A Partial Trace Semantics for Petri Nets. 87-105
• 
  Helmut Jürgensen, Kai Salomaa, Sheng Yu: Transducers and the Decidability of Independence in Free Monoids. 107-117
• 
  Alica Kelemenová, Erzsébet Csuhaj-Varjú: Languages of Colonies. 119-130
• 
  Teo Mora: An Introduction to Commutative and Noncommutative Gröbner Bases. 131-173
• 
  Friedrich Otto, Paliath Narendran: Codes Modulo Finite Monadic String-Rewriting Systems. 175-188
• 
  Norman R. Reilly: Bounds on the Variety Generated by Completely Regular Syntactic Monoids from Finite Prefix Codes. 189-208
• 
  Jean-Claude Spehner: A Bijection Between Cliques in Graphs and Factorizations in Free Monoids. 209-223
• 
  Andreas Weber: Finite-Valued Distance Automata. 225-251
• 
  Andreas Weber: Exponential Upper and Lower Bounds for the Order of a Regular Language. 253-262

Volume 134, Number 2, 21 November 1994

• 
  Johannes Köbler: Locating P/poly Optimally in the Extended Low Hierarchy. 263-285
• 
  Edward P. F. Chan: Testing Satisfiability of a Class of Object-Oriented Conjunctive Queries. 287-309
• 
  Zoltán Fülöp: Undecidable Properties of Deterministic Top-Down Tree Transducers. 311-328
• 
  Michael Kaminski, Nissim Francez: Finite-Memory Automata. 329-363
• 
  Ferucio Laurentiu Tiplea, Cristian Ene, Cecilia Magdalena Ionescu, Octavian Procopiuc: Some Decision Problems for Parallel Communicating Grammar Systems. 365-385
• 
  Bruno Durand: Inversion of 2D Cellular Automata: Some Complexity Results. 387-401
• 
  Tero Harju, H. C. M. Kleijn, Michel Latteux, Alain Terlutte: Representation of Rational Functions with Prefix and Suffix Codings. 403-413
• 
  Eric Rémila: On the Tiling of a Torus with Two Bars. 415-426
• 
  Louis Mak: Speedup of Determinism by Alternation for Multidimensional Turing Machines. 427-453
• 
  Frantisek Matús: Stochastic Independence, Algebraic Independence and Abstract Connectedness. 455-471
• 
  Tao Jiang, Ming Li: Approximating Shortest Superstrings with Constraints. 473-491
• 
  Elias Dahlhaus, Marek Karpinski: An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph. 493-528
• 
  Laurent Alonso: Uniform Generation of a Motzkin Word. 529-536
• 
  John Harrison: Morphic Congruences and D0L Languages. 537-544
• 
  Lance Fortnow, John Rompel, Michael Sipser: On the Power of Multi-Prover Interactive Protocols. 545-557
• 
  Gu Xunrang, Zhu Yuzhang: Asymptotic Optimal HEAPSORT Algorithm. 559-565