Informatique Théorique et Applications, Volume 34, 2000

Volume 34, Number 1, January/February 2000

• Elena Barcucci, Sara Brunetti, Francesco Del Ristoro: Succession rules and deco polyominoes. 1-14
• Roy L. Crole: Encoding FIX in object calculi. 15-38
• Carlo Mereghetti, Beatrice Palano: Threshold circuits for iterated matrix product and powering. 39-46
• Yannick Guesnet: On codes with finite interpreting delay: A defect theorem. 47-60
• Ján Manuch: Construction of very hard functions for multiparty communication complexity. 61-76
• Lucian Ilie, Grzegorz Rozenberg, Arto Salomaa: A characterization of poly-slender context-free languages. 77-86

Volume 34, Number 2, March/April 2000

• Evripidis Bampis, Aristotelis Giannakos, Alexander V. Karzanov, Yannis Manoussakis, Ioannis Milis: Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases. 87-98
• Alain Terlutte, David Simplot: Iteration of rational transductions. 99-130
• Serge Burckel, Marianne Morillon: Three generators for minimal writing-space computations. 131-138
• Marie-Pierre Béal, Olivier Carton: Asynchronous sliding block maps. 139-156
• Vladimir A. Zakharov: On the Decidability of the Equivalence Problem for Monadic Recursive Programs. 157-172

Volume 34, Number 3, May/June 2000

• D. Arun Kumar, C. Pandu Rangan: Approximation algorithms for the Traveling Salesman Problem with range condition. 173-182
• David Simplot, Alain Terlutte: Closure under union and composition of iterated rational transductions. 183-212
• Hans-Joachim Böckenhauer, Sebastian Seibert: Improved lower bounds on the approximability of the Traveling Salesman Problem. 213-255

Volume 34, Number 4, July/August 2000

• Christian Hagenah, Anca Muscholl: Computing epsilon-free NFA from regular expressions in O(n log²(n)) time. 257-278
• Markus E. Nebel: On the Horton-Strahler number for combinatorial tries. 279-296
• Juha Honkala: A Kleene-Schützenberger theorem for Lindenmayerian rational power series. 297-306
• Mireille Clerbout, Yves Roos, Isabelle Ryl: Semi-commutations and partial commutations. 307-

Volume 34, Number 5, September-October 2000

• Pierre-Cyrille Héam:
  A Lower Bound For Reversible Automata. 331-341
  
• Jacques Justin, Laurent Vuillon:
  Return words in Sturmian and episturmian words. 343-356
  
• Viliam Geffert, Norbert Popély:
  A space lower bound for acceptance by one-way II₂-alternating machines. 357-372
  
• Jacques Justin:
  On a paper by Castelli, Mignosi, Restivo. 373-377
  
• Masanao Ozawa, Harumichi Nishimura:
  Local transition functions of quantum Turing machines. 379-402
  
• Valérie Berthé:
  Complexité et automates cellulaires linéaires. 403-423
  

Volume 34, Number 6, November-December 2000

• Osamu Takaki:
  Finite presentability of strongly finite dilators. 425-431
  
• Ken-etsu Fujita:
  Domain-free [lambda][mu]-calculus. 433-466
  
• Lucian Ilie, Wojciech Plandowski:
  Two-variable word equations. 467-501
  
• Marie-Pierre Béal, Olivier Carton:
  Computing the prefix of an automaton. 503-514
  
• Imrich Vrto:
  Cutwidth of the r-dimensional mesh of d-ary trees. 515-519
  
• Marianne Huchard, Hervé Dicky, Hervé Leblanc:
  Galois lattice as a framework to specify building class hierarchies algorithms. 521-548
  
• Salvatore La Torre, Margherita Napoli, Mimmo Parente:
  A compositional approach to synchronize two dimensional networks of processors. 549-564
  
• Luca Aceto, Anna Ingólfsdóttir, Mikkel Lykke Pedersen, Jan Poulsen:
  Characteristic formulae for timed automata. 565-584
  
• Jeanne Devolder:
  Codes générateurs minimaux de langages de mots bi-infinis. 585-596