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 2P3-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 F0 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
Volume 410,
Number 16,
April 2009
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 Rd.
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
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(cdm, 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 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
- M.-A. Jacob-Da Col, P. 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 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
Preface
Contributions
Note
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
Volume 410,
Numbers 30-32,
August 2009
Contributions
- 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
Preface
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
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
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, 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
Preface
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 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
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
- 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(n1.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 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
Notes
Volume 410,
Number 41,
September 2009
Foreword
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
Copyright © Mon Nov 2 21:56:32 2009
by Michael Ley (ley@uni-trier.de)
