Theoretical Computer Science, Volume 108

Volume 108, Number 1, 1993

Selected Papers of the International Colloquium on Words, Languages and Combinatorics, Kyoto, Japan, August 28-31, 1990

Jorge Almeida: Locally Commutative Power Semigroups and Counting Factors of Words. 3-16
Sinisa Crvenkovic, Rozália Sz. Madarász: On Kleene Algebras. 17-24
Volker Diekert: Möbius Functions and Confluent Semi-Commutations. 25-43
Christiane Frougny, Jacques Sakarovitch: Synchronized Rational Relations of Finite and Infinite Words. 45-82
Max H. Garzon: Cayley Automata. 83-102
Juhani Karhumäki: Equations Over Finite Sets of Words and Equivalence Problems in Automata Theory. 103-118
Masashi Katsura, Genjiro Tanaka: Groups of Finite Elementary Codes. 119-149
Michael Kunze: Standard Automata and Semidirect Products of Transformation Semigroups. 151-171
Liang Zhang, Weide Qui: Decomposition of Recognizable Strong Maximal Codes. 173-183

Zoltán Fülöp, Frank Herrmann, Sándor Vágvölgyi, Heiko Vogler: Tree Transducers with External Functions. 185-236
Do Long Van, Bertrand Le Saëc, Igor Litovsky: Stability for the Zigzag Submonoids. 237-249
Marina Madonia, Sergio Salemi, Tecla Sportelli: A Generalization of Sardinas and Patterson's Algorithm to Z-Codes. 251-270
Martin Dietzfelbinger, Wolfgang Maass: The Complexity of Matrix Transposition on One-Tape Off-Line Turing Machines with Output Tape. 271-290
Ulrich Schmid: The Average CRI-Length of a Controlled ALOHA Collision Resolution Algorithm. 291-310
Reuven Bar-Yehuda, Tuvi Etzion, Shlomo Moran: Rotating-Table Games and Derivatives of Words. 311-329
Alberto Apostolico: Efficient CRCW-PRAM Algorithms for Universal Substring Searching. 331-344
Roberto Grossi: On Finding Commong Subtrees. 345-356
Karine Slowinski: Picture Words with Invisible Lines. 357-363
Martin Middendorf: The Shortest Common Nonsubsequence Problem is NP-Complete. 365-369
Fabrizio d'Amore, Alberto Marchetti-Spaccamela, Umberto Nanni: The Weighted List Update Problem and the Lazy Adversary. 371-384
Siegfried Lehr: Sums and Rational Multiples of q-Automatic Sequences are q-Automatic. 385-391
Juraj Hromkovic, Katsushi Inoue: A Note on Realtime One-Way Synchronized Alternating One-Counter Automata. 393-400