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, Raphael 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, J. 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, Julià 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, A. Taormina, R. 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
  
• Benoit 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, Eric 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, Luerbio Faria, Celina M. Herrera 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

• 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 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 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

• Grzegorz Rozenberg:
  Preface. 2453-2454
  

• 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
  

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

Volume 410, Numbers 27-29, June 2009

• 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
  

• 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
  
• Lubomíra Balková, Edita Pelantová:
  A note on symmetries in the Rauzy graph and factor frequencies. 2779-2783
  

Volume 410, Numbers 30-32, August 2009

• Jean-Paul Allouche, Narad Rampersad, Jeffrey 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, Raphael 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 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

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

• 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

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

• 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

• Marios Mavronicolas:
  Preface. 3303-3304
  

• 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, C. 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

• Jan Holub:
  Preface. 3437
  

• 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 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 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

• 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
  
• Raphael 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
  
• J. J. Liu, G. S. Huang, Y. L. 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 Pinedo:
  Online scheduling on two uniform machines subject to eligibility constraints. 3975-3981
  

• 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

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

• 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 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

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

• 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 _INFINITY 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 A. 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

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

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

• 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 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

• Rudolf Fleischer, Jinhui Xu:
  Foreword. 4533
  

• 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 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

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

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

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

• María Alpuente, Santiago Escobar, José Iborra:
  Termination of narrowing revisited. 4608-4625
  
• Gianluca Amato, James Lipton, Robert 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 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 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
  
• Jiri Sgall, Hadas Shachnai, Tami Tamir:
  Periodic scheduling with obligatory vacations. 5112-5121
  
• Soheir M. 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