Theoretical Computer Science, Volume 412

Volume 412, Numbers 1-2, January 2011

• 
  Damien Woods, Turlough Neary, Anthony Karel Seda:
  Preface. 1
• 
  Eric Goles Ch., Pierre-Etienne Meunier, Ivan Rapaport, Guillaume Theyssier:
  Communication complexity and intrinsic universality in cellular automata. 2-21
• 
  Nicolas Ollinger, Gaétan Richard:
  Four states are enough! 22-32
• 
  Maurice Margenstern:
  A universal cellular automaton on the heptagrid of the hyperbolic plane with four states. 33-56
• 
  Jérôme Durand-Lose:
  Abstract geometrical computation 4: Small Turing universal signal machines. 57-67
• 
  Alexander Okhotin:
  A simple P-complete problem and its language-theoretic representations. 68-82
• 
  Markus Holzer, Martin Kutrib, Andreas Malcher:
  Complexity of multi-head finite automata: Origins and directions. 83-96
• 
  Liesbeth De Mol:
  On the complex behavior of simple tag systems - An experimental approach. 97-112
• 
  Matteo Cavaliere, Peter Leupold:
  Computing by observing: Simple systems and simple observers. 113-123
• 
  Erzsébet Csuhaj-Varjú, Sergey Verlan:
  On generalized communicating P systems with minimal interaction rules. 124-135
• 
  Artiom Alhazov, Alexander Krassovitskiy, Yurii Rogozhin, Sergey Verlan:
  P systems with minimal insertion and deletion. 136-144
• 
  David Doty, Matthew J. Patitz, Scott M. Summers:
  Limitations of self-assembly at temperature 1. 145-158
• 
  Matthew J. Patitz, Scott M. Summers:
  Self-assembly of infinite structures: A survey. 159-165
• 
  Jack H. Lutz:
  A divergence formula for randomness and dimension. 166-177
• 
  Cristian S. Calude:
  Simplicity via provability for universal prefix-free Turing machines. 178-182
• 
  Klaus Sutner:
  Computational processes, observers and Turing incompleteness. 183-190

Volume 412, Number 3, January 2011

Preface

• 
  Ding-Zhu Du, Xiaodong Hu, Panos M. Pardalos:
  Preface. 191

Contributions

• 
  Yinfeng Xu, Wenming Zhang, Feifeng Zheng:
  Optimal algorithms for the online time series search problem. 192-197
• 
  Feng Zou, Yuexuan Wang, XiaoHua Xu, Xianyue Li, Hongwei Du, Peng-Jun Wan, Weili Wu:
  New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. 198-208
• 
  Deying Li, Yuexuan Wang, Qinghua Zhu, Huiqiang Yang:
  Fault-tolerant routing: k-inconnected many-to-one routing in wireless networks. 209-216
• 
  Suogang Gao, Zengti Li, Jiangchen Yu, Xiaofeng Gao, Weili Wu:
  DNA library screening, pooling design and unitary spaces. 217-224
• 
  Wei Ding, Guoliang Xue:
  A linear time algorithm for computing a most reliable source on a tree network with faulty nodes. 225-232
• 
  Deshi Ye, Xin Han, Guochuan Zhang:
  Online multiple-strip packing. 233-239
• 
  Zhipeng Cai, Randy Goebel, Guohui Lin:
  Size-constrained tree partitioning: Approximating the multicast k-tree routing problem. 240-245
• 
  Zhiyi Tan, An Zhang:
  Online hierarchical scheduling: An approach using mathematical programming. 246-256
• 
  Eduardo Álvarez-Miranda, Xujin Chen, Jie Hu, Xiaodong Hu, Alfredo Candia-Véjar:
  Deterministic risk control for cost-effective network connections. 257-264
• 
  Feng Wang, David Hongwei Du, Erika Camacho, Kuai Xu, Wonjun Lee, Yan Shi, Shan Shan:
  On positive influence dominating sets in social networks. 265-269
• 
  Peihai Liu, Xiwen Lu:
  An improved approximation algorithm for single machine scheduling with job delivery. 270-274

Volume 412, Numbers 4-5, February 2011

• 
  Baoqiang Fan, Shisheng Li, Li Zhou, Liqi Zhang:
  Scheduling resumable deteriorating jobs on a single machine with non-availability constraints. 275-280
• 
  Zhong Li, Guohui Lin:
  The three column Bandpass problem is solvable in linear time. 281-299
• 
  Tullio Ceccherini-Silberstein, Michel Coornaert:
  On the reversibility and the closed image property of linear cellular automata. 300-306
• 
  Ryotaro Okazaki, Hirotaka Ono, Taizo Sadahiro, Masafumi Yamashita:
  Broadcastings and digit tilings on three-dimensional torus networks. 307-319
• 
  Paola Alimonti, Esteban Feuerstein, Luigi Laura, Umberto Nanni:
  Linear time analysis of properties of conflict-free and general Petri nets. 320-338
• 
  Li-Jui Chen, Jinn-Jy Lin, Min-Zheng Shieh, Shi-Chun Tsai:
  More on the Magnus-Derek game. 339-344
• 
  Clemens Thielen, Stephan Westphal:
  Complexity of the traveling tournament problem. 345-351
• 
  Tatsuya Akutsu, Daiji Fukagawa, Atsuhiro Takasu, Takeyuki Tamura:
  Exact algorithms for computing the tree edit distance between unordered trees. 352-364
• 
  Adam Kasperski, Pawel Zielinski:
  On the approximability of robust spanning tree problems. 365-374
• 
  Christian Knauer, Klaus Kriegel, Fabian Stehn:
  Minimizing the weighted directed Hausdorff distance between colored point sets under translations and rigid motions. 375-382
• 
  Hiroshi Nagamochi:
  Cop-robber guarding game with cycle robber-region. 383-390
• 
  Franz-Josef Brandenburg, Mao-cheng Cai:
  Shortest path and maximum flow problems in networks with additive losses and gains. 391-401
• 
  Geneviève Paquin, Christophe Reutenauer:
  On the superimposition of Christoffel words. 402-418
• 
  Jinshan Zhang, Fengshan Bai:
  An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs. 419-429
• 
  Chun-Cheng Lin, Hsu-Chun Yen, Sheung-Hung Poon, Jia-Hao Fan:
  Complexity analysis of balloon drawing for rooted trees. 430-447
• 
  Warren D. Nichols, Robert G. Underwood:
  Algebraic Myhill-Nerode Theorems. 448-457
• 
  Dana Pardubská, Martin Plátek, Friedrich Otto:
  Parallel communicating grammar systems with regular control and skeleton preserving FRR automata. 458-477
• 
  Hunter Monroe:
  Speedup for natural problems and noncomputability. 478-481
• 
  Mikhail Andreev, Ilya P. Razenshteyn, Alexander Shen:
  Not every domain of a plain decompressor contains the domain of a prefix-free one. 482-486
• 
  Amir M. Ben-Amram, Simon Yoffe:
  A simple and efficient Union-Find-Delete algorithm. 487-492
• 
  Srecko Brlek, Christophe Reutenauer:
  Complexity and palindromic defect of infinite words. 493-497

Volume 412, Number 6, February 2011

Preface

• 
  Grzegorz Rozenberg:
  Preface. 499
• 
  Jon Timmis, Paul S. Andrews, Andrew Hone:
  Preface. 500-501

Contributions

• 
  Chris McEwan, Emma Hart:
  On clonal selection. 502-516
• 
  Thomas Jansen, Christine Zarges:
  Analyzing different variants of immune inspired somatic contiguous hypermutations. 517-533
• 
  Michael Elberfeld, Johannes Textor:
  Negative selection algorithms on strings with efficient training and linear-time classification. 534-542
• 
  Thomas Jansen, Christine Zarges:
  On benefits and drawbacks of aging strategies for randomized search heuristics. 543-559

Volume 412, Number 7, February 2011

Preface

• 
  Christos Kaklamanis, Martin Skutella:
  Preface. 561-562

Contributions

• 
  Wolfgang W. Bein, Kazuo Iwama, Jun Kawahara, Lawrence L. Larmore, James A. Oravec:
  A randomized algorithm for two servers in cross polytope spaces. 563-572
• 
  Amitai Armon:
  On min-max r-gatherings. 573-582
• 
  Johann L. Hurink, Jacob Jan Paulus:
  Improved online algorithms for parallel job scheduling and strip packing. 583-593
• 
  Marek Chrobak, Mathilde Hurand:
  Better bounds for incremental medians. 594-601
• 
  Robert Krauthgamer, Aranyak Mehta, Atri Rudra:
  Pricing commodities. 602-613
• 
  Nedialko B. Dimitrov, C. Greg Plaxton:
  Buyer-supplier games: Optimization over the core. 614-625
• 
  Iftah Gamzu:
  Improved lower bounds for non-utilitarian truthfulness. 626-632

Volume 412, Numbers 8-10, March 2011

• 
  Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, Leen Stougie:
  The distributed wireless gathering problem. 633-641
• 
  György Dósa, Yuxin Wang, Xin Han, He Guo:
  Online scheduling with rearrangement on two related machines. 642-653
• 
  Robert D. Gray, António Malheiro:
  Finite complete rewriting systems for regular semigroups. 654-661
• 
  Guomin Yang, Chik How Tan:
  Certificateless public key encryption: A new generic construction and two pairing-free schemes. 662-674
• 
  Felix Brandt, Felix A. Fischer, Markus Holzer:
  Equilibria of graphical games with symmetries. 675-685
• 
  Sun-Yuan Hsieh:
  On parallel recognition of cographs. 686-694
• 
  Anthony Labarre, Josef Cibulka:
  Polynomial-time sortable stacks of burnt pancakes. 695-702
• 
  Heather Betel, Paola Flocchini:
  On the relationship between fuzzy and Boolean cellular automata. 703-713
• 
  Bo Cui, Lila Kari, Shinnosuke Seki:
  Block insertion and deletion on trajectories. 714-728
• 
  Urban Larsson, Peter Hegarty, Aviezri S. Fraenkel:
  Invariant and dual subtraction games resolving the Duchêne-Rigo conjecture. 729-735
• 
  Zoltán Fülöp, Magnus Steinby:
  Varieties of recognizable tree series over fields. 736-752
• 
  Aïda Ouangraoua, Valentin Guignon, Sylvie Hamel, Cédric Chauve:
  A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes. 753-764
• 
  Martin Beaudry, Markus Holzer:
  On the size of inverse semigroups given by generators. 765-772
• 
  Kei Uchizawa, Eiji Takimoto, Takao Nishizeki:
  Size-energy tradeoffs for unate circuits computing symmetric Boolean functions. 773-782
• 
  Yotam Elor, Alfred M. Bruckstein:
  Uniform multi-agent deployment on a ring. 783-795
• 
  Jung Yeon Hwang:
  A note on an identity-based ring signature scheme with signer verifiability. 796-804
• 
  Zoltán Ésik, Szabolcs Iván:
  Büchi context-free languages. 805-821
• 
  Josef Cibulka:
  On average and highest number of flips in pancake sorting. 822-834
• 
  Zuzana Masáková, Edita Pelantová, Tomás Vávra:
  Arithmetics in number systems with a negative base. 835-845
• 
  Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach:
  Approximation of minimum weight spanners for sparse graphs. 846-852
• 
  Christian Glaßer, Christian Reitwießner, Victor L. Selivanov:
  The shrinking property for NP and coNP. 853-864
• 
  Zhongzhi Zhang, Francesc Comellas:
  Farey graphs as models for complex networks. 865-875
• 
  Wai-Fong Chuan, Chun-Yu Chen, Hui-Ling Ho, Fang-Yi Liao:
  α-words and the radix order. 876-891
• 
  Pascal Pons, Matthieu Latapy:
  Post-processing hierarchical community structures: Quality improvements and multi-scale view. 892-900
• 
  Zeev Nutov:
  Approximating directed weighted-degree constrained networks. 901-912
• 
  Weifan Wang, Xubin Yue, Xuding Zhu:
  The surviving rate of an outerplanar graph for the firefighter problem. 913-921
• 
  Tobias Marschall:
  Construction of minimal deterministic finite automata from biological motifs. 922-930

Volume 412, Number 11, March 2011

Contributions

• 
  Joaquín Aguado, Michael Mendler:
  Constructive semantics for instantaneous reactions. 931-961
• 
  César Domínguez, Julio Rubio:
  Effective homology of bicomplexes, formalized in Coq. 962-970
• 
  Giorgi Japaridze:
  Toggling operators in computability logic. 971-1004
• 
  Foto N. Afrati:
  Determinacy and query rewriting for conjunctive queries and views. 1005-1021

Notes

• 
  René David:
  A short proof that adding some permutation rules to β preserves SN. 1022-1026
• 
  José Espírito Santo:
  A note on preservation of strong normalisation in the λ-calculus. 1027-1032

Volume 412, Numbers 12-14, March 2011

Contributions

• 
  Asaf Levin, Uri Yovel:
  Uniform unweighted set cover: The power of non-oblivious local search. 1033-1053
• 
  Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno:
  On the complexity of reconfiguration problems. 1054-1065
• 
  Roberto Baldoni, Antonio Fernández Anta, Kleoni Ioannidou, Alessia Milani:
  The impact of mobility on the geocasting problem in mobile ad-hoc networks: Solvability and cost. 1066-1080
• 
  Yumei Huo, Hairong Zhao:
  Bicriteria scheduling concerned with makespan and total completion time subject to machine availability constraints. 1081-1091
• 
  Li-ying Hou, Liying Kang:
  Online and semi-online hierarchical scheduling for load balancing on uniform machines. 1092-1098
• 
  Martin Bader:
  The transposition median problem is NP-complete. 1099-1110
• 
  Stepán Starosta:
  On theta-palindromic richness. 1111-1121
• 
  Weiwei Wu, Minming Li, Enhong Chen:
  Min-energy scheduling for aligned jobs in accelerate model. 1122-1139
• 
  Manfred Droste, Karin Quaas:
  A Kleene-Schützenberger theorem for weighted timed automata. 1140-1153
• 
  Mathieu Tracol:
  Recurrence and transience for finite probabilistic tables. 1154-1168
• 
  Vassilis Kountouriotis, Christos Nomikos, Panos Rondogiannis:
  A game-theoretic characterization of Boolean grammars. 1169-1183
• 
  Sebastian Böcker, Quang Bao Anh Bui, Anke Truß:
  Computing bond orders in molecule graphs. 1184-1195
• 
  Oren Ben-Zwi, Amir Ronen:
  Local and global price of anarchy of graphical games. 1196-1207
• 
  Boting Yang:
  Fast edge searching and fast searching on graphs. 1208-1219
• 
  Benoît Libert, Moti Yung:
  Efficient traceable signatures in the standard model. 1220-1242
• 
  Hagit Attiya, Eshcar Hillel:
  Highly concurrent multi-word synchronization. 1243-1262
• 
  Telikepalli Kavitha, Meghana Nasre:
  Popular matchings with variable item copies. 1263-1274
• 
  Pinar Heggernes, Daniel Meister, Andrzej Proskurowski:
  Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs. 1275-1297

Volume 412, Number 15, March 2011

Preface

• 
  Valentin E. Brimkov, Reneta P. Barneva, Petra Wiederhold:
  Preface. 1299-1300

Contributions

• 
  Feliu Sagols, Raúl Marín:
  Two discrete versions of the Inscribed Square Conjecture and some related problems. 1301-1312
• 
  Valentin E. Brimkov, Andrew Leach, Michael Mastroianni, Jimmy Wu:
  Guarding a set of line segments in the plane. 1313-1324
• 
  Alexandre Borghi, Jérôme Darbon, Sylvain Peyronnet:
  Exact optimization for the ℓ¹-Compressive Sensing problem using a modified Dantzig-Wolfe method. 1325-1337
• 
  Filip Malmberg, Joakim Lindblad, Natasa Sladoje, Ingela Nyström:
  A graph-based framework for sub-pixel image segmentation. 1338-1349
• 
  Robin Strand, Benedek Nagy, Gunilla Borgefors:
  Digital distance functions on three-dimensional grids. 1350-1363
• 
  Benedek Nagy, Robin Strand:
  Approximating Euclidean circles by neighbourhood sequences in a hexagonal grid. 1364-1377
• 
  Yohan Thibault, Akihiro Sugimoto, Yukiko Kenmochi:
  3D discrete rotations using hinge angles. 1378-1391
• 
  Stéphane Gosselin, Guillaume Damiand, Christine Solnon:
  Efficient search of combinatorial maps using signatures. 1392-1405
• 
  Phuc Quang Le, Abdullah M. Iliyasu, Fangyan Dong, Kaoru Hirota:
  Strategies for designing geometric transformations on quantum images. 1406-1418
• 
  Xie Xie, Jiu-Lun Fan, Yin Zhu:
  The optimal All-Partial-Sums algorithm in commutative semigroups and its applications for image thresholding segmentation. 1419-1433
• 
  Oscar Dalmau Cedeño, Mariano Rivera:
  Alpha Markov Measure Field model for probabilistic image segmentation. 1434-1441

Volume 412, Number 16, April 2011

Preface

• 
  Ilias S. Kotsireas, Bernard Mourrain, Victor Y. Pan:
  Preface. 1443-1444

Contributions

• 
  Annie A. M. Cuyt, Wen-shin Lee:
  Sparse interpolation of multivariate rational functions. 1445-1456
• 
  Philippe P. Pébay, J. Maurice Rojas, David C. Thompson:
  Optimizing n-variate (n+k)-nomials for small k. 1457-1469
•