Theoretical Computer Science, Volume 410

Volume 410, Number 1, January 2009

• 
  Pinar Heggernes, Charis Papadopoulos:
  Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions. 1-15
• 
  Christian Choffrut, Serge Grigorieff:
  Finite n-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al. 16-34
• 
  Karol Suchan, Ioan Todinca:
  Minimal interval completion through graph exploration. 35-43
• 
  James D. Currie, Ali Aberkane:
  A cyclic binary morphism avoiding Abelian fourth powers. 44-52
• 
  Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, Stéphane Vialette:
  On the parameterized complexity of multiple-interval graph problems. 53-61
• 
  Maryam Shoaran, Alex Thomo:
  Fault-tolerant computation of distributed regular path queries. 62-77
• 
  Ruifang Liu, Zhonghua Lu, Jinlong Shu:
  The minimal Laplacian spectral radius of trees with a given diameter. 78-83
• 
  Surender Baswana, Vishrut Goyal, Sandeep Sen:
  All-pairs nearly 2-approximate shortest paths in I time. 84-93
• 
  Satoshi Ikeda, Izumi Kubo, Masafumi Yamashita:
  The hitting and cover times of random walks on finite graphs using local degree information. 94-100
• 
  Piotr Faliszewski, Lane A. Hemaspaandra:
  The complexity of power-index comparison. 101-107
• 
  Tomás Masopust:
  On the descriptional complexity of scattered context grammars. 108-112

Volume 410, Numbers 2-3, February 2009

• 
  Marcello M. Bonsangue, Einar Broch Johnsen, Amy L. Murphy, Jan Vitek:
  Preface. 113
• 
  Philippe Bidinger, Adriana B. Compagnoni:
  Pict correctness revisited. 114-127
• 
  Frank S. de Boer:
  A shared-variable concurrency analysis of multi-threaded object-oriented programs. 128-141
• 
  Sara Capecchi, Mario Coppo, Mariangiola Dezani-Ciancaglini, Sophia Drossopoulou, Elena Giachino:
  Amalgamating sessions and methods in object-oriented languages with generics. 142-167
• 
  John Field, Maria-Cristina V. Marinescu, Christian Stefansen:
  Reactors: A data-oriented synchronous/asynchronous programming model for distributed applications. 168-201
• 
  Philipp Haller, Martin Odersky:
  Scala Actors: Unifying thread-based and event-based programming. 202-220
• 
  Jean-Marie Jacquet, Isabelle Linden:
  Fully abstract models and refinements as tools to compare agents in timed coordination languages. 221-253
• 
  Peter Csaba Ölveczky, Stian Thorvaldsen:
  Formal modeling, performance estimation, and model checking of wireless sensor network algorithms in Real-Time Maude. 254-280

Volume 410, Numbers 4-5, February 2009

• 
  Grzegorz Rozenberg:
  Preface. 281-282
• 
  Paola Bonizzoni, S. Barry Cooper, Benedikt Löwe, Andrea Sorbi:
  Foreword. 283-284
• 
  Claudio Zandron:
  Nadia Busi (1968-2007). 285
• 
  Nadia Busi, Claudio Zandron:
  Computational expressiveness of Genetic Systems. 286-293
• 
  Anne Condon, Hosna Jabbari:
  Computational prediction of nucleic acid secondary structure: Methods, applications, and challenges. 294-301
• 
  Ellie D'Hondt:
  Quantum approaches to graph colouring. 302-309
• 
  Andrzej Ehrenfeucht, Grzegorz Rozenberg:
  Introducing time in reaction systems. 310-322
• 
  Carmine Garzillo, Giuseppe Trautteur:
  Computational virtuality in biological systems. 323-331
• 
  Natasa Jonoska, Gregory L. McColm:
  Complexity classes for self-assembling flexible tiles. 332-346
• 
  Bjørn Kjos-Hanssen, Anil Nerode:
  Effective dimension of points visited by Brownian motion. 347-354
• 
  Shankara Narayanan Krishna:
  Membrane computing with transport and embedded proteins. 355-375
• 
  James Ladyman:
  What does it mean to say that a physical system implements a computation? 376-383
• 
  James I. Lathrop, Jack H. Lutz, Scott M. Summers:
  Strict self-assembly of discrete Sierpinski triangles. 384-405
• 
  Remco Loos, Florin Manea, Victor Mitrana:
  On small, reduced, and fast universal accepting networks of splicing processors. 406-416
• 
  Florin Manea, Victor Mitrana, Takashi Yokomori:
  Two complementary operations inspired by the DNA hairpin formation: Completion and reduction. 417-425
• 
  Philip D. Welch:
  Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and Normal Form theorems. 426-442
• 
  Damien Woods, Turlough Neary:
  The complexity of small universal Turing machines: A survey. 443-450

Volume 410, Numbers 6-7, February 2009

• 
  Ivan Lavallée, Alexander A. Shvartsman:
  Editors' preface. 451-452
• 
  Baruch Awerbuch, Christian Scheideler:
  Robust random number generation for peer-to-peer systems. 453-466
• 
  Rida A. Bazzi, Young-ri Choi, Mohamed G. Gouda:
  Hop chains: Secure routing and the establishment of distinct identities. 467-480
• 
  Jurek Czyzowicz, Leszek Gasieniec, Andrzej Pelc:
  Gathering few fat mobile robots in the plane. 481-499
• 
  Murat Demirbas, Anish Arora, Vinodkrishnan Kulathumani:
  Glance: A lightweight querying service for wireless sensor networks. 500-513
• 
  Shlomi Dolev, Nir Tzachar:
  Empire of colonies: Self-stabilizing and self-organizing distributed algorithm. 514-532
• 
  Burkhard Englert:
  On the cost of uniform protocols whose memory consumption is adaptive to interval contention. 533-545
• 
  Seth Gilbert, Rachid Guerraoui, Calvin C. Newport:
  Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks. 546-569
• 
  Rachid Guerraoui, Maurice Herlihy, Bastian Pochon:
  A topological treatment of early-deciding set-agreement. 570-580
• 
  Colette Johnen, Le Huy Nguyen:
  Robust self-stabilizing weight-based clustering algorithm. 581-594
• 
  Marios Mavronicolas, Loizos Michael, Paul G. Spirakis:
  Computing on a partially eponymous ring. 595-613
• 
  Neeraj Mittal, Kuppahalli L. Phaneesh, Felix C. Freiling:
  Safe termination detection in an asynchronous distributed system when processes may crash and recover. 614-628
• 
  Heinrich Moser:
  Towards a real-time distributed computing model. 629-659

Volume 410, Numbers 8-10, March 2009

• 
  Deying Li, Hongwei Du, Peng-Jun Wan, Xiaofeng Gao, Zhao Zhang, Weili Wu:
  Construction of strongly connected dominating sets in asymmetric multihop wireless networks. 661-669
• 
  Marcos A. Kiwi, Mauricio Soto, Christopher Thraves:
  Adversarial queuing theory with setups. 670-687
• 
  Yong Gao:
  The degree distribution of random k-trees. 688-695
• 
  Selma Djelloul:
  Treewidth and logical definability of graph products. 696-710
• 
  Wolfgang W. Bein, Lawrence L. Larmore, Linda Morales, Ivan Hal Sudborough:
  A quadratic time 2-approximation algorithm for block sorting. 711-717
• 
  Jiong Guo:
  A more effective linear kernelization for cluster editing. 718-726
• 
  Yuchen Zhang, Xiaoming Sun:
  The antimagicness of the Cartesian product of graphs. 727-735
• 
  Willy Susilo:
  Short fail-stop signature scheme based on factorization and discrete logarithm assumptions. 736-744
• 
  Alexis C. Kaporis, Paul G. Spirakis:
  The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions. 745-755
• 
  Decheng Dai, Changyuan Yu:
  A 5+epsilon-approximation algorithm for minimum weighted dominating set in unit disk graph. 756-765
• 
  Ping-Ying Tsai, Jung-Sheng Fu, Gen-Huey Chen:
  Fault-free longest paths in star networks with conditional link faults. 766-775
• 
  C. T. Ng, Zhiyi Tan, Yong He, T. C. Edwin Cheng:
  Two semi-online scheduling problems on two uniform machines. 776-792
• 
  Francine Blanchet-Sadri, Robert Mercas, Geoffrey Scott:
  A generalization of Thue freeness for partial words. 793-800
• 
  Tzu-Liang Kung, Cheng-Kuan Lin, Tyne Liang, Lih-Hsing Hsu, Jimmy J. M. Tan:
  On the bipanpositionable bipanconnectedness of hypercubes. 801-811
• 
  Zhao Zhang, Xiaofeng Gao, Weili Wu:
  Algorithms for connected set cover problem and fault-tolerant connected set cover problem. 812-817
• 
  Jianer Chen, Iyad A. Kanj, Jie Meng, Ge Xia, Fenghui Zhang:
  On the pseudo-achromatic number problem. 818-829
• 
  Xianglai Qi, Shiguo Zhou, Jinjiang Yuan:
  Single machine parallel-batch scheduling with deteriorating jobs. 830-836
• 
  Aïda Ouangraoua, Pascal Ferraro:
  A constrained edit distance algorithm between semi-ordered trees. 837-846
• 
  Mathilde Bouvel, Dominique Rossin:
  A variant of the tandem duplication - random loss model of genome rearrangement. 847-858
• 
  Vera Asodi, Christopher Umans:
  The complexity of the matroid-greedoid partition problem. 859-866
• 
  Chi-Yuan Chan, Shan-Chyun Ku, Chi-Jen Lu, Biing-Feng Wang:
  Efficient algorithms for two generalized 2-median problems and the group median problem on trees. 867-876
• 
  Jianping Li, Weidong Li, Tongquan Zhang, Zhongxu Zhang:
  The subdivision-constrained minimum spanning tree problem. 877-885
• 
  Alessandro Ferrante, Gennaro Parlato, Francesco Sorrentino, Carmine Ventre:
  Fast payment schemes for truthful mechanisms with verification. 886-899
• 
  Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto:
  Efficient algorithms to compute compressed longest common substrings and compressed palindromes. 900-913
• 
  Hisashi Koga:
  Dynamic TCP acknowledgment with sliding window. 914-925
• 
  Sun-Yuan Hsieh, Chang-Jen Tu:
  Constructing edge-disjoint spanning trees in locally twisted cubes. 926-932
• 
  Spyros C. Kontogiannis, Paul G. Spirakis:
  On the support size of stable strategies in random games. 933-942
• 
  Vesa Halava, Tero Harju, Tomi Kärki, Patrice Séébold:
  Overlap-freeness in infinite partial words. 943-948
• 
  Jean Cardinal, Stefan Langerman, Eythan Levy:
  Improved approximation bounds for edge dominating set in dense graphs. 949-957
• 
  Travis Gagie:
  Compressed depth sequences. 958-962
• 
  Sung-Pil Hong, Myoung-Ju Park, Soo Y. Chang:
  Approximation of the k-batch consolidation problem. 963-967
• 
  Francine Blanchet-Sadri, Raphaël M. Jungers, Justin Palumbo:
  Testing avoidability on sets of partial words is hard. 968-972
• 
  Pablo Sáez:
  A quadratic algorithm for the 2-cyclic robotic scheduling problem. 973-976
• 
  Yury L. Orlovich, Valery S. Gordon, Dominique de Werra:
  On the inapproximability of independent domination in 2P₃-free perfect graphs. 977-982
• 
  Cinzia Pizzi:
  k-difference matching in amortized linear time for all the words in a text. 983-987
• 
  Tsung-Hsi Tsai:
  Efficient computation of the iteration of functions. 988-993
• 
  Martin Wahlen:
  On the complexity of approximating the Hadwiger number. 994-996
• 
  Juha Honkala:
  On the simplification of infinite morphic words. 997-1000

Volume 410, Number 11, March 2009

• 
  S. Barry Cooper, Hong Zhu:
  Preface: Algorithms, complexity and models of computation. 1001-1002
• 
  Vincent Danos, Linus J. Schumacher:
  How liquid is biological signalling? 1003-1012
• 
  Minming Li, Ze Feng, Nan Zang, Ronald L. Graham, Frances F. Yao:
  Approximately optimal trees for group key management with batch updates. 1013-1021
• 
  Wangsen Feng, Li'ang Zhang, Hanpin Wang:
  Approximation algorithm for maximum edge coloring. 1022-1029
• 
  Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk, Christian Schindelhauer:
  Improving the average delay of sorting. 1030-1041
• 
  Angsheng Li:
  Elementary differences among jump classes. 1042-1053
• 
  Hiroki Morizumi, Jun Tarui:
  Linear-size log-depth negation-limited inverter for k-tonic binary sequences. 1054-1060
• 
  Akifumi Kawaguchi, Hiroshi Nagamochi:
  Drawing slicing graphs with face areas. 1061-1072
• 
  He Sun, Chung Keung Poon:
  Two improved range-efficient algorithms for F₀ estimation. 1073-1080
• 
  Yingchao Zhao, Shang-Hua Teng:
  Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces. 1081-1092
• 
  Peng Zhang, Mingji Xia:
  An approximation algorithm to the k-Steiner Forest problem. 1093-1098
• 
  Andrew Chi-Chih Yao, Frances F. Yao, Yunlei Zhao:
  A note on universal composable zero-knowledge in the common reference string model. 1099-1108

Volume 410, Numbers 12-13, March 2009

• 
  Andrei Popescu, Traian-Florin Serbanuta, Grigore Rosu:
  A semantic approach to interpolation. 1109-1128
• 
  H. Peter Gumm:
  Copower functors. 1129-1142
• 
  Simone Bova, Franco Montagna:
  The consequence relation in the logic of commutative GBL-algebras is PSPACE-complete. 1143-1158
• 
  Murdoch James Gabbay:
  A study of substitution, using nominal techniques and Fraenkel-Mostowksi sets. 1159-1189
• 
  Robert Lorenz, Gabriel Juhás, Robin Bergenthum, Jörg Desel, Sebastian Mauser:
  Executability of scenarios in Petri nets. 1190-1216
• 
  Lutz Schröder, Till Mossakowski:
  HasCasl: Integrated higher-order specification and program development. 1217-1260
• 
  Jan A. Bergstra, Yoram Hirshfeld, John V. Tucker:
  Meadows and the equational specification of division. 1261-1271
• 
  Marta Z. Kwiatkowska, Gethin Norman, David Parker, Maria Grazia Vigliotti:
  Probabilistic Mobile Ambients. 1272-1303

Volume 410, Number 14, March 2009

• 
  Giuseppe Prencipe, Shmuel Zaks:
  Preface. 1305-1306
• 
  Nicolas Nisse, David Soguet:
  Graph searching with advice. 1307-1318
• 
  Hajo Broersma, Matthew Johnson, Daniël Paulusma:
  Upper bounds and algorithms for parallel knock-out numbers. 1319-1327
• 
  Eli Gafni, Achour Mostéfaoui, Michel Raynal, Corentin Travers:
  From adaptive renaming to set agreement. 1328-1335
• 
  Fredrik Manne, Morten Mjelde, Laurence Pilard, Sébastien Tixeuil:
  A new self-stabilizing maximal matching algorithm. 1336-1345
• 
  Peter Korteweg, Alberto Marchetti-Spaccamela, Leen Stougie, Andrea Vitaletti:
  Data aggregation in sensor networks: Balancing communication and delay costs. 1346-1354
• 
  Asaf Efrima, David Peleg:
  Distributed algorithms for partitioning a swarm of autonomous mobile robots. 1355-1368
• 
  Guy Even, Tamir Levi, Ami Litman:
  Optimal conclusive sets for comparator networks. 1369-1376
• 
  Rastislav Kralovic, Richard Královic:
  Rapid almost-complete broadcasting in faulty networks. 1377-1387
• 
  Jurek Czyzowicz, Stefan Dobrev, Evangelos Kranakis, Jaroslav Opatrny, Jorge Urrutia:
  Local edge colouring of Yao-like subgraphs of Unit Disk Graphs. 1388-1400
• 
  Amos Korman, Shay Kutten:
  A note on models for graph representations. 1401-1412

Volume 410, Number 15, April 2009

• 
  Grzegorz Rozenberg:
  Preface. 1413-1414
• 
  Natasa Jonoska, Jarkko Kari:
  Preface. 1415-1416
• 
  Sam Greenberg, Dana Randall:
  Convergence rates of Markov chains for some self-assembly and non-saturated Ising models. 1417-1427
• 
  John H. Reif, Sudheer Sahu:
  Autonomous programmable DNA nanorobotic devices using DNAzymes. 1428-1439
• 
  N. E. Grayson, Anne Taormina, Reidun Twarock:
  DNA duplex cage structures with icosahedral symmetry. 1440-1447
• 
  Natasa Jonoska, Nadrian C. Seeman, Gang Wu:
  On existence of reporter strands in DNA-based graph structures. 1448-1460
• 
  Yuriy Brun, Dustin Reishus:
  Path finding in the tile assembly model. 1461-1472

Volume 410, Number 16, April 2009

• 
  Grzegorz Rozenberg:
  Preface. 1473-1474
• 
  Natasa Jonoska, Jarkko Kari:
  Preface. 1475-1476
• 
  Marcella Anselmo, Maria Madonia:
  Deterministic and unambiguous two-dimensional languages over one-letter alphabet. 1477-1485
• 
  Robert Brijder, Hendrik Jan Hoogeboom:
  Perfectly quilted rectangular snake tilings. 1486-1494
• 
  Florent Becker:
  Pictures worth a thousand tiles, a geometrical programming language for self-assembly. 1495-1515
• 
  Ville Lukkarila:
  The 4-way deterministic tiling problem is undecidable. 1516-1533
• 
  Chaim Goodman-Strauss:
  Regular production systems and triangle tilings. 1534-1549

Volume 410, Number 17, April 2009

• 
  Paul G. Spirakis, Marios Mavronicolas, Spyros C. Kontogiannis:
  Preface. 1551
• 
  Heiner Ackermann, Heiko Röglin, Berthold Vöcking:
  Pure Nash equilibria in player-specific and weighted congestion games. 1552-1563
• 
  Davide Bilò, Luciano Gualà, Guido Proietti:
  Dynamic mechanism design. 1564-1572
• 
  Xi Chen, Li-Sha Huang, Shang-Hua Teng:
  Market equilibria with hybrid linear-Leontief utilities. 1573-1580
• 
  Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou:
  A note on approximate Nash equilibria. 1581-1588
• 
  Nicole Immorlica, Li (Erran) Li, Vahab S. Mirrokni, Andreas S. Schulz:
  Coordination mechanisms for selfish scheduling. 1589-1598
• 
  Spyros C. Kontogiannis, Panagiota N. Panagopoulou, Paul G. Spirakis:
  Polynomial algorithms for approximating Nash equilibria of bimatrix games. 1599-1606
• 
  Paolo Penna, Guido Proietti, Peter Widmayer:
  Strongly polynomial-time truthful mechanisms in one shot. 1607-1615

Volume 410, Number 18, April 2009

• 
  Lars Arge, Christian Cachin, Andrzej Tarlecki:
  Preface. 1617
• 
  Jin-yi Cai, Pinyan Lu:
  Holographic algorithms: The power of dimensionality resolved. 1618-1628
• 
  Benoît Larose, Pascal Tesson:
  Universal algebra and hardness results for constraint satisfaction problems. 1629-1647
• 
  Johannes Blömer, Stefanie Naewe:
  Sampling methods for shortest vectors, closest vectors and successive minima. 1648-1665
• 
  Albert Atserias, Andrei A. Bulatov, Anuj Dawar:
  Affine systems of equations and counting infinitary logic. 1666-1683
• 
  Manuel Bodirsky, Hubie Chen, Jan Kára, Timo von Oertzen:
  Maximal infinite-valued constraint languages. 1684-1693
• 
  Bernard Boigelot, Julien Brusten:
  A generalization of Cobham's theorem to automata over real numbers. 1694-1703
• 
  Marcelo P. Fiore, Chung-Kil Hur:
  On the construction of free algebras for equational systems. 1704-1729
• 
  Yuval Ishai, Tal Malkin, Martin J. Strauss, Rebecca N. Wright:
  Private multiparty sampling and approximation of vector combinations. 1730-1745

Volume 410, Number 19, April 2009

• 
  Marcus Hutter, Rocco A. Servedio:
  Preface. 1747-1748
• 
  Markus Maier, Matthias Hein, Ulrike von Luxburg:
  Optimal construction of k-nearest-neighbor graphs for identifying noisy clusters. 1749-1764
• 
  Kevin L. Chang:
  Multiple pass streaming algorithms for learning mixtures of distributions in R^d. 1765-1780
• 
  Vladimir V. V'yugin:
  On calibration error of randomized forecasting algorithms. 1781-1795
• 
  Sanjay Jain, Frank Stephan, Nan Ye:
  Prescribed learning of r.e. classes. 1796-1806
• 
  Ryo Yoshinaka:
  Learning efficiency of very simple grammars from positive data. 1807-1825
• 
  M. M. Hassan Mahmud:
  On universal transfer learning. 1826-1846
• 
  Kilho Shin, Tetsuji Kuboyama:
  Polynomial summaries of positive semidefinite kernels. 1847-1862
• 
  John Case, Samuel E. Moelius:
  Parallelism increases iterative learning power. 1863-1875
• 
  Jean-Yves Audibert, Rémi Munos, Csaba Szepesvári:
  Exploration-exploitation tradeoff using variance estimates in multi-armed bandits. 1876-1902
• 
  Vitaly Feldman, Shrenik Shah:
  Separating models of learning with faulty teachers. 1903-1912

Volume 410, Number 20, May 2009

• 
  Grzegorz Rozenberg:
  Preface. 1913-1914
• 
  Mika Hirvensalo:
  Preface. 1915
• 
  Andris Ambainis, Nikolajs Nahimovs:
  Improved constructions of quantum automata. 1916-1922
• 
  Rusins Freivalds, Maris Ozols, Laura Mancinska:
  Improved constructions of mixed state quantum automata. 1923-1931
• 
  Abuzer Yakaryilmaz, A. C. Cem Say:
  Efficient probability amplification in two-way quantum finite automata. 1932-1941
• 
  Marats Golovkins, Maksim Kravtsev, Vasilijs Kravcevs:
  On a class of languages recognizable by probabilistic reversible decide-and-halt automata. 1942-1951
• 
  Ilze Dzelme-Berzina:
  Mathematical logic and quantum finite state automata. 1952-1959

Volume 410, Numbers 21-23, May 2009

• 
  Alexander Meduna, Jirí Techet:
  An infinite hierarchy of language families generated by scattered context grammars with n-limited derivations. 1961-1969
• 
  Pierre Fraigniaud, Cyril Gavoille, Adrian Kosowski, Emmanuelle Lebhar, Zvi Lotker:
  Universal augmentation schemes for network navigability. 1970-1981
• 
  Guanghui Wang, Guizhen Liu:
  Paths, cycles and circular colorings in digraphs. 1982-1985
• 
  Marcus Oswald, Gerhard Reinelt:
  The simultaneous consecutive ones problem. 1986-1992
• 
  Isaac Elias, Jens Lagergren:
  Fast neighbor joining. 1993-2000
• 
  Jinn-Shyong Yang, Jou-Ming Chang, Shyue-Ming Tang, Yue-Li Wang:
  On the independent spanning trees of recursive circulant graphs G(cd^m, d) with d>2. 2001-2010
• 
  Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang:
  Non-mitotic sets. 2011-2023
• 
  Wenbin Chen, Matthew C. Schmidt, Nagiza F. Samatova:
  On parameterized complexity of the Multi-MCS problem. 2024-2032
• 
  Adrien Guignard, Éric Sopena:
  Compound Node-Kayles on paths. 2033-2044
• 
  Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, Stefan Szeider:
  Covering graphs with few complete bipartite subgraphs. 2045-2053
• 
  Stefan S. Dantchev, Barnaby Martin, Mark Nicholas Charles Rhodes:
  Tight rank lower bounds for the Sherali-Adams proof system. 2054-2063
• 
  Takayuki Nagoya, Seinosuke Toda:
  Computational complexity of computing a partial solution for the Graph Automorphism problems. 2064-2071
• 
  Liliana Alcón, Luérbio Faria, Celina M. H. de Figueiredo, Marisa Gutierrez:
  The complexity of clique graph recognition. 2072-2083
• 
  Ilya Goldstein:
  Asymptotic subword complexity of fixed points of group substitutions. 2084-2098
• 
  Ming Liu, Yinfeng Xu, Chengbin Chu, Feifeng Zheng:
  Online scheduling on two uniform machines to minimize the makespan. 2099-2109
• 
  Roberto Baldoni, Silvia Bonomi, Leonardo Querzoni, Sara Tucci Piergiovanni:
  Investigating the existence and the regularity of Logarithmic Harary Graphs. 2110-2121
• 
  Yuval Lando, Zeev Nutov:
  Inapproximability of survivable networks. 2122-2125
• 
  Marie-Andrée Jacob-Da Col, Pierre Tellier:
  Quasi-linear transformations and discrete tilings. 2126-2134
• 
  Alessandra Cherubini, Andrzej Kisielewicz:
  Collapsing words, permutation conditions and coherent colorings of trees. 2135-2147
• 
  Daniel Reidenbach, Johannes C. Schneider:
  Morphically primitive words. 2148-2161
• 
  Xingwu Liu, Zhiwei Xu, Jianzhong Pan:
  Classifying rendezvous tasks of arbitrary dimension. 2162-2173
• 
  Amos Beimel, Boaz Ben-Moshe, Yehuda Ben-Shimol, Paz Carmi, Eldad Chai, Itzik Kitroser, Eran Omri:
  Matrix columns allocation problems. 2174-2183
• 
  Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos:
  Efficient approximation of min set cover by moderately exponential algorithms. 2184-2195
• 
  Changyuan Yu:
  Truthful mechanisms for two-range-values variant of unrelated scheduling. 2196-2206
• 
  Stefano Galatolo, Mathieu Hoyrup, Cristobal Rojas:
  A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties. 2207-2222
• 
  Chih-Wei Yi:
  Maximum scan statistics and channel assignment problems in homogeneous wireless networks. 2223-2233
• 
  Benjamin Lévêque, Frédéric Maffray, Bruce A. Reed, Nicolas Trotignon:
  Coloring Artemis graphs. 2234-2240
• 
  Hans-Joachim Böckenhauer, Joachim Kneis, Joachim Kupke:
  Approximation hardness of deadline-TSP reoptimization. 2241-2249
• 
  Sándor Vágvölgyi:
  Deterministic bottom-up tree transducers and ground term rewrite systems. 2250-2278
• 
  Conrado Martínez, Helmut Prodinger:
  Moves and displacements of particular elements in Quicksort. 2279-2284
• 
  Shang-Wei Zhao, Xiao-Shan Gao:
  Minimal achievable approximation ratio for MAX-MQ in finite fields. 2285-2290
• 
  Ji Tian, Ruyan Fu, Jinjiang Yuan:
  A best online algorithm for scheduling on two parallel batch machines. 2291-2294
• 
  Jan Hoffmann:
  Finding a tree structure in a resolution proof is NP-complete. 2295-2300

Volume 410, Numbers 24-25, May 2009

Contributions

• 
  Artiom Alhazov, Ion Petre, Vladimir Rogojin:
  The parallel complexity of signed graphs: Decidability results and an improved algorithm. 2308-2315
• 
  Ying Cai, Cunsheng Ding:
  Binary sequences with optimal autocorrelation. 2316-2322
• 
  Cristian S. Calude, Helmut Jürgensen, Ludwig Staiger:
  Topology on words. 2323-2335
• 
  Cezar Câmpeanu, Nicolae Santean:
  On the intersection of regex languages with regular languages. 2336-2344
• 
  Julien Cassaigne, Juhani Karhumäki, Petri Salmela:
  Conjugacy of finite biprefix codes. 2345-2351
• 
  Matteo Cavaliere, Oscar H. Ibarra, Gheorghe Paun, Ömer Egecioglu, Mihai Ionescu, Sara Woodworth:
  Asynchronous spiking neural P systems. 2352-2364
• 
  Shihyen Chen, Bin Ma, Kaizhong Zhang:
  On the similarity metric and the distance metric. 2365-2376
• 
  Michael Domaratzki, Alexander Okhotin:
  State complexity of power. 2377-2392
• 
  Lila Kari, Kalpana Mahalingam, Shinnosuke Seki:
  Twin-roots of words and their properties. 2393-2400
• 
  Dalia Krieger, Avery Miller, Narad Rampersad, Bala Ravikumar, Jeffrey O. Shallit:
  Decimations of languages and state complexity. 2401-2409
• 
  Shuai Cheng Li, Ming Li:
  On two open problems of 2-interval patterns. 2410-2423
• 
  Andrei Paun, Mihaela Paun, Alfonso Rodríguez-Patón:
  On the Hopcroft's minimization technique for DFA and DFCA. 2424-2430
• 
  Narad Rampersad, Nicolae Santean, Jeffrey O. Shallit, Bala Ravikumar:
  State complexity of unique rational operations. 2431-2441
• 
  Hsu-Chun Yen, Chien-Liang Chen:
  On minimal elements of upward-closed sets. 2442-2452

Volume 410, Number 26, June 2009

Preface

• 
  Grzegorz Rozenberg:
  Preface. 2453-2454

Contributions

• 
  Tobias Friedrich, Nils Hebbinghaus, Frank Neumann:
  Comparison of simple diversity mechanisms on plateau functions. 2455-2462
• 
  Rahul Jain, Shengyu Zhang:
  New bounds on classical and quantum one-way communication complexity. 2463-2477
• 
  Xingyi Zhang, Xiangxiang Zeng, Linqiang Pan:
  On languages generated by asynchronous spiking neural P systems. 2478-2488
• 
  Anne Broadbent, Elham Kashefi:
  Parallelizing quantum circuits. 2489-2510
• 
  Dirk Sudholt:
  The impact of parametrization in memetic evolutionary algorithms. 2511-2528

Note

• 
  Lvzhou Li, Daowen Qiu:
  A note on quantum sequential machines. 2529-2535

Volume 410, Numbers 27-29, June 2009

Contributions

• 
  Yo-Sub Han, Kai Salomaa:
  State complexity of basic operations on suffix-free regular languages. 2537-2548
• 
  Petra Berenbrink, Colin Cooper, Zengjian Hu:
  Energy efficient randomised communication in unknown AdHoc networks. 2549-2561
• 
  Sanjay Jain, Efim B. Kinber:
  One-shot learners using negative counterexamples and nearest positive examples. 2562-2580
• 
  Chi-Shiang Su, Jason Chao-Hsien Pan, Tsung-Shin Hsu:
  A new heuristic algorithm for the machine scheduling problem with job delivery coordination. 2581-2591
• 
  Mayur Thakur, Rahul Tripathi:
  Linear connectivity problems in directed hypergraphs. 2592-2618
• 
  Weiwei Wu, Minming Li, Enhong Chen:
  Optimal tree structures for group key tree management considering insertion and deletion cost. 2619-2631
• 
  Jung-Heum Park, Sang Hyuk Son:
  Conditional matching preclusion for hypercube-like interconnection networks. 2632-2640
• 
  Jianer Chen, Iyad A. Kanj, Ge Xia:
  On parameterized exponential time complexity. 2641-2648
• 
  David Harvey:
  A cache-friendly truncated FFT. 2649-2658
• 
  Sanchit Garg, Éric Schost:
  Interpolation of polynomials given by straight-line programs. 2659-2662
• 
  Bin Fu, Yumei Huo, Hairong Zhao:
  Exponential inapproximability and FPTAS for scheduling with availability constraints. 2663-2674
• 
  Soonjo Hong, Sujin Shin:
  Cyclic renewal systems. 2675-2684
• 
  Jean B. Lasserre, Monique Laurent, Philipp Rostalski:
  A prolongation-projection algorithm for computing the finite real variety of an ideal. 2685-2700
• 
  F. De Carli, Andrea Frosini, Simone Rinaldi, Andrea Sorbi:
  Lattices of local two-dimensional languages. 2701-2713
• 
  Ching-Lueh Chang, Yuh-Dauh Lyuu:
  Spreading messages. 2714-2724
• 
  Josep Díaz, Fabrizio Grandoni, Alberto Marchetti-Spaccamela:
  Balanced cut approximation in random geometric graphs. 2725-2731
• 
  Zhigang Cao, Xiaoguang Yang:
  A PTAS for parallel batch scheduling with rejection and dynamic job arrivals. 2732-2745
• 
  Hong Liu, Haodi Feng, Daming Zhu, Junfeng Luan:
  Parameterized computational complexity of control problems in voting systems. 2746-2753

Notes

• 
  Ali Husseinzadeh Kashan, Behrooz Karimi, S. M. T. Fatemi Ghomi:
  A note on minimizing makespan on a single batch processing machine with nonidentical job sizes. 2754-2758
• 
  Yoshifumi Sakai:
  Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence. 2759-2766
• 
  Nicolas Ollinger, Gaétan Richard:
  Automata on the plane vs particles and collisions. 2767-2773
• 
  Mark Nicholas Charles Rhodes:
  On the Chvátal rank of the Pigeonhole Principle. 2774-2778
• 
  L'ubomíra Balková, Edita Pelantová:
  A note on symmetries in the Rauzy graph and factor frequencies. 2779-2783

Volume 410, Numbers 30-32, August 2009

Contributions

• 
  Jean-Paul Allouche, Narad Rampersad, Jeffrey O. Shallit:
  Periodicity, repetitions, and orbits of an automatic sequence. 2795-2803
• 
  Pawel Baturo, Wojciech Rytter:
  Compressed string-matching in standard Sturmian words. 2804-2810
• 
  Jean Berstel, Luc Boasson, Olivier Carton:
  Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm. 2811-2822
• 
  Vincent D. Blondel, Julien Cassaigne, Raphaël M. Jungers:
  On the number of alpha-power-free binary words for 2alpha<=7/3. 2823-2833
• 
  Dongbo Bu, Ming Li, Shuai Cheng Li, Jianbo Qian, Jinbo Xu:
  Finding compact structural motifs. 2834-2839
• 
  Michelangelo Bucci, Aldo de Luca, Alessandro De Luca:
  Characteristic morphisms of generalized episturmian words. 2840-2859
• 
  Michelangelo Bucci, Alessandro De Luca, Amy Glen, Luca Q. Zamboni:
  A new characteristic property of rich words. 2860-2863
• 
  Yann Bugeaud, Christophe Reutenauer, Samir Siksek:
  A Sturmian sequence related to the uniqueness conjecture for Markoff numbers. 2864-2869
• 
  Christian Choffrut, Serge Grigorieff:
  The "equal last letter" predicate for words on infinite alphabets and classes of multitape automata. 2870-2884
• 
  James D. Currie, Narad Rampersad:
  Dejean's conjecture holds for n>=30. 2885-2888
• 
  Elena Czeizler, Wojciech Plandowski:
  On systems of word equations over three unknowns with at most six occurrences of one of the unknowns. 2889-2909
• 
  Jürgen Dassow, Gema M. Martín, Francisco J. Vico:
  Some operations preserving primitivity of words. 2910-2919
• 
  Josep Díaz, Lefteris M. Kirousis, Dieter Mitsche, Xavier Pérez-Giménez:
  On the satisfiability threshold of formulas with three literals per clause. 2920-2934
• 
  Volker Diekert, Dalia Krieger:
  Some remarks about stabilizers. 2935-2946
• 
  Anna E. Frid:
  Simple equations on binary factorial languages. 2947-2956
• 
  Vesa Halava, Jarkko Kari, Yuri V. Matiyasevich:
  On post correspondence problem for letter monotonic languages. 2957-2960
• 
  Yo-Sub Han, Kai Salomaa:
  Nondeterministic state complexity of nested word automata. 2961-2971
• 
  Juraj Hromkovic, Holger Petersen, Georg Schnitger:
  On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's. 2972-2981
• 
  Oscar H. Ibarra, Andrei Paun, Alfonso Rodríguez-Patón:
  Sequential SNP systems based on min/max spike number. 2982-2991
• 
  I. A. Mikhailova, Mikhail V. Volkov:
  Pattern avoidance by palindromes. 2992-2998
• 
  François Nicolas, Veli Mäkinen, Esko Ukkonen:
  Efficient construction of maximal and minimal representations of motifs of a string. 2999-3005
• 
  Daowen Qiu, Sheng Yu:
  Hierarchy and equivalence of multi-letter quantum finite automata. 3006-3017
• 
  Antonio Restivo, Giovanna Rosone:
  Burrows-Wheeler transform and palindromic richness. 3018-3026
• 
  Robert Tijdeman, Luca Q. Zamboni:
  Fine and Wilf words for any periods II. 3027-3034

Volume 410, Numbers 33-34, August 2009

Preface

• 
  Grzegorz Rozenberg:
  Preface. 3035-3036
• 
  Nicola Cannata, Emanuela Merelli:
  Preface. 3037-3038

Contributions

• 
  Cristian Versari, Nadia Busi:
  Stochastic biological modelling in the presence of multiple compartments. 3039-3064
• 
  Federica Ciocchetta, Jane Hillston:
  Bio-PEPA: A framework for the modelling and analysis of biological systems. 3065-3084
• 
  Roberto Barbuti, Giulio Caravagna, Andrea Maggiolo-Schettini, Paolo Milazzo:
  An intermediate language for the stochastic simulation of biological systems. 3085-3109
• 
  Chiara Bodei:
  A Control Flow Analysis for Beta-binders with and without static compartments. 3110-3127
• 
  Jiri Barnat, Lubos Brim, Ivana Cerná, Sven Drazan, Jana Fabriková, David Safránek:
  On algorithmic analysis of transcriptional regulation by LTL model checking. 3128-3148
• 
  Ezio Bartocci, Flavio Corradini, Maria Rita Di Berardini, Emilia Entcheva, Scott A. Smolka, Radu Grosu:
  Modeling and simulation of cardiac tissue using hybrid I/O automata. 3149-3165
• 
  Luca Cardelli, Emmanuelle Caron, Philippa Gardner, Ozan Kahramanogullari, Andrew Phillips:
  A process model of Rho GTP-binding proteins. 3166-3185

Volume 410, Number 35, August 2009

Preface

• 
  Cezar Câmpeanu, Giovanni Pighizzini:
  Preface. 3187

Contributions

• 
  Artiom Alhazov, Erzsébet Csuhaj-Varjú, Carlos Martín-Vide, Yurii Rogozhin:
  On the size of computationally complete hybrid networks of evolutionary processors. 3188-3197
• 
  Franziska Biegler, Kai Salomaa:
  On the synchronized derivation depth of context-free grammars. 3198-3208
• 
  Henning Bordihn, Markus Holzer, Martin Kutrib:
  Determination of finite automata accepting subregular languages. 3209-3222
• 
  Janusz A. Brzozowski, Stavros Konstantinidis:
  State-complexity hierarchies of uniform languages of alphabet-size length. 3223-3235
• 
  Janusz A. Brzozowski, Nicolae Santean:
  Predictable semiautomata. 3236-3249
• 
  Elena Czeizler, Eugen Czeizler, Lila Kari, Kai Salomaa:
  On the descriptional complexity of Watson-Crick automata. 3250-3260
• 
  Jürgen Dassow, Ralf Stiebe, Bianca Truthe:
  Two collapsing hierarchies of subregularly tree controlled languages. 3261-3271
• 
  Zoltán Ésik, Yuan Gao, Guangwu Liu, Sheng Yu:
  Estimation of state complexity of combined operations. 3272-3280
• 
  Hermann Gruber, Markus Holzer:
  Language operations with regular expressions of polynomial size. 3281-3289
• 
  Xiaoxue Piao, Kai Salomaa:
  Operational state complexity of nested word automata. 3290-3302

Volume 410, Number 36, August 2009

Preface

• 
  Marios Mavronicolas:
  Preface. 3303-3304

Contributions

• 
  Dimitris Fotakis, Spyros C. Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, Paul G. Spirakis:
  The structure and complexity of Nash equilibria for a selfish routing game. 3305-3326
• 
  George Christodoulou, Elias Koutsoupias, Akash Nanavati:
  Coordination mechanisms. 3327-3336
• 
  Costas Busch, Malik Magdon-Ismail:
  Atomic routing games on maximum congestion. 3337-3347
• 
  Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano:
  On designing truthful mechanisms for online scheduling. 3348-3356
• 
  Simon Fischer, Berthold Vöcking:
  Adaptive routing with stale information. 3357-3371
• 
  Bhadrachalam Chitturi, William Fahle, Z. Meng, Linda Morales, Charles O. Shields Jr., Ivan Hal Sudborough, Walter Voit:
  An (18/11)n upper bound for sorting by prefix reversals. 3372-3390
• 
  Jaroslaw Kutylowski, Friedhelm Meyer auf der Heide:
  Optimal strategies for maintaining a chain of relays between an explorer and a base camp. 3391-3405
• 
  Giorgio Ausiello, Paolo Giulio Franciosa, Giuseppe F. Italiano:
  Small stretch (alpha, beta)-spanners in the streaming model. 3406-3413
• 
  Robert Elsässer, Thomas Sauerwald:
  On the runtime and robustness of randomized broadcasting. 3414-3427
• 
  Hans-Joachim Böckenhauer, Juraj Hromkovic, Richard Královic, Tobias Mömke, Peter Rossmanith:
  Reoptimization of Steiner trees: Changing the terminal set. 3428-3435

Volume 410, Number 37, September 2009

Preface

• 
  Jan Holub:
  Preface. 3437

Contributions

• 
  Kai Salomaa, Sheng Yu, Jinfeng Zan:
  Deciding determinism of caterpillar expressions. 3438-3446
• 
  Martin Kutrib, Andreas Malcher, Larissa Werlein:
  Regulated nondeterminism in pushdown automata. 3447-3460
• 
  Margareta Ackerman, Jeffrey O. Shallit:
  Efficient enumeration of words in regular languages. 3461-3470
• 
  Maxime Crochemore, Chiara Epifanio, Alessandra Gabriele, Filippo Mignosi:
  From Nerode's congruence to suffix automata with mismatches. 3471-3480
• 
  Manfred Droste, George Rahonis:
  Weighted automata and weighted logics with discounting. 3481-3494
• 
  Magnus Steinby, Catalin Ionut Tîrnauca:
  Defining syntax-directed translations by tree bimorphisms. 3495-3503
• 
  Natasa Jonoska, Joni Burnette Pirnot:
  Finite state automata representing two-dimensional subshifts. 3504-3512
• 
  Mikhail V. Volkov:
  Synchronizing automata preserving a chain of partial orders. 3513-3519
• 
  Marcella Anselmo, Dora Giammarresi, Maria Madonia:
  A computational model for tiling recognizable two-dimensional languages. 3520-3529
• 
  Frantisek Mráz, Friedrich Otto, Martin Plátek:
  The degree of word-expansion of lexicalized RRWW-automata - A new measure for the degree of nondeterminism of (context-free) languages. 3530-3538
• 
  Johanna Högberg, Andreas Maletti, Jonathan May:
  Backward and forward bisimulation minimization of tree automata. 3539-3552
• 
  Mehryar Mohri, Pedro J. Moreno, Eugene Weinstein:
  General suffix automaton construction algorithm and space bounds. 3553-3562
• 
  Shmuel T. Klein, Miri Kopel Ben-Nissan:
  Accelerating Boyer-Moore searches on binary texts. 3563-3571

Volume 410, Numbers 38-40, September 2009

Contributions

• 
  Yossi Moshe:
  On the joint subword complexity of automatic sequences. 3573-3588
• 
  Zuzana Masáková, Edita Pelantová:
  Relation between powers of factors and the recurrence function characterizing Sturmian words. 3589-3596
• 
  An Zhang, Yiwei Jiang, Zhiyi Tan:
  Online parallel machines scheduling with two hierarchies. 3597-3605
• 
  Johannes Müller, Christoph Spandl:
  A Curtis-Hedlund-Lyndon theorem for Besicovitch and Weyl spaces. 3606-3615
• 
  Marni Mishna, Andrew Rechnitzer:
  Two non-holonomic lattice walks in the quarter plane. 3616-3630
• 
  Wolfgang W. Bein, Leah Epstein, Lawrence L. Larmore, John Noga:
  Optimally competitive list batching. 3631-3639
• 
  Christian Komusiewicz, Falk Hüffner, Hannes Moser, Rolf Niedermeier:
  Isolation concepts for efficiently enumerating dense subgraphs. 3640-3654
• 
  Hanna Uscka-Wehlou:
  Two equivalence relations on digital lines with irrational slopes. A continued fraction approach to upper mechanical words. 3655-3669
• 
  Raphaël M. Jungers, Vladimir Protasov, Vincent D. Blondel:
  Overlap-free words and spectra of matrices. 3670-3684
• 
  Luigi Acerbi, Alberto Dennunzio, Enrico Formenti:
  Conservation of some dynamical properties for operations on cellular automata. 3685-3693
• 
  Reza Dorrigiv, Alejandro López-Ortiz, J. Ian Munro:
  On the relative dominance of paging algorithms. 3694-3701
• 
  Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno:
  An O(n^1.75) algorithm for L(2, 1)-labeling of trees. 3702-3710
• 
  Franziska Biegler, Mark Daley, Markus Holzer, Ian McQuillan:
  On the uniqueness of shuffle on words and finite languages. 3711-3724
• 
  Tamir Levi, Ami Litman:
  Accelerating certain outputs of merging and sorting networks. 3725-3732
• 
  Lukasz Kowalik:
  Improved edge-coloring with three colors. 3733-3742
• 
  Dominique Foata, Guo-Niu Han:
  New permutation coding and equidistribution of set-valued statistics. 3743-3750
• 
  Omid Amini, Stéphane Pérennes, Ignasi Sau:
  Hardness and approximation of traffic grooming. 3751-3760
• 
  Min Ji, T. C. Edwin Cheng:
  Parallel-machine scheduling of simple linear deteriorating jobs. 3761-3768
• 
  Tao Jiang, Zevi Miller, Dan Pritikin:
  Separation numbers of trees. 3769-3781
• 
  Geneviève Paquin:
  On a generalization of Christoffel words: epichristoffel words. 3782-3791
• 
  John Augustine, Sudarshan Banerjee, Sandy Irani:
  Strip packing with precedence constraints and strip packing with release times. 3792-3803
• 
  Zi-Long Liu, Fang Tian, Jun-Ming Xu:
  Probabilistic analysis of upper bounds for 2-connected distance k-dominating sets in graphs. 3804-3813
• 
  Miki Hermann, Reinhard Pichler:
  Complexity of counting the optimal solutions. 3814-3825
• 
  Dominik M. Wittmann, Daniel Schmidl, Florian Blöchl, Fabian J. Theis:
  Reconstruction of graphs based on random walks. 3826-3838
• 
  Olaf Beyersdorff, Johannes Köbler, Jochen Messner:
  Nondeterministic functions and the existence of optimal proof systems. 3839-3855
• 
  Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen:
  Hard constraint satisfaction problems have hard gaps at location 1. 3856-3874
• 
  Ming Liu, Chengbin Chu, Yinfeng Xu, Feifeng Zheng:
  Online scheduling on m uniform machines to minimize total (weighted) completion time. 3875-3881
• 
  Qiang-Sheng Hua, Yuexuan Wang, Dongxiao Yu, Francis C. M. Lau:
  Set multi-covering via inclusion-exclusion. 3882-3892
• 
  Veikko Keränen:
  A powerful abelian square-free substitution over 4 letters. 3893-3900
• 
  Gianluigi Greco, Francesco Scarcello:
  On the complexity of constrained Nash equilibria in graphical games. 3901-3924
• 
  Marek Tomasz Biskup, Wojciech Plandowski:
  Shortest synchronizing strings for Huffman codes. 3925-3941
• 
  Jia-Jie Liu, G. S. Huang, Yue-Li Wang:
  A fast algorithm for finding the positions of all squares in a run-length encoded string. 3942-3948
• 
  Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby:
  The complexity of weighted Boolean #CSP with mixed signs. 3949-3961
• 
  Alberto Dennunzio, Pierre Guillon, Benoît Masson:
  Sand automata as cellular automata. 3962-3974
• 
  Kangbok Lee, Joseph Y.-T. Leung, Michael L. Pinedo:
  Online scheduling on two uniform machines subject to eligibility constraints. 3975-3981

Notes

• 
  Christian Mathissen:
  Existential MSO over two successors is strictly weaker than over linear orders. 3982-3987
• 
  Hiroki Morizumi:
  Limiting negations in non-deterministic circuits. 3988-3994
• 
  Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski:
  Generalized juntas and NP-hard sets. 3995-4000

Volume 410, Number 41, September 2009

Foreword

• 
  Marco Carbone, Pawel Sobocinski, Frank D. Valencia:
  Foreword: Festschrift for Mogens Nielsen's 60th birthday. 4001-4005

Contributions

• 
  Romain Beauxis, Catuscia Palamidessi:
  Probabilistic and nondeterministic aspects of anonymity. 4006-4025
• 
  Nikola Benes, Jan Kretínský, Kim Guldstrand Larsen, Jirí Srba:
  On determinism in modal transition systems. 4026-4043
• 
  Filippo Bonchi, Ugo Montanari:
  Reactive systems, (semi-)saturated semantics and coalgebras on presheaves. 4044-4066
• 
  Ehab ElSalamouny, Karl Tikjøb Krukow, Vladimiro Sassone:
  An analysis of the exponential decay principle in probabilistic trust models. 4067-4084
• 
  Gudmund Skovbjerg Frandsen, Peter Frands Frandsen:
  Dynamic matrix rank. 4085-4093
• 
  Thomas Gazagnaire, Blaise Genest, Loïc Hélouët, P. S. Thiagarajan, Shaofa Yang:
  Causal Message Sequence Charts. 4094-4110
• 
  Rob J. van Glabbeek, Gordon D. Plotkin:
  Configuration structures, event structures and Petri nets. 4111-4159
• 
  Glynn Winskel:
  Prime algebraicity. 4160-4168

Volume 410, Number 42, September 2009

• 
  Rohit Chadha, Mahesh Viswanathan:
  Deciding branching time properties for asynchronous programs. 4169-4179
• 
  Peter Niebert, Doron A. Peled:
  Efficient model checking for LTL with partial order snapshots. 4180-4189
• 
  Loïc Colson, David Michel:
  Pedagogical second-order lambda-calculus. 4190-4203
• 
  René David:
  A direct proof of the confluence of combinatory strong reduction. 4204-4215
• 
  Viorel Preoteasa:
  Frame rule for mutually recursive procedures manipulating pointers. 4216-4233
• 
  Xuxin Mao, Luoshan Xu:
  Meet continuity properties of posets. 4234-4240
• 
  Rachid Hadjidj, Hanifa Boucheneb:
  On-the-fly TCTL model checking for time Petri nets. 4241-4261
• 
  Georgios E. Fainekos, George J. Pappas:
  Robustness of temporal logic specifications for continuous-time signals. 4262-4291

Volume 410, Number 43, October 2009

Foreword

• 
  Costas S. Iliopoulos, Wojciech Rytter:
  Foreword: Special issue in honor of the 60th birthday of Prof. Maxime Crochemore. 4293-4294

Contributions

• 
  William F. Smyth, Shu Wang:
  A new approach to the periodicity lemma on strings with holes. 4295-4302
• 
  Shay Mozes, Dekel Tsur, Oren Weimann, Michal Ziv-Ukelson:
  Fast algorithms for computing tree LCS. 4303-4314
• 
  Oren Kapah, Gad M. Landau, Avivit Levy, Nitsan Oz:
  Interchange rearrangement: The element-cost model. 4315-4326
• 
  Giovanni Battaglia, Davide Cangelosi, Roberto Grossi, Nadia Pisanti:
  Masking patterns in sequences: A new class of motif discovery with don't cares. 4327-4340
• 
  Esko Ukkonen:
  Maximal and minimal representations of gapped and non-gapped motifs of a string. 4341-4349
• 
  Mikaël Salson, Thierry Lecroq, Martine Léonard, Laurent Mouchard:
  A four-stage algorithm for updating a Burrows-Wheeler transform. 4350-4359
• 
  Alberto Apostolico, Fabio Cunial:
  The subsequence composition of a string. 4360-4371
• 
  Giusi Castiglione, Antonio Restivo, Marinella Sciortino:
  Circular sturmian words and Hopcroft's algorithm. 4372-4381
• 
  Amihood Amir, Yonatan Aumann, Piotr Indyk, Avivit Levy, Ely Porat:
  Efficient computations of l₁ and l_∞ rearrangement distances. 4382-4390
• 
  Maria Federico, Nadia Pisanti:
  Suffix tree characterization of maximal motifs in biological sequences. 4391-4401
• 
  Sunho Lee, Kunsoo Park:
  Dynamic rank/select structures with applications to run-length encoded texts. 4402-4413
• 
  Rodrigo González, Gonzalo Navarro:
  Rank/select on dynamic compressed sequences and applications. 4414-4422
• 
  Marie-Pierre Béal, Dominique Perrin:
  Completing codes in a sofic shift. 4423-4431
• 
  Ricardo Baeza-Yates, Véronique Bruyère, Olivier Delgrange, Rodrigo Scheihing:
  On the size of Boyer-Moore automata. 4432-4443

Volume 410, Number 44, October 2009

Preface

• 
  Anna Gál:
  Preface: Special Issue of ICALP 2006 - dedicated to the memory of Ingo Wegener. 4445

In memoriam

• 
  Martin Dietzfelbinger:
  In memoriam Prof. Dr. math. Ingo Wegener, 1950-2008. 4446-4447

Contributions

• 
  Xi Chen, Xiaotie Deng:
  On the complexity of 2D discrete fixed point problem. 4448-4456
• 
  Irene Finocchi, Fabrizio Grandoni, Giuseppe F. Italiano:
  Optimal resilient sorting and searching in the presence of memory faults. 4457-4470
• 
  Dániel Marx:
  A parameterized view on matroid optimization problems. 4471-4479
• 
  Piotr Sankowski:
  Maximum weight bipartite matching in matrix multiplication time. 4480-4488
• 
  Kamalika Chaudhuri, Satish Rao, Samantha J. Riesenfeld, Kunal Talwar:
  A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids. 4489-4503
• 
  Rolf Harren:
  Approximation algorithms for orthogonal packing problems for hypercubes. 4504-4532

Volume 410, Number 45, October 2009

Foreword

• 
  Rudolf Fleischer, Jinhui Xu:
  Foreword. 4533

Contributions

• 
  Eric Angel, Evripidis Bampis, Laurent Gourvès:
  On the minimum hitting set of bundles problem. 4534-4542
• 
  Zhi-Zhong Chen, Ruka Tanahashi:
  Approximating maximum edge 2-coloring in simple graphs via local improvement. 4543-4553
• 
  Nadja Betzler, Michael R. Fellows, Jiong Guo, Rolf Niedermeier, Frances A. Rosamond:
  Fixed-parameter algorithms for Kemeny rankings. 4554-4570
• 
  Gregory Z. Gutin, Igor Razgon, Eun Jung Kim:
  Minimum leaf out-branching and related problems. 4571-4579
• 
  Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs:
  Speed scaling with a solar cell. 4580-4587
• 
  Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe:
  Scale free interval graphs. 4588-4600

Volume 410, Number 46, November 2009

Foreword

• 
  Moreno Falaschi, Maurizio Gabbrielli, Catuscia Palamidessi:
  Foreword. 4601-4602

Giorgio Levi in Pisa

• 
  Roberto Barbuti:
  Giorgio Levi in Pisa. 4603-4604

Personal portrait of Giorgio Levi

• 
  Alessio Guglielmi:
  Personal portrait of Giorgio Levi. 4605-4607

Contributions

• 
  María Alpuente, Santiago Escobar, José Iborra:
  Termination of narrowing revisited. 4608-4625
• 
  Gianluca Amato, James Lipton, Robert W. McGrail:
  On the algebraic structure of declarative programming languages. 4626-4671
• 
  Roberto Bagnara, Patricia M. Hill, Enea Zaffanella:
  Applications of polyhedral computations to the analysis and verification of hardware and software systems. 4672-4691
• 
  Annalisa Bossi:
  S-semantics for logic programming: A retrospective look. 4692-4703
• 
  Daniel Cabeza Gras, Manuel V. Hermenegildo:
  Non-strict independence-based program parallelization using sharing and freeness information. 4704-4723
• 
  Patrick Cousot, Radhia Cousot, Roberto Giacobazzi:
  Abstract interpretation of resolution-based semantics. 4724-4746
• 
  Chuck C. Liang, Dale Miller:
  Focusing and polarization in linear, intuitionistic, and classical logics. 4747-4768
• 
  Michael J. Maher:
  Local consistency for extended CSPs. 4769-4783
• 
  Kazunori Ueda:
  LMNtal as a hierarchical logic programming language. 4784-4800

Volume 410, Numbers 47-49, November 2009

• 
  Ali Çivril, Malik Magdon-Ismail:
  On selecting a maximum volume sub-matrix of a matrix and related problems. 4801-4811
• 
  Daniel Bayer, Van Bang Le, H. N. de Ridder:
  Probe threshold and probe trivially perfect graphs. 4812-4822
• 
  Alberto Dennunzio, Pietro di Lena, Enrico Formenti, Luciano Margara:
  On the directional dynamics of additive cellular automata. 4823-4833
• 
  Pim van 't Hof, Daniël Paulusma, Gerhard J. Woeginger:
  Partitioning graphs into connected parts. 4834-4843
• 
  Damien Regnault, Nicolas Schabanel, Eric Thierry:
  Progresses in the analysis of stochastic 2D cellular automata: A study of asynchronous 2D minority. 4844-4855
• 
  Shisheng Li, Jinjiang Yuan:
  Scheduling with families of jobs and delivery coordination under job availability. 4856-4863
• 
  Tamás Kis:
  Scheduling multiprocessor UET tasks of two sizes. 4864-4873
• 
  Pál Dömösi, Géza Horváth, Laurent Vuillon:
  On the Shyr-Yu theorem. 4874-4877
• 
  Jakob Grue Simonsen:
  On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts. 4878-4891
• 
  Yunbao Huang:
  The complexity of C^bomega-words of the form w×w. 4892-4904
• 
  Yingchao Zhao, Wei Chen, Shang-Hua Teng:
  The isolation game: A game of distances. 4905-4919
• 
  Noga Alon, Uri Stav:
  Hardness of edge-modification problems. 4920-4927
• 
  Vikraman Arvind, Johannes Köbler, Wolfgang Lindner:
  Parameterized learnability of juntas. 4928-4936
• 
  Clelia de Felice, Gabriele Fici, Rosalba Zizza:
  A characterization of regular circular languages generated by marked splicing systems. 4937-4960
• 
  Pedro García, Manuel Vazquez de Parga, Antonio Cano, Damián López:
  On locally reversible languages. 4961-4974
• 
  Gennaro Cordasco, Luisa Gargano:
  Navigable Small-World networks with few random bits. 4975-4988
• 
  Elisabeth Gassner, Johannes Hatzl, Sven Oliver Krumke, Heike Sperber, Gerhard J. Woeginger:
  How hard is it to find extreme Nash equilibria in network congestion games? 4989-4999
• 
  Lukasz Kowalik, Marcin Mucha:
  Deterministic 7/8-approximation for the metric maximum TSP. 5000-5009
• 
  Jui-Yi Kao, Narad Rampersad, Jeffrey O. Shallit:
  On NFAs where all states are final, initial, or both. 5010-5021
• 
  Alan J. Cain:
  Automaton semigroups. 5022-5038
• 
  Ming Liu, Yinfeng Xu, Chengbin Chu, Feifeng Zheng:
  Online scheduling to minimize modified total tardiness with an availability constraint. 5039-5046
• 
  Xingyu Chen, Leah Epstein, Zhiyi Tan:
  Semi-online machine covering for two uniform machines. 5047-5062
• 
  Lei Chen, Changhong Lu, Zhenbing Zeng:
  Hardness results and approximation algorithms for (weighted) paired-domination in graphs. 5063-5071
• 
  Lei Chen, Changhong Lu, Zhenbing Zeng:
  Distance paired-domination problems on subclasses of chordal graphs. 5072-5081
• 
  Tugkan Batu, Petra Berenbrink, Christian Sohler:
  A sublinear-time approximation scheme for bin packing. 5082-5092
• 
  Eike Kiltz, David Galindo:
  Direct chosen-ciphertext secure identity-based key encapsulation without random oracles. 5093-5111
• 
  Jirí Sgall, Hadas Shachnai, Tami Tamir:
  Periodic scheduling with obligatory vacations. 5112-5121
• 
  Soheir Mohamed Khamis, Sameh S. Daoud, Hanaa A. E. Essa:
  A randomized algorithm for determining dominating sets in graphs of maximum degree five. 5122-5127
• 
  Joachim Spoerhase, Hans-Christoph Wirth:
  (r, p)-centroid problems on paths and trees. 5128-5137
• 
  Jørgen Bang-Jensen, Matthias Kriesell:
  Disjoint directed and undirected paths and cycles in digraphs. 5138-5144
• 
  Cristina Tîrnauca, Satoshi Kobayashi:
  Necessary and sufficient conditions for learning with correction queries. 5145-5157
• 
  Flavio D'Alessandro, Benedetto Intrigila, Stefano Varricchio:
  The Parikh counting functions of sparse context-free languages are quasi-polynomials. 5158-5181

Notes

• 
  Wenjie Li, Jinjiang Yuan, Jianfa Cao, Hailin Bu:
  Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead. 5182-5187
• 
  Ada Che, Vladimir Kats, Eugene Levner:
  A note on a quadratic algorithm for the 2-cyclic robotic scheduling problem. 5188-5190
• 
  Arturas Dubickas:
  Binary words with a given Diophantine exponent. 5191-5195
• 
  Dongxiao Yu, Jianfeng Hou, Guizhen Liu, Bin Liu, Lan Xu:
  Acyclic edge coloring of planar graphs with large girth. 5196-5200

Volume 410, Number 50, November 2009

Foreword

• 
  Ludek Kucera:
  Foreword. 5201

Contributions

• 
  Markus Bläser, Andreas Meyer de Voltaire:
  Semisimple algebras of almost minimal rank over the reals. 5202-5214
• 
  Paul S. Bonsma, Luis Cereceda:
  Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances. 5215-5226
• 
  Maxime Crochemore, Lucian Ilie, Wojciech Rytter:
  Repetitions in strings: Algorithms and combinatorics. 5227-5235
• 
  William Duckworth, Michele Zito:
  Large independent sets in random regular graphs. 5236-5243
• 
  Pascal Koiran, Sylvain Perifel:
  VPSPACE and a transfer theorem over the complex field. 5244-5251
• 
  Luc Longpré, Pierre McKenzie:
  The complexity of Solitaire. 5252-5260
• 
  Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis:
  Expander properties and the cover time of random intersection graphs. 5261-5272
• 
  Gábor Salamon:
  Approximating the Maximum Internal Spanning Tree problem. 5273-5284
• 
  Seiichiro Tani:
  Claw finding algorithms using quantum walk. 5285-5297

Volume 410, Number 51, November 2009

Foreword

• 
  Paolo Ferragina, Gad M. Landau:
  Foreword. 5299

Contributions

• 
  Anne Bergeron, Julia Mixtacki, Jens Stoye:
  A new linear time algorithm to compute the genomic distance via the double cut and join distance. 5300-5316
• 
  Christian Hundt, Maciej Liskiewicz, Ragnar Nevries:
  A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation. 5317-5333
• 
  Amihood Amir, Yonatan Aumann, Oren Kapah, Avivit Levy, Ely Porat:
  Approximate string matching with address bit errors. 5334-5346
• 
  Orgad Keller, Tsvi Kopelowitz, Moshe Lewenstein:
  On the longest common parameterized subsequence. 5347-5353
• 
  Johannes Fischer, Veli Mäkinen, Gonzalo Navarro:
  Faster entropy-bounded compressed suffix trees. 5354-5364
• 
  Roman Kolpakov, Gregory Kucherov:
  Searching for gapped palindromes. 5365-5373
• 
  Bin Ma:
  Why greed works for shortest common superstring problem. 5374-5381

Volume 410, Number 52, December 2009

Preface

• 
  Boting Yang, Cao An Wang:
  Preface. 5383

Contributions

• 
  Falk Hüffner, Christian Komusiewicz, Hannes Moser, Rolf Niedermeier:
  Isolation concepts for clique enumeration: Comparison and computational experiments. 5384-5397
• 
  Zhao Zhang, Xiaofeng Gao, Weili Wu:
  PTAS for connected vertex cover in unit disk graphs. 5398-5402
• 
  Peter Danziger, Eric Mendelsohn, Lucia Moura, Brett Stevens:
  Covering arrays avoiding forbidden edges. 5403-5414
• 
  Zhipeng Cai, Zhi-Zhong Chen, Guohui Lin:
  A 3.4713-approximation algorithm for the capacitated multicast tree routing problem. 5415-5424
• 
  Nadja Betzler, Johannes Uhlmann:
  Parameterized complexity of candidate control in elections and related digraph problems. 5425-5442
• 
  Andreas Brandstädt, Van Bang Le:
  Simplicial powers of graphs. 5443-5454
• 
  Marjan Marzban, Qian-Ping Gu, Xiaohua Jia:
  Computational study on planar dominating set problem. 5455-5466
• 
  Sebastian Böcker, Sebastian Briesemeister, Quang Bao Anh Bui, Anke Truß:
  Going weighted: Parameterized algorithms for cluster editing. 5467-5480
• 
  Zhizhang Shen, Ke Qiu, Eddie Cheng:
  On the surface area of the (n, k)-star graph. 5481-5490
• 
  Jeannette C. M. Janssen, Pawel Pralat:
  Protean graphs with a variety of ranking schemes. 5491-5504
• 
  Peter Wagner, Andreas Brandstädt:
  The complete inclusion structure of leaf power classes. 5505-5514
• 
  Binay K. Bhattacharya, Mike Burmester, Yuzhuang Hu, Evangelos Kranakis, Qiaosheng Shi, Andreas Wiese:
  Optimal movement of mobile sensors for barrier coverage of a planar region. 5515-5528