Theoretical Computer Science, Volume 289

Volume 289, Number 1, October 2002

• Reiner Durchholz:
  A generic causal model for place latency. 1-49
  
• Peter J. Grabner, Helmut Prodinger:
  Sorting algorithms for broadcast communications: mathematical analysis. 51-67
  
• Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning:
  A deterministic (2-2/(k+1))ⁿ algorithm for k-SAT based on local search. 69-83
  
• Tamar Eilam, Shlomo Moran, Shmuel Zaks:
  The complexity of the characterization of networks supporting shortest-path interval routing. 85-104
  
• André Barbé, Fritz von Haeseler:
  Symmetries of decimation invariant sequences and digit sets. 105-136
  
• Jean-Marc Champarnaud, Djelloul Ziadi:
  Canonical derivatives, partial derivatives and finite automaton constructions. 137-163
  
• Oscar H. Ibarra, Jianwen Su, Zhe Dang, Tevfik Bultan, Richard A. Kemmerer:
  Counter Machines and Verification Problems. 165-189
  
• Oscar H. Ibarra, Jianwen Su:
  Augmenting the discrete timed automaton with other data structures. 191-204
  
• Mike D. Atkinson, Max Murphy, Nikola Ruskuc:
  Sorting with two ordered stacks in series. 205-223
  
• Marie-Pierre Béal, Olivier Carton:
  Determinization of transducers over finite and infinite words. 225-251
  
• Andreas Klein, Martin Kutrib:
  Deterministic Turing machines in the range between real-time and linear-time. 253-275
  
• Wei Chen, Koichi Wada, Kimio Kawaguchi:
  Robust algorithms for constructing strongly convex hulls in parallel. 277-295
  
• Francine Blanchet-Sadri, D. K. Luhmann:
  Conjugacy on partial words. 297-312
  
• Kuo-Liang Chung, Wen-Ming Yan, Jung-Gen Wu:
  Load-balanced parallel banded-system solvers. 313-334
  
• Wolfgang W. Bein, Marek Chrobak, Lawrence L. Larmore:
  The 3-server problem in the plane. 335-354
  
• Vincenzo Auletta, Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano:
  Randomized path coloring on binary trees. 355-399
  
• Hagit Brit, Shlomo Moran, Gadi Taubenfeld:
  Public data structures: counters as a special case. 401-423
  
• Henning Fernau:
  Even linear simple matrix languages: formal language properties and grammatical inference. 425-456
  
• Leslie G. Valiant:
  Expressiveness of matchgates. 457-471
  
• Uriel Feige, Giora Rayzman:
  On the drift of short schedules. 473-484
  
• Petr Sosík:
  Universal computation with Watson-Crick D0L systems. 485-501
  
• Herbert Fleischner, Oliver Kullmann, Stefan Szeider:
  Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference. 503-516
  
• Niklas Eriksen:
  (1+epsilon)-Approximation of sorting by reversals and transpositions. 517-529
  
• Sinisa Crvenkovic, Igor Dolinka:
  On axioms for commutative regular equations without addition. 531-551
  
• Liming Cai, David W. Juedes, Iyad A. Kanj:
  The inapproximability of non-NP-hard optimization problems. 553-571
  
• Vincent D. Blondel, Julien Cassaigne, Codrin M. Nichitiu:
  On the presence of periodic configurations in Turing machines and in counter machines. 573-590
  
• Robert Baumgartner, Georg Gottlob:
  Propositional default logics made easier: computational complexity of model checking. 591-627
  
• Dirk V. Arnold, Hans-Georg Beyer:
  Performance analysis of evolution strategies with multi-recombination in high-dimensional RN-search spaces disturbed by noise. 629-647
  
• Charles Knessl, Wojciech Szpankowski:
  The height of a binary search tree: the limiting distribution perspective. 649-703
  
• Juhani Karhumäki, Ion Petre:
  Conway's problem for three-word sets. 705-725
  
• Pedro V. Silva, Benjamin Steinberg:
  Extensions and submonoids of automatic monoids. 727-754
  
• Antonio Restivo, Pedro V. Silva:
  On the lattice of prefix codes. 755-782
  
• Honghui Wan, John C. Wootton:
  Algorithms for computing lengths of chains in integral partition lattices. 783-800
  
• Gabriel Ciobanu, Mihai Rotaru:
  Molecular interaction. 801-827
  
• Wolfgang Slany:
  Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete. 829-843
  
• Peter Damaschke:
  Two short notes on the on-line travelling salesman: handling times and lookahead. 845-852
  
• Kosaburo Hashiguchi:
  Algorithms for determining the smallest number of nonterminals (states) sufficient for generating (accepting) a regular language R with R1RR2 for given regular languages R1, R2. 853-859
  
• John M. Hitchcock:
  MAX3SAT is exponentially hard to approximate if NP has positive dimension. 861-869
  
• M. Ageev:
  Martin's game: a lower bound for the number of sets. 871-876
  

Volume 289, Number 2, October 2002

• Ding-Zhu Du, Peter Eades, Xuemin Lin:
  Foreword. 877
  
• Franz Aurenhammer, Naoki Katoh, Hiromichi Kojima, Makoto Ohsaki, Yin-Feng Xu:
  Approximating uniform triangular meshes in polygons. 879-895
  
• Giuseppe Di Battista, Giuseppe Liotta, Anna Lubiw, Sue Whitesides:
  Embedding problems for paths with direction constrained edges. 897-917
  
• M. Carmen Hernando, Michael E. Houle, Ferran Hurtado:
  On local transformation of polygons with visibility properties. 919-937
  
• Satoshi Fujita, Takeshi Hada:
  Two-dimensional on-line bin packing problem with rotatable items. 939-952
  
• Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, Shiro Taketomi:
  Online independent sets. 953-962
  
• Tomohiro Yamasaki, Hirotada Kobayashi, Yuuki Tokunaga, Hiroshi Imai:
  One-way probabilistic reversible and quantum one-counter automata. 963-976
  
• Hirotaka Ono, Kazuhisa Makino, Toshihide Ibaraki:
  Logical analysis of data with decomposable structures. 977-995
  
• Subhash Khot, Venkatesh Raman:
  Parameterized complexity of finding subgraphs with hereditary properties. 997-1008
  
• Yuriy A. Reznik:
  Some results on tries with adaptive branching. 1009-1026
  

Last update Mon May 20 04:02:59 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page