Theoretical Computer Science, Volume 296

Volume 296, Number 1, March 2003

Computing and Combinatorics

Jie Wang: Preface. 1-2 BibTeX
Oswin Aichholzer, Franz Aurenhammer, Ferran Hurtado, Hannes Krasser:
Towards compatible triangulations. 3-13
Electronic Edition (link) BibTeX
Jin-yi Cai, Eric Bach:
On testing for zero polynomials by a set of points with bounded precision. 15-25
Electronic Edition (link) BibTeX
Wun-Tat Chan, Tak Wah Lam, Hing-Fung Ting, Prudence W. H. Wong:
On-line stream merging in a general setting. 27-46
Electronic Edition (link) BibTeX
Otfried Cheong, Chan-Su Shin, Antoine Vigneron:
Computing farthest neighbors on a convex polytope. 47-58
Electronic Edition (link) BibTeX
Zhe Dang, Oscar H. Ibarra, Richard A. Kemmerer:
Generalized discrete timed automata: decidable approximations for safety verificatio. 59-74
Electronic Edition (link) BibTeX
Rob Duncan, Jianbo Qian, Antoine Vigneron, Binhai Zhu:
Polynomial time algorithms for three-label point labeling. 75-87
Electronic Edition (link) BibTeX
Liying Kang, Hong Qiao, Erfang Shan, Ding-Zhu Du:
Lower bounds on the minus domination and k-subdomination numbers. 89-98
Electronic Edition (link) BibTeX
Wen-Lian Hsu, Ross M. McConnell:
PC trees and circular-ones arrangements. 99-116
Electronic Edition (link) BibTeX
Michal Koucký:
Log-space constructible universal traversal sequences for cycles of length O(n^4.03). 117-144
Electronic Edition (link) BibTeX
Xiang-Yang Li:
Generating well-shaped d-dimensional Delaunay Meshes. 145-165
Electronic Edition (link) BibTeX
Enrico Nardelli, Guido Proietti, Peter Widmayer:
Finding the most vital node of a shortest path. 167-177
Electronic Edition (link) BibTeX
Bodo Manthey:
Non-approximability of weighted multiple sequence alignment. 179-192
Electronic Edition (link) BibTeX

Volume 296, Number 2, 8 March 2003

Didier Caucal:
On the transition graphs of turing machines. 195-223
Electronic Edition (link) BibTeX
Henning Fernau:
Nonterminal complexity of programmed grammars. 225-251
Electronic Edition (link) BibTeX
Daniela Besozzi, Giancarlo Mauri, Gheorghe Paun, Claudio Zandron:
Gemmating P systems: collapsing hierarchies. 253-267
Electronic Edition (link) BibTeX
Pierluigi Frisco:
Direct constructions of universal extended H systems. 269-293
Electronic Edition (link) BibTeX
Carlos Martín-Vide, Gheorghe Paun, Juan Pazos, Alfonso Rodríguez-Patón:
Tissue P systems. 295-326
Electronic Edition (link) BibTeX
Francine Herrmann, Maurice Margenstern:
A universal cellular automaton in the hyperbolic plane. 327-364
Electronic Edition (link) BibTeX
Klaus Sutner:
Cellular automata and intermediate degrees. 365-375
Electronic Edition (link) BibTeX

Volume 296, Number 3, 14 March 2003

Leonid Libkin:
Expressive power of SQL. 379-404
Electronic Edition (link) BibTeX
Marcelo Arenas, Leopoldo E. Bertossi, Jan Chomicki, Xin He, Vijay Raghavan, Jeremy Spinrad:
Scalar aggregation in inconsistent databases. 405-434
Electronic Edition (link) BibTeX
Jeff Edmonds, Jarek Gryz, Dongming Liang, Renée J. Miller:
Mining for empty spaces in large data sets. 435-452
Electronic Edition (link) BibTeX
Gösta Grahne, Alex Thomo:
Algebraic rewritings for optimizing regular path queries. 453-471
Electronic Edition (link) BibTeX
William Hesse:
The dynamic complexity of transitive closure is in DynTC⁰. 473-485
Electronic Edition (link) BibTeX
Chung Keung Poon:
Dynamic orthogonal range queries in OLAP. 487-510
Electronic Edition (link) BibTeX
Rakesh K. Sinha, Randeep Bhatia, Chung-Min Chen:
Asymptotically optimal declustering schemes for 2-dim range queries. 511-534
Electronic Edition (link) BibTeX