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
• 
  Gudmund Skovbjerg Frandsen, Piotr Sankowski:
  Dynamic normal forms and dynamic characteristic polynomial. 1470-1483
• 
  Michalis Kourniotis, Marilena Mitrouli, Dimitrios Triantafyllou:
  Parallel QR processing of Generalized Sylvester matrices. 1484-1491
• 
  André Galligo, Adrien Poteaux:
  Computing monodromy via continuation methods on random Riemann surfaces. 1492-1507
• 
  Carlos Hoppen, Virginia M. Rodrigues, Vilmar Trevisan:
  A note on Gao's algorithm for polynomial factorization. 1508-1522
• 
  Sylvain Chevillard, J. Harrison, Mioara Joldes, Christoph Quirin Lauter:
  Efficient and accurate computation of upper bounds of approximation errors. 1523-1543

Volume 412, Number 17, April 2011

Preface

• 
  Grzegorz Rozenberg:
  Preface. 1545

Contributions

• 
  Tobias Friedrich, Christian Horoba, Frank Neumann:
  Illustration of fairness in evolutionary multi-objective optimization. 1546-1556
• 
  Chris McCaig, Rachel Norman, Carron Shankland:
  From individuals to populations: A mean field semantics for process algebra. 1557-1580
• 
  Artiom Alhazov, Sergey Verlan:
  Minimization strategies for maximally parallel multiset rewriting systems. 1581-1591
• 
  John H. Reif, Sudheer Sahu, Peng Yin:
  Complexity of graph self-assembly in accretive systems and self-destructible systems. 1592-1605
• 
  Guowu Yang, Fei Xie, William N. N. Hung, Xiaoyu Song, Marek A. Perkowski:
  Realization and synthesis of reversible functions. 1606-1613
• 
  Pei Jiang, Ying-Ping Chen:
  Free lunches on the discrete Lipschitz class. 1614-1628
• 
  Benjamin Doerr, Frank Neumann, Dirk Sudholt, Carsten Witt:
  Runtime analysis of the 1-ANT ant colony optimizer. 1629-1644

Volume 412, Number 18, April 2011

Preface

• 
  Manindra Agrawal, Angsheng Li:
  Theory and applications of models of computation (TAMC 2008). 1645

Contributions

• 
  Kazuyuki Amano, Jun Tarui:
  A well-mixed function with circuit complexity 5n: Tightness of the Lachish-Raz-type bounds. 1646-1651
• 
  Klaus Ambos-Spies, Serikzhan A. Badaev, Sergey S. Goncharov:
  Inductive inference and computable numberings. 1652-1668
• 
  Marat M. Arslanov, S. Barry Cooper, Iskander Sh. Kalimullin, Mariya Ivanova Soskova:
  Splitting and nonsplitting in the Σ₂⁰ enumeration degrees. 1669-1685
• 
  Beate Bollig:
  On the OBDD complexity of the most significant bit of integer multiplication. 1686-1695
• 
  Jurek Czyzowicz, Stefan Dobrev, Hernán González-Aguilar, Rastislav Kralovic, Evangelos Kranakis, Jaroslav Opatrny, Ladislav Stacho, Jorge Urrutia:
  Local 7-coloring for planar subgraphs of unit disk graphs. 1696-1704
• 
  Jiamou Liu, Mia Minnes:
  Deciding the isomorphism problem in classes of unary automatic structures. 1705-1717
• 
  Linqing Tang:
  On the derandomization of the graph test for homomorphism over groups. 1718-1728
• 
  Cong Tian, Zhenhua Duan:
  Expressiveness of propositional projection temporal logic with star. 1729-1744
• 
  Jianxin Wang, Qilong Feng, Jianer Chen:
  An O^*(3.53^3k)-time parameterized algorithm for the 3-set packing problem. 1745-1753

Volume 412, Number 19, April 2011

Preface

• 
  Gábor Lugosi, Sandra Zilles:
  Preface. 1755

Contributions

• 
  Malte Darnstädt, Hans Ulrich Simon:
  Smart PAC-learners. 1756-1766
• 
  Sanjoy Dasgupta:
  Two faces of active learning. 1767-1781
• 
  Nader H. Bshouty, Hanna Mazzawi:
  Reconstructing weighted graphs with minimal query complexity. 1782-1790
• 
  Nicolò Cesa-Bianchi, Claudio Gentile, Fabio Vitale:
  Predicting the labels of an unknown graph via adaptive exploration. 1791-1804
• 
  Sanjay Jain, Qinglong Luo, Pavel Semukhin, Frank Stephan:
  Uncountable automatic classes and learning. 1805-1820
• 
  Ryo Yoshinaka:
  Efficient learning of multiple context-free languages with multidimensional substitutability from positive data. 1821-1831
• 
  Sébastien Bubeck, Rémi Munos, Gilles Stoltz:
  Pure exploration in finitely-armed and continuous-armed bandits. 1832-1852

Volume 412, Number 20, April 2011

Preface

• 
  Pierre-Louis Curien:
  Preface. 1853-1859

Contributions

• 
  Jean-Yves Girard:
  Geometry of Interaction V: Logic in the hyperfinite factor. 1860-1883
• 
  Daniel de Carvalho, Michele Pagani, Lorenzo Tortora de Falco:
  A semantic measure of the execution time in linear logic. 1884-1902
• 
  Luca Paolini, Elaine Pimentel, Simona Ronchi Della Rocca:
  Strong normalization from an unusual point of view. 1903-1915
• 
  Benno van den Berg, Ieke Moerdijk:
  Aspects of predicative algebraic set theory, II: Realizability. 1916-1940
• 
  Paulin Jacobé de Naurois, Virgile Mogbil:
  Correctness of linear logic proof structures is NL-complete. 1941-1957
• 
  Stefano Guerrini:
  A linear algorithm for MLL proof net correctness and sequentialization. 1958-1978
• 
  Paolo Tranquilli:
  Intuitionistic differential nets and lambda-calculus. 1979-1997
• 
  Jean Goubault-Larrecq:
  Musings around the geometry of interaction, and coherence. 1998-2014
• 
  Esfandiar Haghverdi:
  Towards a geometry of recursion. 2015-2028
• 
  Ugo Dal Lago, Martin Hofmann:
  Realizability models and implicit complexity. 2029-2047
• 
  Kazushige Terui:
  Computational ludics. 2048-2071
• 
  Max I. Kanovich, Jacqueline Vauzeilles:
  Linear logic as a tool for planning under temporal uncertainty. 2072-2092

Volume 412, Number 21, May 2011

Preface

• 
  Grzegorz Rozenberg:
  Preface. 2093
• 
  Pierpaolo Degano:
  Preface. 2094

Contributions

• 
  Thao Dang, Colas Le Guernic, Oded Maler:
  Computing reachable states for nonlinear biological models. 2095-2107
• 
  Elisabetta De Maria, François Fages, Aurélien Rizk, Sylvain Soliman:
  Design, optimization and predictions of a coupled model of the cell cycle, circadian clock, DNA repair system, irinotecan metabolism and exposure control under temporal logic constraints. 2108-2127
• 
  Frédéric Didier, Thomas A. Henzinger, Maria Mateescu, Verena Wolf:
  Approximation of event probabilities in noisy cellular processes. 2128-2141
• 
  Vashti Galpin, Jane Hillston:
  A semantic equivalence for Bio-PEPA based on discretisation of continuous values. 2142-2161
• 
  Sumit Kumar Jha, Christopher James Langmead:
  Synthesis and infeasibility analysis for stochastic models of biochemical systems using statistical model checking and abstraction refinement. 2162-2187
• 
  Bing Liu, David Hsu, P. S. Thiagarajan:
  Probabilistic approximations of ODEs based bio-pathway dynamics. 2188-2206
• 
  Aurélien Naldi, Elisabeth Remy, Denis Thieffry, Claudine Chaouiya:
  Dynamically consistent reduction of logical regulatory graphs. 2207-2218

Volume 412, Number 22, May 2011

Contributions

• 
  Charles-Éric Drevet, Md. Nazrul Islam, Éric Schost:
  Optimization techniques for small matrix multiplication. 2219-2236
• 
  Yi-Jiun Liu, James K. Lan, Well Y. Chou, Chiuyuan Chen:
  Constructing independent spanning trees for locally twisted cubes. 2237-2252
• 
  Cristian S. Calude, André Nies, Ludwig Staiger, Frank Stephan:
  Universal recursively enumerable sets of strings. 2253-2261
• 
  Guillaume Aupy, Olivier Bournez:
  On the number of binary-minded individuals required to compute sqrt(1/2). 2262-2267
• 
  Jean-Paul Allouche, Laurence Maillard-Teyssier:
  Inconstancy of finite and infinite sequences. 2268-2281
• 
  Tamir Levi, Ami Litman:
  Bitonic sorters of minimal depth. 2282-2295
• 
  Vittorio Bilò, Michele Flammini:
  Extending the notion of rationality of selfish agents: Second Order Nash equilibria. 2296-2311
• 
  Angelos Mantzaflaris, Bernard Mourrain, Elias P. Tsigaridas:
  On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers. 2312-2330
• 
  Víctor Lavín Puente:
  On learning multivalued dependencies with queries. 2331-2339
• 
  Petar Mitankin, Stoyan Mihov, Klaus U. Schulz:
  Deciding word neighborhood with universal neighborhood automata. 2340-2355
• 
  Nicolas Bedon, Chloe Rispal:
  Series-parallel languages on scattered and countable posets. 2356-2369
• 
  Vinícius G. P. de Sá, Guilherme Dias da Fonseca, Raphael C. S. Machado, Celina M. H. de Figueiredo:
  Complexity dichotomy on partial grid recognition. 2370-2379
• 
  Ji Tian, T. C. Edwin Cheng, C. T. Ng, Jinjiang Yuan:
  Online scheduling on unbounded parallel-batch machines with incompatible job families. 2380-2386
• 
  Yancai Zhao, Liying Kang, Moo Young Sohn:
  The algorithmic complexity of mixed domination in graphs. 2387-2392
• 
  Ziming Duan, Pingli Lv, Lianying Miao, Zhengke Miao, Cuiqi Wang:
  New upper bounds on the L(2, 1)-labeling of the skew and converse skew product graphs. 2393-2397
• 
  Guy Even, Moti Medina:
  Parallel randomized load balancing: A lower bound for a more general model. 2398-2408
• 
  Xiaofan Yang, Qiang Dong, Erjie Yang, Jianqiu Cao:
  Hamiltonian properties of twisted hypercube-like networks with more faulty elements. 2409-2417
• 
  Tseng-Kuei Li, Chia-Jui Lai, Chang-Hsiung Tsai:
  A novel algorithm to embed a multi-dimensional torus into a locally twisted cube. 2418-2424
• 
  Nicolas Catusse, Victor Chepoi, Yann Vaxès:
  Embedding into the rectilinear plane in optimal O(n²) time. 2425-2433
• 
  Othon Michail, Ioannis Chatzigiannakis, Paul G. Spirakis:
  Mediated population protocols. 2434-2450

Note

• 
  Johannes Fischer:
  Combined data structure for previous- and next-smaller-values. 2451-2456

Volume 412, Number 23, May 2011

Preface

• 
  Jianer Chen, S. Barry Cooper:
  Algorithms, complexity and computational models. 2457-2458

Contributions

• 
  Sergey Bereg, Minghui Jiang, Boting Yang, Binhai Zhu:
  On the red/blue spanning tree problem. 2459-2467
• 
  Jin-yi Cai, Pinyan Lu, Mingji Xia:
  A computational proof of complexity of some restricted counting problems. 2468-2485
• 
  Alessandra Carbone, Linda Dib:
  Co-evolution and information signals in biological sequences. 2486-2495
• 
  Maw-Shang Chang, Ling-Ju Hung, Ton Kloks, Sheng-Lung Peng:
  Block-graph width. 2496-2502
• 
  Jianer Chen, Qilong Feng, Yang Liu, Songjian Lu, Jianxin Wang:
  Improved deterministic algorithms for weighted matching and packing problems. 2503-2512
• 
  Jirí Fiala, Petr A. Golovach, Jan Kratochvíl:
  Parameterized complexity of coloring problems: Treewidth versus vertex cover. 2513-2523
• 
  Marc Kaplan, Sophie Laplante:
  Kolmogorov complexity and combinatorial methods in communication complexity. 2524-2535
• 
  Daniel Lokshtanov, Matthias Mnich, Saket Saurabh:
  A linear kernel for planar connected dominating set. 2536-2543
• 
  Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai:
  Best-order streaming model. 2544-2555
• 
  Anke van Zuylen:
  Linear programming based approximation algorithms for feedback set problems in bipartite tournaments. 2556-2561

Volume 412, Number 24, May 2011

Preface

• 
  Susanne Albers, Alberto Marchetti-Spaccamela:
  Preface. 2563

Contributions

• 
  Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal:
  Sorting and selection on dynamic data. 2564-2576
• 
  Yossi Azar, Aleksander Madry, Thomas Moscibroda, Debmalya Panigrahi, Aravind Srinivasan:
  Maximum bipartite flow in networks with adaptive channel width. 2577-2587
• 
  Gerth Stølting Brodal, Beat Gfeller, Allan Grønlund Jørgensen, Peter Sanders:
  Towards optimal range medians. 2588-2601
• 
  Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi:
  Rumor spreading in social networks. 2602-2610
• 
  Jan Draisma, Eyal Kushilevitz, Enav Weinreb:
  Partition arguments in multiparty communication complexity. 2611-2622
• 
  Robert Elsässer, Thomas Sauerwald:
  Tight bounds for the cover time of multiple random walks. 2623-2641
• 
  Yuval Emek, Pierre Fraigniaud, Amos Korman, Adi Rosén:
  Online computation with advice. 2642-2656
• 
  Alexander Fanghänel, Thomas Kesselheim, Berthold Vöcking:
  Improved algorithms for latency minimization in wireless networks. 2657-2667
• 
  Arash Farzan, J. Ian Munro:
  Succinct representation of dynamic trees. 2668-2678
• 
  Telikepalli Kavitha, Julián Mestre, Meghana Nasre:
  Popular mixed matchings. 2679-2690
• 
  Li Zhang:
  Proportional response dynamics in the Fisher market. 2691-2698
• 
  Fedor V. Fomin, Pierre Fraigniaud, Stephan Kreutzer, Dimitrios M. Thilikos:
  Special Issue on "Theory and Applications of Graph Searching Problems". 2699

Volume 412, Number 25, June 2011

• 
  Klaus Keimel, Artus Ph. Rosenbusch, Thomas Streicher:
  Relating direct and predicate transformer partial correctness semantics for an imperative probabilistic-nondeterministic language. 2701-2713
• 
  Mai Gehrke, Jacob Vosmaer:
  Canonical extensions and canonicity via dcpo presentations. 2714-2723
• 
  Uri Abraham:
  Logical classification of distributed algorithms (Bakery algorithms as an example). 2724-2745
• 
  Yongjian Li, William N. N. Hung, Xiaoyu Song:
  A novel formalization of symbolic trajectory evaluation semantics in Isabelle/HOL. 2746-2765
• 
  Wesley Calvert:
  Metric structures and probabilistic computation. 2766-2775
• 
  Guillaume Bonfante, Jean-Yves Marion, Jean-Yves Moyen:
  Quasi-interpretations a way to control resources. 2776-2796

Volume 412, Number 26, June 2011

Preface

• 
  Grzegorz Rozenberg:
  Preface. 2797
• 
  Monika Heiner, Adelinde M. Uhrmacher:
  Foundations of formal reconstruction of biochemical networks. 2798-2799

Contributions

• 
  Markus Durzinsky, Annegret Wagler, Robert Weismantel:
  An algorithmic framework for network reconstruction. 2800-2815
• 
  Elena S. Dimitrova, Luis David García-Puente, Franziska Hinkelmann, Abdul Salam Jarrah, Reinhard C. Laubenbacher, Brandilyn Stigler, Michael Eugene Stillman, Paola Vera-Licona:
  Parameter estimation for Boolean models of biological networks. 2816-2826
• 
  Aurélien Rizk, Grégory Batt, François Fages, Sylvain Soliman:
  Continuous valuations of temporal logic specifications with applications to parameter optimization and robustness measures. 2827-2839
• 
  Geoffrey Koh, David Hsu, P. S. Thiagarajan:
  Component-based construction of bio-pathway models: The parameter estimation problem. 2840-2853
• 
  Radu Mateescu, Pedro T. Monteiro, Estelle Dumas, Hidde de Jong:
  CTRL: Extension of CTL with regular expressions and fairness operators to verify genetic regulatory networks. 2854-2883
• 
  Martin Schwarick, Alexej Tovchigrechko:
  IDD-based model validation of biochemical networks. 2884-2908

Volume 412, Number 27, June 2011

Preface

• 
  Arturo Carpi, Clelia de Felice:
  Combinatorics on words. 2909-2910

Contributions

• 
  Sergey V. Avgustinovich, Anna E. Frid, Teturo Kamae, Pavel Salimov:
  Infinite permutations of lowest maximal pattern complexity. 2911-2921
• 
  Alexandre Blondin Massé, Srecko Brlek, Ariane Garon, Sébastien Labbé:
  Equations on palindromes and circular words. 2922-2930
• 
  Maxime Crochemore, Lucian Ilie, Liviu Tinta:
  The "runs" conjecture. 2931-2941
• 
  Manuel Domínguez, Thomas Noll, Marco Castrillón:
  An extension of Christoffel duality to a subset of Sturm numbers and their characteristic words. 2942-2954
• 
  Francesca Fiorenzi, Pascal Ochem, Elise Vaslet:
  Bounds for the generalized repetition threshold. 2955-2963
• 
  Roberto Grossi:
  A quick tour on suffix arrays and compressed suffix arrays. 2964-2973
• 
  Damien Jamet, Geneviève Paquin, Gwénaël Richomme, Laurent Vuillon:
  On the fixed points of the iterated pseudopalindromic closure operator. 2974-2987
• 
  Donatella Merlini, Renzo Sprugnoli:
  Algebraic aspects of some Riordan arrays related to binary words avoiding a pattern. 2988-3001
• 
  Xavier Provençal:
  Minimal non-convex words. 3002-3009
• 
  Michaël Rao:
  Last cases of Dejean's conjecture. 3010-3018
• 
  Antonio Restivo, Giovanna Rosone:
  Balancing and clustering of words in the Burrows-Wheeler transform. 3019-3032

Volume 412, Number 28, June 2011

Preface

• 
  Inge Bethke, Alban Ponse, Piet Rodenburg:
  Preface: This issue is dedicated to Jan Bergstra on the occasion of his sixtieth birthday. 3033-3034

Contributions

• 
  Luca Aceto, Taolue Chen, Anna Ingólfsdóttir, Bas Luttik, Jaco van de Pol:
  On the axiomatizability of priority II. 3035-3044
• 
  Luca Aceto, Matteo Cimini, Anna Ingólfsdóttir, Mohammad Reza Mousavi, Michel A. Reniers:
  SOS rule formats for zero and unit elements. 3045-3071
• 
  Miguel E. Andrés, Catuscia Palamidessi, Peter van Rossum, Ana Sokolova:
  Information hiding in probabilistic concurrent systems. 3072-3089
• 
  Jos C. M. Baeten, Bas Luttik:
  Unguardedness mostly means many solutions. 3090-3100
• 
  Sebastian S. Bauer, Rolf Hennicker, Martin Wirsing:
  Interface theories for concurrency and data. 3101-3121
• 
  Jan A. Bergstra, Jaco van de Pol:
  A calculus for four-valued sequential logic. 3122-3128
• 
  Sjoerd Cranen, Jan Friso Groote, Michel A. Reniers:
  A linear translation from CTL* to the first-order modal μ -calculus. 3129-3139
• 
  Dirk van Dalen:
  Brouwer's ϵ-fixed point and Sperner's lemma. 3140-3144
• 
  Razvan Diaconescu, Ionut Tutu:
  On the algebra of structured specifications. 3145-3174
• 
  Jörg Endrullis, Clemens Grabmayer, Jan Willem Klop, Vincent van Oostrom:
  On equal μ-terms. 3175-3202
• 
  Jörg Endrullis, Dimitri Hendriks:
  Lazy productivity via termination. 3203-3225
• 
  Javier Esparza, Stefan Kiefer, Michael Luttenberger:
  Derivation tree analysis for accelerated fixed-point computation. 3226-3241
• 
  Herman Geuvers, Robbert Krebbers:
  The correctness of Newman's typability algorithm and some of its extensions. 3242-3261
• 
  Fatemeh Ghassemi, Wan J. Fokkink, Ali Movaghar:
  Verification of mobile ad hoc networks: An algebraic approach. 3262-3282
• 
  Rob J. van Glabbeek:
  On cool congruence formats for weak bisimulations. 3283-3302
• 
  Peter Höfner, Bernhard Möller:
  Fixing Zeno gaps. 3303-3322
• 
  Bart Jacobs:
  Probabilities, distribution monads, and convex categories. 3323-3336
• 
  Gerald Lüttgen, Walter Vogler:
  Safe reasoning with Logic LTS. 3337-3357
• 
  Kim G. Larsen, Uli Fahrenberg, Claus R. Thrane:
  Metrics for weighted transition systems: Axiomatization and complexity. 3358-3369
• 
  Piet Rodenburg, Jan Willem Klop, Karst Koymans, Jos L. M. Vrancken:
  The free process algebra generated by δ, ϵ and τ. 3370-3377
• 
  John V. Tucker, Jeffery I. Zucker:
  Continuity of operators on continuous and discrete time streams. 3378-3403
• 
  Albert Visser:
  On the ambiguation of Polish notation. 3404-3411

Volume 412, Number 29, July 2011

• 
  Dong Han Kim:
  Return time complexity of Sturmian sequences. 3413-3417
• 
  Swan Dubois, Maria Potop-Butucaru, Sébastien Tixeuil:
  Dynamic FTSS in asynchronous systems: The case of unison. 3418-3439
• 
  Jianxi Fan, Xiaohua Jia, Baolei Cheng, Jia Yu:
  An efficient fault-tolerant routing algorithm in bijective connection networks with restricted faulty edges. 3440-3450
• 
  Murat Cenk, Ferruh Özbudak:
  Multiplication of polynomials modulo xⁿ. 3451-3462
• 
  Achim Blumensath:
  Recognisability for algebras of infinite trees. 3463-3486
• 
  Dániel Marx:
  Complexity of clique coloring and related problems. 3487-3500
• 
  Ge Xia, Yong Zhang:
  On the small cycle transversal of planar graphs. 3501-3509
• 
  Daniel Reidenbach, Johannes C. Schneider:
  Restricted ambiguity of erasing morphisms. 3510-3523
• 
  Xiaoming Sun:
  An improved lower bound on the sensitivity complexity of graph properties. 3524-3529
• 
  Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh:
  An exact algorithm for minimum distortion embedding. 3530-3536
• 
  Amihood Amir, Estrella Eisenberg, Orgad Keller, Avivit Levy, Ely Porat:
  Approximate string matching with stuck address bits. 3537-3544
• 
  Nicholas Korpelainen, Vadim V. Lozin, Dmitriy S. Malyshev, Alexander Tiskin:
  Boundary properties of graphs for algorithmic graph problems. 3545-3554
• 
  Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo T. de A. Moreira, Rudini Menezes Sampaio:
  Testing permutation properties through subpermutations. 3555-3567
• 
  Carlos Fisch Brito, Shailesh Vaya:
  Improved lower bound for deterministic broadcasting in radio networks. 3568-3578
• 
  Wing-Kai Hon, Tak Wah Lam, Rahul Shah, Siu-Lung Tam, Jeffrey Scott Vitter:
  Cache-oblivious index for approximate string matching. 3579-3588
• 
  Dieter Mitsche, Maria Saumell, Rodrigo I. Silveira:
  On the number of higher order Delaunay triangulations. 3589-3597
• 
  Daniel Turetsky:
  Connectedness properties of dimension level sets. 3598-3603
• 
  Gabriele Fici:
  Special factors and the combinatorics of suffix and factor automata. 3604-3615
• 
  Eric Goles Ch., Andrés Moreira, Ivan Rapaport:
  Communication complexity in number-conserving and monotone cellular automata. 3616-3628
• 
  Steffen Kopecki:
  On iterated hairpin completion. 3629-3638
• 
  Madhusudan Manjunath, Vikram Sharma:
  Applications of dimensionality reduction and exponential sums to graph automorphism. 3639-3649
• 
  Enrico Angelelli, Carlo Filippi:
  On the complexity of interval scheduling with a resource constraint. 3650-3657
• 
  Hsien-Jone Hsieh, Dyi-Rong Duh:
  ω-wide diameters of enhanced pyramid networks. 3658-3675
• 
  Symeon Bozapalidis, Zoltán Fülöp, George Rahonis:
  Equational tree transformations. 3676-3692
• 
  Carmen C. Centeno, Mitre Costa Dourado, Lucia Draque Penso, Dieter Rautenbach, Jayme Luiz Szwarcfiter:
  Irreversible conversion of graphs. 3693-3700
• 
  Nicolas Baudru:
  Compositional synthesis of asynchronous automata. 3701-3716
• 
  Boaz Patt-Shamir, Dror Rawitz:
  Video distribution under multiple constraints. 3717-3730
• 
  Qian Cao, Zhaohui Liu, T. C. Edwin Cheng:
  Semi-online scheduling with known partial information about job sizes on two identical machines. 3731-3737
• 
  Spyridon Antonakopoulos, Lisa Zhang:
  Approximation algorithms for grooming in optical network design. 3738-3751
• 
  Francine Blanchet-Sadri, Ilkyoo Choi, Robert Mercas:
  Avoiding large squares in partial words. 3752-3758
• 
  Minghui Jiang:
  Inapproximability of maximal strip recovery. 3759-3774
• 
  Mauro Mezzini:
  Fast minimal triangulation algorithm using minimum degree criterion. 3775-3787

Note

• 
  Daniel Lenz, Zuzana Masáková, Edita Pelantová:
  Note on powers in three interval exchange transformations. 3788-3794

Erratum

• 
  Pascal Caron, Jean-Marc Champarnaud, Ludovic Mignot:
  Erratum to "Acyclic automata and small expressions using multi-tilde-bar operators" [Theoret. Comput. Sci. 411 (38-39) (2010) 3423-3435]. 3795-3796

Volume 412, Number 30, July 2011

Prefaces

• 
  Grzegorz Rozenberg:
  Preface. 3797
• 
  Jarkko Kari:
  Preface. 3798-3799

Contributions

• 
  Martin Delacourt, Victor Poupet, Mathieu Sablik, Guillaume Theyssier:
  Directional dynamics along arbitrary curves in cellular automata. 3800-3821
• 
  Silvio Capobianco:
  Generalized Besicovitch and Weyl spaces: Topology, patterns, and sliding block codes. 3822-3837
• 
  Marcus Pivato:
  Positive expansiveness versus network dimension in symbolic dynamical systems. 3838-3855
• 
  Kenichi Morita:
  Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata. 3856-3865
• 
  Marianne Delorme, Jacques Mazoyer, Nicolas Ollinger, Guillaume Theyssier:
  Bulking I: An abstract theory of bulking. 3866-3880
• 
  Marianne Delorme, Jacques Mazoyer, Nicolas Ollinger, Guillaume Theyssier:
  Bulking II: Classifications of cellular automata. 3881-3905
• 
  Eric Goles Ch., Pierre Guillon, Ivan Rapaport:
  Traced communication complexity of cellular automata. 3906-3916
• 
  Martin Kutrib, Andreas Malcher:
  Cellular automata with limited inter-cell bandwidth. 3917-3931
• 
  Christopher L. Barrett, Harry B. Hunt III, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Richard Edwin Stearns:
  Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems. 3932-3946
• 
  Jean-Baptiste Rouquier, Damien Regnault, Eric Thierry:
  Stochastic minority on graphs. 3947-3963
• 
  Carolina Mejía, J. Andrés Montoya:
  On the complexity of sandpile critical avalanches. 3964-3974

Volume 412, Number 31, July 2011

Fundamental Study

• 
  Michal Krynicki, Jerzy Tomasik, Konrad Zdanowski:
  Theories of initial segments of standard models of arithmetics and their complete extensions. 3975-3991

Contributions

• 
  Rostislav Horcík, Kazushige Terui:
  Disjunction property and complexity of substructural logics. 3992-4006
• 
  David A. Basin, Carlos Caleiro, Jaime Ramos, Luca Viganò:
  Distributed temporal logic for the analysis of security protocol models. 4007-4043
• 
  Joachim Biskup, Lena Wiese:
  A sound and complete model-generation procedure for consistent and confidentiality-preserving databases. 4044-4072

Volume 412, Number 32, July 2011

Preface

• 
  Ding-Zhu Du, Yingfei Dong, Zhao Zhang:
  Preface. 4073

Contributions

• 
  Minming Li:
  Approximation algorithms for variable voltage processors: Min energy, max throughput and online heuristics. 4074-4080
• 
  Cristina Bazgan, Basile Couëtoux, Zsolt Tuza:
  Complexity and approximation of the Constrained Forest problem. 4081-4091
• 
  Robert Franke, Ignaz Rutter, Dorothea Wagner:
  Computing large matchings in planar graphs with fixed minimum degree. 4092-4099
• 
  Qian-Ping Gu, Hisao Tamaki:
  Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in O(n^1+ϵ) time. 4100-4109
• 
  Li Chen, Bin Fu:
  Linear and sublinear time algorithms for the basis of abelian groups. 4110-4122
• 
  Jonathan A. Kelner, Petar Maymounkov:
  Electric routing and concurrent flow cutting. 4123-4135
• 
  Raphael Eidenbenz, Roger Wattenhofer:
  Good programming in transactional memory: Game theory meets multicore architecture. 4136-4150
• 
  Johannes Schneider, Roger Wattenhofer:
  Bounds on contention management algorithms. 4151-4160
• 
  Therese Biedl, Stephane Durocher, Jack Snoeyink:
  Reconstructing polygons from scanner data. 4161-4172
• 
  Christian Knauer, Maarten Löffler, Marc Scherfenberg, Thomas Wolle:
  The directed Hausdorff distance between imprecise point sets. 4173-4186
• 
  Shuai Cheng Li, Yen Kaow Ng:
  On protein structure alignment under distance constraint. 4187-4199
• 
  Diego Arroyuelo, Francisco Claude, Reza Dorrigiv, Stephane Durocher, Meng He, Alejandro López-Ortiz, J. Ian Munro, Patrick K. Nicholson, Alejandro Salinger, Matthew Skala:
  Untangled monotonic chains and adaptive range search. 4200-4211
• 
  Ankur Narang, Rudrapatna K. Shyamasundar:
  Performance driven distributed scheduling of parallel hybrid computations. 4212-4225

Volume 412, Number 33, July 2011

Preface

• 
  Ajoy Kumar Datta, Franck Petit, Rachid Guerraoui:
  Stabilization, Safety, and Security of Distributed Systems (SSS 2009). 4227

Contributions

• 
  Fuad Abujarad, Sandeep S. Kulkarni:
  Automated constraint-based addition of nonmasking and stabilizing fault-tolerance. 4228-4246
• 
  Joffroy Beauquier, Janna Burman, Shay Kutten:
  A self-stabilizing transformer for population protocols with covering. 4247-4259
• 
  Martin Biely, Martin Hutle:
  Consensus when all processes may be Byzantine for some time. 4260-4272
• 
  François Bonnet, Michel Raynal:
  On the road to the weakest failure detector for k-set agreement in message-passing systems. 4273-4284
• 
  Alain Cournier, Swan Dubois, Vincent Villain:
  How to improve snap-stabilizing point-to-point communication space complexity? 4285-4296
• 
  Anurag Dasgupta, Sukumar Ghosh, Xin Xiao:
  Fault containment in weakly stabilizing systems. 4297-4311
• 
  K. Ghosh Dastidar, T. Herman:
  Separation of circulating tokens. 4312-4324
• 
  Mohamed G. Gouda, Hrishikesh B. Acharya:
  Nash equilibria in stabilizing systems. 4325-4335
• 
  Hirotsugu Kakugawa, Yukiko Yamauchi, Sayaka Kamei, Toshimitsu Masuzawa:
  Observations on non-silent self-stabilizing algorithms in sensor networks with probabilistically intermittent link failures. 4336-4349
• 
  Samia Souissi, Taisuke Izumi, Koichi Wada:
  Oracle-based flocking of mobile robots in crash-recovery model. 4350-4360
• 
  Volker Turau, Bernd Hauck:
  A fault-containing self-stabilizing (3 - 2/(Delta+1))-approximation algorithm for vertex cover in anonymous networks. 4361-4371

Volume 412, Number 34, August 2011

• 
  Benoît Caillaud, Benoît Delahaye, Kim G. Larsen, Axel Legay, Mikkel L. Pedersen, Andrzej Wasowski:
  Constraint Markov Chains. 4373-4404
• 
  Isabelle Gnaedig, Hélène Kirchner:
  Proving weak properties of rewriting. 4405-4438
• 
  Fernando Rosa-Velardo, David de Frutos-Escrig:
  Decidability and complexity of Petri nets with unordered data. 4439-4451
• 
  John G. Stell, Michael F. Worboys:
  Relations between adjacency trees. 4452-4468

Volume 412, Number 35, August 2011

In Memorium

• 
  Bruno Salvy, Bob Sedgewick, Michèle Soria, Wojciech Szpankowski, Brigitte Vallée:
  Philippe Flajolet, the Father of Analytic Combinatorics. 4469-4470

Contributions

• 
  Sylvie Delaët, Partha Sarathi Mandal, Mariusz A. Rokicki, Sébastien Tixeuil:
  Deterministic secure positioning in wireless sensor networks. 4471-4481
• 
  Guy Kortsarz, Zeev Nutov:
  Approximating some network design problems with node costs. 4482-4492
• 
  Guillaume Chèze, André Galligo, Bernard Mourrain, Jean-Claude Yakoubsohn:
  A subdivision method for computing nearest gcd with certification. 4493-4503
• 
  Ro-Yu Wu, Jou-Ming Chang, Kung-Jui Pai, Yue-Li Wang:
  Amortized efficiency of generating planar paths in convex position. 4504-4512
• 
  Yuan-Kang Shih, Shin-Shin Kao:
  One-to-one disjoint path covers on k-ary n-cubes. 4513-4530
• 
  Lily Chen, Xueliang Li, Yongtang Shi:
  The complexity of determining the rainbow vertex-connection of a graph. 4531-4535
• 
  Sergey Sevastyanov, Bertrand M. T. Lin, Hsiao-Lan Huang:
  Tight complexity analysis of the relocation problem with arbitrary release dates. 4536-4544
• 
  Maryam Shoaran, Alex Thomo:
  Evolving schemas for streaming XML. 4545-4557
• 
  Sheng-Hao Chiang, I-Chen Wu, Ping-Hung Lin:
  Drawn k-in-a-row games. 4558-4569
• 
  Hans L. Bodlaender, Stéphan Thomassé, Anders Yeo:
  Kernel bounds for disjoint cycles and disjoint paths. 4570-4578
• 
  Heidi Gebauer:
  Finding and enumerating Hamilton cycles in 4-regular graphs. 4579-4591
• 
  Amir Hashemi, Benyamin M.-Alizadeh:
  Applying IsRewritten criterion on Buchberger algorithm. 4592-4603
• 
  Alexander Meduna, Petr Zemek:
  Workspace theorems for regular-controlled grammars. 4604-4612
• 
  Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto:
  An exact algorithm for the Boolean connectivity problem for k-CNF. 4613-4618
• 
  Ashley Montanaro, Harumichi Nishimura, Rudy Raymond:
  Unbounded-error quantum query complexity. 4619-4628
• 
  S. Kanthi Kiran, N. S. Narayanaswamy:
  Hardness of subgraph and supergraph problems in c-tournaments. 4629-4635
• 
  Sook-Yeon Kim, Jae-Ha Lee, Jung-Heum Park:
  Disjoint path covers in recursive circulants G(2^m, 4) with faulty elements. 4636-4649
• 
  Akinobu Miyata, Jun Tarui, Etsuji Tomita:
  Learning Boolean functions in AC⁰ on attribute and classification noise - Estimating an upper bound on attribute and classification noise. 4650-4660
• 
  Yaniv Altshuler, Alfred M. Bruckstein:
  Static and expanding grid coverage with ant robots: Complexity results. 4661-4674
• 
  Nathann Cohen, David Coudert, Dorian Mazauric, Napoleão Nepomuceno, Nicolas Nisse:
  Tradeoffs in process strategy games with application in the WDM reconfiguration problem. 4675-4687
• 
  Stephan Kreutzer, Sebastian Ordyniak:
  Digraph decompositions and monotonicity in digraph searching. 4688-4703
• 
  Iyad A. Kanj, Andreas Wiese, Fenghui Zhang:
  Local algorithms for edge colorings in UDGs. 4704-4714
• 
  Daniel Perrucci:
  Linear solving for sign determination. 4715-4720
• 
  Damian Bogdanowicz, Krzysztof Giaro, Robert Janczewski:
  Consensus models: Computational complexity aspects in modern approaches to the list coloring problem. 4721-4728

Notes

• 
  Chae Hoon Lim:
  A note on the average number of RSA fixed points. 4729-4737
• 
  Thomas W. Cusick, Lavinia Corina Ciungu:
  Sum of digits sequences modulo m. 4738-4741
• 
  James D. Currie:
  Lexicographically least words in the orbit closure of the Rudin-Shapiro word. 4742-4746
• 
  Ruo-Wei Hung:
  Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes. 4747-4753

Volume 412, Number 36, August 2011

Preface

• 
  Srecko Brlek, Xavier Provençal:
  Advances in discrete geometry. 4755-4756

Contributions

• 
  Valérie Berthé:
  About thin arithmetic discrete planes. 4757-4769
• 
  Anders Kock:
  Affine connections, midpoint formation, and point reflection. 4770-4777
• 
  Alexandre Blondin Massé, Srecko Brlek, Ariane Garon, Sébastien Labbé:
  Two infinite families of polyominoes that tile the plane by translation in two distinct ways. 4778-4786
• 
  Olivier Bodini, Thomas Fernique, Michaël Rao, Eric Rémila:
  Distances on rhombus tilings. 4787-4794
• 
  Stefano Brocchi, Andrea Frosini, Simone Rinaldi:
  A reconstruction algorithm for a subclass of instances of the 2-color problem. 4795-4804
• 
  Henri-Alex Esbelin, Rémy Malgouyres, Colin Cartade:
  Convergence of binomial-based derivative estimation for C² noisy discretized curves. 4805-4813
• 
  Emilie Charrier, Fabien Feschet, Lilian Buzer:
  Computing efficiently the lattice width in any dimension. 4814-4823
• 
  Mohamed Tajine, Alain Daurat:
  Patterns for multigrid equidistributed functions: Application to general parabolas and length estimation. 4824-4840
• 
  Srecko Brlek, Michel Koskas, Xavier Provençal:
  A linear time and space algorithm for detecting path intersection in Z^d. 4841-4850

Volume 412, Number 37, August 2011

• 
  Mauricio Ayala-Rincón, Elaine Pimentel, Fairouz Kamareddine:
  Preface. 4851-4852
• 
  Camilo Rocha, César A. Muñoz, Gilles Dowek:
  A formal library of set relations and its application to synchronous languages. 4853-4866
• 
  Delia Kesner, Fabien Renaud:
  A prismoid framework for languages with resources. 4867-4892
• 
  Francicleber Martins Ferreira, Ana Teresa C. Martins:
  Recursive definitions and fixed-points on well-founded structures. 4893-4904
• 
  Jonathan P. Seldin:
  The search for a reduction in combinatory logic equivalent to λβ-reduction. 4905-4918
• 
  Feryal Fulya Horozal, Florian Rabe:
  Representing model theory in a type-theoretical logical framework. 4919-4945
• 
  Mario R. F. Benevides, Luis Menasché Schechter:
  A study on multi-dimensional products of graphs and hybrid logics. 4946-4966

Volume 412, Number 38, September 2011

Preface

• 
  Bart Jacobs, Milad Niqui, Jan J. M. M. Rutten, Alexandra Silva:
  Preface. 4967-4968

Contributions

• 
  Jirí Adámek, Stefan Milius, Jirí Velebil:
  On second-order iterative monads. 4969-4988
• 
  Adriana Balan, Alexander Kurz:
  On coalgebras over algebras. 4989-5005
• 
  Venanzio Capretta:
  Coalgebras in functional programming and type theory. 5006-5024
• 
  Corina Cîrstea:
  Maximal traces and path-based coalgebraic temporal logics. 5025-5042
• 
  Bartek Klin:
  Bialgebras for structural operational semantics: An introduction. 5043-5069
• 
  Clemens Kupke, Dirk Pattinson:
  Coalgebraic semantics of modal logics: An overview. 5070-5094
• 
  Ana Sokolova:
  Probabilistic systems coalgebraically: A survey. 5095-5110

Volume 412, Number 39, September 2011

• 
  Pawel Pralat, Changping Wang:
  An edge deletion model for complex networks. 5111-5120
• 
  Marcin Bienkowski, Marek Chrobak, Lukasz Jez:
  Randomized competitive algorithms for online buffer management in the adaptive adversary model. 5121-5131
• 
  Alexander Okhotin:
  Expressive power of LL(k) Boolean grammars. 5132-5155
• 
  Walter Didimo, Peter Eades, Giuseppe Liotta:
  Drawing graphs with right angle crossings. 5156-5166
• 
  Atsushi Murata, Akira Matsubayashi:
  Minimum energy broadcast on rectangular grid wireless networks. 5167-5175
• 
  Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung:
  Succinct data structures for Searchable Partial Sums with optimal worst-case performance. 5176-5186
• 
  Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle:
  Boolean-width of graphs. 5187-5204
• 
  Marcin Kaminski, Paul Medvedev, Martin Milanic:
  Shortest paths between shortest paths. 5205-5210
• 
  Kyungkuk Lim, Kangbok Lee, Soo Y. Chang:
  Improved bounds for online scheduling with eligibility constraints. 5211-5224
• 
  Ming Liu, Feifeng Zheng, Chengbin Chu, Yinfeng Xu:
  Optimal algorithms for online scheduling on parallel machines to minimize the makespan with a periodic availability constraint. 5225-5231
• 
  Narges Ghareghani, Morteza Mohammad Noori, Pouyeh Sharifani:
  On z-factorization and c-factorization of standard episturmian words. 5232-5238
• 
  Amihood Amir, Gad M. Landau, Joong Chae Na, Heejin Park, Kunsoo Park, Jeong Seop Sim:
  Efficient algorithms for consensus string problems minimizing both distance sum and radius. 5239-5246
• 
  Haitao Wang, Amitabh Chaudhary, Danny Z. Chen:
  Online rectangle filling. 5247-5275
• 
  Tero Harju, Tomi Kärki:
  On the number of frames in binary words. 5276-5284
• 
  Alex Thomo, Srinivasan Venkatesh:
  Rewriting of visibly pushdown languages for XML data integration. 5285-5297
• 
  Elliot Anshelevich, Bugra Çaskurlu:
  Exact and approximate equilibria for optimal group network formation. 5298-5314
• 
  Angelo Monti, Blerina Sinaimeri:
  Rainbow graph splitting. 5315-5324
• 
  Cédric Bentz:
  On the hardness of finding near-optimal multicuts in directed acyclic graphs. 5325-5332
• 
  Yang Fang, Xiwen Lu, Peihai Liu:
  Online batch scheduling on parallel machines with delivery times. 5333-5339
• 
  Wen-Qi Zhang, Yong-Jin Liu:
  Approximating the longest paths in grid graphs. 5340-5350
• 
  Ruo-Wei Hung, Maw-Shang Chang:
  An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs. 5351-5373
• 
  Shenghui Su, Shuwang Lü, Xiubin Fan:
  Asymptotic granularity reduction and its application. 5374-5386
• 
  Sujin Shin:
  Pseudo-cyclic renewal systems. 5387-5399
• 
  Emilie Charlier, Narad Rampersad:
  The growth function of S-recognizable sets. 5400-5408
• 
  Livio Colussi:
  The convergence classes of Collatz function. 5409-5419
• 
  Martin Hoefer, Vahab S. Mirrokni, Heiko Röglin, Shang-Hua Teng:
  Competitive routing over time. 5420-5432
• 
  Arnold Beckmann, Samuel R. Buss:
  Corrected upper bounds for free-cut elimination. 5433-5445
• 
  Guomin Yang, Chik How Tan:
  Certificateless cryptography with KGC trust level 3. 5446-5457
• 
  Qi Cheng, Yu-Hsin Li:
  On the minimum gap between sums of square roots of small integers. 5458-5465
• 
  Pinar Heggernes, Daniel Meister, Charis Papadopoulos:
  Graphs of linear clique-width at most 3. 5466-5486

Notes

• 
  Benjamin Steinberg:
  The Černý conjecture for one-cluster automata with prime length cycle. 5487-5491
• 
  Gwénaël Richomme, Patrice Séébold:
  On factorially balanced sets of words. 5492-5497

Review Article

• 
  Xiaofeng Chen, Willy Susilo, Fangguo Zhang, Haibo Tian, Jin Li:
  Identity-based trapdoor mercurial commitments and applications. 5498-5512

Volume 412, Number 40, September 2011

• 
  Shlomi Dolev, Sandeep S. Kulkarni, André Schiper:
  Preface. 5513-5514
• 
  Fredrik Manne, Morten Mjelde, Laurence Pilard, Sébastien Tixeuil:
  A self-stabilizing 2/3-approximation algorithm for the maximum matching problem. 5515-5526
• 
  Volker Turau, Bernd Hauck:
  A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2. 5527-5540
• 
  Ajoy Kumar Datta, Lawrence L. Larmore, Priyanka Vemula:
  Self-stabilizing leader election in optimal space under an arbitrary scheduler. 5541-5561
• 
  Jorge Arturo Cobb, Mohamed G. Gouda:
  Stabilization of max-min fair networks without per-flow state. 5562-5579
• 
  Peter Robinson, Ulrich Schmid:
  The Asynchronous Bounded-Cycle model. 5580-5601
• 
  Martin Biely, Ulrich Schmid, Bettina Weiss:
  Synchronous consensus under hybrid process and link failures. 5602-5630
• 
  Jaap-Henk Hoepman, Andreas Larsson, Elad Michael Schiller, Philippas Tsigas:
  Secure and self-stabilizing clock synchronization in sensor networks. 5631-5647

Volume 412, Number 41, September 2011

Contributions

• 
  L'ubomíra Balková, Edita Pelantová, Stepán Starosta:
  On Brlek-Reutenauer conjecture. 5649-5655
• 
  George Barmpalias, C. S. Vlek:
  Kolmogorov complexity of initial segments of sequences and arithmetical definability. 5656-5667
• 
  Cristian S. Calude, Kai Salomaa, Tania Roblot:
  Finite state complexity. 5668-5677
• 
  Alessandro Cincotti:
  The game of n-player Cutcake. 5678-5683
• 
  Alfredo De Santis, Anna Lisa Ferrara, Barbara Masucci:
  Efficient provably-secure hierarchical key assignment schemes. 5684-5699
• 
  Dariusz Dereniowski:
  Connected searching of weighted trees. 5700-5713
• 
  Christiane Frougny, Edita Pelantová, Milena Svobodová:
  Parallel addition in non-standard numeration systems. 5714-5727
• 
  Ilya Goldstein:
  Subword complexity of uniform D0L words over finite groups. 5728-5743
• 
  Gregory Z. Gutin, Mark Jones, Anders Yeo:
  Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems. 5744-5751
• 
  Adrian Kosowski, Alfredo Navarra, Maria Cristina Pinotti:
  Synchronous black hole search in directed graphs. 5752-5759
• 
  Sergio Rajsbaum, Jorge Urrutia:
  Some problems in distributed computational geometry. 5760-5770
• 
  Asaf Shiloni, Noa Agmon, Gal A. Kaminka:
  Of robot ants and elephants: A computational comparison. 5771-5788
• 
  Sherzod Turaev, Jürgen Dassow, Mohd Hasan Selamat:
  Nonterminal complexity of tree controlled grammars. 5789-5795

Notes

• 
  Andrew Drucker:
  Block sensitivity of minterm-transitive functions. 5796-5801
• 
  Pedro García, Damián López, José Ruiz, Gloria Inés Alvarez:
  From regular expressions to smaller NFAs. 5802-5807
• 
  Pierre-Cyrille Héam:
  On the complexity of computing the profinite closure of a rational language. 5808-5813

Volume 412, Number 42, September 2011

Preface

• 
  Grzegorz Rozenberg:
  Preface. 5815
• 
  Hung Son Nguyen, Sankar K. Pal, Andrzej Skowron:
  Rough sets and fuzzy sets in natural computing. 5816-5819

Contributions

• 
  Zoltán Csajbók:
  Approximation of sets based on partial covering. 5820-5833
• 
  Avatharam Ganivada, Soumitra Dutta, Sankar K. Pal:
  Fuzzy rough granular neural networks, fuzzy granules, and classification. 5834-5853
• 
  Danilo Horta, Ivan C. de Andrade, Ricardo J. G. B. Campello:
  Evolutionary fuzzy clustering of relational data. 5854-5870
• 
  Richard Jensen, Chris Cornelis:
  Fuzzy-rough nearest neighbour classification and prediction. 5871-5884
• 
  Pawan Lingras, Cory J. Butz:
  Conservative and aggressive rough SVR modeling. 5885-5901
• 
  Juan Lu, Sheng-Gang Li, Xiao-Fei Yang, Wen-Qing Fu:
  Categorical properties of M-indiscernibility spaces. 5902-5908
• 
  Nick J. Pizzi:
  Fuzzy quartile encoding as a preprocessing method for biomedical pattern classification. 5909-5925
• 
  Sheela Ramanna, Amir H. Meghdadi, James F. Peters:
  Nature-inspired framework for measuring visual image resemblance: A near rough set approach. 5926-5938
• 
  Andrzej Skowron, Piotr Wasilewski:
  Information systems in modeling interactive computations on granules. 5939-5959
• 
  Marcin S. Szczuka, Dominik Slezak:
  Feedforward neural networks for compound signals. 5960-5973

Volume 412, Number 43, October 2011

Preface

• 
  Grzegorz Rozenberg:
  Preface. 5975

Contributions

• 
  Roberto Barbuti, Andrea Maggiolo-Schettini, Paolo Milazzo, Giovanni Pardini:
  Spatial Calculus of Looping Sequences. 5976-6001
• 
  Francisco Chicano, L. Darrell Whitley, Enrique Alba, Francisco Luna:
  Elementary landscape decomposition of the frequency assignment problem. 6002-6019
• 
  Benjamin Doerr, Anton V. Eremeev, Frank Neumann, Madeleine Theile, Christian Thyssen:
  Evolutionary algorithms and dynamic programming. 6020-6035
• 
  Francesca Cordero, András Horváth, Daniele Manini, Lucia Napione, Massimiliano De Pierro, Simona Pavan, Andrea Picco, Andrea Veglio, Matteo Sereno, Federico Bussolino, Gianfranco Balbo:
  Simplification of a complex signal transduction model using invariants and flow equivalent servers. 6036-6057
• 
  Vashti Galpin:
  Equivalences for a biological process algebra. 6058-6082
• 
  Lila Kari, Benoît Masson:
  Polyominoes simulating arbitrary-neighborhood zippers and tilings. 6083-6100
• 
  Daniel Lobo, Francisco J. Vico, Jürgen Dassow:
  Graph grammars with string-regulated rewriting. 6101-6111

Erratum

• 
  David Soloveichik, Erik Winfree:
  Erratum to "The computational power of Benenson automata" [Theoret. Comput. Sci. 344 (2005) 279-297]. 6112-6113

Volume 412, Number 44, October 2011

• 
  Natasha Alechina, Mehdi Dastani, Brian Logan, John-Jules Ch. Meyer:
  Reasoning about plan revision in BDI agent programs. 6115-6134
• 
  Patrick Cousot, Radhia Cousot:
  Grammar semantics, analysis and parsing by abstract interpretation. 6135-6192
• 
  Koji Nakazawa, Makoto Tatsuta, Yukiyoshi Kameyama, Hiroshi Nakano:
  Type checking and typability in domain-free lambda calculi. 6193-6207
• 
  Amit Sasturkar, Ping Yang, Scott D. Stoller, C. R. Ramakrishnan:
  Policy analysis for Administrative Role-Based Access Control. 6208-6234

Volume 412, Number 45, October 2011

Contributions

• 
  Yohji Akama:
  Set systems: Order types, continuous nondeterministic deformations, and quasi-orders. 6235-6251
• 
  L'ubomíra Balková, Karel Brinda, Ondrej Turek:
  Abelian complexity of infinite words associated with quadratic Parry numbers. 6252-6260
• 
  Flavia Bonomo, Sara Mattia, Gianpaolo Oriolo:
  Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem. 6261-6268
• 
  Xin Chen, Yan Lan, Attila Benko, György Dósa, Xin Han:
  Optimal algorithms for online scheduling with bounded rearrangement at the end. 6269-6278
• 
  Eddie Cheng, Marc J. Lipman, László Lipták, David Sherman:
  Conditional matching preclusion for the arrangement graphs. 6279-6289
• 
  Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith:
  An exact algorithm for the Maximum Leaf Spanning Tree problem. 6290-6302
• 
  Peter J. Grabner, Wolfgang Steiner:
  Redundancy of minimal weight expansions in Pisot bases. 6303-6315
• 
  Xiangquan Gui, Xiaohong Hao, Yuanping Zhang, Xuerong Yong:
  A volume first maxima-finding algorithm. 6316-6326
• 
  Yun Bao Huang:
  The complexity of smooth words on 2-letter alphabets. 6327-6339
• 
  Takehiro Ito, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos:
  Parameterizing cut sets in a graph by the number of their components. 6340-6350
• 
  Stasys Jukna, Georg Schnitger:
  Yet harder knapsack problems. 6351-6358
• 
  Marcos A. Kiwi, Gonzalo Navarro, Claudio Telha:
  On-line approximate string matching with bounded errors. 6359-6370
• 
  Tomás Kulich:
  Dynamic monopolies with randomized starting configuration. 6371-6381
• 
  Prashant Kushwah, Sunder Lal:
  An efficient identity based generalized signcryption scheme. 6382-6389
• 
  Yaron Orenstein, Dana Ron:
  Testing Eulerianity and connectivity in directed sparse graphs. 6390-6408
• 
  Jung-Heum Park, Insung Ihm:
  Strong matching preclusion. 6409-6419
• 
  Adam Woryna:
  The concept of duality for automata over a changing alphabet and generation of a free group by such automata. 6420-6431
• 
  Tomoyuki Yamakami:
  Immunity and pseudorandomness of context-free languages. 6432-6450

Note

• 
  Wei Ren, Qing Zhao:
  A note on 'Algorithms for connected set cover problem and fault-tolerant connected set cover problem'. 6451-6454

Volume 412, Number 46, October 2011

Contributions

• 
  Alexandre Blondin Massé, Srecko Brlek, Sébastien Labbé, Laurent Vuillon:
  Palindromic complexity of codings of rotations. 6455-6463
• 
  Yuehua Bu, Yulin Li:
  Backbone coloring of planar graphs without special circles. 6464-6468
• 
  Ioannis Chatzigiannakis, Othon Michail, Stavros Nikolaou, Andreas Pavlogiannis, Paul G. Spirakis:
  Passively mobile communicating machines that use restricted space. 6469-6483
• 
  Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov:
  Guard games on graphs: Keep the intruder out! 6484-6497
• 
  Javier Herranz:
  Restricted adaptive oblivious transfer. 6498-6506
• 
  Roman Kolpakov, Michaël Rao:
  On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters. 6507-6516
• 
  Elizabeth Maltais, Lucia Moura:
  Hardness results for covering arrays avoiding forbidden edges and error-locating arrays. 6517-6530
• 
  Claudio Marini, Giulia Simi, Andrea Sorbi, Marianna Sorrentino:
  A note on algebras of languages. 6531-6536
• 
  Conrado Martínez, Alois Panholzer, Helmut Prodinger:
  The analysis of Range Quickselect and related problems. 6537-6555
• 
  Ana Moura:
  The word problem for omega-terms over DA. 6556-6569
• 
  Shiying Wang, Shurong Zhang:
  Embedding hamiltonian paths in k-ary n-cubes with conditional edge faults. 6570-6584

Volume 412, Number 47, November 2011

• 
  Massimo Merro, Francesco Ballardin, Eleonora Sibilio:
  A timed calculus for wireless systems. 6585-6611
• 
  Matthias Baaz, Agata Ciabattoni, Norbert Preining:
  First-order satisfiability in Gödel logics: An NP-complete fragment. 6612-6623

Volume 412, Number 48, November 2011

Contributions

• 
  Golnaz Badkobeh:
  Fewest repetitions versus maximal-exponent powers in infinite binary words. 6625-6633
• 
  Mukul S. Bansal, Jianrong Dong, David Fernández-Baca:
  Comparing and aggregating partially resolved trees. 6634-6652
• 
  Daniel Dombek, Zuzana Masáková, Edita Pelantová:
  Number representation using generalized (-beta)-transformation. 6653-6665
• 
  Leah Epstein, Hanan Zebedat-Haider:
  Online scheduling with rejection and withdrawal. 6666-6674
• 
  Joaquim Gabarró, Alina García, Maria J. Serna:
  The complexity of game isomorphism. 6675-6695
• 
  Xiaoyang Gu, Jack H. Lutz:
  Effective dimensions and relative frequencies. 6696-6711
• 
  Caixia Jing, Wanzhen Huang, Guochun Tang:
  Minimizing total completion time for re-entrant flow shop scheduling problems. 6712-6719
• 
  Changwook Kim:
  Quasi-rocking real-time pushdown automata. 6720-6735
• 
  Wonhong Nam, Hyunyoung Kil, Dongwon Lee:
  On the computational complexity of behavioral description-based web service composition. 6736-6749
• 
  Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis:
  On the independence number and Hamiltonicity of uniform random intersection graphs. 6750-6760
• 
  Daniël Paulusma, Johan M. M. van Rooij:
  On partitioning a graph into two connected subgraphs. 6761-6769
• 
  Vladimeros Vladimerou, Pavithra Prabhakar, Mahesh Viswanathan, Geir E. Dullerud:
  Specifications for decidable hybrid games. 6770-6785
• 
  Chaoxia Yang, Guojun Li:
  A polynomial time approximation scheme for embedding hypergraph in a weighted cycle. 6786-6793

Volume 412, Number 49, November 2011

• 
  Laura Bozzelli, Axel Legay, Sophie Pinchinat:
  Hardness of preorder checking for basic formalisms. 6795-6808
• 
  Sebastian Danicic, Richard W. Barraclough, Mark Harman, John Howroyd, Ákos Kiss, Michael R. Laurence:
  A unifying theory of control dependence and its application to arbitrary program structures. 6809-6842
• 
  Daniel Weller:
  On the elimination of quantifier-free cuts. 6843-6854

Volume 412, Number 50, November 2011

• 
  Carme Àlvarez, Maria J. Blesa, Maria J. Serna:
  The robustness of stability under link and node failures. 6855-6878
• 
  Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, Marco Molinaro:
  On the complexity of searching in trees and partially ordered structures. 6879-6896
• 
  Stuart MacLean, Suprakash Datta:
  The minimum positional error incurred by any connectivity-based positioning algorithm for mobile wireless systems. 6897-6912
• 
  Haisheng Tan, Tiancheng Lou, Yuexuan Wang, Qiang-Sheng Hua, Francis C. M. Lau:
  Exact algorithms to minimize interference in wireless sensor networks. 6913-6925
• 
  Jurek Czyzowicz, David Ilcinkas, Arnaud Labourel, Andrzej Pelc:
  Asynchronous deterministic rendezvous in bounded terrains. 6926-6937
• 
  Chao-Wen Huang, Hui-Ling Huang, Sun-Yuan Hsieh:
  Edge-bipancyclicity of star graphs with faulty elements. 6938-6947
• 
  Jens Maßberg, Jan Schneider:
  Rectangle packing with additional restrictions. 6948-6958
• 
  Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda:
  Verifying and enumerating parameterized border arrays. 6959-6981
• 
  Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
  Dominating set is fixed parameter tractable in claw-free graphs. 6982-7000
• 
  Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Daniel Meister, Saket Saurabh:
  Bandwidth on AT-free graphs. 7001-7008
• 
  Frantisek Kardos, Ján Katrenic, Ingo Schiermeyer:
  On computing the minimum 3-path vertex cover and dissociation number of graphs. 7009-7017
• 
  Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos:
  Faster parameterized algorithms for minor containment. 7018-7028
• 
  Zhongxuan Luo, Wenyu Hu, Dongwoo Sheen:
  The nearest complex polynomial with a zero in a given complex domain. 7029-7043
• 
  Jianhua Tu, Wenli Zhou:
  A primal-dual approximation algorithm for the vertex cover P₃ problem. 7044-7048
• 
  Zhigang Cao, Xiaoguang Yang:
  Selfish bin covering. 7049-7058

Note

• 
  Tamás Fleiner, Robert W. Irving, David F. Manlove:
  An algorithm for a super-stable roommates problem. 7059-7065

Volume 412, Number 51, December 2011

Preface

• 
  Grzegorz Rozenberg:
  Preface. 7067

Contributions

• 
  David A. Meyer, James Pommersheim:
  On the uselessness of quantum queries. 7068-7074
• 
  Daniel Manrique, Alfonso Rodríguez-Patón, Petr Sosík:
  On the scalability of biocomputing algorithms: The case of the maximum clique problem. 7075-7086

Volume 412, Number 52, December 2011

Contributions

• 
  Ariel Kulik, Hadas Shachnai, Oded Shmueli, Robert Sayegh:
  Approximation schemes for deal splitting and covering integer programs with multiplicity constraints. 7087-7098
• 
  Hajnal Andréka, Szabolcs Mikulás, István Németi:
  The equational theory of Kleene lattices. 7099-7108
• 
  Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Mordechai Shalom, Shmuel Zaks:
  Optimizing regenerator cost in traffic grooming. 7109-7121
• 
  Neil A. McKay:
  Canonical forms of uptimals. 7122-7132
• 
  George Barmpalias, Tom F. Sterkenburg:
  On the number of infinite sequences with trivial initial segment complexity. 7133-7146
• 
  Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang, Jiajie Zhu:
  Bounded budget betweenness centrality game for strategic network formations. 7147-7168

Erratum

• 
  Eric Goles Ch., Pierre-Etienne Meunier, Ivan Rapaport, Guillaume Theyssier:
  Erratum to: "Communication Complexity and Intrinsic Universality in Cellular Automata" [Theor. Comput. Sci 412 (1-2) (2011) 2-21]. 7169-7170