Last update: Thu Oct 17 07:16:40 MDT 2024
Volume 295, Number 1--3, February 24, 2003Sven O. Krumke and Willem E. de Paepe and Diana Poensgen and Leen Stougie News from the online traveling repairman 279--294
Takashi Yokomori Polynomial-time identification of very simple grammars from positive data . . . 179--206
J.-M. Champarnaud and F. Coulon NFA reduction algorithms by means of regular inequalities . . . . . . . . . . 241--253
Juhani Karhumäki and Grzegorz Rozenberg Preface . . . . . . . . . . . . . . . . 1--1 D. S. Ananichev and M. V. Volkov Synchronizing generalized monotonic automata . . . . . . . . . . . . . . . . 3--13 Holger Austinat and Volker Diekert and Ulrich Hertrampf and Holger Petersen Regular frequency computations . . . . . 15--21 Cezar Câmpeanu and Nicolae Sântean and Sheng Yu Mergible states in large NFA . . . . . . 23--34 Arturo Carpi and Aldo de Luca Completions in measure of languages and related combinatorial problems . . . . . 35--57 Zhe Dang and Oscar H. Ibarra and Zhi-Wei Sun On two-way nondeterministic finite automata with one reversal-bounded counter . . . . . . . . . . . . . . . . 59--79 Cunsheng Ding and Xuesong Wang A coding theory construction of new systematic authentication codes . . . . 81--99 Rudolf Freund and Gheorghe P\uaun and Mario J. Pérez-Jiménez Tissue P systems with channel states . . 101--116 Tero Harju and Dirk Nowotka On the equation $ x^k = z_1^{k_1} z_2^{k_2} \cdots z_n^{k_n} $ in a free semigroup . . . . . . . . . . . . . . . 117--121 Juha Honkala The language equivalence problem for HD0L systems having D0L growths . . . . 123--133 Juraj Hromkovi\vc and Georg Schnitger On the power of randomized multicounter machines . . . . . . . . . . . . . . . . 135--144 Yuri Matiyasevich and Géraud Sénizergues Decision problems for semi-Thue systems with a few rules . . . . . . . . . . . . 145--169 Keijo Ruohonen Explicit test sets for iterated morphisms in free monoids and metabelian groups . . . . . . . . . . . . . . . . . 171--191 Anonymous Editorial board . . . . . . . . . . . . v--ix
E. Csuhaj-Varjú and D. Wotschke Preface . . . . . . . . . . . . . . . . 193--193 Henning Bordihn On the number of components in cooperating distributed grammar systems 195--204 Juan Castellanos and Peter Leupold and Victor Mitrana On the size complexity of hybrid networks of evolutionary processors . . 205--220 Jean-Marc Champarnaud and Thomas Paranthoën Random generation of DFAs . . . . . . . 221--235 Mark Daley and Ian McQuillan Template-guided DNA recombination . . . 237--250 Rudolf Freund and Lila Kari and Marion Oswald and Petr Sosík Computationally universal P systems without priorities: two catalysts are sufficient . . . . . . . . . . . . . . . 251--266 Markus Holzer and Martin Kutrib On the descriptional complexity of finite automata with modified acceptance conditions . . . . . . . . . . . . . . . 267--285 Galina Jirásková State complexity of some operations on binary regular languages . . . . . . . . 287--298 Martin Kappes and Frank Nießner Succinct representations of languages by DFA with different levels of reliability 299--310 Martin Kutrib On the descriptional power of heads, counters, and pebbles . . . . . . . . . 311--324 Andreas Malcher On two-way communication in cellular automata with a fixed number of cells 325--338 Maurice Margenstern and Gheorghe P\uaun and Yurii Rogozhin and Sergey Verlan Context-free insertion--deletion systems 339--348 Filippo Mera and Giovanni Pighizzini Complementing unary nondeterministic automata . . . . . . . . . . . . . . . . 349--360 György Vaszil On the descriptional complexity of some rewriting mechanisms regulated by context conditions . . . . . . . . . . . 361--373
Flavio Corradini and Uwe Nestmann Selected papers of the Tenth International Workshop on Expressiveness in Concurrency (EXPRESS 2003) . . . . . 375--376 Luca Aceto and Wan Fokkink and Anna Ingólfsdóttir and Bas Luttik CCS with Hennessy's merge has no finite-equational axiomatization . . . . 377--405 Christie Bolton and Gavin Lowe A hierarchy of failures-based models: theory and application . . . . . . . . . 407--438 Arnaud Carayol and Daniel Hirschkoff and Davide Sangiorgi On the representation of McCarthy's \em amb in the $ \pi $-calculus . . . . . . 439--473 Étienne Lozes Elimination of spatial connectives in static spatial logics . . . . . . . . . 475--499 Sergio Maffeis and Iain Phillips On the computational strength of pure ambient calculi . . . . . . . . . . . . 501--551 Richard Mayr Weak bisimilarity and regularity of context-free processes is EXPTIME-hard 553--575 Frank D. Valencia Decidability of infinite-state timed CCP processes and first-order LTL . . . . . 577--607 Anonymous Author index . . . . . . . . . . . . . . 609--610 Anonymous Master index . . . . . . . . . . . . . . 611--622
Fernando Orejas and Jan van Leeuwen Preface . . . . . . . . . . . . . . . . 1--2 Markus Bläser Beyond the Alder--Strassen bound . . . . 3--21 Kunihiko Sadakane and Nadia Takki-Chebihi and Takeshi Tokuyama Combinatorics and algorithms for low-discrepancy roundings of a real sequence . . . . . . . . . . . . . . . . 23--36 Artur Czumaj and Christian Sohler Testing hypergraph colorability . . . . 37--52 Jop F. Sibeyn Faster gossiping on butterfly networks 53--72 Edith Cohen and Eran Halperin and Haim Kaplan Performance aspects of distributed caches using TTL-based consistency . . . 73--96 Rajeev Alur and Kousha Etessami and Mihalis Yannakakis Realizability and verification of MSC graphs . . . . . . . . . . . . . . . . . 97--114 Franck van Breugel and James Worrell A behavioural pseudometric for probabilistic transition systems . . . . 115--142 Hubert Comon and Véronique Cortier Tree automata with one memory set constraints and cryptographic protocols 143--214 Lutz Schröder and Till Mossakowski and Andrzej Tarlecki and Bartek Klin and Piotr Hoffman Amalgamation in the semantics of CASL 215--247 Anonymous Editorial board . . . . . . . . . . . . v--ix
Frank de Boer and Marcello Bonsangue Preface . . . . . . . . . . . . . . . . 249--250 Erika Ábrahám and Frank S. de Boer and Willem-Paul de Roever and Martin Steffen An assertion-based proof system for multithreaded Java . . . . . . . . . . . 251--290 Jozef Hooman and Jaco van de Pol Semantic models of a timed distributed dataspace architecture . . . . . . . . . 291--323 Gianluigi Ferrari and Ugo Montanari and Emilio Tuosto Coalgebraic minimization of HD-automata for the $ \pi $-calculus using polymorphic types . . . . . . . . . . . 325--365 Franz Achermann and Oscar Nierstrasz A calculus for reasoning about software composition . . . . . . . . . . . . . . 367--396 Yonit Kesten and Amir Pnueli A compositional approach to CTL$^*$ verification . . . . . . . . . . . . . . 397--428 Emil Sekerinski Verification and refinement with fine-grained action-based concurrent objects . . . . . . . . . . . . . . . . 429--455 Dirk Pattinson and Martin Wirsing A coordination approach to mobile components . . . . . . . . . . . . . . . 457--483 Anonymous Author index . . . . . . . . . . . . . . 485--486
Andrew Lim and Brian Rodrigues and Fan Wang and Zhou Xu $k$-Center problems with minimum coverage . . . . . . . . . . . . . . . . 1--17 Alain Daurat Determination of Q-convex sets by X-rays 19--45 Lila Kari and Petr Sosík Aspects of shuffle and deletion on trajectories . . . . . . . . . . . . . . 47--61 Steven S. Seiden and Peter P. Chen and R. F. Lax and J. Chen and Guoli Ding New bounds for randomized busing . . . . 63--81 Marc Demange and Vangelis Th. Paschos On-line vertex-covering . . . . . . . . 83--108 Qingmin Shi and Joseph JáJá A new framework for addressing temporal range queries and some preliminary results . . . . . . . . . . . . . . . . 109--121 Maria Serna and Luca Trevisan and Fatos Xhafa The approximability of non-Boolean satisfiability problems and restricted integer programming . . . . . . . . . . 123--139 Sylvain Lombardy and Jacques Sakarovitch Derivatives of rational expressions with multiplicity . . . . . . . . . . . . . . 141--177 Jean Berstel and Luc Boasson and Michel Latteux Mixed languages . . . . . . . . . . . . 179--198 F. J. Brandenburg and K. Skodinis Finite graph automata for linear and boundary graph languages . . . . . . . . 199--232 Salvatore La Torre and Aniello Murano and Margherita Napoli Weak Muller acceptance conditions for tree automata . . . . . . . . . . . . . 233--250 Bernhard Fuchs and Winfried Hochstättler and Walter Kern Online matching on a line . . . . . . . 251--264 Vilhelm Dahllöf and Peter Jonsson and Magnus Wahlström Counting models for 2SAT and 3SAT formulae . . . . . . . . . . . . . . . . 265--291 Nikola Jevti\'c and Alon Orlitsky and Narayana P. Santhanam A lower bound on compression of unknown alphabets . . . . . . . . . . . . . . . 293--311 Marco Pedicini Greedy expansions and sets with deleted digits . . . . . . . . . . . . . . . . . 313--336 Klaus Weihrauch and Ning Zhong Computing the solution of the Korteweg--de Vries equation with arbitrary precision on Turing machines 337--366 A. Cincotti Three-player partizan games . . . . . . 367--389 Longtao He and Binxing Fang and Jie Sui The wide window string matching algorithm . . . . . . . . . . . . . . . 391--404 Jean Cardinal and Stefan Langerman Designing small keyboards is hard . . . 405--415 Hiroshi Nagamochi On the one-sided crossing minimization in a bipartite graph with large degrees 417--446 Hong-Gwa Yeh and Xuding Zhu Resource-sharing system scheduling and circular chromatic number . . . . . . . 447--460 H. J. Huang and L. Jiao and T. Y. Cheung Property-preserving subnet reductions for designing manufacturing systems with shared resources . . . . . . . . . . . . 461--485 Harumichi Nishimura and Masanao Ozawa Uniformity of quantum circuit families for error-free algorithms . . . . . . . 487--496 Cristina Bazgan and Jérôme Monnot and Vangelis Th. Paschos and Fabrice Serri\`ere On the differential approximation of MIN SET COVER . . . . . . . . . . . . . . . 497--513 Jesper Makholm Byskov and Bolette Ammitzbòll Madsen and Bjarke Skjernaa New algorithms for Exact Satisfiability 515--541 Reza Gharavi and V. Anantharam An upper bound for the largest Lyapunov exponent of a Markovian product of nonnegative matrices . . . . . . . . . . 543--557 Dekel Tsur Sequencing by hybridization with errors: handling longer sequences . . . . . . . 559--566 Maxime Crochemore and Jacques Désarménien and Dominique Perrin A note on the Burrows--Wheeler transformation . . . . . . . . . . . . . 567--572 Ali Aberkane and James D. Currie The Thue--Morse word contains circular $ 5 / 2^+ $ power free words of every length . . . . . . . . . . . . . . . . . 573--581 Anonymous Author index . . . . . . . . . . . . . . 583--584 Anonymous Editorial board . . . . . . . . . . . . v--ix
Andrew D. Gordon, Programme Chair FOSSACS 2003 Preface for the Special Issue . . . . . 1--1 Andreas Abel and Ralph Matthes and Tarmo Uustalu Iteration and coiteration schemes for higher-order and nested datatypes . . . 3--66 Bruno Blanchet and Andreas Podelski Verification of cryptographic protocols: tagging enforces termination . . . . . . 67--90 Eduardo Bonelli Normalisation for higher-order calculi with explicit substitutions . . . . . . 91--125 Iovka Boneva and Jean-Marc Talbot When ambients cannot be opened . . . . . 127--169 Franck van Breugel and Michael Mislove and Joël Ouaknine and James Worrell Domain theory, testing and simulation for labelled Markov processes . . . . . 171--197 J. Laird Game semantics and linear CPS interpretation . . . . . . . . . . . . . 199--224 Denis Lugiez Multitree automata that count . . . . . 225--263 Luigi Santocanale and André Arnold Ambiguous classes in $ \mu $-calculi hierarchies . . . . . . . . . . . . . . 265--296 Vladimiro Sassone and Pawe\l Soboci\'nski Locating reaction with 2-categories . . 297--327 Anonymous Editorial board . . . . . . . . . . . . v--ix
David Peleg and Jop Sibeyn Preface . . . . . . . . . . . . . . . . 329--330 Andre Osterloh Optimal oblivious routing on $d$-dimensional meshes . . . . . . . . . 331--346 Hiro Ito and Kazuo Iwama and Yasuo Okabe and Takuya Yoshihiro Single backup table schemes for shortest-path routing . . . . . . . . . 347--353 Dariusz R. Kowalski and Andrzej Pelc Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism . . . . . 355--371 Costas Busch and Marios Mavronicolas and Paul Spirakis The cost of concurrent, low-contention Read&Modify&Write . . . . . . . . . . . . 373--400 Michele Flammini and Alfredo Navarra and Andrzej Proskurowski On routing of wavebands for all-to-all communications in all-optical paths and cycles $^,$ . . . . . . . . . . . . . . 401--413 Cyril Gavoille and Martin Nehéz Interval routing in reliability networks 415--432 Antonio Fernández and Chryssis Georgiou and Alexander Russell and Alex A. Shvartsman The Do-All problem with Byzantine processor failures . . . . . . . . . . . 433--454 Anonymous Author index . . . . . . . . . . . . . . 455--456
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1--2 Jarkko Kari Theory of cellular automata: a survey 3--33 Anne Auger Convergence results for the $ (1, \lambda)$-SA-ES using the theory of $ \phi $-irreducible Markov chains . . . . 35--69 Paola Bonizzoni and Clelia De Felice and Rosalba Zizza The structure of reflexive regular splicing languages via Schützenberger constants . . . . . . . . . . . . . . . 71--98 Philippe Gaborit and Oliver D. King Linear constructions for DNA codes . . . 99--113 Oscar H. Ibarra On membrane hierarchy in P systems . . . 115--129 Lila Kari and Stavros Konstantinidis and Petr Sosík On properties of bond-free DNA languages 131--159 Madhu Mutyam Rewriting P systems: improved hierarchies . . . . . . . . . . . . . . 161--175 Martin Sauerhoff and Detlef Sieling Quantum branching programs and space-bounded nonuniform quantum complexity . . . . . . . . . . . . . . . 177--225 Damien Woods and Thomas J. Naughton An optical model of computation . . . . 227--258 Guowu Yang and William N. N. Hung and Xiaoyu Song and Marek Perkowski Majority-based reversible logic gates 259--274 Tomohiro Yamasaki and Hirotada Kobayashi and Hiroshi Imai Quantum versus deterministic counter automata . . . . . . . . . . . . . . . . 275--297 Anonymous Author index . . . . . . . . . . . . . . 299--299 Anonymous Editorial board . . . . . . . . . . . . v--ix
Alberto Apostolico and Raffaele Giancarlo Foreword . . . . . . . . . . . . . . . . 1--2 Abhijit Chattaraj and Laxmi Parida An inexact-suffix-tree-based algorithm for detecting extensible patterns . . . 3--14 Lusheng Wang and Hao Zhao and Guozhu Dong and Jianping Li On the complexity of finding emerging patterns . . . . . . . . . . . . . . . . 15--27 Giancarlo Mauri and Giulio Pavesi Algorithms for pattern matching and discovery in RNA secondary structure . . 29--51 Ying Xu and Lusheng Wang and Hao Zhao and Jianping Li Exact matching of RNA secondary structure patterns . . . . . . . . . . . 53--66 Jérôme Waldispühl and Jean-Marc Steyaert Modeling and predicting all-$ \alpha $ transmembrane proteins including helix--helix pairing . . . . . . . . . . 67--92 Charles Choy and Jesper Jansson and Kunihiko Sadakane and Wing-Kin Sung Computing the maximum agreement of phylogenetic networks . . . . . . . . . 93--107 Vineet Bafna and Sorin Istrail and Giuseppe Lancia and Romeo Rizzi Polynomial and APX-hard cases of the individual haplotyping problem . . . . . 109--125 Anonymous Editorial board . . . . . . . . . . . . v--ix
Luca Aceto and Wan Fokkink and Anna Ingolfsdottir and Zoltán Ésik Guest editors' foreword . . . . . . . . 127--129 J. C. M. Baeten A brief history of process algebra . . . 131--146 Bas Luttik and Vincent van Oostrom Decomposition orders --- another generalisation of the fundamental theorem of arithmetic . . . . . . . . . 147--186 F. Corradini and W. Vogler Measuring the performance of asynchronous systems with PAFAS . . . . 187--213 J. A. Bergstra and C. A. Middelburg Process algebra for hybrid systems . . . 215--280 Alessandro Aldini and Marco Bernardo On the usability of process algebra: an architectural view . . . . . . . . . . . 281--329 Roberto Bruni and Ugo Montanari and Vladimiro Sassone Observational congruences for dynamically reconfigurable tile systems 331--372 Catuscia Palamidessi and Oltea Mihaela Herescu A randomized encoding of the $ \pi $-calculus with mixed choice . . . . . . 373--404 Anonymous Author index . . . . . . . . . . . . . . 405--406
Maurizio Lenzerini Preface . . . . . . . . . . . . . . . . 1--1 Michael Benedikt and Wenfei Fan and Gabriel Kuper Structural properties of XPath fragments 3--31 Diego Calvanese and Giuseppe De Giacomo and Moshe Y. Vardi Decidable containment of recursive queries . . . . . . . . . . . . . . . . 33--56 Alin Deutsch and Val Tannen XML queries and constraints, containment and reformulation . . . . . . . . . . . 57--87 Ronald Fagin and Phokion G. Kolaitis and Renée J. Miller and Lucian Popa Data exchange: semantics and query answering . . . . . . . . . . . . . . . 89--124 Floris Geerts and Bart Kuijpers On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases . . . . . . . . . . . . . . . 125--151 Wim Martens and Frank Neven On the complexity of typechecking top-down XML transformations . . . . . . 153--180 David Toman and Grant Weddell On reasoning about structural equality in XML: a description logic approach . . 181--203 Anonymous Editorial board . . . . . . . . . . . . v--ix
Egon Börger Abstract state machines and high-level system design and analysis . . . . . . . 205--207 Cyrille Artho and Howard Barringer and Allen Goldberg and Klaus Havelund and Sarfraz Khurshid and Mike Lowry and Corina Pasareanu and Grigore Ro\csu and Koushik Sen and Willem Visser and Rich Washington Combining test case generation and runtime verification . . . . . . . . . . 209--234 Egon Börger and Nicu G. Fruja and Vincenzo Gervasi and Robert F. Stärk A high-level modular definition of the semantics of C# . . . . . . . . . . . . 235--284 Uwe Glässer and Qian-Ping Gu Formal description and analysis of a distributed location service for mobile ad hoc networks . . . . . . . . . . . . 285--309 Yuri Gurevich and Nikolai Tillmann Partial updates . . . . . . . . . . . . 311--342 Stanislas Nanchen and Robert F. Stärk A logic for secure memory access of abstract state machines . . . . . . . . 343--365 Gruia-Catalin Roman and Jamie Payton A principled exploration of coordination models . . . . . . . . . . . . . . . . . 367--401 Gerhard Schellhorn ASM refinement and generalizations of forward simulation in data refinement: a comparison . . . . . . . . . . . . . . . 403--435 Anonymous Author index . . . . . . . . . . . . . . 437--438
Roberto Giacobazzi and Isabella Mastroeni Transforming semantics by abstract interpretation . . . . . . . . . . . . . 1--50 Gennaro Costagliola and Filomena Ferrucci and Carmine Gravino Adding symbolic information to picture models: definitions and properties . . . 51--104 Juhani Karhumäki and Wojciech Plandowski and Wojciech Rytter On the complexity of decidable cases of the commutation problem of languages . . 105--118 I. McQuillan The generative capacity of block-synchronized context-free grammars 119--133 T. C. Edwin Cheng and Hans Kellerer and Vladimir Kotov Semi-on-line multiprocessor scheduling with given total processing time . . . . 134--146 Paola Flocchini and Giuseppe Prencipe and Nicola Santoro and Peter Widmayer Gathering of asynchronous robots with limited visibility . . . . . . . . . . . 147--168 Wai-Fong Chuan Factors of characteristic words of irrational numbers . . . . . . . . . . . 169--182 Etsuro Moriya and Dieter Hofbauer and Maria Huber and Friedrich Otto On state-alternating context-free grammars . . . . . . . . . . . . . . . . 183--216 Philip Bille A survey on tree edit distance and related problems . . . . . . . . . . . . 217--239 Vânia M. F. Dias and Celina M. H. de Figueiredo and Jayme L. Szwarcfiter Generating bicliques of a graph in lexicographic order . . . . . . . . . . 240--248 Michael Elkin and David Peleg Approximating $k$-spanner problems for $ k > 2$ . . . . . . . . . . . . . . . . . 249--277 Dimitar P. Guelev and Dang Van Hung On the completeness and decidability of duration calculus with iteration . . . . 278--304 Jianer Chen and Iyad A. Kanj On approximating minimum vertex cover for graphs with perfect matching . . . . 305--318 Martin Aigner and Gianluca De Marco and Manuela Montangero The plurality problem with three colors and more . . . . . . . . . . . . . . . . 319--330 Bodo Manthey and Rüdiger Reischuk The intractability of computing the Hamming distance . . . . . . . . . . . . 331--346 Shlomo Hoory and Stefan Szeider Computing unsatisfiable $k$-SAT instances with few occurrences per variable . . . . . . . . . . . . . . . . 347--359 Arthur W. Chou and Ker-I Ko The computational complexity of distance functions of two-dimensional domains . . 360--369 Sun-Yuan Hsieh Embedding longest fault-free paths onto star graphs with more vertex faults . . 370--378 H. Bruin and O. Volkova The complexity of Fibonacci-like kneading sequences . . . . . . . . . . . 379--389 Li-Sha Huang and Minming Li and Bo Zhang Approximation of Walrasian equilibrium in single-minded auctions . . . . . . . 390--398 Anonymous Author index . . . . . . . . . . . . . . 399--400 Anonymous Editorial board . . . . . . . . . . . . v--ix
Andrzej M. Borzyszkowski and Philippe Darondeau Transition systems without transitions 1--16 Alan Jeffrey and Julian Rathke A fully abstract may testing semantics for concurrent objects . . . . . . . . . 17--63 Giovanna D'Agostino and Giacomo Lenzi An axiomatization of bisimulation quantifiers via the $ \mu $-calculus . . 64--95 Yuxi Fu On quasi-open bisimulation . . . . . . . 96--126 Chiaki Sakama Ordering default theories and nonmonotonic logic programs . . . . . . 127--152 Cormac Flanagan and Stephen N. Freund and Shaz Qadeer and Sanjit A. Seshia Modular verification of multithreaded programs . . . . . . . . . . . . . . . . 153--183 James Worrell On the final sequence of a finitary set functor . . . . . . . . . . . . . . . . 184--199 Mircea-Dan Hernest and Ulrich Kohlenbach A complexity analysis of functional interpretations . . . . . . . . . . . . 200--246 Yannick Chevalier and Ralf Küsters and Michaël Rusinowitch and Mathieu Turuani An NP decision procedure for protocol insecurity with XOR . . . . . . . . . . 247--274 Carsten Fritz and Thomas Wilke Simulation relations for alternating Büchi automata . . . . . . . . . . . . . 275--314 Andrzej S. Murawski Functions with local state: Regularity and undecidability . . . . . . . . . . . 315--349 Antonio Bueno and Valentín Valero and Fernando Cuartero A translation of TPAL$_p$ into a class of timed-probabilistic Petri nets . . . 350--392 Michele Boreale and Maria Grazia Buscemi A method for symbolic analysis of security protocols . . . . . . . . . . . 393--425 Anonymous Author index . . . . . . . . . . . . . . 426--426 Anonymous Editorial board . . . . . . . . . . . . v--ix
T. Harju and J. Karhumäki and A. Restivo Preface . . . . . . . . . . . . . . . . 1--2 S. I. Adian Divisibility problem for one relator monoids . . . . . . . . . . . . . . . . 3--6 James D. Currie Pattern avoidance: themes and variations 7--18 Narad Rampersad and Jeffrey Shallit and Ming-wei Wang Avoiding large squares in infinite binary words . . . . . . . . . . . . . . 19--34 Leszek Ga\csieniec and Roman Kolpakov and Igor Potapov Space efficient search for maximal repetitions . . . . . . . . . . . . . . 35--48 Sorin Constantinescu and Lucian Ilie Generalised fine and Wilf's theorem for arbitrary number of periods . . . . . . 49--60 \vSt\vepán Holub A proof of the extended Duval's conjecture . . . . . . . . . . . . . . . 61--67 A. E. Frid Sequences of linear arithmetical complexity . . . . . . . . . . . . . . . 68--87 Isabel M. Araújo and Véronique Bruy\`ere Sturmian words and a criterium by Michaux--Villemaire . . . . . . . . . . 88--102 F. Levé and G. Richomme On a conjecture about finite fixed points of morphisms . . . . . . . . . . 103--128 F. Hivert and J.-C. Novelli and J.-Y. Thibon The algebra of binary search trees . . . 129--165 Anonymous Editorial board . . . . . . . . . . . . v--ix
Yijia Chen and Jörg Flum and Martin Grohe Machine-based methods in parameterized complexity theory . . . . . . . . . . . 167--199 Andreas Maletti HASSE diagrams for classes of deterministic bottom-up tree-to-tree-series transformations . . 200--240 Shengyu Zhang On the power of Ambainis lower bounds 241--256 Cheng-Kuan Lin and Hua-Min Huang and Lih-Hsing Hsu The super connectivity of the pancake graphs and the super laceability of the star graphs . . . . . . . . . . . . . . 257--271 Cristina Bazgan and Bruno Escoffier and Vangelis Th. Paschos Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness 272--292 Yong He and Yiwei Jiang Optimal semi-online preemptive algorithms for machine covering on two uniform machines . . . . . . . . . . . . 293--314 Amitabha Bagchi and Amitabh Chaudhary and Petr Kolman Short length Menger's theorem and reliable optical routing . . . . . . . . 315--332 Peter Damaschke and Zhen Zhou On queuing lengths in on-line switching 333--343 Murray Elder A context-free and a $1$-counter geodesic language for a Baumslag--Solitar group . . . . . . . . 344--371 Anonymous Author index . . . . . . . . . . . . . . 372--373
Roberto Gorrieri and Fabio Martinelli Theoretical foundations of security analysis and design II . . . . . . . . . 1--2 Alessandra Di Pierro and Chris Hankin and Herbert Wiklicky Measuring the confinement of probabilistic systems . . . . . . . . . 3--56 Jonathan Herzog A computational interpretation of Dolev--Yao adversaries . . . . . . . . . 57--81 Gordon Thomas Rohrmair and Gavin Lowe Using data-independence in the analysis of intrusion detection systems . . . . . 82--101 Karthikeyan Bhargavan and Cédric Fournet and Andrew D. Gordon A semantics for web services authentication . . . . . . . . . . . . . 102--153 Roberto Zunino and Pierpaolo Degano Weakening the perfect encryption assumption in Dolev--Yao adversaries . . 154--178 Anonymous Editorial board . . . . . . . . . . . . v--ix
A. de Luca and F. Mignosi and D. Perrin and G. Rozenberg Preface . . . . . . . . . . . . . . . . 179--185 Anonymous Editorial: From Antonio's former students . . . . . . . . . . . . . . . . 186--187 Arto Salomaa Connections between subwords and certain matrix mappings . . . . . . . . . . . . 188--203 Isabel M. Araújo and Véronique Bruy\`ere Words derivated from Sturmian words . . 204--219 Arturo Carpi and Aldo de Luca Codes of central Sturmian words . . . . 220--239 Clelia De Felice An enhanced property of factorizing codes . . . . . . . . . . . . . . . . . 240--256 Stefano Crespi Reghizzi and Matteo Pradella Tile rewriting grammars and picture languages . . . . . . . . . . . . . . . 257--272 Tero Harju and Dirk Nowotka Counting bordered and primitive words with a fixed weight . . . . . . . . . . 273--279 Jean Berstel Growth of repetition-free words --- a review . . . . . . . . . . . . . . . . . 280--290 Zoltán Ésik and Pascal Weil Algebraic recognizability of regular tree languages . . . . . . . . . . . . . 291--321 Juhani Karhumäki and Michel Latteux and Ion Petre Commutation with codes . . . . . . . . . 322--333 J.-P. Borel and C. Reutenauer Palindromic factors of billiard words 334--348 Paola Bonizzoni and Giancarlo Mauri Regular splicing languages and subclasses . . . . . . . . . . . . . . . 349--363 Christian Choffrut and Berke Durak Collage of two-dimensional words . . . . 364--380 Marie-Pierre Béal and Dominique Perrin Codes and sofic constraints . . . . . . 381--393 Alberto Bertoni and Carlo Mereghetti and Beatrice Palano Small size quantum automata recognizing some regular languages . . . . . . . . . 394--407 Marcella Anselmo and Dora Giammarresi and Maria Madonia New operations and regular expressions for two-dimensional languages over one-letter alphabet . . . . . . . . . . 408--431 Julien Clément and Jean-Pierre Duval and Giovanna Guaiana and Dominique Perrin and Giuseppina Rindone Parsing with a finite dictionary . . . . 432--442 Jean-Éric Pin and Pedro V. Silva A topological approach to transductions 443--456
K. Auinger and B. Steinberg Constructing divisions into power groups 1--21 Eden Chlamtac and Uriel Feige Improved approximation of the minimum cover time . . . . . . . . . . . . . . . 22--38 Yan-Cheng Chang and Chi-Jen Lu Oblivious polynomial evaluation and oblivious neural learning . . . . . . . 39--54 Clemens Heuberger and Rajendra Katti and Helmut Prodinger and Xiaoyu Ruan The alternating greedy expansion and applications to computing digit expansions from left-to-right in cryptography . . . . . . . . . . . . . . 55--72 J. Sawada Oracles for vertex elimination orderings 73--90 Peter Gács Uniform test of algorithmic randomness over a general space . . . . . . . . . . 91--137 Atsuyuki Inoue and Akira Ito and Katsushi Inoue and Tokio Okazaki Some properties of one-pebble Turing machines with sublogarithmic space . . . 138--149 Xiaochun Cheng and Dantong Ouyang and Jiang Yunfei and Chengqi Zhang An improved model-based method to test circuit faults . . . . . . . . . . . . . 150--161 Pieter Collins Continuity and computability of reachable sets . . . . . . . . . . . . . 162--195 Cheng-Nan Lai and Gen-Huey Chen Strong Rabin numbers of folded hypercubes . . . . . . . . . . . . . . . 196--215 Guido Schäfer and Naveen Sivadasan Topology matters: Smoothed competitiveness of metrical task systems 216--246 Blanca Cases and Manuel Alfonseca Towards a proof of the decidability of the momentary stagnation of the growth function of D . . . . . . . . . . . . . 247--262 Maurice H. ter Beek and Carlos Martín-Vide and Victor Mitrana Synchronized shuffles . . . . . . . . . 263--275 Giuseppe Pirillo Inequalities characterizing standard Sturmian and episturmian words . . . . . 276--292 Valérie Berthé and Sre\vcko Brlek and Philippe Choquette Smooth words over arbitrary alphabets 293--310 Subhamoy Maitra and Kishan Chand Gupta and Ayineedi Venkateswarlu Results on multiples of primitive polynomials and their products over GF(2) . . . . . . . . . . . . . . . . . 311--343 Zhe Dang and Oscar H. Ibarra and Jianwen Su On composition and lookahead delegation of e-services modeled by automata . . . 344--363 Hiroshi Nagamochi and Kengo Iwata and Toshimasa Ishii A robust algorithm for bisecting a triconnected graph with two resource sets . . . . . . . . . . . . . . . . . . 364--378 Zden\vek Troní\vcek and Ayumi Shinohara The size of subsequence automaton . . . 379--384 Quincy Wu and Chin Lung Lu and Richard Chia-Tung Lee The approximability of the weighted Hamiltonian path completion problem on a tree . . . . . . . . . . . . . . . . . . 385--397 Wei-Mei Chen Probabilistic analysis of algorithms for the Dutch national flag problem . . . . 398--410 Ruo-Wei Hung and Maw-Shang Chang Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs . . . . . . . 411--440 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Eugenio Moggi Applied semantics: Selected topics . . . 1--2 Michael Abbott and Thorsten Altenkirch and Neil Ghani Containers: Constructing strictly positive types . . . . . . . . . . . . . 3--27 Mark R. Shinwell and Andrew M. Pitts On a monadic semantics for freshness . . 28--55 David Cachera and Thomas Jensen and David Pichardie and Vlad Rusu Extracting a data flow analyser in constructive logic . . . . . . . . . . . 56--78 Sandra Alves and Mário Florido Weak linearization of the lambda calculus . . . . . . . . . . . . . . . . 79--103 Philippa Gardner and Sergio Maffeis Modelling dynamic web data . . . . . . . 104--131 J. Laird Locally Boolean domains . . . . . . . . 132--148 Mads Sig Ager and Olivier Danvy and Jan Midtgaard A functional correspondence between monadic evaluators and abstract machines for languages with computational effects 149--172 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Bruno Courcelle and Pascal Weil The recognizability of sets of graphs is a robust property . . . . . . . . . . . 173--228 Esfandiar Haghverdi and Paulo Tabuada and George J. Pappas Bisimulation relations for dynamical, control, and hybrid systems . . . . . . 229--261 Frank J. Oles Precedence--inclusion patterns and relational learning . . . . . . . . . . 262--315 Rance Cleaveland and S. Purushothaman Iyer and Murali Narasimha Probabilistic temporal logics via the modal mu-calculus . . . . . . . . . . . 316--350 Yann Loyer and Umberto Straccia Any-world assumptions in logic programming . . . . . . . . . . . . . . 351--381 Christos Nomikos and Panos Rondogiannis and Manolis Gergatsoulis Temporal stratification tests for linear and branching-time deductive databases 382--415
Samson Abramsky and Marios Mavronicolas Game Theory Meets Theoretical Computer Science . . . . . . . . . . . . . . . . 1--3 Luis López and Gemma del Rey Almansa and Stéphane Paquelet and Antonio Fernández A mathematical model for the TCP Tragedy of the Commons . . . . . . . . . . . . . 4--26 Christoph Ambühl and Andrea E. F. Clementi and Paolo Penna and Gianluca Rossi and Riccardo Silvestri On the approximability of the range assignment problem on radio networks in presence of selfish agents . . . . . . . 27--41 Oswin Aichholzer and David Bremner and Erik D. Demaine and Ferran Hurtado and Evangelos Kranakis and Hannes Krasser and Suneeta Ramaswami and Saurabh Sethia and Jorge Urrutia Games on triangulations . . . . . . . . 42--71 Robert A. Hearn and Erik D. Demaine PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation . . . . . . . . . . . . . 72--96 Yoav Shoham and Moshe Tennenholtz Non-cooperative computation: Boolean functions with correctness and exclusivity . . . . . . . . . . . . . . 97--113 Joan Feigenbaum and Lance Fortnow and David M. Pennock and Rahul Sami Computation in a distributed information market . . . . . . . . . . . . . . . . . 114--132 M. Gairing and T. Lücking and M. Mavronicolas and B. Monien and P. Spirakis Structure and complexity of extreme Nash equilibria . . . . . . . . . . . . . . . 133--157 Oleg Verbitsky The first order definability of graphs with separators via the Ehrenfeucht game 158--176 Olivier Laurent Syntax vs. semantics: a polarized approach . . . . . . . . . . . . . . . . 177--206 Andrzej S. Murawski Games for complexity of second-order call-by-name programs . . . . . . . . . 207--236 Paul-André Melli\`es Sequential algorithms and strongly stable functions . . . . . . . . . . . . 237--281 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Frank de Boer and Marcello Bonsangue Preface . . . . . . . . . . . . . . . . 283--284 J. A. Bergstra and I. Bethke Polarized process algebra with reactive composition . . . . . . . . . . . . . . 285--304 R\uazvan Diaconescu Behavioural specification for hierarchical object composition . . . . 305--331 Jan Friso Groote and Tim A. C. Willemse Parameterised Boolean equation systems 332--369 Yuri Gurevich and Benjamin Rossman and Wolfram Schulte Semantic essence of AsmL . . . . . . . . 370--412 Cees Pierik and Frank S. de Boer A proof outline logic for object-oriented programming . . . . . . 413--442 J. J. M. M. Rutten A tutorial on coinductive stream calculus and signal flow graphs . . . . 443--481 Robert F. Stärk Formal specification and verification of the C# thread model . . . . . . . . . . 482--508 Heike Wehrheim Slicing techniques for verification re-use . . . . . . . . . . . . . . . . . 509--528
Sotiris Nikoletseas and Jose Rolim Preface . . . . . . . . . . . . . . . . 1--2 Christos H. Papadimitriou and David Ratajczak On a conjecture related to geometric routing . . . . . . . . . . . . . . . . 3--14 Mihaela Enachescu and Ashish Goel and Ramesh Govindan and Rajeev Motwani Scale-free aggregation in sensor networks . . . . . . . . . . . . . . . . 15--29 Patrik Floréen and Petteri Kaski and Jukka Kohonen and Pekka Orponen Exact and approximate balanced data gathering in energy-constrained sensor networks . . . . . . . . . . . . . . . . 30--46 R. O'Dell and R. Wattenhofer Theoretical aspects of connectivity-based multi-hop positioning 47--68 Pierre Leone and José Rolim Towards a dynamical model for wireless sensor networks . . . . . . . . . . . . 69--85 Gideon Stupp and Moshe Sidi The expected uncertainty of range-free localization protocols in sensor networks . . . . . . . . . . . . . . . . 86--99 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
G. Rozenberg Preface . . . . . . . . . . . . . . . . 101--102 Hongtao Lu and Ruiming Shen and Fu-Lai Chung Absolute exponential stability of a class of recurrent neural networks with multiple and variable delays . . . . . . 103--119 Oscar H. Ibarra On determinism versus nondeterminism in P systems . . . . . . . . . . . . . . . 120--133 Mingsheng Ying A theory of computation based on quantum logic (I) . . . . . . . . . . . . . . . 134--207 Simon Fischer and Ingo Wegener The one-dimensional Ising model: Mutation versus recombination . . . . . 208--225 Sergey Verlan A boundary result on enhanced time-varying distributed H systems with parallel computations . . . . . . . . . 226--242 Marco Dorigo and Christian Blum Ant colony optimization theory: a survey 243--278 David Soloveichik and Erik Winfree The computational power of Benenson automata . . . . . . . . . . . . . . . . 279--297 Aurélie Goulon-Sigwalt-Abram and Arthur Duprat and Gérard Dreyfus From Hopfield nets to recursive networks to graph machines: Numerical machine learning for structured data . . . . . . 298--334 Yaoyun Shi Quantum and classical tradeoffs . . . . 335--345
Kurt Jensen and Andreas Podelski Special issue . . . . . . . . . . . . . 1--1 Christel Baier and Holger Hermanns and Joost-Pieter Katoen and Boudewijn R. Haverkort Efficient computation of time-bounded reachability probabilities in uniform continuous-time Markov decision processes . . . . . . . . . . . . . . . 2--26 D. Lugiez and P. Niebert and S. Zennou A partial order semantics approach to the clock explosion problem of timed automata . . . . . . . . . . . . . . . . 27--59 Jaco Geldenhuys and Antti Valmari More efficient on-the-fly LTL verification with Tarjan's algorithm . . 60--82 Orna Kupferman and Moshe Y. Vardi From complementation to certification 83--100 K. L. McMillan An interpolating theorem prover . . . . 101--121 Zhendong Su and David Wagner A class of polynomially solvable range constraints for interval analysis without widenings . . . . . . . . . . . 122--138 Luca de Alfaro and Marco Faella and Thomas A. Henzinger and Rupak Majumdar and Mariëlle Stoelinga Model checking discounted temporal properties . . . . . . . . . . . . . . . 139--170 Anonymous Special issue . . . . . . . . . . . . . v--ix
V. Koubek and J. Kratochvíl Preface . . . . . . . . . . . . . . . . 171--172 Sebastian Bab and Arfst Nickelsen One query reducibilities between partial information classes . . . . . . . . . . 173--189 Marie-Pierre Béal and Francesca Fiorenzi and Dominique Perrin A hierarchy of shift equivalent sofic shifts . . . . . . . . . . . . . . . . . 190--205 Martin Beaudry and José M. Fernandez and Markus Holzer A common algebraic description for probabilistic and quantum computations 206--234 Vincent Bernardi and Bruno Durand and Enrico Formenti and Jarkko Kari A new dimension sensitive property for cellular automata . . . . . . . . . . . 235--247 Alina Beygelzimer and Mitsunori Ogihara The enumerability of P collapses P to NC 248--259 E. Böhler and C. Glaßer and B. Schwarz and K. W. Wagner Generation problems . . . . . . . . . . 260--295 Elena Czeizler The non-parametrizability of the word equation xyz . . . . . . . . . . . . . . 296--303 Michael Domaratzki and Kai Salomaa Decidability of trajectory-based equations . . . . . . . . . . . . . . . 304--330 Pierre Fraigniaud and David Ilcinkas and Guy Peer and Andrzej Pelc and David Peleg Graph exploration by a finite automaton 331--344 Edith Hemaspaandra and Lane A. Hemaspaandra and Harald Hempel All superlinear inverse schemes are coNP-hard . . . . . . . . . . . . . . . 345--358 Lucian Ilie and Pascal Ochem and Jeffrey Shallit A generalization of repetition threshold 359--369 Akinori Kawachi and Hirotada Kobayashi and Takeshi Koshiba and Raymond H. Putra Universal test for quantum one-way permutations . . . . . . . . . . . . . . 370--385 Troy Lee and Andrei Romashchenko Resource bounded symmetry of information revisited . . . . . . . . . . . . . . . 386--405 Gustav Nordh The complexity of equivalence and isomorphism of systems of equations over finite groups . . . . . . . . . . . . . 406--424 Alexander Okhotin The dual of concatenation . . . . . . . 425--447 Victor L. Selivanov and Klaus W. Wagner A reducibility for the dot-depth hierarchy . . . . . . . . . . . . . . . 448--472 Klaus Wich Sublogarithmic ambiguity . . . . . . . . 473--504
Antonio Cerone and Alessandra Di Pierro Preface . . . . . . . . . . . . . . . . 1--2 Karl Lermer and Colin J. Fidge and Ian J. Hayes A theory for execution-time derivation in real-time programs . . . . . . . . . 3--27 Mario Bravetti and Roberto Gorrieri and Roberto Lucchi and Gianluigi Zavattaro Quantitative information in the tuple space coordination model . . . . . . . . 28--57 María Alpuente and María del Mar Gallardo and Ernesto Pimentel and Alicia Villanueva A semantic framework for the abstract model checking of tccp . . . . . . . . . 58--95 Joe Hurd and Annabelle McIver and Carroll Morgan Probabilistic guarded commands mechanized in HOL . . . . . . . . . . . 96--112 Michael Huth On finite-state approximants for probabilistic computation tree logic . . 113--134 Alberto Lluch-Lafuente and Ugo Montanari Quantitative $ \mu $-calculus and CTL defined over constraint semirings . . . 135--160 P. G. Harrison and T. T. Lee Separable equilibrium state probabilities via time reversal in Markovian process algebra . . . . . . . 161--182 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Elisa Pergola and Simone Rinaldi Preface . . . . . . . . . . . . . . . . 183--183 E. Pergola and S. Rinaldi In memoriam: Alberto Del Lungo (1965--2003) . . . . . . . . . . . . . . 184--188 Jean-Luc Baril and Vincent Vajnovszki Minimal change list for Lucas strings and some graph theoretic consequences 189--199 S. Brlek and G. Labelle and A. Lacasse The discrete Green Theorem and some applications in discrete geometry . . . 200--225 Frédéric Chavanon and Matthieu Latapy and Michel Morvan and Eric Rémila and Laurent Vuillon Graph encoding of 2 D . . . . . . . . . 226--253 Anna de Mier and Marc Noy A solution to the tennis ball problem 254--264 Chiara Epifanio and Filippo Mignosi A multidimensional critical factorization theorem . . . . . . . . . 265--280 Edgar Garduño and Gabor T. Herman Implicit surface visualization of reconstructed biological molecules . . . 281--299 Y. Gerard Reduction from three-dimensional discrete tomography to multicommodity flow problem . . . . . . . . . . . . . . 300--306 Dominique Gouyou-Beauchamps and Pierre Leroux Enumeration of symmetry classes of convex polyominoes on the honeycomb lattice . . . . . . . . . . . . . . . . 307--334 Attila Kuba and Murice Nivat A sufficient condition for non-uniqueness in binary tomography with absorption . . . . . . . . . . . . . . . 335--357 Guy Louchard Monotone runs of uniformly distributed integer random variables: a probabilistic analysis . . . . . . . . . 358--387 Conrado Martínez and Xavier Molinero Efficient iteration in admissible combinatorial classes . . . . . . . . . 388--417 P. Massazza and R. Radicioni On computing the coefficients of bivariate holonomic formal series . . . 418--438 C. Picouleau Reconstruction of convex polyominoes from orthogonal projections of their contours . . . . . . . . . . . . . . . . 439--454 Robert A. Sulanke Three dimensional Narayana and Schröder numbers . . . . . . . . . . . . . . . . 455--468 Robert Tijdeman Rauzy substitutions and multi-dimensional Sturmian words . . . . 469--489
Tatjana Petkovi\'c and Saeed Salehi Positive varieties of tree languages . . 1--35 Paola Bonizzoni and Gianluca Della Vedova and Riccardo Dondi Reconciling a gene tree to a species tree under the duplication cost model 36--53 Victor D. Chepoi and Feodor F. Dragan and Chenyu Yan Additive sparse spanners for graphs with bounded length of largest induced cycle 54--75 Frank Gurski and Egon Wanke On the relationship between NLC-width and linear NLC-width . . . . . . . . . . 76--89 Tomoyuki Yamakami and Toshio Suzuki Resource bounded immunity and simplicity 90--129 Chryssis Georgiou and Dariusz R. Kowalski and Alexander A. Shvartsman Efficient gossip and robust distributed computation . . . . . . . . . . . . . . 130--166 Peter R. J. Asveld Fuzzy context-free languages---Part 1: Generalized fuzzy context-free grammars 167--190 Peter R. J. Asveld Fuzzy context-free languages---Part 2: Recognition and parsing algorithms . . . 191--213 Krzysztof C. Kiwiel On Floyd and Rivest's SELECT algorithm 214--238 Kimmo Fredriksson and Gonzalo Navarro and Esko Ukkonen Sequential and indexed two-dimensional combinatorial template matching allowing rotations . . . . . . . . . . . . . . . 239--275 Zoltán Fülöp and Armin Kühnemann and Heiko Vogler Linear deterministic multi bottom-up tree transducers . . . . . . . . . . . . 276--287 Zhaohui Liu and T. C. Edwin Cheng Approximation schemes for minimizing total (weighted) completion time with release dates on a batch machine . . . . 288--298 Éric Schost There is no efficient reverse derivation mode for discrete derivatives . . . . . 299--305 H. K. Hsiao and Y. T. Yeh and S. S. Yu Dependences related to strict binary relations . . . . . . . . . . . . . . . 306--324 Peter Bro Miltersen and Jaikumar Radhakrishnan and Ingo Wegener On converting CNF to DNF . . . . . . . . 325--335 G. Castiglione and A. Frosini and A. Restivo and S. Rinaldi Enumeration of L-convex polyominoes by rows and columns . . . . . . . . . . . . 336--352 Emanuele Munarini and Damiano Torri Cayley continuants . . . . . . . . . . . 353--369 Andrea Frosini and Maurice Nivat and Laurent Vuillon An introduction to periodical discrete sets from a tomographical perspective 370--392 Sara Brunetti and Alain Daurat Random generation of Q-convex sets . . . 393--414 N. V. Vinodchandran A note on the circuit complexity of PP 415--418 Tero Harju and Arto Lepistö and Dirk Nowotka A characterization of periodicity of bi-infinite words . . . . . . . . . . . 419--422 Feng Feng and Xianzhong Zhao and Young Bae Jun *-$ \mu $-semirings and *-$ \lambda $-semirings . . . . . . . . . . . . . . 423--431 A. Daurat and Y. Gérard and M. Nivat Some necessary clarifications about the chords' problem and the Partial Digest Problem . . . . . . . . . . . . . . . . 432--436 J.-M. Champarnaud and F. Coulon Erratum to ``NFA reduction algorithms by means of regular inequalities'' [Theoret. Comput. Sci. 327 (2004) 241--253] . . . . . . . . . . . . . . . 437--440 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Samson Abramsky A structural approach to reversible computation . . . . . . . . . . . . . . 441--464 Zurab Khasidashvili and John Glauert The conflict-free Reduction Geometry . . 465--497 Ivo Düntsch and Michael Winter A representation theorem for Boolean contact algebras . . . . . . . . . . . . 498--512
H. Arimura and S. Jain Preface . . . . . . . . . . . . . . . . 1--2 Osamu Watanabe Sequential sampling techniques for algorithmic learning theory . . . . . . 3--14 Steffen Lange and Gunter Grieser and Thomas Zeugmann Inductive inference of approximations for recursive concepts . . . . . . . . . 15--40 Jochen Nessel and Steffen Lange Learning erasing pattern languages with queries . . . . . . . . . . . . . . . . 41--57 Ken Satoh Learning taxonomic relation by case-based reasoning . . . . . . . . . . 58--69 François Denis and Rémi Gilleron and Fabien Letouzey Learning from positive and unlabeled examples . . . . . . . . . . . . . . . . 70--83 Kouichi Hirata Prediction-hardness of acyclic conjunctive queries . . . . . . . . . . 84--94 Bhaskar DasGupta and Barbara Hammer On approximate learning by multi-layered feedforward circuits . . . . . . . . . . 95--127 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Josep Díaz and Juhani Karhumaki Preface . . . . . . . . . . . . . . . . 129--129 Olivier Bournez and Emmanuel Hainry Elementarily computable functions over the real numbers and $ \mathbb {R} $-sub-recursive functions . . . . . . . 130--147 Andrei Bulatov and Martin Grohe The complexity of partition functions 148--186 Zden\vek Dvo\vrák and Daniel Král' and Ond\vrej Pangrác Locally consistent constraint satisfaction problems . . . . . . . . . 187--206 Joan Feigenbaum and Sampath Kannan and Andrew McGregor and Siddharth Suri and Jian Zhang On graph problems in a semi-streaming model . . . . . . . . . . . . . . . . . 207--216 Lisa Fleischer Linear tolls suffice: New bounds and algorithms for tolls in single source networks . . . . . . . . . . . . . . . . 217--225 Dimitris Fotakis and Spyros Kontogiannis and Paul Spirakis Selfish unsplittable flows . . . . . . . 226--239 Eran Halperin and Richard M. Karp The minimum-entropy set cover problem 240--250 Shlomo Hoory and Avner Magen and Steven Myers and Charles Rackoff Simple permutations mix well . . . . . . 251--261 Robert Krauthgamer and James R. Lee The black-box complexity of nearest-neighbor search . . . . . . . . 262--276 Michal Kunc Regular solutions of language inequalities and well quasi-orders . . . 277--293 Emmanuelle Lebhar and Nicolas Schabanel Close to optimal decentralized routing in long-range contact networks . . . . . 294--310 Dieter van Melkebeek and Ran Raz A time lower bound for satisfiability 311--320 Michael Soltys LA, permutations, and the Hajós Calculus 321--333 Sergei Vassilvitskii and Mihalis Yannakakis Efficiently computing succinct trade-off curves . . . . . . . . . . . . . . . . . 334--356 Ryan Williams A new algorithm for optimal 2-constraint satisfaction and its implications . . . 357--365
Jaroslav Ne\vset\vril and Gerhard Woeginger Graph colorings . . . . . . . . . . . . 1--1 Hans L. Bodlaender and Andreas Brandstädt and Dieter Kratsch and Michaël Rao and Jeremy Spinrad On algorithms for ($P$,gem)-free graphs 2--21 Hans L. Bodlaender and Fedor V. Fomin Equitable colorings of bounded treewidth graphs . . . . . . . . . . . . . . . . . 22--30 Andrei A. Bulatov H-Coloring dichotomy revisited . . . . . 31--39 Josep Díaz and Vishal Sanwalani and Maria Serna and Paul G. Spirakis The chromatic and clique numbers of random scaled sector graphs . . . . . . 40--51 Tomás Feder and Pavol Hell and Sulamita Klein and Loana Tito Nogueira and Fábio Protti List matrix partitions of chordal graphs 52--66 Ji\vrí Fiala and Daniël Paulusma A complete complexity classification of the role assignment problem . . . . . . 67--81 A. V. Kostochka and K. Nakprasit On equitable $ \Delta $-coloring of graphs with low average degree . . . . . 82--91 Anja Kohl and Jens Schreyer and Zsolt Tuza and Margit Voigt List version of $ L(d, s) $-labelings 92--98 Daniel Král' Group coloring is $ \Pi_2^p $-complete 99--111 Edita Má\vcajová and Martin \vSkoviera Fano colourings of cubic graphs and the Fulkerson Conjecture . . . . . . . . . . 112--120 Anonymous Editorial Board . . . . . . . . . . . . v--ix
H. Jaap van den Herik and Hiroyuki Iida Foreword . . . . . . . . . . . . . . . . 121--122 Ryan Hayward and Yngvi Björnsson and Michael Johanson and Morgan Kan and Nathan Po and Jack van Rijswijck Solving 7$ \times $7 Hex with domination, fill-in, and virtual connections . . . . . . . . . . . . . . 123--139 M. S. Bourzutschky and J. A. Tamplin and G. McC. Haworth Chess endgames: 6-man data and strategy 140--157 R. B. Andrist and G. Mc. Haworth Deeper model endgame analysis . . . . . 158--167 Erik C. D. van der Werf and H. Jaap van den Herik and Jos W. H. M. Uiterwijk Learning to score final positions in the game of Go . . . . . . . . . . . . . . . 168--183 Katsuhiko Nakamura Static analysis based on formal models and incremental computation in Go programming . . . . . . . . . . . . . . 184--201 D. Gomboc and M. Buro and T. A. Marsland Tuning evaluation functions by maximizing concordance . . . . . . . . . 202--229 Jens Lieberum An evaluation function for the game of amazons . . . . . . . . . . . . . . . . 230--244 H. H. L. M. Donkers and H. J. van den Herik and J. W. H. M. Uiterwijk Selecting evaluation functions in Opponent-Model search . . . . . . . . . 245--267 A. Sadikov and I. Bratko and I. Kononenko Bias and pathology in minimax search . . 268--281
Alexander Okhotin Unresolved systems of language equations: Expressive power and decision problems . . . . . . . . . . . . . . . . 283--308 R. E. L. Aldred and M. D. Atkinson and H. P. van Ditmarsch and C. C. Handley and D. A. Holton and D. J. McCaughan Permuting machines and priority queues 309--317 F. Blanchard and J. Cervelle and E. Formenti Some results about the chaotic behavior of cellular automata . . . . . . . . . . 318--336 Leah Epstein and Asaf Levin The chord version for SONET ADMs minimization . . . . . . . . . . . . . . 337--346 Henrik Björklund and Sergei Vorobyov Combinatorial structure and randomized subexponential algorithms for infinite games . . . . . . . . . . . . . . . . . 347--360 Mark Cieliebak and Stephan Eidenbenz and Paolo Penna Partial Digest is hard to solve for erroneous input data . . . . . . . . . . 361--381 Edith Hemaspaandra and Holger Spakowski and Jörg Vogel The complexity of Kemeny elections . . . 382--391 Chris Bourke and John M. Hitchcock and N. V. Vinodchandran Entropy rates and finite-state dimension 392--406 Bang Ye Wu An analysis of the LPT algorithm for the max--min and the min--ratio partition problems . . . . . . . . . . . . . . . . 407--419 Sergey Kitaev Segmental partially ordered generalized patterns . . . . . . . . . . . . . . . . 420--428 Wai-Fong Chuan and Hui-Ling Ho Locating factors of the infinite Fibonacci word . . . . . . . . . . . . . 429--442 Martin Kutz Conway's Angel in three dimensions . . . 443--451 Weigen Yan and Yeong-Nan Yeh and Fuji Zhang Graphical condensation of plane graphs: a combinatorial approach . . . . . . . . 452--461 Marc Demange and Tìnaz Ekim and Dominique de Werra $ (p, k)$-coloring problems in line graphs . . . . . . . . . . . . . . . . . 462--474 Toshio Nakata On the expected time for Herman's probabilistic self-stabilizing algorithm 475--483 F. Cazals and C. Karande An algorithm for reporting maximal $c$-cliques . . . . . . . . . . . . . . 484--490
Nicol\`o Cesa-Bianchi and Rüdiger Reischuk and Thomas Zeugmann Foreword . . . . . . . . . . . . . . . . 1--2 Kazuyuki Amano and Akira Maruoka On learning monotone Boolean functions under the uniform distribution . . . . . 3--12 Rocco A. Servedio On learning embedded midbit functions 13--23 Nader H. Bshouty and Lynn Burroughs Maximizing agreements and coagnostic learning . . . . . . . . . . . . . . . . 24--39 Jürgen Forster and Hans Ulrich Simon On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes . . . . . . . . . . . . . . . . 40--48 Johannes Köbler and Wolfgang Lindner The complexity of learning concept classes with polynomial general dimension . . . . . . . . . . . . . . . 49--62 Yusuke Suzuki and Takayoshi Shoudai and Tomoyuki Uchida and Tetsuhiro Miyahara Ordered term tree languages which are polynomial time inductively inferable from positive data . . . . . . . . . . . 63--90 Daniel Reidenbach A non-learnable class of E-pattern languages . . . . . . . . . . . . . . . 91--102 Éric Martin and Arun Sharma and Frank Stephan Unifying logic, topology and learning in Parametric logic . . . . . . . . . . . . 103--124 Susumu Hayashi Mathematics based on incremental learning---Excluded middle and inductive inference . . . . . . . . . . . . . . . 125--139 Bertram Fronhöfer and Akihiro Yamamoto Hypothesis finding with proof theoretical appropriateness criteria . . 140--162 Anonymous Foreword . . . . . . . . . . . . . . . . v--ix
Donald Sannella Preface . . . . . . . . . . . . . . . . 163--163 Mikolaj Boja\'nczyk and Thomas Colcombet Tree-walking automata cannot be determinized . . . . . . . . . . . . . . 164--173 Anuj Dawar and Erich Grädel and Stephan Kreutzer Backtracking games and inflationary fixed points . . . . . . . . . . . . . . 174--187 Yuxin Deng and Davide Sangiorgi Towards an algebraic theory of typed mobile processes . . . . . . . . . . . . 188--212 Claudia Faggian Interactive observability in Ludics: The geometry of tests . . . . . . . . . . . 213--233 D. R. Ghica and A. S. Murawski and C.-H. L. Ong Syntactic control of concurrency . . . . 234--251 Esfandiar Haghverdi and Philip Scott A categorical model for the geometry of interaction . . . . . . . . . . . . . . 252--274 J. Laird A calculus of coroutines . . . . . . . . 275--291 Keye Martin Entropy as a fixed point . . . . . . . . 292--324 Nicole Schweikardt On the expressive power of monadic least fixed point logic . . . . . . . . . . . 325--344 Olivier Serre Games with winning conditions of high Borel complexity . . . . . . . . . . . . 345--372 Anonymous Author index . . . . . . . . . . . . . . 373--373 Anonymous Master index . . . . . . . . . . . . . . 375--384
Marc Daumas and Nathalie Revol Preface . . . . . . . . . . . . . . . . 1--1 Matthew W. Parker Three concepts of decidability for general subsets of uncountable spaces 2--13 Martin Ziegler Stability versus speed in a computable algebraic model . . . . . . . . . . . . 14--26 Xizhong Zheng and Dianchen Lu and Kejin Bao Divergence bounded computable real numbers . . . . . . . . . . . . . . . . 27--38 Alberto Ciaffaglione and Pietro Di Gianantonio A certified, corecursive implementation of exact real numbers . . . . . . . . . 39--51 Joris van der Hoeven Computations with effective real numbers 52--60 Jesse Hughes and Milad Niqui Admissible digit sets . . . . . . . . . 61--73 Keith Briggs Implementing exact real arithmetic in python, C++ and C . . . . . . . . . . . 74--81 M. Hill and I. Robinson Quadrature using 64-bit IEEE arithmetic for integrands over $ [0, 1] $ with a singularity at $1$ . . . . . . . . . . . 82--100 Peter Kornerup and Jean-Michel Muller Choosing starting values for certain Newton--Raphson iterations . . . . . . . 101--110 Hervé Brönnimann and Guillaume Melquiond and Sylvain Pion The design of the Boost interval arithmetic library . . . . . . . . . . . 111--118 Nicolas Delanoue and Luc Jaulin and Bertrand Cottenceau Using interval arithmetic to prove that a set is path-connected . . . . . . . . 119--128 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Savi Maharaj and Carron Shankland and Charles Rattray Preface . . . . . . . . . . . . . . . . 129--130 Hubert Garavel and Wendelin Serwe State space reduction for process algebra specifications . . . . . . . . . 131--145 Gillian Hill and Steven Vickers A language for configuring multi-level specifications . . . . . . . . . . . . . 146--166 Abdessamad Imine and Michaël Rusinowitch and Gérald Oster and Pascal Molli Formal design and verification of operational transformation algorithms for copies convergence . . . . . . . . . 167--183 Alexander Knapp and Stephan Merz and Martin Wirsing and Júlia Zappe Specification and refinement of mobile systems in MTLA and mobile UML . . . . . 184--202 Juliana Küster-Filipe Modelling concurrent interactions . . . 203--220 Bernhard Möller and Georg Struth Algebras of modal operators and partial correctness . . . . . . . . . . . . . . 221--239 M. Birna van Riemsdijk and John-Jules Ch. Meyer and Frank S. de Boer Semantics of plan revision in intelligent agents . . . . . . . . . . . 240--257 Élodie-Jane Sims Extending separation logic with fixpoints and postponed substitution . . 258--275 Sun Meng and Luís S. Barbosa Components as coalgebras: The refinement dimension . . . . . . . . . . . . . . . 276--294
Rod Downey and Mike Langston and Rolf Niedermeier Editorial . . . . . . . . . . . . . . . 295--295 David Bryant and Jens Lagergren Compatibility of unrooted phylogenetic trees is FPT . . . . . . . . . . . . . . 296--302 Jonathan F. Buss and Tarique Islam Simplifying the weft hierarchy . . . . . 303--313 Yijia Chen and Jörg Flum On miniaturized problems in parameterized complexity theory . . . . 314--336 Peter Damaschke Parameterized enumeration, transversals, and imperfect phylogeny reconstruction 337--350 Michael R. Fellows and Stefan Szeider and Graham Wrightson On finding short resolution refutations and small unsatisfiable subsets . . . . 351--359 Robert Haas and Michael Hoffmann Chordless paths through three vertices 360--371 Petr Hlin\vený and Detlef Seese Trees, grids, and MSO decidability: From graphs to matroids . . . . . . . . . . . 372--393 Dániel Marx Parameterized graph separation problems 394--406 Dániel Marx Parameterized coloring problems on chordal graphs . . . . . . . . . . . . . 407--424 Matthias Müller-Hannemann and Karsten Weihe Moving policies in cyclic assembly line scheduling . . . . . . . . . . . . . . . 425--436 Elena Prieto and Christian Sloper Looking at the stars . . . . . . . . . . 437--445 Venkatesh Raman and Saket Saurabh Parameterized algorithms for feedback set problems and their duals in tournaments . . . . . . . . . . . . . . 446--458
Weili Wu and Hongwei Du and Xiaohua Jia and Yingshu Li and Scott C.-H. Huang Minimum connected dominating sets and maximal independent sets in unit disk graphs . . . . . . . . . . . . . . . . . 1--7 Pawe\l Hitczenko and Jeremy R. Johnson and Hung-Jen Huang Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh--Hadamard transform . . . . . . . . . . . . . . . 8--30 Amy Glen Occurrences of palindromes in characteristic Sturmian words . . . . . 31--46 Igor Edm. Zverovich Satgraphs and independent domination. Part 1 . . . . . . . . . . . . . . . . . 47--56 Genjiro Tanaka On syntactic monoids of biunitary submonoids determined by homomorphisms from free semigroups onto completely simple semigroups . . . . . . . . . . . 57--70 E. C. Xavier and F. K. Miyazawa Approximation schemes for knapsack problems with shelf divisions . . . . . 71--84 Dhruv Mubayi and György Turán and Yi Zhao The DNF exception problem . . . . . . . 85--96 Véronique Terrier Closure properties of cellular automata 97--107 A. Dal Palú and E. Pontelli and D. Ranjan Sequential and parallel algorithms for the NCA problem on pure pointer machines 108--135 Patricio V. Poblete and J. Ian Munro and Thomas Papadakis The binomial transform and the analysis of skip lists . . . . . . . . . . . . . 136--158 Marie Ferbus-Zanda and Serge Grigorieff Kolmogorov complexities $ K_\mathrm {max}, K_\mathrm {min} $ on computable partially ordered sets . . . . . . . . . 159--180 Periklis A. Papakonstantinou Hierarchies for classes of priority algorithms for Job Scheduling . . . . . 181--189 Thomas Colcombet and Damian Niwi\'nski On the positional determinacy of edge-labeled games . . . . . . . . . . . 190--196 Xuewen Bao and Frank K. Hwang and Qiao Li Rearrangeability of bit permutation networks . . . . . . . . . . . . . . . . 197--214 Igor É. Zverovich and Olga I. Zverovich Independent domination in hereditary classes . . . . . . . . . . . . . . . . 215--225 T. K. Subrahmonian Moothathu Set of periods of additive cellular automata . . . . . . . . . . . . . . . . 226--231 F. H. Chang and J. Y. Guo and F. K. Hwang Wide-sense nonblocking for multi-$ \log_d N $ networks under various routing strategies . . . . . . . . . . . 232--239 Trinh N. D. Huynh and Wing-Kai Hon and Tak-Wah Lam and Wing-Kin Sung Approximate string matching using compressed suffix arrays . . . . . . . . 240--249 Greg N. Frederickson and Roberto Solis-Oba Efficient algorithms for robustness in resource allocation and scheduling problems . . . . . . . . . . . . . . . . 250--265 Gonzalo Navarro and Edgar Chávez A metric index for approximate string matching . . . . . . . . . . . . . . . . 266--279 Zhu Zhao and Zhongqi Dong and Yongge Wang Security analysis of a password-based authentication protocol proposed to IEEE 1363 . . . . . . . . . . . . . . . . . . 280--287 A. M. Youssef and G. Gong On linear complexity of sequences over GF . . . . . . . . . . . . . . . . . . . 288--292 S. Ballet An improvement of the construction of the D. V. and G. V. Chudnovsky algorithm for multiplication in finite fields . . 293--305 S. Brlek and S. Dulucq and A. Ladouceur and L. Vuillon Combinatorial properties of smooth infinite words . . . . . . . . . . . . . 306--317 M. T. Hajiaghayi and Tom Leighton On the max-flow min-cut ratio for directed multicommodity flows . . . . . 318--321 Daming Zhu and Lusheng Wang On the complexity of unsigned translocation distance . . . . . . . . . 322--328 Ioan Tomescu A characterization of the words occurring as factors in a minimum number of words . . . . . . . . . . . . . . . . 329--331 Gautam K. Das and Sandip Das and Subhas C. Nandy Range assignment for energy efficient broadcasting in linear radio networks 332--341 Oscar H. Ibarra and Zhe Dang On the solvability of a class of diophantine equations and applications 342--346 Sven O. Krumke and Willem E. de Paepe and Diana Poensgen and Leen Stougie Erratum to ``News from the online traveling repairman'' [Theoret. Comput. Sci. 295 (1--3) (2003) 279--294] . . . . 347--348 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Lutz Schröder The \sc HasCasl prologue: Categorical syntax and semantics of the partial $ \lambda $-calculus . . . . . . . . . . . 1--25 Zhaohui Zhu Similarity between preferential models 26--52 Sven Hartmann and Sebastian Link On a problem of Fagin concerning multivalued dependencies in relational databases . . . . . . . . . . . . . . . 53--62 Wenhui Zhang Structure of proofs and the complexity of cut elimination . . . . . . . . . . . 63--70 Shiyong Lu and Arthur Bernstein and Philip Lewis Automatic workflow verification and generation . . . . . . . . . . . . . . . 71--92 Valentin Goranko and Govert van Drimmelen Complete axiomatization and decidability of Alternating-time temporal logic . . . 93--117 John C. Mitchell and Ajith Ramanathan and Andre Scedrov and Vanessa Teague A probabilistic polynomial-time process calculus for the analysis of cryptographic protocols . . . . . . . . 118--164 Norihiro Kamide Linear and affine logics with temporal, spatial and epistemic operators . . . . 165--207 Hanifa Boucheneb and Rachid Hadjidj CTL . . . . . . . . . . . . . . . . . . 208--227 Natalia López and Manuel Núñez and Ismael Rodríguez Specification, testing and implementation relations for symbolic-probabilistic systems . . . . . 228--248 F. Laroussinie and N. Markey and Ph. Schnoebelen Efficient timed model checking for discrete-time systems . . . . . . . . . 249--271 Mark Kambites Automatic semigroups and categories . . 272--290 Florentin Ipate Testing against a non-controllable stream X-machine using state counting 291--316 Anonymous Editorial Board . . . . . . . . . . . . v--ix
A. Nijholt and G. Scollo and U. Mönnich Editorial . . . . . . . . . . . . . . . 1--3 C. Berline and A. Salibra Easiness in graph models . . . . . . . . 4--23 Dana Harrington Uniqueness logic . . . . . . . . . . . . 24--41 Markus Roggenbach CSP-CASL --- a new integration of process algebra and algebraic specification . . . . . . . . . . . . . 42--71 Gerald Penn Efficient transitive closure of sparse matrices over closed semirings . . . . . 72--81 Stephan Kepser and Uwe Mönnich Closure properties of linear context-free tree languages with an application to optimality theory . . . . 82--97 Helmar Gust and Kai-Uwe Kühnberger and Ute Schmid Metaphors and heuristic-driven theory projection (HDTP) . . . . . . . . . . . 98--117 Peter R. J. Asveld Generating all permutations by context-free grammars in Chomsky normal form . . . . . . . . . . . . . . . . . . 118--130 Marcus Kracht Partial algebras, meaning categories and algebraization . . . . . . . . . . . . . 131--141 Radu Gramatovici and Carlos Martín-Vide Sorted dependency insertion grammars . . 142--152 Rohit N. Kundaji and R. K. Shyamasundar Refinement calculus: a basis for translation validation, debugging and certification . . . . . . . . . . . . . 153--168 Anonymous Editorial . . . . . . . . . . . . . . . v--ix
Hubert Garavel and John Hatcliff TACAS 2003 Special Issue---Preface . . . 169--172 Thomas A. Henzinger and Orna Kupferman and Rupak Majumdar On the universal and existential fragments of the $ \mu $-calculus . . . 173--186 Sylvain Conchon and Sava Krsti\'c Strategies for combining decision procedures . . . . . . . . . . . . . . . 187--210 Samik Basu and C. R. Ramakrishnan Compositional analysis for verification of parameterized systems . . . . . . . . 211--229 Rajeev Alur and Salvatore La Torre and P. Madhusudan Modular strategies for recursive game graphs . . . . . . . . . . . . . . . . . 230--249 Rajeev Alur and Thao Dang and Franjo Ivan\vci\'c Counterexample-guided predicate abstraction of hybrid systems . . . . . 250--271 Yasmina Abdeddaì\"m and Eugene Asarin and Oded Maler Scheduling with timed automata . . . . . 272--300 Elena Fersman and Leonid Mokrushin and Paul Pettersson and Wang Yi Schedulability analysis of fixed-priority systems using timed automata . . . . . . . . . . . . . . . . 301--317
Andrzej Lingas and Leszek Ga\csieniec Preface . . . . . . . . . . . . . . . . 319--319 Miroslav Chlebík and Janka Chlebíková Complexity of approximating bounded variants of optimization problems . . . 320--338 Takao Asano An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT 339--353 Grzegorz Stachowiak Fast periodic correction networks . . . 354--366 Mikael Hammar and Bengt J. Nilsson and Mia Persson Competitive exploration of rectilinear polygons . . . . . . . . . . . . . . . . 367--378 John H. Reif and Zheng Sun On boundaries of highly visible spaces and applications . . . . . . . . . . . . 379--390 Luis Antunes and Lance Fortnow and Dieter van Melkebeek and N. V. Vinodchandran Computational depth: Concept and applications . . . . . . . . . . . . . . 391--404 Jean Berstel and Luc Boasson and Olivier Carton and Bruno Petazzoni and Jean-Eric Pin Operations preserving regular languages 405--420 Wan Fokkink and Rob van Glabbeek and Paulien de Wind Compositionality of Hennessy--Milner logic by structural operational semantics . . . . . . . . . . . . . . . 421--440
Ravi Kumar and Matthieu Latapy Preface . . . . . . . . . . . . . . . . 1--5 Luca Dall'Asta and Ignacio Alvarez-Hamelin and Alain Barrat and Alexei Vázquez and Alessandro Vespignani Exploring networks with traceroute-like probes: Theory and simulations . . . . . 6--24 Fred S. Annexstein and Kenneth A. Berman and Mijhalo A. Jovanovi\'c Broadcasting in unstructured peer-to-peer overlay networks . . . . . 25--36 Michael Behrisch and Anusch Taraz Efficiently covering complex networks with cliques of similar vertices . . . . 37--47 Nima Sarshar and Oscar Boykin and Vwani Roychowdhury Scalable percolation search on complex networks . . . . . . . . . . . . . . . . 48--64 Pierre Fraigniaud and Philippe Gauron D2B: a de Bruijn based content-addressable network . . . . . . 65--79 Alexandre O. Stauffer and Valmir C. Barbosa Local heuristics and the emergence of spanning subgraphs in complex networks 80--95 Philippe Duchon and Nicolas Hanusse and Emmanuelle Lebhar and Nicolas Schabanel Could any graph be turned into a small-world? . . . . . . . . . . . . . . 96--103 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Ruy de Queiroz and Dexter Kozen Logic, Language, Information and Computation . . . . . . . . . . . . . . 105--107 Fabio Alessi and Franco Barbanera and Mariangiola Dezani-Ciancaglini Intersection types and lambda models . . 108--126 Eric Allender NL-printable sets and nondeterministic Kolmogorov complexity . . . . . . . . . 127--138 Denis Béchet and Annie Foret k . . . . . . . . . . . . . . . . . . . 139--152 Marcelo Finger and Renata Wassermann The universe of propositional approximations . . . . . . . . . . . . . 153--166 Sven Hartmann and Sebastian Link and Klaus-Dieter Schewe Axiomatisations of functional dependencies in the presence of records, lists, sets and multisets . . . . . . . 167--196 Lauri Hella and José María Turull-Torres Computing queries with higher-order logics . . . . . . . . . . . . . . . . . 197--214 Yngve Lamo and Micha\l Walicki Quantifier-free logic for nondeterministic theories . . . . . . . 215--227 Hans Rott Revision by comparison as a unifying framework: Severe withdrawal, irrevocable revision and irrefutable revision . . . . . . . . . . . . . . . . 228--242 Marek Zaionc Probability distribution for simple tautologies . . . . . . . . . . . . . . 243--260
Stavros G. Kolliopoulos and George Steiner Approximation algorithms for minimizing the total weighted tardiness on a single machine . . . . . . . . . . . . . . . . 261--273 António Malheiro Finite derivation type for Rees matrix semigroups . . . . . . . . . . . . . . . 274--290 Ke Xu and Wei Li Many hard examples in exact phase transitions . . . . . . . . . . . . . . 291--302 Ro-Yu Wu and Jou-Ming Chang and Yue-Li Wang A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations . . . . . . . . 303--314 Gianluca De Marco and Luisa Gargano and Evangelos Kranakis and Danny Krizanc and Andrzej Pelc and Ugo Vaccaro Asynchronous deterministic rendezvous in graphs . . . . . . . . . . . . . . . . . 315--326 José-Ramón Sánchez-Couso and María-Inés Fernández-Camacho Reductions in binary search trees . . . 327--353 Zemin Jin and Xueliang Li On the $k$-path cover problem for cacti 354--363 Caterina De Simone and C. P. de Mello Edge-colouring of join graphs . . . . . 364--370 Philippe Flajolet and Markus Nebel and Helmut Prodinger The scientific works of Rainer Kemp (1949--2004) . . . . . . . . . . . . . . 371--381 John M. Hitchcock Hausdorff dimension and oracle constructions . . . . . . . . . . . . . 382--388 Cristina Bazgan and Zsolt Tuza and Daniel Vanderpooten Degree-constrained decompositions of graphs: Bounded treewidth and planarity 389--395
Alberto Bertoni and Zoltan Ésik and Juhani Karhumäki Preface . . . . . . . . . . . . . . . . 1--5 Marie-Pierre Béal and Dominique Perrin Codes, unambiguous automata and sofic systems . . . . . . . . . . . . . . . . 6--13 Alberto Bertoni and Carlo Mereghetti and Beatrice Palano Some formal tools for analyzing quantum automata . . . . . . . . . . . . . . . . 14--25 Robert Brijder and Hendrik Jan Hoogeboom and Grzegorz Rozenberg Reducibility of gene patterns in ciliates using the breakpoint graph . . 26--45 Janusz. A. Brzozowski Representation of a class of nondeterministic semiautomata by canonical words . . . . . . . . . . . . 46--57 Giusi Castiglione and Antonio Restivo and Roberto Vaglica A reconstruction algorithm for L-convex polyominoes . . . . . . . . . . . . . . 58--72 Laura Chaubard and Jean-Éric Pin and Howard Straubing Actions, wreath products of $ \mathcal {C} $-varieties and concatenation product . . . . . . . . . . . . . . . . 73--89 Alessandra Cherubini and Stefano Crespi Reghizzi and Matteo Pradella and Pierluigi San Pietro Picture languages: Tiling systems versus tile rewriting grammars . . . . . . . . 90--103 Flavio D'Alessandro and Benedetto Intrigila and Stefano Varricchio On the structure of the counting function of sparse context-free languages . . . . . . . . . . . . . . . 104--117 Aldo de Luca and Alessandro De Luca Some characterizations of finite Sturmian words . . . . . . . . . . . . . 118--125 Volker Diekert and Paul Gastin From local to global temporal logics over Mazurkiewicz traces . . . . . . . . 126--135 Zoltán Ésik Characterizing CTL-like logics on finite trees . . . . . . . . . . . . . . . . . 136--152 Massimiliano Goldwurm and Violetta Lonati Pattern statistics and Vandermonde matrices . . . . . . . . . . . . . . . . 153--169 Serge Grigorieff Synchronization of a bounded degree graph of cellular automata with nonuniform delays in time $ D \lfloor \log_m D \rfloor $ . . . . . . . . . . . 170--185 Tero Harju and Dirk Nowotka On unique factorizations of primitive words . . . . . . . . . . . . . . . . . 186--189 Oscar H. Ibarra and Bala Ravikumar On partially blind multihead finite automata . . . . . . . . . . . . . . . . 190--199 Juhani Karhumäki and Michal Kunc and Alexander Okhotin Computing by commuting . . . . . . . . . 200--211 Michel Latteux and Aurélien Lemay and Yves Roos and Alain Terlutte Identification of biRFSA languages . . . 212--223 Sylvain Lombardy and Jacques Sakarovitch Sequential? . . . . . . . . . . . . . . 224--244 Jean Néraud Completing prefix codes in submonoids 245--254 Wies\law Zielonka Time-stamps for Mazurkiewicz traces . . 255--262 Anonymous Professor Choffrut . . . . . . . . . . . v--ix Anonymous Preface . . . . . . . . . . . . . . . . xiv--xiv
Jos Baeten and Flavio Corradini Preface . . . . . . . . . . . . . . . . 263--264 R. J. van Glabbeek On the expressiveness of higher dimensional automata . . . . . . . . . . 265--290 F. Corradini and M. R. Di Berardini and W. Vogler Fairness of components in system computations . . . . . . . . . . . . . . 291--324 Suzana Andova and Tim A. C. Willemse Branching bisimulation for probabilistic systems: Characteristics and decidability . . . . . . . . . . . . . . 325--355 Emmanuel Beffara and François Maurel Concurrent nets: a study of prefixing in process calculi . . . . . . . . . . . . 356--373 A. Finkel and G. Geeraerts and J.-F. Raskin and L. Van Begin On the $ \omega $-language expressive power of extended Petri nets . . . . . . 374--386 Rocco De Nicola and Daniele Gorla and Rosario Pugliese On the expressive power of KLAIM-based calculi . . . . . . . . . . . . . . . . 387--421 Mikkel Bundgaard and Thomas Hildebrandt and Jens Chr. Godskesen A CPS encoding of name-passing in Higher-order mobile embedded resources 422--439 Xudong Guan Name-passing in an ambient-like calculus and its proof using spatial logic . . . 440--467 Iain Phillips and Maria Grazia Vigliotti Leader election in rings of ambient processes . . . . . . . . . . . . . . . 468--494
Sergei Artemov and Michael Mislove Preface . . . . . . . . . . . . . . . . 1--3 Sergei Artemov Justified common knowledge . . . . . . . 4--22 Vladimir Brezhnev and Roman Kuznets Making knowledge explicit: How hard it is . . . . . . . . . . . . . . . . . . . 23--34 Samuel R. Buss Polynomial-size Frege and resolution proofs of st . . . . . . . . . . . . . . 35--52 Nachum Dershowitz and Claude Kirchner Abstract canonical presentations . . . . 53--69 Martin Hyland and Gordon Plotkin and John Power Combining effects: Sum and tensor . . . 70--99 Giorgi Japaridze From truth to computability I . . . . . 100--135 Nikolai V. Krupski On the complexity of the reflected logic of proofs . . . . . . . . . . . . . . . 136--142 Vladimir N. Krupski Referential logic of proofs . . . . . . 143--166 Pavel Naumov Logic of subtyping . . . . . . . . . . . 167--185 Mati Pentus Lambek calculus is NP-complete . . . . . 186--201 Helmut Schwichtenberg An arithmetic for polynomial-time computation . . . . . . . . . . . . . . 202--214 Sergey Slavnov Geometrical semantics for linear logic (multiplicative fragment) . . . . . . . 215--229 Frédéric De Jaeger and Martín Escardó and Gabriele Santini On the computational content of the Lawson topology . . . . . . . . . . . . 230--240 Lisbeth Fajstrup and Martin Raußen and Eric Goubault Algebraic topology and concurrency . . . 241--278 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1--2 Anne Broadbent and André Allan Méthot On the power of non-local boxes . . . . 3--14 Katarzyna Miakisz and Edward W. Piotrowski and Jan S\ladkowski Quantization of games: Towards quantum artificial intelligence . . . . . . . . 15--22 Petrus H. Potgieter Zeno machines and hypercomputation . . . 23--33 Artur S. d'Avila Garcez and Luís C. Lamb and Dov M. Gabbay Connectionist computations of intuitionistic reasoning . . . . . . . . 34--55 Bo Liao and Kequan Ding A 3D graphical representation of DNA sequences and its application . . . . . 56--64 Lvzhou Li and Daowen Qiu Determination of equivalence between quantum sequential machines . . . . . . 65--74 Remco Loos An alternative definition of splicing 75--87 Oscar H. Ibarra and Gheorghe P\uaun Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems . . 88--103 Rajeev Kumar and Nilanjan Banerjee Analysis of a Multiobjective Evolutionary Algorithm on the 0--1 knapsack problem . . . . . . . . . . . . 104--120 Alex Rogers and Adam Prügel-Bennett and Nicholas R. Jennings Phase transitions and symmetry breaking in genetic algorithms with crossover . . 121--141 Elena Czeizler and Eugen Czeizler On the power of parallel communicating Watson--Crick automata systems . . . . . 142--147 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Philippa Gardner and Nobuko Yoshida Editorial . . . . . . . . . . . . . . . 149--149 Benedikt Bollig and Martin Leucker Message-passing automata are expressively equivalent to EMSO logic 150--172 Daniele Varacca and Hagen Völzer and Glynn Winskel Probabilistic event structures and domains . . . . . . . . . . . . . . . . 173--199 Paul-André Melli\`es Asynchronous games 2: The true concurrency of innocence . . . . . . . . 200--228 Roberto M. Amadio and Silvano Dal Zilio Resource control for synchronous cooperative threads . . . . . . . . . . 229--254 Mikolaj Boja\'nczyk and Igor Walukiewicz Characterizing EF and EX tree logics . . 255--272 Nicolas Markey and Jean-François Raskin Model checking restricted sets of timed paths . . . . . . . . . . . . . . . . . 273--292 Luís Caires and Etienne Lozes Elimination of quantifiers and undecidability in spatial logics for concurrency . . . . . . . . . . . . . . 293--314 Antonín Ku\vcera and Philippe Schnoebelen A general approach to comparing infinite-state systems with their finite-state specifications . . . . . . 315--333
Matthias Homeister Lower bounds for restricted read-once parity branching programs . . . . . . . 1--14 Teturo Kamae and Hui Rao and Yu-Mei Xue Maximal pattern complexity of two-dimensional words . . . . . . . . . 15--27 Yongcheng Wu and Klaus Weihrauch A computable version of the Daniell--Stone theorem on integration and linear functionals . . . . . . . . . 28--42 József Balogh and Dhruv Mubayi and András Pluhár On the edge-bandwidth of graph products 43--57 Yves F. Verhoeven A lower bound on the competitivity of memoryless algorithms for a generalization of the CNN problem . . . 58--68 Chiuyuan Chen and James K. Lan and Wen-Shiang Tang An efficient algorithm to find a double-loop network that realizes a given L-shape . . . . . . . . . . . . . 69--76 Ferucio Lauren\ctiu \cTiplea and Aurora \cTiplea Petri net reactive modules . . . . . . . 77--100 Fredrick Arnold and Benjamin Steinberg Synchronizing groups and automata . . . 101--110 Anton Leykin and Jan Verschelde and Ailing Zhao Newton's method with deflation for isolated singularities of polynomial systems . . . . . . . . . . . . . . . . 111--122 Benjamin Doerr and Nils Hebbinghaus and Sören Werth Improved bounds and schemes for the declustering problem . . . . . . . . . . 123--132 Taizo Sadahiro Multiple points of tilings associated with Pisot numeration systems . . . . . 133--147 Emilio Di Giacomo and Walter Didimo and Giuseppe Liotta and Matthew Suderman k . . . . . . . . . . . . . . . . . . . 148--175 Xiaoyang Gu A note on dimensions of polynomial size circuits . . . . . . . . . . . . . . . . 176--187 Frank Gurski and Egon Wanke Vertex disjoint paths on clique-width bounded graphs . . . . . . . . . . . . . 188--199 Vijay K. Garg Algorithmic combinatorics based on slicing posets . . . . . . . . . . . . . 200--213 Gabriele Fici and Filippo Mignosi and Antonio Restivo and Marinella Sciortino Word assembly through minimal forbidden words . . . . . . . . . . . . . . . . . 214--230 Peter M. Higgins and Christopher J. Saker Unavoidable sets . . . . . . . . . . . . 231--238 Christian Lavault and Guy Louchard Asymptotic analysis of a leader election algorithm . . . . . . . . . . . . . . . 239--254 A. Barbé and F. von Haeseler Averages of automatic sequences . . . . 255--281 Anders Björner and Bruce E. Sagan Rationality of the Möbius function of a composition poset . . . . . . . . . . . 282--298 Guangjun Xu and Liying Kang and Erfang Shan and Min Zhao Power domination in block graphs . . . . 299--305 Carl S. McTague and James P. Crutchfield Automated pattern detection---An algorithm for constructing optimally synchronizing multi-regular language filters . . . . . . . . . . . . . . . . 306--328 Markus E. Nebel Fast string matching by using probabilities: On an optimal mismatch variant of Horspool's algorithm . . . . 329--343 Sonia Pérez-Díaz and Juana Sendra and J. Rafael Sendra Distance bounds of $ \epsilon $-points on hypersurfaces . . . . . . . . . . . . 344--368 Bruno Escoffier and Vangelis Th. Paschos Completeness in approximation classes beyond APX . . . . . . . . . . . . . . . 369--377 Pawe\l Górecki and Jerzy Tiuryn DLS-trees: a model of evolutionary scenarios . . . . . . . . . . . . . . . 378--399 Pavlos S. Efraimidis and Paul G. Spirakis Approximation schemes for scheduling and covering on unrelated machines . . . . . 400--417 Leah Epstein and Asaf Levin The conference call search problem in wireless networks . . . . . . . . . . . 418--429 Wun-Tat Chan and Tak-Wah Lam and Kin-Shing Liu and Prudence W. H. Wong New resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor scheduling . . . . . . . 430--439 Boris Ryabko and Jaakko Astola and Alex Gammerman Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series . . . . . . 440--448 Sándor Szabó Completing codes and the Rédei property of groups . . . . . . . . . . . . . . . 449--454 Liviu P. Dinu and Florin Manea An efficient approach for the rank aggregation problem . . . . . . . . . . 455--461 Anonymous Editorial Board . . . . . . . . . . . . v--ix
David Friggens and Robert Goldblatt A modal proof theory for final polynomial coalgebras . . . . . . . . . 1--22 Dave Binkley and Sebastian Danicic and Tibor Gyimóthy and Mark Harman and Ákos Kiss and Bogdan Korel Theoretical foundations of dynamic program slicing . . . . . . . . . . . . 23--41 Paola Bruscoli and Alessio Guglielmi On structuring proof search for first order linear logic . . . . . . . . . . . 42--76 Ernie Manes Boolean restriction categories and taut monads . . . . . . . . . . . . . . . . . 77--95 Stéphane Demri LTL over integer periodicity constraints 96--123 Yves Guiraud Two polygraphic presentations of Petri nets . . . . . . . . . . . . . . . . . . 124--146 Zhaohui Zhu and Rong Zhang and Shan Lu A characterization theorem for injective model classes axiomatized by general rules . . . . . . . . . . . . . . . . . 147--171 Slawomir Lasota Decidability of performance equivalence for basic parallel processes . . . . . . 172--192 Gilles Dowek and Ying Jiang Eigenvariables, bracketing and the decidability of positive minimal predicate logic . . . . . . . . . . . . 193--208 Gerald Lüttgen and Walter Vogler Bisimulation on speed: a unified approach . . . . . . . . . . . . . . . . 209--227 Daniel J. Dougherty and Claudio Gutiérrez Normal forms for binary relations . . . 228--246 Linh Anh Nguyen Multimodal logic programming . . . . . . 247--288 Nikos Tzevelekos Investigations on the Dual Calculus . . 289--326 Haruo Hosoya and Makoto Murata Boolean operations and inclusion test for attribute-element constraints . . . 327--351 Laura Bozzelli Model checking for process rewrite systems and a class of action-based regular properties . . . . . . . . . . . 352--372 Franck van Breugel and James Worrell Approximating and computing behavioural distances in probabilistic transition systems . . . . . . . . . . . . . . . . 373--385 Roberto Bruni and José Meseguer Semantic foundations for generalized rewrite theories . . . . . . . . . . . . 386--414 Markus Michelbrink Interfaces as functors, programs as coalgebras --- a final coalgebra theorem in intensional type theory . . . . . . . 415--439 Michele Boreale and Fabio Gadducci Processes as formal power series: a coinductive approach to denotational semantics . . . . . . . . . . . . . . . 440--458 Sven Hartmann and Sebastian Link and Klaus-Dieter Schewe Erratum to ``Axiomatisations of functional dependencies in the presence of records, lists, sets and multisets'' 459--459 Anonymous Author index . . . . . . . . . . . . . . 461--461 Anonymous Master index . . . . . . . . . . . . . . 463--472 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Michael D. Vose Preface . . . . . . . . . . . . . . . . 1--1 Darrell Whitley and Jonathan Rowe Subthreshold-seeking local search . . . 2--17 Dirk V. Arnold Weighted multirecombination evolution strategies . . . . . . . . . . . . . . . 18--37 Jens Jägersküpper How the (1+1) ES using isotropic mutations minimizes positive definite quadratic forms . . . . . . . . . . . . 38--56 Marc Toussaint Compact representations as a search strategy: Compression EDAs . . . . . . . 57--71 Boris Mitavskiy and Jonathan Rowe Some results about the Markov chains associated to GPs and general EAs . . . 72--110 Jonathan E. Rowe and Michael D. Vose and Alden H. Wright Differentiable coarse graining . . . . . 111--129 Anonymous Editorial Board . . . . . . . . . . . . v--ix Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Klaus Jansen and Roberto Solis-Oba Preface . . . . . . . . . . . . . . . . 131--132 Dániel Marx Minimum sum multicoloring on the edges of trees . . . . . . . . . . . . . . . . 133--149 Piotr Krysta and Krzysztof Lory\'s Efficient approximation algorithms for the achromatic number . . . . . . . . . 150--171 Erik D. Demaine and Dotan Emanuel and Amos Fiat and Nicole Immorlica Correlation clustering in general weighted graphs . . . . . . . . . . . . 172--187 Inge Li Gòrtz and Anthony Wirth Asymmetry in $k$-center variants . . . . 188--199 Baruch Awerbuch and Yossi Azar and Yossi Richter and Dekel Tsur Tradeoffs in worst-case equilibria . . . 200--209 Etienne de Klerk and Monique Laurent and Pablo A. Parrilo A PTAS for the minimization of polynomials of fixed degree over the simplex . . . . . . . . . . . . . . . . 210--225 T. Decker and T. Lücking and B. Monien A $ 5 / 4 $-approximation algorithm for scheduling identical malleable tasks . . 226--240 R. N. Uma and Joel Wein and David P. Williamson On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems . . . . 241--256 A. A. Ageev and A. V. Fishkin and A. V. Kononov and S. V. Sevastyanov Open block scheduling in optical communication networks . . . . . . . . . 257--274 Dimitris Fotakis Incremental algorithms for Facility Location and $k$-Median . . . . . . . . 275--313 Yossi Azar and Amir Epstein and Leah Epstein Load balancing of temporary tasks in the $ \ell_p $ norm . . . . . . . . . . . . 314--328 Sandra Gutiérrez and Sven O. Krumke and Nicole Megow and Tjark Vredeveld How to whack moles . . . . . . . . . . . 329--341 Erik D. Demaine and Sándor P. Fekete and Shmuel Gal Online searching with turn cost . . . . 342--355 Anonymous Author index . . . . . . . . . . . . . . 356--357
Nazim Fat\`es and Éric Thierry and Michel Morvan and Nicolas Schabanel Fully asynchronous behavior of double-quiescent elementary cellular automata . . . . . . . . . . . . . . . . 1--16 Khaled El-Fakih and Nina Yevtushenko and Sergey Buffalov and Gregor v. Bochmann Progressive solutions to a parallel automata equation . . . . . . . . . . . 17--32 Francesc Rosselló and Gabriel Valiente An algebraic view of the relation between largest common subtrees and smallest common supertrees . . . . . . . 33--53 Lane A. Hemaspaandra and Kari Pasanen and Jörg Rothe If P $ \not = $ NP then some strongly noninvertible functions are invertible 54--62 Guizhen Yang Computational aspects of mining maximal frequent patterns . . . . . . . . . . . 63--85 Beate Bollig and Stephan Waack and Philipp Woelfel Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication . . . . . . . 86--99 Pedro García and José Ruiz V . . . . . . . . . . . . . . . . . . . 100--114 Min Ji and Yong He and T. C. E. Cheng Scheduling linear deteriorating jobs with an availability constraint on a single machine . . . . . . . . . . . . . 115--126 Joan Boyar and Leah Epstein and Lene M. Favrholdt and Jens S. Kohrt and Kim S. Larsen and Morten M. Pedersen and Sanne Wòhlk The maximum resource bin packing problem 127--139 Francesco M. Malvestuto and Mauro Mezzini and Marina Moscarini Minimal invariant sets in a vertex-weighted graph . . . . . . . . . 140--161 Chih-Huai Cheng and Kuan-Yu Chen and Wen-Chin Tien and Kun-Mao Chao Improved algorithms for the $k$-maximum-sums problems . . . . . . . 162--170 Turlough Neary and Damien Woods Small fast universal Turing machines . . 171--195 Leszek G\kasieniec and Evangelos Kranakis and Andrzej Pelc and Qin Xin Deterministic M2M multicast in radio networks . . . . . . . . . . . . . . . . 196--206 Matthieu Picantin Finite transducers for divisibility monoids . . . . . . . . . . . . . . . . 207--221 Arto Salomaa Independence of certain quantities indicating subword occurrences . . . . . 222--231 Mark Kambites Word problems recognisable by deterministic blind monoid automata . . 232--237 Mohamed Eid Hussein and Uwe Schwiegelshohn Utilization of nonclairvoyant online schedules . . . . . . . . . . . . . . . 238--247 Maxime Crochemore and Costas S. Iliopoulos and Manal Mohamed and Marie-France Sagot Longest repeats with a block of $k$ don't cares . . . . . . . . . . . . . . 248--254 Alain Bretto and Alain Faisant and Thierry Vallée Compatible topologies on graphs: an application to graph isomorphism problem complexity . . . . . . . . . . . . . . . 255--272 T. C. E. Cheng and C. T. Ng and J. J. Yuan Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs . . . . . . . . . . 273--281 Aldo de Luca and Alessandro De Luca Pseudopalindrome closure operators in free monoids . . . . . . . . . . . . . . 282--300 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Kyung-Yong Chwa and J. Ian Munro Preface . . . . . . . . . . . . . . . . 1--1 Joel Ratsaby Complexity of hyperconcepts . . . . . . 2--10 Udo Adamy and Michael Hoffmann and József Solymosi and Milo\vs Stojakovi\'c Coloring octrees . . . . . . . . . . . . 11--17 Yossi Azar and Amos Fiat and Meital Levy and N. S. Narayanaswamy An improved algorithm for online coloring of intervals with bandwidth . . 18--27 Etsuji Tomita and Akira Tanaka and Haruhisa Takahashi The worst-case time complexity for generating all maximal cliques and computational experiments . . . . . . . 28--42 Tatsuie Tsukiji and Zhi-Zhong Chen Computing phylogenetic roots with bounded degrees and errors is NP-complete . . . . . . . . . . . . . . 43--59 Jesper Jansson and Wing-Kin Sung Inferring a level-1 phylogenetic network from a dense set of rooted triplets . . 60--68 H. F. Leung and Z. S. Peng and H. F. Ting An efficient algorithm for online square detection . . . . . . . . . . . . . . . 69--75 Philipp Woelfel A construction method for optimally universal hash families and its consequences for the existence of RBIBDs 76--84 Hanno Lefmann Large triangles in the $d$-dimensional unit cube . . . . . . . . . . . . . . . 85--98 Yong Zhang and Qi Ge and Rudolf Fleischer and Tao Jiang and Hong Zhu Approximating the minimum weight weak vertex cover . . . . . . . . . . . . . . 99--105 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Jacques Farré and Igor Litovsky Editorial . . . . . . . . . . . . . . . 107--107 Arnaud Bailly and Mireille Clerbout and Isabelle Simplot-Ryl Component composition preserving behavioral contracts based on communication traces . . . . . . . . . . 108--123 Cédric Bastien and Jurek Czyzowicz and Wojciech Fraczak and Wojciech Rytter Prime normal form and equivalence of simple grammars . . . . . . . . . . . . 124--134 Cezar Câmpeanu and Andrei P\uaun and Jason R. Smith Incremental construction of minimal deterministic finite cover automata . . 135--148 Oscar H. Ibarra and Hsu-Chun Yen Deterministic catalytic systems are not universal . . . . . . . . . . . . . . . 149--161 Tomasz Jurdzi\'nski and Friedrich Otto Restarting automata with restricted utilization of auxiliary symbols . . . . 162--181 Joachim Klein and Christel Baier Experiments with deterministic $ \omega $-automata for formulas of linear temporal logic . . . . . . . . . . . . . 182--195 Markus Lohrey and Sebastian Maneth The complexity of tree automata and XPath on grammar-compressed trees . . . 196--210 Wojciech Rytter The structure of subword graphs and suffix trees of Fibonacci words . . . . 211--223 Christoph Schulte Althoff and Wolfgang Thomas and Nico Wallmeier Observations on determinization of Büchi automata . . . . . . . . . . . . . . . . 224--233 Hellis Tamm and Matti Nykänen and Esko Ukkonen On size reduction techniques for multitape automata . . . . . . . . . . . 234--246
Nimrod Megiddo and Yinfeng Xu and Binhai Zhu Preface . . . . . . . . . . . . . . . . 247--247 Mao-cheng Cai and Xiaotie Deng and Zhongfei Li Computation of arbitrage in frictional bond markets . . . . . . . . . . . . . . 248--256 Yong He and Weiya Zhong and Huikun Gu Improved algorithms for two single machine scheduling problems . . . . . . 257--265 Mingen Lin and Zhiyong Lin and Jinhui Xu Graph bandwidth of weighted caterpillars 266--277 Jianer Chen and Fenghui Zhang On product covering in 3-tier supply chain models: Natural complete problems for W . . . . . . . . . . . . . . . . . 278--288 Adriana F. Gabor and Jan-Kees C. W. van Ommeren Approximation algorithms for facility location problems with a special class of subadditive cost functions . . . . . 289--300
Richard Gavald\`a and Eiji Takimoto Foreword . . . . . . . . . . . . . . . . 1--2 Ilia Nouretdinov and Vladimir Vovk Criterion of calibration for transductive confidence machine with limited feedback . . . . . . . . . . . . 3--9 Vladimir Vovk Well-calibrated predictions from on-line compression models . . . . . . . . . . . 10--26 Marcus Hutter On generalized computable universal priors and their convergence . . . . . . 27--41 Sandra Zilles An approach to intrinsic complexity of uniform learning . . . . . . . . . . . . 42--61 Eric Martin and Arun Sharma and Frank Stephan On ordinal VC-dimension and some notions of complexity . . . . . . . . . . . . . 62--76 Thomas Zeugmann From learning in the limit to stochastic finite learning . . . . . . . . . . . . 77--97 Jin Uemura and Masako Sato Learning of erasing primitive formal systems from positive examples . . . . . 98--114 John Case and Sanjay Jain and Rüdiger Reischuk and Frank Stephan and Thomas Zeugmann Learning a subclass of regular patterns in polynomial time . . . . . . . . . . . 115--131 Genshiro Kitagawa Signal extraction and knowledge discovery based on statistical modeling 132--142 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Ruy de Queiroz and Patrick Cégielski Preface . . . . . . . . . . . . . . . . 143--145 Gianluigi Bellin and Martin Hyland and Edmund Robinson and Christian Urban Categorical proof theory of classical propositional calculus . . . . . . . . . 146--165 T. Ehrhard and L. Regnier Differential interaction nets . . . . . 166--195 Olivier Finkel On decidability properties of local sentences . . . . . . . . . . . . . . . 196--211 Sven Hartmann and Sebastian Link Deciding implication for functional dependencies in complex-value databases 212--240 Michael Kaminski and Julia Rubin-Mosin Default theories over monadic languages 241--253 John Power Generic models for computational effects 254--269
Martin Hofmann and Hans-Wolfgang Loidl Preface . . . . . . . . . . . . . . . . 271--272 Frédéric Besson and Thomas Jensen and David Pichardie Proof-carrying code from certified abstract interpretation and fixpoint compression . . . . . . . . . . . . . . 273--291 Peeter Laud and Tarmo Uustalu and Varmo Vene Type systems equivalent to data-flow analyses for imperative languages . . . 292--310 Andrew Kennedy Securing the .NET programming model . . 311--317 Dominique Cansell and Dominique Méry Formal and incremental construction of distributed algorithms: On the distributed reference counting algorithm 318--337 J. Niehren and J. Schwinghammer and G. Smolka A concurrent lambda calculus with futures . . . . . . . . . . . . . . . . 338--356
Frank de Boer and Marcello Bonsangue Preface . . . . . . . . . . . . . . . . 1--1 Luís S. Barbosa and José N. Oliveira Transposing partial components---An exercise on coalgebraic refinement . . . 2--22 Einar Broch Johnsen and Olaf Owe and Ingrid Chieh Yu Creol: a type-safe object-oriented model for distributed concurrent systems . . . 23--66 Krishnendu Chatterjee and Thomas A. Henzinger and Marcin Jurdzi\'nski Games with secure equilibria . . . . . . 67--82 Ling Cheung and Nancy Lynch and Roberto Segala and Frits Vaandrager Switched PIOA: Parallel composition via distributed scheduling . . . . . . . . . 83--108 He Jifeng and Xiaoshan Li and Zhiming Liu rCOS: a refinement calculus of object systems . . . . . . . . . . . . . . . . 109--142 David A. Naumann and Mike Barnett Towards imperative modules: Reasoning about invariants and sharing of mutable state . . . . . . . . . . . . . . . . . 143--168 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Ralph Kopperman and Prakash Panangaden and Michael B. Smyth and Dieter Spreen and Julian Webster Foreword . . . . . . . . . . . . . . . . 169--170 Samy Abbes and Klaus Keimel Projective topology on bifinite domains and applications . . . . . . . . . . . . 171--183 K. Abe and J. Bisceglio and D. R. Ferguson and T. J. Peters and A. C. Russell and T. Sakkalis Computational topology for isotopic surface reconstruction . . . . . . . . . 184--198 Lisbeth Fajstrup Cubical local partial orders on cubically subdivided spaces---Existence and construction . . . . . . . . . . . . 199--205 Jonathan Gratus and Timothy Porter A spatial view of information . . . . . 206--215 G. Hamrin and V. Stoltenberg-Hansen Two categories of effective continuous cpos . . . . . . . . . . . . . . . . . . 216--236 H.-P. A. Künzi and H. Pajoohesh and M. P. Schellekens Partial quasi-metrics . . . . . . . . . 237--246 Martin Raußen Deadlocks and dihomotopy in mutual exclusion models . . . . . . . . . . . . 247--257 Victor L. Selivanov Towards a descriptive set theory for domain-like structures . . . . . . . . . 258--282
José Fiadeiro and Jan Rutten Preface . . . . . . . . . . . . . . . . 1--2 Stefan Milius and Lawrence S. Moss The category-theoretic solution of recursive program schemes . . . . . . . 3--59 Luca Aceto and Wan Fokkink and Anna Ingolfsdottir and Sumit Nain Bisimilarity is not finitely based over BPA with interrupt . . . . . . . . . . . 60--81 J. Adámek The intersection of algebra and coalgebra . . . . . . . . . . . . . . . 82--97 Roberto Bruni and Ivan Lanese and Ugo Montanari A basic algebra of stateless connectors 98--120 Daniel Hausmann and Till Mossakowski and Lutz Schröder A coalgebraic approach to the semantics of the ambient calculus . . . . . . . . 121--143 Martin Hyland and John Power Discrete Lawvere theories and computational effects . . . . . . . . . 144--162 Prasanna Thati and José Meseguer Complete symbolic reachability analysis using back-and-forth narrowing . . . . . 163--179 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Zoltán Ésik Preface . . . . . . . . . . . . . . . . 181--181 Michael Domaratzki and Kai Salomaa Codes defined by multiple sets of trajectories . . . . . . . . . . . . . . 182--193 Pál Dömösi and Géza Horváth Alternative proof of the Lyndon--Schützenberger Theorem . . . . . 194--198 Manfred Droste and Dietrich Kuske Skew and infinitary formal power series 199--227 Manfred Droste and Heiko Vogler Weighted tree automata and weighted logics . . . . . . . . . . . . . . . . . 228--247 Andreas Maletti Compositions of tree series transformations . . . . . . . . . . . . 248--271 F. Mráz and F. Otto and M. Plátek and T. Jurdzi\'nski Marcus $t$-contextual grammars and cut hierarchies and monotonicity for restarting automata . . . . . . . . . . 272--296 Bianca Truthe The finiteness of synchronous, tabled picture languages is decidable . . . . . 297--315
Pierpaolo Degano and Luca Vigan\`o Preface . . . . . . . . . . . . . . . . 1--1 Martín Abadi and Véronique Cortier Deciding knowledge in security protocols under equational theories . . . . . . . 2--32 Michael Backes and Anupam Datta and Ante Derek and John C. Mitchell and Mathieu Turuani Compositional analysis of contract-signing protocols . . . . . . . 33--56 Frederick Butler and Iliano Cervesato and Aaron D. Jaggard and Andre Scedrov and Christopher Walstad Formal analysis of Kerberos 5 . . . . . 57--87 Carlos Caleiro and Luca Vigan\`o and David Basin On the semantics of Alice&Bob specifications of security protocols . . 88--122 Konstantinos Chatzikokolakis and Catuscia Palamidessi Probable innocence revisited . . . . . . 123--138 C. J. F. Cremers and S. Mauw and E. P. de Vink Injective synchronisation: an extension of the authentication hierarchy . . . . 139--161 Santiago Escobar and Catherine Meadows and José Meseguer A rewriting-based inference system for the NRL Protocol Analyzer and its meta-logical properties . . . . . . . . 162--202 Sebastian Nanz and Chris Hankin A framework for security analysis of mobile wireless networks . . . . . . . . 203--227 R. Ramanujam and S. P. Suresh A (restricted) quantifier elimination for security protocols . . . . . . . . . 228--256 Graham Steel Formal analysis of PIN block attacks . . 257--270 Anonymous Editorial Board . . . . . . . . . . . . v--ix
G. Rozenberg Preface . . . . . . . . . . . . . . . . 271--272 Yiguang Liu and Zhisheng You and Liping Cao A concise functional neural network computing the largest modulus eigenvalues and their corresponding eigenvectors of a real skew matrix . . . 273--285 Jian Cheng Lv and Zhang Yi and K. K. Tan Global convergence of Oja's PCA learning algorithm with a non-zero-approaching adaptive learning rate . . . . . . . . . 286--307 Oleg Izmerly and Tal Mor Chosen ciphertext attacks on lattice-based public key encryption and modern (non-quantum) cryptography in a quantum environment . . . . . . . . . . 308--323 Marco Carpentieri A genetic system based on simulated crossover of sequences of two-bit genes 324--335 Faisal Shah Khan and Marek Perkowski Synthesis of multi-qudit hybrid and $d$-valued quantum logic circuits by decomposition . . . . . . . . . . . . . 336--346 Anonymous Editorial Board . . . . . . . . . . . . iii--vii
Sophia Drossopoulou and Giovanni Lagorio and Susan Eisenbach A flexible model for dynamic linking in Java and C# . . . . . . . . . . . . . . 1--29 Markus Krötzsch Generalized ultrametric spaces in quantitative domain theory . . . . . . . 30--49 Michael Kaminski Invariance under stuttering in a temporal logic of actions . . . . . . . 50--63 Vasco T. Vasconcelos and Simon J. Gay and António Ravara Type checking a multithreaded functional language with session types . . . . . . 64--87 Foto Afrati and Chen Li and Prasenjit Mitra Rewriting queries using views in the presence of arithmetic comparisons . . . 88--123 Yi-Xiang Chen and Achim Jung A logical approach to stable domains . . 124--148 Zaiyue Zhang and Yuefei Sui and Cungen Cao and Guohua Wu A formal fuzzy reasoning system and reasoning mechanism based on propositional modal logic . . . . . . . 149--160 Stéphanie Delaune An undecidability result for AGh . . . . 161--167 R. J. van Glabbeek Erratum to ``On the expressiveness of higher dimensional automata'': [Theoret. Comput. Sci. 356 (2006) 265--290] . . . 168--194 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Suleyman Cenk Sahinalp and Ugur Dogrusoz and S. Muthukrishnan Preface . . . . . . . . . . . . . . . . 195--195 Amihood Amir and Oren Kapah and Dekel Tsur Faster two-dimensional pattern matching with rotations . . . . . . . . . . . . . 196--204 Eugene Davydov and Serafim Batzoglou A computational model for RNA multiple structural alignment . . . . . . . . . . 205--216 Stefano Lonardi and Wojciech Szpankowski and Qiaofeng Yang Finding biclusters by random projections 217--230 Richard F. Geary and Naila Rahman and Rajeev Raman and Venkatesh Raman A simple optimal representation for balanced parentheses . . . . . . . . . . 231--246
T. Jurdzi\'nski and F. Mráz and F. Otto and M. Plátek Degrees of non-monotonicity for restarting automata . . . . . . . . . . 1--34 Oleg Pikhurko and Jerzy Wojciechowski Edge-bandwidth of grids and tori . . . . 35--43 Jing-Chao Chen Efficient sample sort and the average case analysis of PEsort . . . . . . . . 44--66 Henning Bordihn and Henning Fernau and Markus Holzer and Vincenzo Manca and Carlos Martín-Vide Iterated sequential transducers as language generating devices . . . . . . 67--81 Thomas Eiter and Georg Gottlob Reasoning under minimal upper bounds in propositional logic . . . . . . . . . . 82--115 Martin Gairing and Thomas Lücking and Marios Mavronicolas and Burkhard Monien The price of anarchy for polynomial social cost . . . . . . . . . . . . . . 116--135 Bang Ye Wu On the intercluster distance of a tree metric . . . . . . . . . . . . . . . . . 136--141 Véronique Terrier Low complexity classes of multidimensional cellular automata . . . 142--156 Eric Angel and Evripidis Bampis and Fanny Pascual Truthful algorithms for scheduling selfish tasks on parallel machines . . . 157--168 Carlo Blundo and Stelvio Cimato and Alfredo De Santis Visual cryptography schemes with optimal pixel expansion . . . . . . . . . . . . 169--182 Michael Domaratzki and Petr Sosík and Alfonso Rodríguez-Patón Algebraic properties of substitution on trajectories . . . . . . . . . . . . . . 183--196 Farshad Rostamabadi and Mohammad Ghodsi Label updating to avoid point-shaped obstacles in fixed model . . . . . . . . 197--210 Stephen Travers The complexity of membership problems for circuits over sets of integers . . . 211--229 Hans Kellerer and Vitaly A. Strusevich A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date 230--238 G. Bebek and P. Berenbrink and C. Cooper and T. Friedetzky and J. Nadeau and S. C. Sahinalp The degree distribution of the generalized duplication model . . . . . 239--249 Jianfeng Hou and Guizhen Liu and Jiansheng Cai List edge and list total colorings of planar graphs without 4-cycles . . . . . 250--255 Weigen Yan and Yeong-Nan Yeh Enumeration of subtrees of trees . . . . 256--268 V. Bil\`o and M. Flammini and G. Melideo and L. Moscardelli and A. Navarra Sharing the cost of multicast transmissions in wireless networks . . . 269--284 Leah Epstein and Alex Kesselman On the remote server problem or more about TCP acknowledgments . . . . . . . 285--299 Michael Hoffmann and Richard M. Thomas A geometric characterization of automatic semigroups . . . . . . . . . . 300--313 Wit Fory\'s and Tomasz Krawczyk An algorithmic approach to the problem of a semiretract base . . . . . . . . . 314--322 Amrinder Arora and Fanchun Jin and Hyeong-Ah Choi Scheduling resource allocation with timeslot penalty for changeover . . . . 323--337 Ronald Koch and Ines Spenke Complexity and approximability of $k$-splittable flows . . . . . . . . . . 338--347 Shlomi Dolev and Roberto Segala and Alexander Shvartsman Dynamic load balancing with group communication . . . . . . . . . . . . . 348--360 Sylvain Pion and Chee K. Yap Constructive root bound for $k$-ary rational input numbers . . . . . . . . . 361--376 D. Azriel and D. Berend On a question of Leiss regarding the Hanoi Tower problem . . . . . . . . . . 377--383 Asaf Levin and Danny Segev Partial multicuts in trees . . . . . . . 384--395 Vicente Acuña and Gilles Didier and Alejandro Maass Coding with variable block maps . . . . 396--405 Mário J. J. Branco Two algebraic approaches to variants of the concatenation product . . . . . . . 406--426 Teofilo F. Gonzalez and David Serena Pairwise edge disjoint shortest paths in the $n$-cube . . . . . . . . . . . . . . 427--435 Lakshmanan Kuppusamy A note on ambiguity of internal contextual grammars . . . . . . . . . . 436--441 Wei-Mei Chen Cost distribution of the Chang--Roberts leader election algorithm and related problems . . . . . . . . . . . . . . . . 442--447 Wenqiang Dai and Yinfeng Xu and Binhai Zhu On the edge $ l_\infty $ radius of Saitou and Nei's method for phylogenetic reconstruction . . . . . . . . . . . . . 448--455 Wenbo Zhao and Peng Zhang and Tao Jiang A network flow approach to the Minimum Common Integer Partition Problem . . . . 456--462 A. Gajardo and E. Goles Crossing information in two-dimensional Sandpiles . . . . . . . . . . . . . . . 463--469 Anonymous Editorial Board . . . . . . . . . . . . v--ix
François Nicolas and Eric Rivals Longest common subsequence problem for unoriented and cyclic strings . . . . . 1--18 Jin Wook Kim and Kunsoo Park An efficient alignment algorithm for masked sequences . . . . . . . . . . . . 19--33 A. Gajardo and J. Mazoyer One Head Machines from a symbolic approach . . . . . . . . . . . . . . . . 34--47 Jeremy Avigad and Yimu Yin Quantifier elimination for the reals with a predicate for the powers of two 48--59 Christian Glaßer and Alan L. Selman and Liyu Zhang Canonical disjoint NP-pairs of propositional proof systems . . . . . . 60--73 Vassilis Giakoumakis and Stephan Olariu All minimal prime extensions of hereditary classes of graphs . . . . . . 74--93 Shane Saunders and Tadao Takaoka Solving shortest paths efficiently on nearly acyclic directed graphs . . . . . 94--109 Yo-Sub Han and Derick Wood Obtaining shorter regular expressions from finite-state automata . . . . . . . 110--120 Jun-Jie Pan and Gerard J. Chang Induced-path partition on graphs with special blocks . . . . . . . . . . . . . 121--130 Jorge Almeida and Marc Zeitoun An automata-theoretic approach to the word problem for $ \omega $-terms over $R$ . . . . . . . . . . . . . . . . . . 131--169 Peter Leupold Languages generated by iterated idempotency . . . . . . . . . . . . . . 170--185 Dario Catalano and Rosario Gennaro Cramer-Damgård signatures revisited: Efficient flat-tree signatures based on factoring . . . . . . . . . . . . . . . 186--200 Andrea Frosini and Maurice Nivat Binary matrices under the microscope: a tomographical problem . . . . . . . . . 201--217 L. Sunil Chandran and L. Shankar Ram On the relationship between ATSP and the cycle cover problem . . . . . . . . . . 218--228 Andreas Brandstädt and Van Bang Le and Suhail Mahfud New applications of clique separator decomposition for the Maximum Weight Stable Set problem . . . . . . . . . . . 229--239 Yongxi Cheng and Xi Chen and Yiqun Lisa Yin On searching a table consistent with division poset . . . . . . . . . . . . . 240--253 Boaz Patt-Shamir A note on efficient aggregate queries in sensor networks . . . . . . . . . . . . 254--264 Markus Kuba and Alois Panholzer The left-right-imbalance of binary search trees . . . . . . . . . . . . . . 265--278 Andrzej Pelc and David Peleg Feasibility and complexity of broadcasting with random transmission failures . . . . . . . . . . . . . . . . 279--292 Chi-Jen Lu and Shi-Chun Tsai and Hsin-Lung Wu Improved hardness amplification in NP 293--298 Sun-Yuan Hsieh Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species . . . . . . . . . . . . . . . . 299--308 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Thomas Bäck and Benedikt Löwe Computing and the natural sciences at CiE 2005 . . . . . . . . . . . . . . . . 1--3 Edwin J. Beggs and John V. Tucker Can Newtonian systems, bounded in space, time, mass and energy compute all functions? . . . . . . . . . . . . . . . 4--19 Francesco Bernardini and Marian Gheorghe and Natalio Krasnogor Quorum sensing P systems . . . . . . . . 20--33 Artur S. d'Avila Garcez and Luís C. Lamb and Dov M. Gabbay Connectionist modal logic: Representing modalities in neural networks . . . . . 34--53 Miguel A. Gutiérrez-Naranjo and Mario J. Pérez-Jiménez and Francisco J. Romero-Campero A uniform solution to SAT using membrane creation . . . . . . . . . . . . . . . . 54--61 Krzysztof Michalak and Halina Kwa\'snicka Influence of data dimensionality on the quality of forecasts given by a multilayer perceptron . . . . . . . . . 62--71 Florin Manea and Carlos Martín-Vide and Victor Mitrana Accepting networks of splicing processors: Complexity results . . . . . 72--82 Shankara Narayanan Krishna Universality results for P systems based on brane calculi operations . . . . . . 83--105 Giuseppe Trautteur and Guglielmo Tamburrini A note on discreteness and virtuality in analog computing . . . . . . . . . . . . 106--114 John V. Tucker and Jeffery I. Zucker Computability of analog networks . . . . 115--146 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Thomas Eiter and Leonid Libkin Preface . . . . . . . . . . . . . . . . 147--147 Vladlen Koltun and Christos H. Papadimitriou Approximately dominating representatives 148--154 Albert Atserias Conjunctive query evaluation by search-tree revisited . . . . . . . . . 155--168 Diego Calvanese and Giuseppe De Giacomo and Maurizio Lenzerini and Moshe Y. Vardi View-based query processing: On the relationship between rewriting, answering and losslessness . . . . . . . 169--182 Jan Van den Bussche and Dirk Van Gucht and Stijn Vansummeren Well-definedness and semantic type-checking for the nested relational calculus . . . . . . . . . . . . . . . . 183--199 Alin Deutsch and Bertram Ludäscher and Alan Nash Rewriting queries using views with access patterns under integrity constraints . . . . . . . . . . . . . . 200--226 Yossi Matias and Daniel Urieli Optimal workload-based weighted wavelet synopses . . . . . . . . . . . . . . . . 227--246 José L. Balcázar and Gemma C. Garriga Horn axiomatizations for sequential data 247--264
Igor Dolinka Axiomatizing the identities of binoid languages . . . . . . . . . . . . . . . 1--14 F. Levé and G. Richomme Quasiperiodic Sturmian words and morphisms . . . . . . . . . . . . . . . 15--25 Piotr Berman and Marek Karpinski and Yakov Nekrich Optimal trade-off for Merkle tree traversal . . . . . . . . . . . . . . . 26--36 Paul Bell and Igor Potapov On the membership of invertible diagonal and scalar matrices . . . . . . . . . . 37--45 Marcus Pivato RealLife: The continuum limit of Larger than Life cellular automata . . . . . . 46--68 Zhiyi Tan and Yong Wu Optimal semi-online algorithms for machine covering . . . . . . . . . . . . 69--80 Toshimasa Ishii and Hitoshi Fujita and Hiroshi Nagamochi Minimum cost source location problem with local 3-vertex-connectivity requirements . . . . . . . . . . . . . . 81--93 Deshi Ye and Guochuan Zhang On-line scheduling mesh jobs with dependencies . . . . . . . . . . . . . . 94--102 Wenqing Dou and Enyu Yao On rearrangeable multirate three-stage Clos networks . . . . . . . . . . . . . 103--107 Frank Gurski Characterizations for restricted graphs of NLC-width 2 . . . . . . . . . . . . . 108--114 Paolo Ferragina and Rossano Venturini A simple storage scheme for strings achieving entropy bounds . . . . . . . . 115--121 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Gheorghe P\uaun and Mario J. Pérez-Jiménez Fourth Brainstorming Week on Membrane Computing . . . . . . . . . . . . . . . 123--124 Nadia Busi Using well-structured transition systems to decide divergence for catalytic P systems . . . . . . . . . . . . . . . . 125--135 Matteo Cavaliere and Rudolf Freund and Marion Oswald and Drago\cs Sburlan Multiset random context grammars, checkers, and transducers . . . . . . . 136--151 Erzsébet Csuhaj-Varjú and Maurice Margenstern and György Vaszil and Sergey Verlan On small universal antiport P systems 152--164 Federico Fontana and Vincenzo Manca Discrete solutions to differential equations by metabolic P systems . . . . 165--182 Miguel A. Gutiérrez-Naranjo and Mario J. Pérez-Jiménez and Agustín Riscos-Núñez On the degree of parallelism in membrane systems . . . . . . . . . . . . . . . . 183--195 Oscar H. Ibarra and Andrei P\uaun and Gheorghe P\uaun and Alfonso Rodríguez-Patón and Petr Sosík and Sara Woodworth Normal forms for spiking neural P systems . . . . . . . . . . . . . . . . 196--217 Alberto Leporati and Sara Felloni Three ``quantum'' algorithms to solve 3-SAT . . . . . . . . . . . . . . . . . 218--241 Michael Muskulus and Daniela Besozzi and Robert Brijder and Paolo Cazzaniga and Sanne Houweling and Dario Pescini and Grzegorz Rozenberg Cycles and communicating classes in membrane systems and molecular dynamics 242--266 Anonymous Editorial Board . . . . . . . . . . . . i--v
Sebastian Danicic and Mark Harman and Rob Hierons and John Howroyd and Michael R. Laurence Equivalence of linear, free, liberal, structured program schemas is decidable in polynomial time . . . . . . . . . . . 1--18 Gerald Lüttgen and Walter Vogler Conjunction on processes: Full abstraction via ready-tree semantics . . 19--40 Franco Barbanera and Michele Bugliesi and Mariangiola Dezani-Ciancaglini and Vladimiro Sassone Space-aware ambients and processes . . . 41--69 Manuel Clavel and José Meseguer and Miguel Palomino Reflection in membership equational logic, many-sorted equational logic, Horn logic with equality, and rewriting logic . . . . . . . . . . . . . . . . . 70--91 Yuxin Deng and Catuscia Palamidessi Axiomatizations for probabilistic finite-state behaviors . . . . . . . . . 92--114 Ugo Dal Lago and Angelo Montanari and Gabriele Puppis Compact and tractable automaton-based representations of time granularities 115--141 Isar Stubbe Towards ``dynamic domains'': Totally continuous cocomplete $ \mathcal {Q} $-categories . . . . . . . . . . . . . . 142--160 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Peter D. Mosses and Irek Ulidowski Preface . . . . . . . . . . . . . . . . 161--162 Oana Andrei and Gabriel Ciobanu and Dorel Lucanu A rewriting logic framework for operational semantics of membrane systems . . . . . . . . . . . . . . . . 163--181 Samuel Hym and Matthew Hennessy Adding recursion to Dpi . . . . . . . . 182--212 José Meseguer and Grigore Ro\csu The rewriting logic semantics project 213--237 MohammadReza Mousavi and Michel A. Reniers and Jan Friso Groote SOS formats and meta-theory: 20 years after . . . . . . . . . . . . . . . . . 238--272 Ando Saabas and Tarmo Uustalu A compositional natural semantics and Hoare logic for low-level languages . . 273--302
M. Murakami and M. Hara and M. Yamamoto and S. Tani Fast algorithms for computing Jones polynomials of certain links . . . . . . 1--24 S. Nicolay and M. Rigo About frequencies of letters in generalized automatic sequences . . . . 25--40 Biao Wu and Enyue Yao k-Partitioning problems with partition matroid constraint . . . . . . . . . . . 41--48 Ji Tian and Ruyan Fu and Jinjiang Yuan On-line scheduling with delivery time on a single batch machine . . . . . . . . . 49--57 Jamie Simpson Intersecting periodic words . . . . . . 58--65 Yongxi Cheng Lattice grids and prisms are antimagic 66--73 Erzsébet Csuhaj-Varjú and Ion Petre and György Vaszil Self-assembly of strings and languages 74--81 Gerard J. Chang and Sen-Peng Eu and Chung-Heng Yeh On the $ (n, t)$-antipodal Gray codes 82--90 Estela M. Rodrigues and Marie-France Sagot and Yoshiko Wakabayashi The maximum agreement forest problem: Approximation algorithms and computational experiments . . . . . . . 91--110 Niklas Eriksen Reversal and transposition medians . . . 111--126 Dietrich Kuske Weighted asynchronous cellular automata 127--148 Noga Alon and Andrzej Lingas and Martin Wahlen Approximating the maximum clique minor and some subgraph homeomorphism problems 149--158 L. L. Liu and C. T. Ng and T. C. E. Cheng Scheduling jobs with agreeable processing times and due dates on a single batch processing machine . . . . 159--169 Jun-Ho Her and R. S. Ramakrishna An external-memory depth-first search algorithm for general grid graphs . . . 170--180 Qiqi Yan Classifying regular languages by a split game . . . . . . . . . . . . . . . . . . 181--190 Wenbin Chen and Jiangtao Meng Hardness of approximating the Minimum Solutions of Linear Diophantine Equations . . . . . . . . . . . . . . . 191--195 Ruyan Fu and Tian Ji and Jinjiang Yuan and Yixun Lin Online scheduling in a parallel batch processing system to minimize makespan using restarts . . . . . . . . . . . . . 196--202 R. Královi\vc and P. Ru\vzi\vcka Ranks of graphs: The size of acyclic orientation cover for deadlock-free packet routing . . . . . . . . . . . . . 203--213 Ina Mäurer Characterizations of recognizable picture series . . . . . . . . . . . . . 214--228 Dario Catalano and Ivan Visconti Hybrid commitments and their applications to zero-knowledge proof systems . . . . . . . . . . . . . . . . 229--260 S. Cimato and R. De Prisco and A. De Santis Colored visual cryptography without color darkening . . . . . . . . . . . . 261--276 Jerzy Mycka and José Félix Costa A new conceptual framework for analog computation . . . . . . . . . . . . . . 277--290 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Olivier Danvy and Peter O'Hearn and Philip Wadler Preface . . . . . . . . . . . . . . . . 1--2 C. Hermida and R. D. Tennent A fibrational framework for possible-world semantics of Algol . . . 3--19 Martin Hyland and Paul Blain Levy and Gordon Plotkin and John Power Combining algebraic effects with continuations . . . . . . . . . . . . . 20--40 Andrzej Filinski On the relations between monadic semantics . . . . . . . . . . . . . . . 41--75 Ma\lgorzata Biernacka and Olivier Danvy A syntactic correspondence between context-sensitive calculi and abstract machines . . . . . . . . . . . . . . . . 76--108 C. B. Jones Splitting atoms safely . . . . . . . . . 109--119 Neil D. Jones and Nils Andersen Flow analysis of lazy higher-order functional programs . . . . . . . . . . 120--136 Matthew Might and Olin Shivers Analyzing the environment structure of higher-order languages using frame strings . . . . . . . . . . . . . . . . 137--168 Eijiro Sumii and Benjamin C. Pierce A bisimulation for dynamic sealing . . . 169--192 Peter Freyd Core algebra revisited . . . . . . . . . 193--200 Philip Wadler The Girard--Reynolds isomorphism (second edition) . . . . . . . . . . . . . . . . 201--226 Stephen Brookes A semantics for concurrent separation logic . . . . . . . . . . . . . . . . . 227--270 Peter W. O'Hearn Resources, concurrency, and local reasoning . . . . . . . . . . . . . . . 271--307 Hongseok Yang Relational separation logic . . . . . . 308--334 F. Lockwood Morris A few exercises in theorem processing 335--345 Frank J. Oles On being a student of John Reynolds . . 346--350 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Oscar H. Ibarra Developments in language theory . . . . 1--2 A. Ehrenfeucht and G. Rozenberg Events and modules in reaction systems 3--16 Yuri Gurevich and Margus Veanes and Charles Wallace Can abstract state machines be useful in language theory? . . . . . . . . . . . . 17--29 D. S. Ananichev and M. V. Volkov and Yu. I. Zaks Synchronizing automata with a letter of deficiency 2 . . . . . . . . . . . . . . 30--41 Cédric Bastien and Jurek Czyzowicz and Wojciech Fraczak and Wojciech Rytter Equivalence of simple functions . . . . 42--51 Olivier Carton The growth ratio of synchronous rational relations is unique . . . . . . . . . . 52--59 Yo-Sub Han and Arto Salomaa and Kai Salomaa and Derick Wood and Sheng Yu On the existence of prime decompositions 60--69 Dalia Krieger On critical exponents in fixed points of non-erasing morphisms . . . . . . . . . 70--88 Manfred Kufleitner Polynomials, fragments of temporal logic and the variety DA over traces . . . . . 89--100 Martin Kutrib and Andreas Malcher Context-dependent nondeterminism for pushdown automata . . . . . . . . . . . 101--111 Alexander Okhotin and Oksana Yakimova Language equations with complementation: Decision problems . . . . . . . . . . . 112--126 Bala Ravikumar On some variations of two-way probabilistic finite automata models . . 127--136 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Maura Cerioli and Tiziana Margaria and Michel Wermelinger Foreword . . . . . . . . . . . . . . . . 137--138 Juan de Lara and Roswitha Bardohl and Hartmut Ehrig and Karsten Ehrig and Ulrike Prange and Gabriele Taentzer Attributed graph transformation with node type inheritance . . . . . . . . . 139--163 Carlo A. Furia and Matteo Rossi and Dino Mandrioli and Angelo Morzenti Automated compositional proofs for real-time systems . . . . . . . . . . . 164--184 Gruia-Catalin Roman and Christine Julien and Jamie Payton Modeling adaptive behaviors in Context UNITY . . . . . . . . . . . . . . . . . 185--204 David A. Naumann Observational purity and encapsulation 205--224
Saeed Salehi and Magnus Steinby Tree algebras and varieties of tree languages . . . . . . . . . . . . . . . 1--24 Zhao Zhang and Hao Li Algorithms for long paths in graphs . . 25--34 Adi Avidor and Michael Langberg The multi-multiway cut problem . . . . . 35--42 Jiro Uchida and Wei Chen and Koichi Wada Acknowledged broadcasting and gossiping in ad hoc radio networks . . . . . . . . 43--54 Leah Epstein and Yanir Kleiman and Ji\vrí Sgall and Rob van Stee Paging with connections: FIFO strikes again . . . . . . . . . . . . . . . . . 55--64 Ana Marco and José-Javier Martínez Bernstein--Bezoutian matrices and curve implicitization . . . . . . . . . . . . 65--72 Flavio D'Alessandro and Gwénaël Richomme and Stefano Varricchio Well quasi-orders generated by a word-shuffle rewriting . . . . . . . . . 73--92 Olaf Beyersdorff Classes of representable disjoint NP . . 93--109 Zhiyi Tan and Yong He Semi-online scheduling problems on two identical machines with inexact partial information . . . . . . . . . . . . . . 110--125 Verónica Becher and Santiago Figueira and Rafael Picchi Turing's unpublished algorithm for normal numbers . . . . . . . . . . . . . 126--138 Richard Nock and Frank Nielsen Self-improved gaps almost everywhere for the agnostic approximation of monomials 139--150 Tien-Ching Lin and D. T. Lee Randomized algorithm for the sum selection problem . . . . . . . . . . . 151--156 Hanna Uscka-Wehlou Digital lines with irrational slopes . . 157--169 Jung-Heum Park and Hyeong-Seok Lim and Hee-Chul Kim Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements . . . . . . . . . . 170--180 Florian Diedrich and Klaus Jansen Faster and simpler approximation algorithms for mixed packing and covering problems . . . . . . . . . . . 181--204 Marcus Pivato Defect particle kinematics in one-dimensional cellular automata . . . 205--228 Fredrik Bengtsson and Jingsen Chen Ranking $k$ maximum sums . . . . . . . . 229--237 Yung-Ling Lai and Chang-Sin Tian An extremal graph with given bandwidth 238--242 A. Rogers and R. K. Dash and S. D. Ramchurn and P. Vytelingum and N. R. Jennings Coordinating team players within a noisy Iterated Prisoner's Dilemma tournament 243--259 Michaël Rao MSOL partitioning problems on graphs of bounded treewidth and clique-width . . . 260--267 Alexander Rybalov On the strongly generic undecidability of the Halting Problem . . . . . . . . . 268--270 Josep Díaz and Marcin Kami\'nski MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs . . . . . . . . . . . . 271--276 Sean Cleary and Fabrizio Luccio and Linda Pagli Refined upper bounds for right-arm rotation distances . . . . . . . . . . . 277--281 Takashi Yokomori Erratum to ``Polynomial-time identification of very simple grammars from positive data'' [Theoret. Comput. Sci. 298 (2003) 179--206] . . . . . . . 282--283 Anonymous Editorial Board . . . . . . . . . . . . v--ix
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1--2 Mark Daley and Michael Domaratzki On codes defined by bio-operations . . . 3--16 Yuriy Brun Arithmetic computation in the tile assembly model: Addition and multiplication . . . . . . . . . . . . . 17--31 Frank Neumann and Ingo Wegener Randomized local search, evolutionary algorithms, and the minimum spanning tree problem . . . . . . . . . . . . . . 32--40 Andris Ambainis and Kazuo Iwama and Akinori Kawachi and Rudy Raymond and Shigeru Yamashita Improved algorithms for quantum identification of Boolean oracles . . . 41--53 S. Verel and P. Collard and M. Tomassini and L. Vanneschi Fitness landscape of the cellular automata majority problem: View from the ``Olympus'' . . . . . . . . . . . . . . 54--77 El-Ghazali Talbi and Benjamin Weinberg Breaking the search space symmetry in partitioning problems: an application to the graph coloring problem . . . . . . . 78--86 Dezhong Peng and Zhang Yi Convergence analysis of the OJAn MCA learning algorithm by the deterministic discrete time method . . . . . . . . . . 87--100 Elham Kashefi and Iordanis Kerenidis Statistical Zero Knowledge and quantum one-way functions . . . . . . . . . . . 101--116 Gabriel Ciobanu and Linqiang Pan and Gheorghe P\uaun and Mario J. Pérez-Jiménez P systems with minimal parallelism . . . 117--130 Florin Manea and Carlos Martín-Vide and Victor Mitrana Erratum to: ``Accepting networks of splicing processors: Complexity results'' [Theoret. Comput. Sci. 371 (2007) 72--82] . . . . . . . . . . . . . 131--131 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Xiaotie Deng Preface . . . . . . . . . . . . . . . . 133--133 Yinyu Ye Exchange market equilibria with Leontief's utility: Freedom of pricing leads to rationality . . . . . . . . . . 134--142 Dinesh Garg and Kamal Jain and Kunal Talwar and Vijay V. Vazirani A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property . . . . 143--152 Sanjiv Kapoor and Aranyak Mehta and Vijay Vazirani An auction-based market equilibrium algorithm for a production model . . . . 153--164 Simon Fischer and Berthold Vöcking On the structure and complexity of worst-case equilibria . . . . . . . . . 165--174 Joan Feigenbaum and David R. Karger and Vahab S. Mirrokni and Rahul Sami Subjective-cost policy routing . . . . . 175--189 Gang Cheng and Ping Li and Peng Shi A new algorithm based on copulas for VaR valuation with empirical calculations 190--197 Robert W. Zhu and Guomin Yang and Duncan S. Wong An efficient identity-based key exchange protocol with KGS forward secrecy for low-power devices . . . . . . . . . . . 198--207
Zhi-Zhong Chen and Xiaotie Deng and Ding-zhu Du Preface . . . . . . . . . . . . . . . . 209--210 Sumit Ganguly Counting distinct items over update streams . . . . . . . . . . . . . . . . 211--222 Erdong Chen and Linji Yang and Hao Yuan Longest increasing subsequences in windows based on canonical antichain partition . . . . . . . . . . . . . . . 223--236 Boaz Ben-Moshe and Binay Bhattacharya and Qiaosheng Shi and Arie Tamir Efficient algorithms for center problems in cactus networks . . . . . . . . . . . 237--252 Heiner Ackermann and Alantha Newman and Heiko Röglin and Berthold Vöcking Decision-making based on approximate and smoothed Pareto curves . . . . . . . . . 253--270 Ming-Yang Kao and Xiang-Yang Li and Weizhao Wang Average case analysis for tree labelling schemes . . . . . . . . . . . . . . . . 271--291 Bodo Manthey and Rüdiger Reischuk Smoothed analysis of binary search trees 292--315 Lan Liu and Chen Xi and Jing Xiao and Tao Jiang Complexity and approximation of the minimum recombinant haplotype configuration problem . . . . . . . . . 316--330
Jan Friso Groote and Marc Voorhoeve Operational semantics for Petri net components . . . . . . . . . . . . . . . 1--19 Giorgi Japaridze From truth to computability II . . . . . 20--52 Manuel A. Martins Closure properties for the class of behavioral models . . . . . . . . . . . 53--83 Max Kanovich and Jacqueline Vauzeilles Strong planning under uncertainty in domains with numerous but identical elements (a generic approach) . . . . . 84--119 J. Raymundo Marcial-Romero and Martín H. Escardó Semantics of a sequential language for exact real-number computation . . . . . 120--141 R. Chadha and L. Cruz-Filipe and P. Mateus and A. Sernadas Reasoning about probabilistic sequential programs . . . . . . . . . . . . . . . . 142--165 Lionel Vaux The differential $ \lambda \mu $ calculus . . . . . . . . . . . . . . . . 166--209 R\uazvan Diaconescu and Petros Stefaneas Ultraproducts and possible worlds semantics in institutions . . . . . . . 210--230 Eugene Asarin and Gerardo Schneider and Sergio Yovine Algorithmic analysis of polygonal hybrid systems, part I: Reachability . . . . . 231--265 Anuj Dawar and Stephan Kreutzer Generalising automaticity to modal properties of finite structures . . . . 266--285 Laura Bozzelli Complexity results on branching-time pushdown model checking . . . . . . . . 286--297 Sándor Vágvölgyi Losing recognizability . . . . . . . . . 298--304 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Jos C. M. Baeten and Jan Karel Lenstra and Gerhard J. Woeginger Preface . . . . . . . . . . . . . . . . 305--305 Noam Berger and Béla Bollobás and Christian Borgs and Jennifer Chayes and Oliver Riordan Degree distribution of the FKP network model . . . . . . . . . . . . . . . . . 306--316 Vipul Bansal and Aseem Agrawal and Varun S. Malhotra Polynomial time algorithm for an optimal stable assignment with multiple partners 317--328 Jens Jägersküpper Algorithmic analysis of a basic evolutionary algorithm for continuous optimization . . . . . . . . . . . . . . 329--347 Daniel Bleichenbacher and Aggelos Kiayias and Moti Yung Decoding interleaved Reed--Solomon codes over noisy channels . . . . . . . . . . 348--360 Leonid Khachiyan and Endre Boros and Khaled Elbassioni and Vladimir Gurvich and Kazuhisa Makino Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data 361--376 Manuel Bodirsky and Clemens Gröpl and Mihyun Kang Generating labeled planar graphs uniformly at random . . . . . . . . . . 377--386 Alex Hall and Steffen Hippler and Martin Skutella Multicommodity flows over time: Efficient algorithms and complexity . . 387--404 Anna Gál and Peter Bro Miltersen The cell probe complexity of succinct data structures . . . . . . . . . . . . 405--417 Yossi Matias and Ely Porat Efficient pebbling for list traversal synopses with application to program rollback . . . . . . . . . . . . . . . . 418--436
Giuseppe F. Italiano and Catuscia Palamidessi Preface . . . . . . . . . . . . . . . . 1--1 Chen Avin and Gunes Ercal On the cover time and mixing time of random geometric graphs . . . . . . . . 2--22 Eugen Czeizler and Jarkko Kari A tight linear bound on the synchronization delay of bijective automata . . . . . . . . . . . . . . . . 23--36 Artur Czumaj and Miros\law Kowaluk and Andrzej Lingas Faster algorithms for finding lowest common ancestors in directed acyclic graphs . . . . . . . . . . . . . . . . . 37--46 Martin Dietzfelbinger and Christoph Weidling Balanced allocation and dictionaries with tightly packed constant size bins 47--68 Manfred Droste and Paul Gastin Weighted automata and weighted logics 69--86 Martin Gairing and Burkhard Monien and Andreas Woclaw A faster combinatorial approximation algorithm for scheduling unrelated parallel machines . . . . . . . . . . . 87--99 Juraj Hromkovi\vc and Georg Schnitger Comparing the size of NFAs with and without $ \epsilon $-transitions . . . . 100--114 Pascal Koiran and Vincent Nesme and Natacha Portier The quantum query complexity of the abelian hidden subgroup problem . . . . 115--126 Mihai Pa\utra\cscu and Corina E. Tarni\ct\ua On dynamic bit-probe complexity . . . . 127--142 Franck van Breugel and Claudio Hermida and Michael Makkai and James Worrell Recursively defined metric spaces without contraction . . . . . . . . . . 143--163 Damien Pous New up-to techniques for weak bisimulation . . . . . . . . . . . . . . 164--180 Michael Mislove Discrete random variables over domains 181--198 Martin Grohe and Christoph Koch and Nicole Schweikardt Tight lower bounds for query processing on streaming and external memory data 199--217 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Srecko Brlek and Christophe Reutenauer Preface . . . . . . . . . . . . . . . . 219--219 Boris Adamczewski and Jean-Paul Allouche Reversals and palindromes in continued fractions . . . . . . . . . . . . . . . 220--237 Petr Ambroz and Christiane Frougny On alpha-adic expansions in Pisot bases 238--250 Pierre Arnoux and Valérie Berthé and Thomas Fernique and Damien Jamet Functional stepped surfaces, flips, and generalized substitutions . . . . . . . 251--265 Peter Balázi and Zuzana Masáková and Edita Pelantová Factor versus palindromic complexity of uniformly recurrent infinite words . . . 266--275 Valérie Berthé and Bertrand Nouvel Discrete rotations and symbolic dynamics 276--285 Jean-Pierre Borel A geometrical characterization of factors of multidimensional Billiard words and some applications . . . . . . 286--303 J. Cassaigne and A. E. Frid On the arithmetical complexity of Sturmian words . . . . . . . . . . . . . 304--316 Thomas Fernique Local rule substitutions and stepped surfaces . . . . . . . . . . . . . . . . 317--329 Amy Glen Powers in a class of $ \mathcal {A} $-strict standard episturmian words . . 330--354 Vesa Halava and Tero Harju and Juhani Karhumäki and Michel Latteux Extension of the decidability of the marked PCP to instances with unique blocks . . . . . . . . . . . . . . . . . 355--362 Stepán Holub and Juha Kortelainen On systems of word equations with simple loop sets . . . . . . . . . . . . . . . 363--372 Lucian Ilie A note on the number of squares in a word . . . . . . . . . . . . . . . . . . 373--376 Arto Lepistö and Francesco Pappalardi and Kalle Saari Transposition invariant words . . . . . 377--387 Pascal Ochem Letter frequency in infinite repetition-free words . . . . . . . . . 388--392 G. Richomme Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words 393--400 Maurice H. ter Beek and Jetty Kleijn Infinite unfair shuffles and associativity . . . . . . . . . . . . . 401--410
Julien Cervelle and Enrico Formenti and Beno\^\it Masson From sandpiles to sand automata . . . . 1--28 Feng Wang and Hongwei David Du and Xiaohua Jia and Ping Deng and Weili Wu and David MacCallum Non-unique probe selection and group testing . . . . . . . . . . . . . . . . 29--32 Helmut Jürgensen and Ludwig Staiger and Hideki Yamasaki Finite automata encoding geometric figures . . . . . . . . . . . . . . . . 33--43 Dimitrios Koukopoulos and Marios Mavronicolas and Paul Spirakis The increase of the instability of networks due to Quasi-Static link capacities . . . . . . . . . . . . . . . 44--56 C. M. H. de Figueiredo and L. Faria and S. Klein and R. Sritharan On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs . . . . . . . . 57--67 Domingo Gómez and Jaime Gutierrez and Álvar Ibeas Optimal routing in double loop networks 68--85 Frédérique Bassino and Cyril Nicaud Enumeration and random generation of accessible automata . . . . . . . . . . 86--104 David Doty and Jared Nichols Pushdown dimension . . . . . . . . . . . 105--123 Mingxia Chen and Jianbo Li and Jianping Li and Weidong Li and Lusheng Wang Some approximation algorithms for the clique partition problem in weighted interval graphs . . . . . . . . . . . . 124--133 A. Amiraslani and D. A. Aruliah and R. M. Corless Block $ L U $ factors of generalized companion matrix pencils . . . . . . . . 134--147 Ker-I Ko and Fuxiang Yu Jordan curves with polynomial inverse moduli of continuity . . . . . . . . . . 148--161 Tamás Fleiner and Robert W. Irving and David F. Manlove Efficient algorithms for generalized Stable Marriage and Roommates problems 162--176 Dalia Krieger and Jeffrey Shallit Every real number greater than 1 is a critical exponent . . . . . . . . . . . 177--182 Michal Parnas and Dana Ron Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms . . . . . . . . . 183--196 Carme \`Alvarez and Rafel Cases and Josep Díaz and Jordi Petit and Maria Serna Communication tree problems . . . . . . 197--217 Cheng-Kuan Lin and Jimmy J. M. Tan and D. Frank Hsu and Lih-Hsing Hsu On the spanning connectivity and spanning laceability of hypercube-like networks . . . . . . . . . . . . . . . . 218--229 Jian-Liang Wu and Jian-Feng Hou and Gui-Zhen Liu The linear arboricity of planar graphs with no short cycles . . . . . . . . . . 230--233 Cheng He and Yixun Lin and Jinjiang Yuan Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan . . . . . . . . . . . . . . . . 234--240 Weiping Shang and Pengjun Wan and Frances Yao and Xiaodong Hu Algorithms for minimum $m$-connected $k$-tuple dominating set problem . . . . 241--247 Katerina Asdre and Stavros D. Nikolopoulos NP-completeness results for some problems on subclasses of bipartite and chordal graphs . . . . . . . . . . . . . 248--259 Andreas Brandstädt and Elaine M. Eschen and R. Sritharan The induced matching and chain subgraph cover problems for convex bipartite graphs . . . . . . . . . . . . . . . . . 260--265 Sylvain Lavallée and Christophe Reutenauer On a zeta function associated with automata and codes . . . . . . . . . . . 266--273 Christian Choffrut and Flavio D'Alessandro and Stefano Varricchio On the separability of sparse context-free languages and of bounded rational relations . . . . . . . . . . . 274--279 Vincenzo Bonifaci An adversarial queueing model for online server routing . . . . . . . . . . . . . 280--287 Sun-Yuan Hsieh and Shih-Cheng Yang Approximating the selected-internal Steiner tree . . . . . . . . . . . . . . 288--291 Xinmao Wang and Yaokun Wu Minimum light number of lit-only $ \sigma $-game on a tree . . . . . . . . 292--300 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Alessandra Di Pierro and Herbert Wiklicky Preface: Quantitative aspects of programming languages . . . . . . . . . 1--2 Alessandro Aldini and Marco Bernardo Mixing logics and rewards for the component-oriented specification of performance measures . . . . . . . . . . 3--23 Anne Remke and Boudewijn R. Haverkort and Lucia Cloth CSL model checking algorithms for QBDs 24--41 Rocco De Nicola and Joost-Pieter Katoen and Diego Latella and Michele Loreti and Mieke Massink Model checking mobile stochastic logic 42--70 Osman Hasan and Sofi\`ene Tahar Formalization of the Standard Uniform random variable . . . . . . . . . . . . 71--83 Anonymous Preface: Quantitative aspects of programming languages . . . . . . . . . v--ix
Mary Cryan and Martin Farach-Colton Preface . . . . . . . . . . . . . . . . 85--85 Mihai B\uadoiu and Richard Cole and Erik D. Demaine and John Iacono A unified access bound on comparison-based dynamic dictionaries 86--96 Saverio Caminiti and Irene Finocchi and Rossella Petreschi On coding labeled trees . . . . . . . . 97--108 Olivier Carton and Chloé Rispal Complementation of rational sets on scattered linear orderings of finite rank . . . . . . . . . . . . . . . . . . 109--119 J. Díaz and M. J. Serna and N. C. Wormald Bounds on the bisection width for random $d$-regular graphs . . . . . . . . . . . 120--130 Claudio Gutierrez and Flavio Gutierrez and Maria-Cecilia Rivara Complexity of the bisection method . . . 131--138 Leonid Khachiyan and Endre Boros and Khaled Elbassioni and Vladimir Gurvich On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs . . . . . 139--150 Kirk Pruhs and Gerhard J. Woeginger Approximation schemes for a class of subset selection problems . . . . . . . 151--156 Ke Yang On the (im)possibility of non-interactive correlation distillation 157--166
Shai Ben-David and JohnCase and Thomas Zeugmann Foreword . . . . . . . . . . . . . . . . 167--169 Eric Martin and Arun Sharma and Frank Stephan On the data consumption benefits of accepting increased uncertainty . . . . 170--182 Jérôme Besombes and Jean-Yves Marion Learning tree languages from positive examples and membership queries . . . . 183--197 Robert H. Sloan and Balázs Szörényi and György Turán Revising threshold functions . . . . . . 198--208 Andrei Bulatov and Hubie Chen and Víctor Dalmau Learning intersection-closed classes with signatures . . . . . . . . . . . . 209--220 Nicol\`o Cesa-Bianchi Applications of regularized least squares to pattern classification . . . 221--231 Amiran Ambroladze and Emilio Parrado-Hernández and John Shawe-Taylor Complexity of pattern classes and the Lipschitz property . . . . . . . . . . . 232--246 Marcus Hutter and Andrej Muchnik On semimeasures predicting Martin-Löf random sequences . . . . . . . . . . . . 247--261 Hans Ulrich Simon On the complexity of working set selection . . . . . . . . . . . . . . . 262--279
Rastislav Královi\vc Preface . . . . . . . . . . . . . . . . 1--1 Anonymous Dedication . . . . . . . . . . . . . . . 3--3 Bogdan S. Chlebus and Mariusz A. Rokicki Centralized asynchronous broadcast in radio networks . . . . . . . . . . . . . 5--22 Aleksej Di Salvo and Guido Proietti Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor . . . . . . . . . . . . . 23--33 Yon Dourisboure and Feodor F. Dragan and Cyril Gavoille and Chenyu Yan Spanners for bounded tree-length graphs 34--44 Leszek G\kasieniec and Igor Potapov and Qin Xin Time efficient centralized gossiping in radio networks . . . . . . . . . . . . . 45--58 Chryssis Georgiou and Peter M. Musial and Alexander A. Shvartsman Long-lived Rambo: Trading knowledge for communication . . . . . . . . . . . . . 59--85 Flaminia L. Luccio and Jop F. Sibeyn Feedback vertex sets in mesh-based networks . . . . . . . . . . . . . . . . 86--101 Rachel Matichin and David Peleg Approximation algorithm for hotlink assignment in the greedy model . . . . . 102--110 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Mark Burgin and Cristian S. Calude Preface . . . . . . . . . . . . . . . . 111--114 Chris Pollett and Norman Danner Circuit principles and weak pigeonhole variants . . . . . . . . . . . . . . . . 115--131 James M. Calvin A lower bound on complexity of optimization on the Wiener space . . . . 132--139 Arto Salomaa and Kai Salomaa and Sheng Yu State complexity of combined operations 140--152 Lane A. Hemaspaandra and Mayur Thakur Query-monotonic Turing reductions . . . 153--186 Ludwig Staiger The Kolmogorov complexity of infinite words . . . . . . . . . . . . . . . . . 187--199 Eugene Eberbach The \$-calculus process algebra for problem solving: a paradigmatic shift in handling hard computational problems . . 200--243 Mark Burgin Algorithmic complexity as a criterion of unsolvability . . . . . . . . . . . . . 244--259 Ji\vrí Wiedermann Autopoietic automata: Complexity issues in offspring-producing evolving processes . . . . . . . . . . . . . . . 260--269 Kevin T. Kelly Ockham's razor, empirical complexity, and truth-finding efficiency . . . . . . 270--289
Barry Cooper and Angsheng Li Preface: Theory and applications of models of computation . . . . . . . . . 1--1 Jan Arpe and Rüdiger Reischuk Learning juntas in the presence of noise 2--21 Jin-Yi Cai and Vinay Choudhary Valiant's Holant Theorem and matchgate tensors . . . . . . . . . . . . . . . . 22--32 Marcus Hutter On universal prediction and Bayesian confirmation . . . . . . . . . . . . . . 33--48 Sanjay Jain and Jochen Nessel and Frank Stephan Invertible classes . . . . . . . . . . . 49--65 Lisa Hellerstein and Rocco A. Servedio On PAC learning algorithms for rich Boolean function classes . . . . . . . . 66--76 Andrej Muchnik and Alexander Shen and Mikhail Ustinov and Nikolai Vereshchagin and Michael Vyugin Non-reducible descriptions for conditional Kolmogorov complexity . . . 77--86 Xiaoming Sun Block sensitivity of weakly symmetric functions . . . . . . . . . . . . . . . 87--91 Xuehou Tan A linear-time $2$-approximation algorithm for the watchman route problem for simple polygons . . . . . . . . . . 92--103 Alasdair Urquhart Width versus size in resolution proofs 104--110 Mingji Xia and Peng Zhang and Wenbo Zhao Computational complexity of counting problems on 3-regular planar graphs . . 111--125 Peng Zhang A new approximation algorithm for the $k$-facility location problem . . . . . 126--135 Anonymous Preface: Theory and applications of models of computation . . . . . . . . . v--ix
Andrzej Pelc and David Peleg and Michel Raynal Preface . . . . . . . . . . . . . . . . 137--138 Jean-Claude Bermond and Laurent Braud and David Coudert Traffic grooming on the path . . . . . . 139--151 Ioannis Caragiannis and Aleksei V. Fishkin and Christos Kaklamanis and Evi Papaioannou A tight bound for online colouring of disk graphs . . . . . . . . . . . . . . 152--160 Andrea E. F. Clementi and Miriam Di Ianni and Massimo Lauria and Angelo Monti and Gianluca Rossi and Riccardo Silvestri On the bounded-hop MST problem on random Euclidean instances . . . . . . . . . . 161--167 Yefim Dinitz and Noam Solomon Two absolute bounds for distributed bit complexity . . . . . . . . . . . . . . . 168--183 Markus Hinkelmann and Andreas Jakoby Communications in unknown networks: Preserving the secret of topology . . . 184--200 Ralf Klasing and Euripides Markou and Tomasz Radzik and Fabiano Sarracco Hardness and approximation results for Black Hole Search in arbitrary networks 201--221 Giuseppe Prencipe Impossibility of gathering by a set of autonomous mobile robots . . . . . . . . 222--231 Nicola Santoro and Peter Widmayer Agreement in synchronous networks with ubiquitous faults . . . . . . . . . . . 232--249 Mordechai Shalom and Shmuel Zaks Minimization of the number of ADMs in SONET rings with maximum throughput with implications to the traffic grooming problem . . . . . . . . . . . . . . . . 250--262 Rui Wang and Francis C. M. Lau Optimal gossiping in square $2$D meshes 263--286
Xueliang Li and Xiaoyan Zhang On the minimum monochromatic or multicolored subgraph partition problems 1--10 Y. André and A. C. Caron and D. Debarbieux and Y. Roos and S. Tison Path constraints in semistructured data 11--33 Shantanu Das and Paola Flocchini and Shay Kutten and Amiya Nayak and Nicola Santoro Map construction of unknown graphs by multiple agents . . . . . . . . . . . . 34--48 My T. Thai and Ning Zhang and Ravi Tiwari and Xiaochun Xu On approximation algorithms of $k$-connected $m$-dominating sets in disk graphs . . . . . . . . . . . . . . 49--59 Hajo Broersma and Xueliang Li On the complexity of dominating set problems related to the minimum all-ones problem . . . . . . . . . . . . . . . . 60--70 Weifan Wang and Yongzhu Chen A sufficient condition for a planar graph to be class 1 . . . . . . . . . . 71--77 Giulia Galbiati and Francesco Maffioli Approximation algorithms for maximum cut with limited unbalance . . . . . . . . . 78--87 Ming Yu Hsieh and Shi-Chun Tsai On the fairness and complexity of generalized $k$-in-a-row games . . . . . 88--100 Maleq Khan and Gopal Pandurangan and V. S. Anil Kumar A simple randomized scheme for constructing low-weight $k$-connected spanning subgraphs with applications to distributed algorithms . . . . . . . . . 101--114 V. Yu. Popov Multiple genome rearrangement by swaps and by element duplications . . . . . . 115--126 Joong Chae Na and Kunsoo Park Alphabet-independent linear-time construction of compressed suffix arrays using $ o(n \log n)$-bit working space 127--136 Arturo Carpi On Dejean's conjecture over large alphabets . . . . . . . . . . . . . . . 137--151 C. Epifanio and A. Gabriele and F. Mignosi and A. Restivo and M. Sciortino Languages with mismatches . . . . . . . 152--166 A. Pavan and Alan L. Selman and Samik Sengupta and N. V. Vinodchandran Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy . . . . . . . . . . . . . . . 167--178 F. Blanchet-Sadri and Nathan D. Wetzler Partial words and the critical factorization theorem revisited . . . . 179--192 Verónica Becher and Serge Grigorieff Random reals \`a la Chaitin with or without prefix-freeness . . . . . . . . 193--201 André Berger and Takuro Fukunaga and Hiroshi Nagamochi and Ojas Parekh Approximability of the capacitated $b$-edge dominating set problem . . . . 202--213 Nicolas Bedaride Classification of rotations on the torus $ \mathcal {T}^2 $ . . . . . . . . . . . 214--225 Dieter Kratsch and Mathieu Liedloff An exact algorithm for the minimum dominating clique problem . . . . . . . 226--240 Guillaume Blin and Guillaume Fertin and Stéphane Vialette Extracting constrained 2-interval subsets in 2-interval sets . . . . . . . 241--263 Francesco M. Malvestuto and Mauro Mezzini and Marina Moscarini An analytical approach to the inference of summary data of additive type . . . . 264--285 Jywe-Fei Fang The bipanconnectivity and $m$-panconnectivity of the folded hypercube . . . . . . . . . . . . . . . 286--300 Anonymous Editorial Board . . . . . . . . . . . . v--ix
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1--2 Chris Barrett and Harry B. Hunt III and Madhav V. Marathe and S. S. Ravi and Daniel J. Rosenkrantz and Richard E. Stearns and Mayur Thakur Predecessor existence problems for finite discrete dynamical systems . . . 3--37 Daowen Qiu Automata theory based on quantum logic: Reversibilities and pushdown automata 38--56 Andrew Carnell and Daniel Richardson Parallel computation in spiking neural nets . . . . . . . . . . . . . . . . . . 57--72 Thomas Jansen and Ingo Wegener A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-boolean functions of unitation 73--93 W. Benfold and J. Hallam and A. Prügel-Bennett Optimal parameters for search using a barrier tree Markov model . . . . . . . 94--113 Tobias Storch Finding large cliques in sparse semi-random graphs by simple randomized search heuristics . . . . . . . . . . . 114--131 Remco Loos and Mitsunori Ogihara Complexity theory for splicing systems 132--150 Yuan Feng and Runyao Duan and Zhengfeng Ji and Mingsheng Ying Proof rules for the correctness of quantum programs . . . . . . . . . . . . 151--166 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Jos C. M. Baeten and Iain C. C. Phillips Preface . . . . . . . . . . . . . . . . 167--168 Sibylle Fröschle and S\lawomir Lasota Causality versus true-concurrency . . . 169--187 Luca de Alfaro and Thomas A. Henzinger and Orna Kupferman Concurrent reachability games . . . . . 188--217 D. Cacciagrano and F. Corradini and C. Palamidessi Separation of synchronous and asynchronous communication via testing 218--235 Sébastien Briais and Uwe Nestmann Open bisimulation, revisited . . . . . . 236--271
Hans Ulrich Simon and Etsuji Tomita Guest editors' foreword . . . . . . . . 1--3 Kazuho Watanabe and Sumio Watanabe Stochastic complexity for mixture of exponential families in generalized variational Bayes . . . . . . . . . . . 4--17 Nick Palmer and Paul W. Goldberg PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance . . . . . . 18--31 Rotem Bennet and Nader H. Bshouty Learning attribute-efficiently with corrupt oracles . . . . . . . . . . . . 32--50 Sanjay Jain and Steffen Lange and Sandra Zilles A general comparison of language learning from examples and from queries 51--66 Sanjay Jain and Efim Kinber Learning multiple languages in groups 67--76 Vladimir Vovk Non-asymptotic calibration and resolution . . . . . . . . . . . . . . . 77--89 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Hing Leung and Giovanni Pighizzini Preface . . . . . . . . . . . . . . . . 91--92 Marco Almeida and Nelma Moreira and Rogério Reis Enumeration and generation with a string automata representation . . . . . . . . 93--102 Franziska Biegler and Michael J. Burrell and Mark Daley Regulated RNA rewriting: Modelling RNA editing with guided insertion . . . . . 103--112 Franziska Biegler and Ian McQuillan and Kai Salomaa An infinite hierarchy induced by depth synchronization . . . . . . . . . . . . 113--124 Brendan Cordy and Kai Salomaa On the existence of regular approximations . . . . . . . . . . . . . 125--135 Jürgen Dassow and Bianca Truthe On the number of components for some parallel communicating grammar systems 136--146 Michael Domaratzki and Kai Salomaa Transition complexity of language operations . . . . . . . . . . . . . . . 147--154 Hermann Gruber and Markus Holzer On the average state and transition complexity of finite languages . . . . . 155--166 Hermann Gruber and Markus Holzer and Martin Kutrib The size of Higman--Haines sets . . . . 167--176 Carlo Mereghetti and Beatrice Palano Quantum automata for some multiperiodic languages . . . . . . . . . . . . . . . 177--186 Frank Nießner and Ulrich Ultes-Nitsche A complete characterization of deterministic regular liveness properties . . . . . . . . . . . . . . . 187--195
Paolo Ferragina and Giovanni Manzini and S. Muthukrishnan Foreword . . . . . . . . . . . . . . . . 197--199 Peter Fenwick Burrows--Wheeler compression: Principles and reflections . . . . . . . . . . . . 200--219 Haim Kaplan and Shir Landau and Elad Verbin A simpler analysis of Burrows--Wheeler-based compression . . . 220--235 R. Giancarlo and A. Restivo and M. Sciortino From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization . . . . . . . 236--248 Juha Kärkkäinen Fast BWT in small space by blockwise suffix sorting . . . . . . . . . . . . . 249--257 N. Jesper Larsson and Kunihiko Sadakane Faster suffix sorting . . . . . . . . . 258--272 Binh Dao Vo and Kiem-Phong Vo Compressing table data with column dependency . . . . . . . . . . . . . . . 273--283 Jérémy Barbay and Alexander Golynski and J. Ian Munro and S. Srinivasa Rao Adaptive searching in succinctly encoded binary relations and tree-structured documents . . . . . . . . . . . . . . . 284--297 S. Mantaci and A. Restivo and G. Rosone and M. Sciortino An extension of the Burrows--Wheeler Transform . . . . . . . . . . . . . . . 298--312 Ankur Gupta and Wing-Kai Hon and Rahul Shah and Jeffrey Scott Vitter Compressed data structures: Dictionaries and data-aware measures . . . . . . . . 313--331 Veli Mäkinen and Gonzalo Navarro Rank and select revisited and extended 332--347 Alexander Golynski Optimal lower bounds for rank and select indexes . . . . . . . . . . . . . . . . 348--359
Hongliang Lai and Dexue Zhang Complete and directed complete $ \Omega $-categories . . . . . . . . . . . . . . 1--25 Dominique Geniet and Gaëlle Largeteau WCET free time analysis of hard real-time systems on multiprocessors: a regular language-based model . . . . . . 26--52 Fausto Spoto Optimality and condensing of information flow through linear refinement . . . . . 53--82 Corina C\u\irstea and Dirk Pattinson Modular construction of complete coalgebraic logics . . . . . . . . . . . 83--108 Michael Johnson and Robert Rosebrugh Fibrations and universal view updatability . . . . . . . . . . . . . . 109--129 Ji\vrí Adámek and Stefan Milius and Ji\vrí Velebil Algebras with parametrized iterativity 130--151 L. Birkedal and R. E. Mògelberg and R. L. Petersen Domain-theoretical models of parametric polymorphism . . . . . . . . . . . . . . 152--172 Andrew R. Plummer S4 enriched multimodal categorial grammars are context-free . . . . . . . 173--180 Krishnendu Chatterjee Concurrent games with tail objectives 181--198 Jan Komenda and Jan H. van Schuppen Control of discrete-event systems with modular or distributed structure . . . . 199--226 Byron Cook and Daniel Kroening and Natasha Sharygina Verification of Boolean programs with unbounded thread creation . . . . . . . 227--242 Mark Schaefer and Walter Vogler Component refinement and CSC-solving for STG decomposition . . . . . . . . . . . 243--266 Maria Grazia Vigliotti and Iain Phillips and Catuscia Palamidessi Tutorial on separation results in process calculi via leader election problems . . . . . . . . . . . . . . . . 267--289 Janis Voigtländer and Patricia Johann Selective strictness and parametricity in structural operational semantics, inequationally . . . . . . . . . . . . . 290--318 Alban Ponse and Mark B. van der Zwaag Belnap's logic and conditional composition . . . . . . . . . . . . . . 319--336 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Ramtin Khosravi and Mohammad Ghodsi Query-point visibility constrained shortest paths in simple polygons . . . 1--11 Julien Bernat and Zuzana Masáková and Edita Pelantová On a class of infinite words with affine factor complexity . . . . . . . . . . . 12--25 James Aspnes and Joan Feigenbaum and Aleksandr Yampolskiy and Sheng Zhong Towards a theory of data entanglement 26--43 Ilan Gronau and Shlomo Moran On the hardness of inferring phylogenies from triplet-dissimilarities . . . . . . 44--55 Tomasz Jurdzi\'nski On complexity of grammars related to the safety problem . . . . . . . . . . . . . 56--72 Alexander Meduna and Ji\vrí Techet Canonical scattered context generators of sentences with their parses . . . . . 73--81 Minh Ha Le and Thi Ha Duong Phan Strict partitions and discrete dynamical systems . . . . . . . . . . . . . . . . 82--90 Caterina De Simone and Anna Galluccio Edge-colouring of regular graphs of large degree . . . . . . . . . . . . . . 91--99 Javier Herranz Identity-based ring signatures from RSA 100--117 Bo Tan Mirror substitutions and palindromic sequences . . . . . . . . . . . . . . . 118--124 Dimitrios Michail Reducing rank-maximal to maximum weight matching . . . . . . . . . . . . . . . . 125--132 Fábio Viduani Martinez and José Coelho de Pina and José Soares Algorithms for terminal Steiner trees 133--142 Yinfeng Xu and Wenqiang Dai and Naoki Katoh and Makoto Ohsaki Triangulating a convex polygon with fewer number of non-standard bars . . . 143--151 Oddvar Kloster A solution to the Angel Problem . . . . 152--161 Ryan C. Harkins and John M. Hitchcock Upward separations and weaker hypotheses in resource-bounded measure . . . . . . 162--171 Pascal Koiran and Sylvain Perifel The complexity of two problems on arithmetic circuits . . . . . . . . . . 172--181 Hsiao-Fei Liu and Kun-Mao Chao A tight analysis of the Katriel--Bodlaender algorithm for online topological ordering . . . . . . . . . . 182--189 Sanjay Jain and Efim Kinber Learning languages from positive data and a limited number of short counterexamples . . . . . . . . . . . . 190--218 V. E. Alekseev and R. Boliac and D. V. Korobitsyn and V. V. Lozin NP-hard graph problems and boundary classes of graphs . . . . . . . . . . . 219--236 Vesa Halava and Tero Harju and Tomi Kärki Relational codes of words . . . . . . . 237--249 Rui Wang and Francis C. M. Lau and Yan Yan Liu On the hardness of minimizing space for all-shortest-path interval routing schemes . . . . . . . . . . . . . . . . 250--264 Florin Manea and Robert Merca\cs Freeness of partial words . . . . . . . 265--277 Dirk Strothmann The affix array data structure and its applications to RNA secondary structure analysis . . . . . . . . . . . . . . . . 278--294 Andreas Brandstädt and Chính T. Ho\`ang On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem . . . . . . . . . . . . . . 295--306 Yo-Sub Han and Yajun Wang and Derick Wood Prefix-free regular languages and pattern matching . . . . . . . . . . . . 307--317 Yossi Moshe On the subword complexity of Thue--Morse polynomial extractions . . . . . . . . . 318--329 Van Bang Le and Bert Randerath and Ingo Schiermeyer On the complexity of 4-coloring graphs without long induced paths . . . . . . . 330--335 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Donald Sannella and Vladimiro Sassone Semantic and logical foundations of global computing: Papers from the EU-FET global computing initiative (2001--2005) 337--340 Alexander Ahern and Nobuko Yoshida Formalising Java RMI with explicit code mobility . . . . . . . . . . . . . . . . 341--410 David Aspinall and Lennart Beringer and Martin Hofmann and Hans-Wolfgang Loidl and Alberto Momigliano A program logic for resources . . . . . 411--445 P. Baldan and A. Bracciali and R. Bruni A semantic framework for open processes 446--483 Sébastien Briais and Uwe Nestmann A formal semantics for protocol narrations . . . . . . . . . . . . . . . 484--511 Konstantinos Chatzikokolakis and Catuscia Palamidessi A framework for analyzing probabilistic protocols and its application to the Partial Secrets Exchange . . . . . . . . 512--527 Karl Krukow and Andrew Twigg The complexity of fixed point models of trust in distributed networks . . . . . 528--549
Eugene Asarinp and Gordon Pace and Gerardo Schneider and Sergio Yovine Algorithmic analysis of polygonal hybrid systems, Part II: Phase portrait and tools . . . . . . . . . . . . . . . . . 1--26 Ralf Klasing and Euripides Markou and Andrzej Pelc Gathering asynchronous oblivious mobile robots in a ring . . . . . . . . . . . . 27--39 Alberto Apostolico and Laxmi Parida and Simona E. Rombo Motif patterns in $2$D . . . . . . . . . 40--55 Victor Chepoi and Karim Nouioua and Yann Vax\`es A rounding algorithm for approximating minimum Manhattan networks . . . . . . . 56--69 Jung-Heum Park Panconnectivity and edge-pancyclicity of faulty recursive circulant G . . . . . . 70--80 Ehab Morsy and Hiroshi Nagamochi An improved approximation algorithm for capacitated multicast routings in networks . . . . . . . . . . . . . . . . 81--91 Liesbeth De Mol Tag systems and Collatz-like functions 92--101 Adrian Atanasiu and Radu Atanasiu and Ion Petre Parikh matrices and amiable words . . . 102--109 Yongqiang Shi and Deshi Ye Online bin packing with arbitrary release times . . . . . . . . . . . . . 110--119 Yongxi Cheng and Ker-I Ko and Weili Wu On the complexity of non-unique probe selection . . . . . . . . . . . . . . . 120--125 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Vladimiro Sassone Foundations of Software Science and Computational Structures: Selected papers from FOSSACS 2005 . . . . . . . . 127--128 Samy Abbes and Albert Benveniste True-concurrency probabilistic models: Markov nets and a law of large numbers 129--170 Alan Jeffrey and Julian Rathke Full abstraction for polymorphic $ \pi $-calculus . . . . . . . . . . . . . . . 171--196 Kim Guldstrand Larsen and Jacob Illum Rasmussen Optimal reachability for multi-priced timed automata . . . . . . . . . . . . . 197--213 Andrzej S. Murawski and Igor Walukiewicz Third-order Idealized Algol with iteration is decidable . . . . . . . . . 214--229 Lutz Schröder Expressivity of coalgebraic modal logic: The limits and beyond . . . . . . . . . 230--247 Ian Stark Free-algebra models for the $ \pi $-calculus . . . . . . . . . . . . . . . 248--270
Valérie Berthé and Pierre Lecomte and Michel Rigo Preface to the special issue dedicated to combinatorics, automata and number theory . . . . . . . . . . . . . . . . . 1--2 Paul Bell and Igor Potapov On undecidability bounds for matrix decision problems . . . . . . . . . . . 3--13 Elena Czeizler Multiple constraints on three and four words . . . . . . . . . . . . . . . . . 14--19 F. Durand Cobham--Semenov theorem and $ \mathbb {N}^d $-subshifts . . . . . . . . . . . 20--38 D. Frettlöh Self-dual tilings with respect to star-duality . . . . . . . . . . . . . . 39--50 Amy Glen A characterization of fine words over a finite alphabet . . . . . . . . . . . . 51--60 Juha Honkala Cancellation and periodicity properties of iterated morphisms . . . . . . . . . 61--64 Christoph Koutschan Regular languages and their generating functions: The inverse problem . . . . . 65--74 S. Brlek and G. Labelle and A. Lacasse Shuffle operations on discrete paths . . 75--89 Jean Néraud Completing circular codes in regular submonoids . . . . . . . . . . . . . . . 90--98 I. V. Petrov An algorithm for recognition of $n$-collapsing words . . . . . . . . . . 99--108 Guy Louchard and Helmut Prodinger Generalized approximate counting revisited . . . . . . . . . . . . . . . 109--125 Jui-Yi Kao and Narad Rampersad and Jeffrey Shallit and Manuel Silva Words avoiding repetitions in arithmetic progressions . . . . . . . . . . . . . . 126--137 B. Schratzberger A conversion algorithm based on the technique of singularization . . . . . . 138--149 Robert Brignall and Nik Ru\vskuc and Vincent Vatter Simple permutations: Decidability and unavoidable substructures . . . . . . . 150--163 Julien Bernat Symmetrized $ \beta $-integers . . . . . 164--177 S. A. Puzynina and S. V. Avgustinovich On periodicity of two-dimensional words 178--187 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Corrado Priami Preface . . . . . . . . . . . . . . . . 189--189 Luca Cardelli On process rate semantics . . . . . . . 190--215 Matteo Cavaliere and Radu Mardare and Sean Sedwards A multiset-based model of synchronizing agents: Computability and robustness . . 216--238 John Heath and Marta Kwiatkowska and Gethin Norman and David Parker and Oksana Tymchyshyn Probabilistic model checking of complex biological pathways . . . . . . . . . . 239--257 Heike Siebert and Alexander Bockmayr Temporal constraints in the logical analysis of regulatory networks . . . . 258--275 Hila Amir-Kroll and Avital Sadot and Irun R. Cohen and David Harel GemCell: a generic platform for modeling multi-cellular biological systems . . . 276--290 Anonymous Preface . . . . . . . . . . . . . . . . i--v
Laurent Busé and Mohamed Elkadi and Bernard Mourrain Editorial . . . . . . . . . . . . . . . 1--2 André Galligo Preface . . . . . . . . . . . . . . . . 3--4 S. Biasotti and D. Giorgi and M. Spagnuolo and B. Falcidieno Reeb graphs for shape analysis and applications . . . . . . . . . . . . . . 5--22 David A. Cox The moving curve ideal and the Rees algebra . . . . . . . . . . . . . . . . 23--36 Xavier Dahan and Xin Jin and Marc Moreno Maza and Éric Schost Change of order for regular chains in positive dimension . . . . . . . . . . . 37--65 James Damon Swept regions and surfaces: Modeling and volumetric properties . . . . . . . . . 66--91 D. Haviv and Y. Yomdin Uniform approximation of near-singular surfaces . . . . . . . . . . . . . . . . 92--100 Vladimir Petrov Kostov On multiplier sequences . . . . . . . . 101--112 Henri Lombardi and Claude Quitté Seminormal rings (following Thierry Coquand) . . . . . . . . . . . . . . . . 113--127 Carlos Simpson Algebraic cycles from a computational point of view . . . . . . . . . . . . . 128--140 Zbyn\vek \vSír and Jens Gravesen and Bert Jüttler Curves and surfaces represented by polynomial support functions . . . . . . 141--157 Elias P. Tsigaridas and Ioannis Z. Emiris On the complexity of real root isolation using continued fractions . . . . . . . 158--173 Ihsen Yengui Making the use of maximal ideals constructive . . . . . . . . . . . . . . 174--178 Anonymous Editorial . . . . . . . . . . . . . . . v--ix
Tian-Ming Bu and Qi Qi and Aries Wei Sun Unconditional competitive auctions with copy and budget constraints . . . . . . 1--13 Wolfgang Bein and José R. Correa and Xin Han A fast asymptotic approximation scheme for bin packing with rejection . . . . . 14--22 Michelangelo Bucci and Aldo de Luca and Alessandro De Luca and Luca Q. Zamboni On different generalizations of episturmian words . . . . . . . . . . . 23--36 Alessandro Ferrante and Mimmo Parente Mixed Nash equilibria in selfish routing problems with dynamic constraints . . . 37--53 Piotr Berman and Bhaskar DasGupta Approximating the online set multicover problems via randomized winnowing . . . 54--71 Binh-Minh Bui-Xuan and Michel Habib and Christophe Paul Competitive graph searches . . . . . . . 72--80 Hao Li and Huifang Miao and Li Liu and Lian Li and Heping Zhang Energy conservation in wireless sensor networks and connectivity of graphs . . 81--89 Tomoko Suzuki and Taisuke Izumi and Fukuhito Ooshita and Hirotsugu Kakugawa and Toshimitsu Masuzawa Move-optimal gossiping among mobile agents . . . . . . . . . . . . . . . . . 90--101 Lingfa Lu and Jinjiang Yuan and Liqi Zhang Single machine scheduling with release dates and job delivery to minimize the makespan . . . . . . . . . . . . . . . . 102--108 Peter Buchholz Bisimulation relations for weighted automata . . . . . . . . . . . . . . . . 109--123 Z. Nedev and S. Muthukrishnan The Magnus--Derek game . . . . . . . . . 124--132 Hiroshi Nagamochi and Takaharu Ohnishi Approximating a vehicle scheduling problem with time windows and handling times . . . . . . . . . . . . . . . . . 133--146 Symeon Bozapalidis and Antonios Kalampakas Graph automata . . . . . . . . . . . . . 147--165 S. Brlek and D. Jamet and G. Paquin Smooth words on 2-letter alphabets having same parity . . . . . . . . . . . 166--181 Hajo Broersma and Matthew Johnson and Daniël Paulusma and Iain A. Stewart The computational complexity of the parallel knock-out problem . . . . . . . 182--195 Jean Berstel and Christophe Reutenauer Another proof of Soittola's theorem . . 196--203 Wen-Hung Kuo and Dar-Li Yang Parallel-machine scheduling with time dependent processing times . . . . . . . 204--210 Enrico Angelelli and Maria Grazia Speranza and Zsolt Tuza Semi-online scheduling on two uniform processors . . . . . . . . . . . . . . . 211--219 Alessandro Ferrante and Gopal Pandurangan and Kihong Park On the hardness of optimization in power-law graphs . . . . . . . . . . . . 220--230 Jussi Kujala and Tapio Elomaa The cost of offline binary search tree algorithms and the complexity of the request sequence . . . . . . . . . . . . 231--239 E. C. Xavier and F. K. Miyazawa The class constrained bin packing problem with applications to video-on-demand . . . . . . . . . . . . 240--259 Hervé Daudé and Marc Mézard and Thierry Mora and Riccardo Zecchina Pairs of SAT-assignments in random Boolean formulæ . . . . . . . . . . . . . 260--279 Y. B. Huang About the number of $ C^\infty $-words of form $ \tilde {w} \times w $ . . . . 280--286 Ji Tian and Ruyan Fu and Jinjiang Yuan A best on-line algorithm for single machine scheduling with small delivery times . . . . . . . . . . . . . . . . . 287--293 Michael Segal and Eli Zeitlin Computing closest and farthest points for a query segment . . . . . . . . . . 294--300 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Bruno Courcelle and Christian Delhommé The modular decomposition of countable graphs. Definition and construction in monadic second-order logic . . . . . . . 1--38 Yu Zhang Cryptographic logical relations . . . . 39--63 J. Laird Decidability and syntactic control of interference . . . . . . . . . . . . . . 64--83 Toon Calders Itemset frequency satisfiability: Complexity and axiomatization . . . . . 84--111 Flavio D. Garcia and Peter van Rossum Sound and complete computational interpretation of symbolic hashes in the standard model . . . . . . . . . . . . . 112--133 Mojmír K\vretínský and Vojt\vech \vRehák and Jan Strej\vcek Petri nets are less expressive than state-extended PA . . . . . . . . . . . 134--140 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Arnold Beckmann and Edwin Beggs and Benedikt Löwe From Gödel to Einstein: Computability between logic and physics at CiE 2006 141--143 Arnon Avron Constructibility and decidability versus domain independence and absoluteness . . 144--158 Paul Cockshott and Lewis Mackenzie and Greg Michaelson Physical constraints on hypercomputation 159--174 Willem L. Fouché Dynamics of a generic Brownian motion: Recursive aspects . . . . . . . . . . . 175--186 Viv Kendon and Olivier Maloyer Optimal computation with non-unitary quantum walks . . . . . . . . . . . . . 187--196 Peter Koepke and Ryan Siders Minimality considerations for ordinal computers modeling constructibility . . 197--207 Benedek Nagy and Sándor Vályi Interval-valued computations and their connection with PSPACE . . . . . . . . . 208--222 Philip D. Welch Bounding lemmata for non-deterministic halting times of transfinite Turing machines . . . . . . . . . . . . . . . . 223--228
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1--2 Yuriy Brun Nondeterministic polynomial time factoring in the tile assembly model . . 3--23 Miika Langille and Ion Petre Sequential vs. parallel complexity in simple gene assembly . . . . . . . . . . 24--30 Yuriy Brun Solving NP-complete problems in the tile assembly model . . . . . . . . . . . . . 31--46 Shile Gao and Kequan Ding A graphical criterion of planarity for RNA secondary structures with pseudoknots in Rivas--Eddy class . . . . 47--56 Ioannis D. Zaharakis and Achilles D. Kameas Modeling spiking neural networks . . . . 57--76 Roberto Barbuti and Andrea Maggiolo-Schettini and Paolo Milazzo and Simone Tini Compositional semantics and behavioral equivalences for $P$ Systems . . . . . . 77--100 Kenichi Morita Reversible computing and cellular automata --- a survey . . . . . . . . . 101--131 Chris Barrett and Harry B. Hunt III and Madhav V. Marathe and S. S. Ravi and Daniel J. Rosenkrantz and Richard E. Stearns and Mayur Thakur Errata for the paper ``Predecessor existence problems for finite discrete dynamical systems'' [Theoret. Comput. Sci. 386 (1--2) (2007) 3--37] . . . . . 132--133 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Raffaele Giancarlo and Stefano Lonardi Foreword: Special issue in honor of the 60th Birthday of Professor Alberto Apostolico: Work is for people who do not know how to: SAIL --- String Algorithms, Information and Learning . . 135--136 Cinzia Pizzi and Esko Ukkonen Fast profile matching algorithms --- a survey . . . . . . . . . . . . . . . . . 137--157 Matteo Comin and Laxmi Parida Detection of subtle variations as consensus motifs . . . . . . . . . . . . 158--170 Claire Lemaitre and Marie-France Sagot A small trip in the untranquil world of genomes: a survey on the detection and analysis of genome rearrangement breakpoints . . . . . . . . . . . . . . 171--192 Max A. Alekseyev and Pavel A. Pevzner Multi-break rearrangements and chromosomal evolution . . . . . . . . . 193--202 Philippe Jacquet and Gadiel Seroussi and Wojciech Szpankowski On the entropy of a hidden Markov process . . . . . . . . . . . . . . . . 203--219 Klaus-Bernd Schürmann and Jens Stoye Counting suffix arrays and strings . . . 220--234 Mark-Jan Nederhof and Giorgio Satta Computation of distances for regular and context-free probabilistic languages . . 235--254 Costas S. Iliopoulos and M. Sohel Rahman Algorithms for computing variants of the longest common subsequence problem . . . 255--267 Jin Wook Kim and Amihood Amir and Gad M. Landau and Kunsoo Park Computing similarity of run-length encoded strings with affine gap penalty 268--282 Maxime Crochemore and Danny Hermelin and Gad M. Landau and Dror Rawitz and Stéphane Vialette Approximating the 2-interval pattern problem . . . . . . . . . . . . . . . . 283--297 Amihood Amir and Eran Chencinski and Costas Iliopoulos and Tsvi Kopelowitz and Hui Zhang Property matching and weighted matching 298--310
WenBin Chen and Jiangtao Meng and Dengpan Yin An improved lower bound for approximating minimum GCD multiplier in $ \ell_\infty $ norm (GCDM$_\infty $) 1--9 L. Salinas and E. Goles Covering by squares . . . . . . . . . . 10--27 Longcheng Liu and Enyu Yao Inverse min--max spanning tree problem under the Weighted sum-type Hamming distance . . . . . . . . . . . . . . . . 28--34 W. M. B. Dukes and M. F. Flanagan and T. Mansour and V. Vajnovszki Combinatorial Gray codes for classes of pattern avoiding permutations . . . . . 35--49 Min-Zheng Shieh and Shi-Chun Tsai Jug measuring: Algorithms and complexity 50--62 Bruno Escoffier and Jérôme Monnot A better differential approximation ratio for symmetric TSP . . . . . . . . 63--70 Miguel Couceiro and Maurice Pouzet On a quasi-ordering on Boolean functions 71--87 Trevor Fenner and Mark Levene and George Loizou Modelling the navigation potential of a web page . . . . . . . . . . . . . . . . 88--96 Xavier Défago and Samia Souissi Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity . . . . . 97--112 Paul E. Dunne and Yann Chevaleyre The complexity of deciding reachability properties of distributed negotiation schemes . . . . . . . . . . . . . . . . 113--144 Raphael Yuster All-pairs disjoint paths from a common ancestor in $ \tilde {O}(n^\omega) $ time . . . . . . . . . . . . . . . . . . 145--150 Xueliang Li and Wenli Zhou The 2nd-order conditional 3-coloring of claw-free graphs . . . . . . . . . . . . 151--157 Sandy Irani and Vitus Leung Probabilistic analysis for scheduling with conflicts . . . . . . . . . . . . . 158--179 Chen Wang and Myung-Ah Park and James Willson and Yongxi Cheng and Andras Farago and Weili Wu On approximate optimal dual power assignment for biconnectivity and edge-biconnectivity . . . . . . . . . . 180--190 Ying-You Chen and Dyi-Rong Duh and Tai-Ling Ye and Jung-Sheng Fu Weak-vertex-pancyclicity of $ (n, k)$-star graphs . . . . . . . . . . . . 191--199 Regant Y. S. Hung and H. F. Ting Competitive analysis of most-request-first for scheduling broadcasts with start-up delay . . . . . 200--211 David B. Chandler and Maw-Shang Chang and Ton Kloks and Jiping Liu and Sheng-Lung Peng Partitioned probe comparability graphs 212--222 Joan Boyar and René Peralta Tight bounds for the multiplicative complexity of symmetric functions . . . 223--246 E. Goles and L. Salinas Comparison between parallel and serial dynamics of Boolean networks . . . . . . 247--253 James D. Currie Palindrome positions in ternary square-free words . . . . . . . . . . . 254--257 Guizhen Liu and Ping Li Paths in circuit graphs of matroids . . 258--263 Lila Kari and Petr Sosík On the weight of universal insertion grammars . . . . . . . . . . . . . . . . 264--270 Samuel R. Buss and Jan Hoffmann The NP-hardness of finding a directed acyclic graph for regular resolution . . 271--276 Gregory Neven A simple transitive signature scheme for directed trees . . . . . . . . . . . . . 277--282 Lingfa Lu and Liqi Zhang and Jinjiang Yuan The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan . . . . . 283--289 Young-Soo Myung On the clique partitioning problem in weighted interval graphs . . . . . . . . 290--293 Oleg Verbitsky On the obfuscation complexity of planar graphs . . . . . . . . . . . . . . . . . 294--300 Anonymous Editorial Board . . . . . . . . . . . . v--ix
John Case and Takeshi Shinohara and Thomas Zeugmann and Sandra Zilles Foreword . . . . . . . . . . . . . . . . 1--3 Thomas Zeugmann and Sandra Zilles Learning recursive functions: a survey 4--56 Gunter Grieser Reflective inductive inference of recursive functions . . . . . . . . . . 57--69 R. Freivalds and R. F. Bonner Quantum inductive inference by finite automata . . . . . . . . . . . . . . . . 70--76 Jan Poland Nonstochastic bandits: Countable decision set, unbounded costs and reactive environments . . . . . . . . . 77--93 Frank J. Balbach Measuring teachability using variants of the teaching dimension . . . . . . . . . 94--113 Sanjay Jain and Eric Martin and Frank Stephan Absolute versus probabilistic classification in a logical setting . . 114--128 M. R. K. Krishna Rao Some classes of term rewriting systems inferable from positive data . . . . . . 129--149 Yen Kaow Ng and Takeshi Shinohara Developments from enquiries into the learnability of the pattern languages from positive data . . . . . . . . . . . 150--165 Daniel Reidenbach Discontinuities in pattern inference . . 166--193 Steffen Lange and Thomas Zeugmann and Sandra Zilles Learning indexed families of recursive languages from positive data: a survey 194--232 Sanjay Jain and Efim Kinber Learning and extending sublanguages . . 233--246 Anonymous Foreword . . . . . . . . . . . . . . . . v--ix
Stefano Berardi and Ugo de'Liguoro Calculi, types and applications: Essays in honour of M. Coppo, M. Dezani-Ciancaglini and S. Ronchi Della Rocca . . . . . . . . . . . . . . . . . 1--11 Henk Barendregt Towards the range property for the lambda theory $ \mathcal {H} $ . . . . . 12--15 Jan Willem Klop and Vincent van Oostrom and Roel de Vrijer Lambda calculus with patterns . . . . . 16--31 Ugo Dal Lago and Simone Martini The weak lambda calculus as a reasonable machine . . . . . . . . . . . . . . . . 32--50 Luca Paolini Parametric $ \lambda $-theories . . . . 51--62 Gérard Boudol On strong normalization and type inference in the intersection type discipline . . . . . . . . . . . . . . . 63--81 Steffen van Bakel The heart of intersection type assignment: Normalisation proofs revisited . . . . . . . . . . . . . . . 82--94 Viviana Bono and Betti Venneri and Lorenzo Bettini A typed lambda calculus with intersection types . . . . . . . . . . . 95--113 Daniel J. Dougherty and Silvia Ghilezan and Pierre Lescanne Characterizing strong normalization in the Curien--Herbelin symmetric lambda calculus: Extending the Coppo--Dezani heritage . . . . . . . . . . . . . . . . 114--128 Fabio Alessi An irregular filter model . . . . . . . 129--149 Pietro Di Gianantonio and Furio Honsell and Marina Lenisa A type assignment system for game semantics . . . . . . . . . . . . . . . 150--169 Mathieu Hoyrup and Arda Kolçak and Giuseppe Longo Computability and the morphological complexity of some dynamics on continuous domains . . . . . . . . . . . 170--182 Ines Margaria and Maddalena Zacchi Access control in mobile ambient calculi: a comparative view . . . . . . 183--202 Adriana Compagnoni and Elsa L. Gunter and Philippe Bidinger Role-based access control for boxed ambients . . . . . . . . . . . . . . . . 203--216 Giuseppe Castagna and Rocco De Nicola and Daniele Varacca Semantic subtyping for the pi-calculus 217--242 Luigi Liquori and Arnaud Spiwack Extending FeatherTrait Java with Interfaces . . . . . . . . . . . . . . . 243--260 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Paola Flocchini and Leszek A. G\kasieniec Preface . . . . . . . . . . . . . . . . 1--2 Amotz Bar-Noy and Richard E. Ladner and Tami Tamir Optimal delay for media-on-demand with pre-loading and pre-buffering . . . . . 3--11 Lélia Blin and Pierre Fraigniaud and Nicolas Nisse and Sandrine Vial Distributed chasing of network intruders 12--37 Tiziana Calamoneri and Andrea E. F. Clementi and Miriam Di Ianni and Massimo Lauria and Angelo Monti and Riccardo Silvestri Minimum-Energy Broadcast and disk cover in grid wireless networks . . . . . . . 38--53 Jérémie Chalopin Election and rendezvous with incomparable labels . . . . . . . . . . 54--70 Reuven Cohen and David Peleg Local spreading algorithms for autonomous robot systems . . . . . . . . 71--82 Bilel Derbel and Cyril Gavoille Fast deterministic distributed algorithms for sparse spanners . . . . . 83--100 Stefan Dobrev and Rastislav Královi\vc and Richard Královi\vc and Nicola Santoro On fractional dynamic faults with thresholds . . . . . . . . . . . . . . . 101--117 Wayne Goddard and Stephen T. Hedetniemi and David P. Jacobs and Vilmar Trevisan Distance-$k$ knowledge in self-stabilizing algorithms . . . . . . 118--127 Adrian Kosowski The maximum edge-disjoint paths problem in complete graphs . . . . . . . . . . . 128--140 Dariusz R. Kowalski and Adam Malinowski How to meet in anonymous network . . . . 141--156 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Fedor V. Fomin and Pierre Fraigniaud and Dimitrios M. Thilikos Forewords: Special issue on graph searching . . . . . . . . . . . . . . . 157--157 Brian Alspach and Danny Dyer and Denis Hanson and Boting Yang Time constrained graph searching . . . . 158--168 Frédéric Mazoit and Nicolas Nisse Monotonicity of non-deterministic graph searching . . . . . . . . . . . . . . . 169--178 Volkan Isler and Nikhil Karnad The role of information in the cop-robber game . . . . . . . . . . . . 179--190 M. E. Messinger and R. J. Nowakowski and P. Pra\lat Cleaning a network with brushes . . . . 191--205 Paul Hunter and Stephan Kreutzer Digraph measures: Kelly decompositions, games, and orderings . . . . . . . . . . 206--219 Adrian Dumitrescu and Ichiro Suzuki and Pawe\l \.Zyli\'nski Offline variants of the ``lion and man'' problem: ---Some problems and techniques for measuring crowdedness and for safe path planning--- . . . . . . . . . . . . 220--235 Fedor V. Fomin and Dimitrios M. Thilikos An annotated bibliography on guaranteed graph searching . . . . . . . . . . . . 236--245
Mathieu Sablik Directional dynamics for cellular automata: a sensitivity to initial condition approach . . . . . . . . . . . 1--18 Achim Blumensath On the structure of graphs in the Caucal hierarchy . . . . . . . . . . . . . . . 19--45 Philippe Moser Martingale families and dimension in P 46--61 Yossi Moshe On some questions regarding $k$-regular and $k$-context-free sequences . . . . . 62--69 Claribet Piña and Carlos Uzcátegui Reconstruction of a word from a multiset of its factors . . . . . . . . . . . . . 70--83 Christine Cheng and Eric McDermid and Ichiro Suzuki A unified approach to finding good stable matchings in the hospitals/residents setting . . . . . . 84--99 Jurijs Kirillovs Polyomino coloring and complex numbers 100--112 P. Ambro\'z and Z. Masáková and E. Pelantová Matrices of $3$-iet preserving morphisms 113--136 Caixia Jing and Guochun Tang and Xingsan Qian Heuristic algorithms for two machine re-entrant flow shop . . . . . . . . . . 137--143 Jean Berstel and Christophe Reutenauer Extension of Brzozowski's derivation calculus of rational expressions to series over the free partially commutative monoids . . . . . . . . . . 144--158 Ojas Parekh Approximation algorithms for partially covering with edges . . . . . . . . . . 159--168 Dalia Krieger On stabilizers of infinite words . . . . 169--181 John Rhodes and Pedro V. Silva Turing machines and bimachines . . . . . 182--224 Tullio Ceccherini-Silberstein and Michel Coornaert A generalization of the Curtis--Hedlund theorem . . . . . . . . . . . . . . . . 225--229 Zhendong Shao and David Zhang Improved upper bounds on the $ L(2, 1) $-labeling of the skew and converse skew product graphs . . . . . . . . . . . . . 230--233 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Gregory Karagiorgos and Nikolaos M. Missirlis Convergence of the diffusion method for weighted torus graphs using Fourier analysis . . . . . . . . . . . . . . . . 1--16 Christian J. Michel and Giuseppe Pirillo and Mario A. Pirillo A relation between trinucleotide comma-free codes and trinucleotide circular codes . . . . . . . . . . . . . 17--26 Lane A. Hemaspaandra and Jörg Rothe and Amitabh Saxena Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions . . . . . . . . . . . . . . . 27--35 David A. Cohen and Martin C. Cooper and Peter G. Jeavons Generalising submodularity and horn clauses: Tractable optimization problems defined by tournament pair multimorphisms . . . . . . . . . . . . . 36--51 Zhi-Zhong Chen and Ze Feng and Minming Li and Frances Yao Optimizing deletion cost for secure multicast key management . . . . . . . . 52--61 Dániel Marx Complexity of unique list colorability 62--76 Hing-Fung Ting A near optimal scheduler for on-demand data broadcasts . . . . . . . . . . . . 77--84 Yumei Huo and Joseph Y.-T. Leung and Xin Wang Online scheduling of equal-processing-time task systems . . . 85--95 Janina Brenner and Guido Schäfer Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems . . . . . . . . . . 96--106 Rodolphe Giroudeau and Jean-Claude Konig and Farida Kamila Moulai and Jérôme Palaysi Complexity and approximation for precedence constrained scheduling problems with large communication delays 107--119 Eduardo Sany Laber A randomized competitive algorithm for evaluating priced AND/OR trees . . . . . 120--130 Victor Chepoi and Bertrand Estellon and Yann Vax\`es Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length . . . . . . . . . . . 131--143 Vincenzo Bonifaci and Ugo Di Iorio and Luigi Laura The complexity of uniform Nash equilibria and related regular subgraph problems . . . . . . . . . . . . . . . . 144--152 Iyad A. Kanj and Luay Nakhleh and Cuong Than and Ge Xia Seeing the trees and their branches in the network is hard . . . . . . . . . . 153--164 Simon J. Puglisi and Jamie Simpson and W. F. Smyth How many runs can a string contain? . . 165--171 Eitan Bachmat and Tao Kai Lam and Avner Magen Analysis of set-up time models: a metric perspective . . . . . . . . . . . . . . 172--180 Chang-Hsiung Tsai Embedding of meshes in Möbius cubes . . . 181--190 André Hernich and Nicole Schweikardt Reversal complexity revisited . . . . . 191--205 José Carlos Costa and Conceição Nogueira On bases of identities for the $ \omega $-variety generated by locally testable semigroups . . . . . . . . . . . . . . . 206--216 Manuel Kauers Solving difference equations whose coefficients are not transcendental . . 217--227 Ching-Lueh Chang and Yuh-Dauh Lyuu and Yen-Wu Ti The complexity of Tarski's fixed point theorem . . . . . . . . . . . . . . . . 228--235 David Ilcinkas Setting port numbers for fast graph exploration . . . . . . . . . . . . . . 236--242 Dietrich Kuske Schützenberger's theorem on formal power series follows from Kleene's theorem . . 243--248 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Sotiris Nikoletseas and Jose Rolim Preface . . . . . . . . . . . . . . . . 1--1 Alan A. Bertossi and Stephan Olariu and Cristina M. Pinotti Efficient corona training protocols for sensor networks . . . . . . . . . . . . 2--15 J. Cicho\'n and M. Kuty\lowski and M. Zawada Adaptive initialization algorithm for ad hoc radio networks with carrier sensing 16--28 Magnús M. Halldórsson and Takeshi Tokuyama Minimizing interference of a wireless ad-hoc network in a plane . . . . . . . 29--42 Davide Bil\`o and Guido Proietti On the complexity of minimizing interference in ad-hoc and sensor networks . . . . . . . . . . . . . . . . 43--55 Sotiris Nikoletseas and Paul Spirakis Efficient sensor network design for continuous monitoring of moving objects 56--66 Paola Flocchini and Giuseppe Prencipe and Nicola Santoro Self-deployment of mobile sensors on a ring . . . . . . . . . . . . . . . . . . 67--80 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Ugo Montanari and Donald Sannella Preface . . . . . . . . . . . . . . . . 81--81 Aslan Askarov and Daniel Hedin and Andrei Sabelfeld Cryptographically-masked flows . . . . . 82--101 Roberto Bruni and Ivan Lanese Parametric synchronizations in mobile nominal calculi . . . . . . . . . . . . 102--119 Luís Caires Spatial-behavioral types for concurrency and resource control in distributed systems . . . . . . . . . . . . . . . . 120--141 Ioannis Caragiannis and Christos Kaklamanis and Panagiotis Kanellopoulos and Evi Papaioannou Scheduling to maximize participation . . 142--155 Mariangiola Dezani-Ciancaglini and Silvia Ghilezan and Jovanka Pantovi\'c and Daniele Varacca Security types for dynamic web data . . 156--171 Reiner Hähnle and Jing Pan and Philipp Rümmer and Dennis Walter Integration of a security type system into a program logic . . . . . . . . . . 172--189 Nicolas Hanusse and Dimitris Kavvadias and Evangelos Kranakis and Danny Krizanc Memoryless search algorithms in a network with faulty advice . . . . . . . 190--198 Damien Pous Using bisimulation proof techniques for the analysis of distributed abstract machines . . . . . . . . . . . . . . . . 199--220 Francesco Silvestri On the limits of cache-oblivious rational permutations . . . . . . . . . 221--233 Ian Wehrman and David Kitchin and William R. Cook and Jayadev Misra A timed semantics of Orc . . . . . . . . 234--248
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1--2 Zhiguo Yang and Daoyi Xu Global dynamics for non-autonomous reaction-diffusion neural networks with time-varying delays . . . . . . . . . . 3--10 J. Timmis and A. Hone and T. Stibor and E. Clark Theoretical advances in artificial immune systems . . . . . . . . . . . . . 11--32 P. A. Borisovsky and A. V. Eremeev Comparing evolutionary algorithms to the $ (1 + 1)$-EA . . . . . . . . . . . . . 33--41 Lvzhou Li and Daowen Qiu Determining the equivalence for one-way quantum finite automata . . . . . . . . 42--51 François Fages and Sylvain Soliman Abstract interpretation and types for systems biology . . . . . . . . . . . . 52--70 Tommaso Toffoli and Silvio Capobianco and Patrizia Mentrasti When--and how--can a cellular automaton be rewritten as a lattice gas? . . . . . 71--88 M. V. Panduranga Rao Interference automata . . . . . . . . . 89--103 Carsten Witt Population size versus runtime of a simple evolutionary algorithm . . . . . 104--120 Willem Fouché and Johannes Heidema and Glyn Jones and Petrus H. Potgieter Universality and programmability of quantum computers . . . . . . . . . . . 121--129 Faisal Shah Khan and Marek Perkowski Erratum to: ``Synthesis of multi-qudit hybrid and $d$-valued quantum logic circuits by decomposition'' [Theoret. Comput. Sci. 367 (3) (2006) 336--346] 130--131 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Jean-François Dufourd Polyhedra genus theorem and Euler formula: a hypermap-formalized intuitionistic proof . . . . . . . . . . 133--159 Matthias Baaz and Stefan Hetzl and Alexander Leitsch and Clemens Richter and Hendrik Spohr CERES: an analysis of Fürstenberg's proof of the infinity of primes . . . . . . . 160--175 Florentin Ipate and Mike Holcombe Testing data processing-oriented systems from stream X-machine models . . . . . . 176--191 Sanjiang Li and Mingsheng Ying Soft constraint abstraction based on semiring homomorphism . . . . . . . . . 192--201 B. Bérard and F. Cassez and S. Haddad and D. Lime and O. H. Roux When are Timed Automata weakly timed bisimilar to Time Petri Nets? . . . . . 202--220 Torsten Stüber and Heiko Vogler Weighted monadic datalog . . . . . . . . 221--238 José Meseguer and Miguel Palomino and Narciso Martí-Oliet Equational abstractions . . . . . . . . 239--264 Dan Olteanu and Christoph Koch and Lyublena Antova World-set decompositions: Expressiveness and efficient algorithms . . . . . . . . 265--284 Christophe Calv\`es and Maribel Fernández A polynomial nominal unification algorithm . . . . . . . . . . . . . . . 285--306 Étienne Payet Loop detection in term rewriting using the eliminating unfoldings . . . . . . . 307--327 Agata Ciabattoni and George Metcalfe Density elimination . . . . . . . . . . 328--346 Thomas Ehrhard and Laurent Regnier Uniformity and the Taylor expansion of ordinary lambda-terms . . . . . . . . . 347--372 Alexander Rabinovich Arity hierarchy for temporal logics . . 373--381 Laura Bozzelli and Salvatore La Torre and Adriano Peron Verification of well-formed communicating recursive state machines 382--405 Andrew R. Plummer S4 enriched multimodal categorial grammars are context-free: Corrigendum 406--408 Stefan Milius and Lawrence S. Moss Corrigendum to: ``The category theoretic solution of recursive program schemes'' [Theoret. Comput. Sci. 366 (2006) 3--59] 409--415
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1--2 Nadia Busi and Claudio Zandron Foreword . . . . . . . . . . . . . . . . 3--4 Luca Cardelli Bitonal membrane systems: Interactions of biological membranes . . . . . . . . 5--18 Gheorghe P\uaun Membrane computing and brane calculi. Old, new, and future bridges . . . . . . 19--25 Robert Brijder and Matteo Cavaliere and Agustín Riscos-Núñez and Grzegorz Rozenberg and Drago\cs Sburlan Membrane systems with proteins embedded in membranes . . . . . . . . . . . . . . 26--39 Matteo Cavaliere and Sean Sedwards Decision problems in membrane systems with peripheral proteins, transport and evolution . . . . . . . . . . . . . . . 40--51 Erzsébet Csuhaj-Varjú and György Vaszil (Mem)brane automata . . . . . . . . . . 52--60 Pierre-Louis Curien and Vincent Danos and Jean Krivine and Min Zhang Computational self-assembly . . . . . . 61--75 Daniel Díaz-Pernil and Miguel A. Gutiérrez-Naranjo and Mario J. Pérez-Jiménez and Agustín Riscos-Núñez A uniform family of tissue P systems with cell division solving 3-COL in a linear time . . . . . . . . . . . . . . 76--87 Giuditta Franco and Maurice Margenstern A DNA computing inspired computational model . . . . . . . . . . . . . . . . . 88--96 Nil Geisweiller and Jane Hillston and Marco Stenico Relating continuous and discrete PEPA models of signalling pathways . . . . . 97--111 Jetty Kleijn and Maciej Koutny Processes of membrane systems with promoters and inhibitors . . . . . . . . 112--126 Cosimo Laneve and Fabien Tarissan A simple calculus for proteins and cells 127--141 Vincenzo Manca The metabolic algorithm for P systems: Principles and applications . . . . . . 142--155 A. Romanel and C. Priami On the decidability and complexity of the structural congruence for beta-binders . . . . . . . . . . . . . . 156--169 Sergey Verlan and Francesco Bernardini and Marian Gheorghe and Maurice Margenstern Generalized communicating P systems . . 170--184 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Tiziana Margaria and Bernhard Steffen Preface . . . . . . . . . . . . . . . . 185--185 Altaf Hussain and Michael Huth On model checking multiple hybrid views 186--201 Shoham Ben-David and Dana Fisman and Sitvanit Ruah Embedding finite automata within regular expressions . . . . . . . . . . . . . . 202--218 Shady Copty and Shai Fine and Shmuel Ur and Elad Yom-Tov and Avi Ziv A probabilistic alternative to regression suites . . . . . . . . . . . 219--234 M. Calder and A. Miller An automatic abstraction technique for verifying featured, parameterised systems . . . . . . . . . . . . . . . . 235--255 Franjo Ivan\vci\'c and Zijiang Yang and Malay K. Ganai and Aarti Gupta and Pranav Ashar Efficient SAT-based bounded model checking for software verification . . . 256--274 Saddek Bensalem and Doron Peled and Hongyang Qu and Stavros Tripakis Automatic generation of path conditions for concurrent timed systems . . . . . . 275--292 Jens Schönherr and Martin Freibothe and Bernd Straube and Jörg Bormann Semi-formal verification of the steady state behavior of mixed-signal circuits by SAT-based property checking . . . . . 293--307
Ralph Kopperman and Prakash Panangaden and Michael B. Smyth and Dieter Spreen Foreword . . . . . . . . . . . . . . . . 1--2 Douglas Bridges and Hajime Ishihara and Peter M. Schuster and Lumini\cta V\^\i\ct\ua Apartness, compactness and nearness . . 3--10 Francesco Ciraulo and Giovanni Sambin Finitary formal topologies and Stone's representation theorem . . . . . . . . . 11--23 K. A. Hardie and P. J. Witbooi Finite relational structure models of topological spaces and maps . . . . . . 24--34 Fangping Huang and Jihua Liang On computational environments of topological spaces . . . . . . . . . . . 35--40 K. E. Jordan and Lance E. Miller and E. L. F. Moore and T. J. Peters and Alexander Russell Modeling time and topology for animation and visualization with examples on parametric geometry . . . . . . . . . . 41--49 Vladik Kreinovich and Olga Kosheleva Computational complexity of determining which statements about causality hold in different space--time models . . . . . . 50--63 Hans-Peter A. Künzi and Vladik Kreinovich Static space--times naturally lead to quasi-pseudometrics . . . . . . . . . . 64--72 Jimmie D. Lawson Metric spaces and $ F S $-domains . . . 73--74 Keye Martin Topology in information theory in topology . . . . . . . . . . . . . . . . 75--87 Timothy Porter Enriched categories and models for spaces of evolving states . . . . . . . 88--100 Peter Schuster The Zariski spectrum as a formal geometry . . . . . . . . . . . . . . . . 101--115 Victor L. Selivanov Fine hierarchies and $m$-reducibilities in theoretical computer science . . . . 116--163 Josef \vSlapal A quotient-universal digital topology 164--175 Dieter Spreen and Luoshan Xu and Xuxin Mao Information systems revisited --- the general continuous case . . . . . . . . 176--187 Sumati Surya Causal set topology . . . . . . . . . . 188--197 Hideki Tsuiki and Yasunao Hattori Lawson topology of the space of formal balls and the hyperbolic topology . . . 198--205 Anonymous Foreword . . . . . . . . . . . . . . . . v--ix
Philip M. Long and Frank Stephan Preface . . . . . . . . . . . . . . . . 207--208 Alp Atìcì and Rocco A. Servedio Learning unions of $ \omega (1)$-dimensional rectangles . . . . . . 209--222 Leonid (Aryeh) Kontorovich and Corinna Cortes and Mehryar Mohri Kernel methods for learning languages 223--236 Andreas Maurer Unsupervised slow subspace-learning from stationary processes . . . . . . . . . . 237--255 Jan Poland Consistency of discrete Bayesian learning . . . . . . . . . . . . . . . . 256--273 Daniil Ryabko and Marcus Hutter On the possibility of learning in reactive environments with arbitrary dependence . . . . . . . . . . . . . . . 274--284 Vladimir Vovk Leading strategies in competitive on-line prediction . . . . . . . . . . . 285--296
Kees Joost Batenburg and Antal Nagy and Maurice Nivat Preface . . . . . . . . . . . . . . . . 1--1 Kees Joost Batenburg and Antal Nagy and Maurice Nivat In Memoriam: Attila Kuba (1953--2006) 2--7 Eric Andres The supercover of an $m$-flat is a discrete analytical object . . . . . . . 8--14 Péter Balázs A framework for generating some discrete sets with disjoint components by using uniform distributions . . . . . . . . . 15--23 Valentin E. Brimkov and Reneta P. Barneva On the polyhedral complexity of the integer points in a hyperball . . . . . 24--30 S. Brlek and G. Labelle and A. Lacasse Discrete sets with minimal moment of inertia . . . . . . . . . . . . . . . . 31--42 S. Brocchi and A. Frosini and C. Picouleau Reconstruction of binary matrices under fixed size neighborhood constraints . . 43--54 Sara Brunetti and Alain Daurat Reconstruction of convex lattice sets from tomographic projections in quartic time . . . . . . . . . . . . . . . . . . 55--62 S. Brunetti and A. Del Lungo and P. Gritzmann and S. de Vries On the reconstruction of binary and permutation matrices under (binary) tomographic constraints . . . . . . . . 63--71 David Coeurjolly and Jérôme Hulin and Isabelle Sivignon Finding a minimum medial axis of a discrete shape is NP-hard . . . . . . . 72--79 Paolo Dulio Convex decomposition of $U$-polygons . . 80--89 Andrea Frosini and Maurice Nivat and Simone Rinaldi Scanning integer matrices by means of two rectangular windows . . . . . . . . 90--96 T. Yung Kong Minimal non-deletable sets and minimal non-codeletable sets in binary images 97--118 Kálmán Palágyi A $3$D fully parallel surface-thinning algorithm . . . . . . . . . . . . . . . 119--135 Miguel Santoyo and Ernesto Vallejo Additivity obstructions for integral matrices and pyramids . . . . . . . . . 136--145 Daniel Vainsencher and Alfred M. Bruckstein On isoperimetrically optimal polyforms 146--159 Rafal Zdunek On image reconstruction algorithms for binary electromagnetic geotomography . . 160--170 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Christos Kaklamanis Preface . . . . . . . . . . . . . . . . 171--172 Pasquale Ambrosio and Vincenzo Auletta Deterministic monotone algorithms for scheduling on related machines . . . . . 173--186 Thomas Lücking and Marios Mavronicolas and Burkhard Monien and Manuel Rode A new model for selfish routing . . . . 187--206 Miroslav Chlebík and Janka Chlebíková The Steiner tree problem on graphs: Inapproximability results . . . . . . . 207--214 S. Nikoletseas and C. Raptopoulos and P. Spirakis Large independent sets in general random intersection graphs . . . . . . . . . . 215--224 Ralf Klasing and Nelson Morales and Stéphane Pérennes On the complexity of bandwidth allocation in radio networks . . . . . . 225--239 Carme \`Alvarez and Josep Díaz and Jordi Petit and José Rolim and Maria Serna High level communication functionalities for wireless sensor networks . . . . . . 240--247 Colin Cooper and Ralf Klasing and Tomasz Radzik A randomized algorithm for the joining protocol in dynamic distributed networks 248--262
Stefan Eckhardt and Sven Kosub and Moritz G. Maaß and Hanjo Täubig and Sebastian Wernicke Combinatorial network abstraction by trees and distances . . . . . . . . . . 1--20 Junlei Zhu and Yuehua Bu Equitable list colorings of planar graphs without short cycles . . . . . . 21--28 Maurice Margenstern The domino problem of the hyperbolic plane is undecidable . . . . . . . . . . 29--84 Leah Epstein and Asaf Levin and Rob van Stee Online unit clustering: Variations on a theme . . . . . . . . . . . . . . . . . 85--96 Hervé Fournier and Guillaume Malod Universal relations and #P-completeness 97--109 Meijie Ma and Guizhen Liu and Jun-Ming Xu Fault-tolerant embedding of paths in crossed cubes . . . . . . . . . . . . . 110--116 Marion Le Gonidec On complexity functions of infinite words associated with generalized Dyck languages . . . . . . . . . . . . . . . 117--133 Charilaos Efthymiou and Paul G. Spirakis Random sampling of colourings of sparse random graphs with a constant number of colours . . . . . . . . . . . . . . . . 134--154 Alin Bostan and Claude-Pierre Jeannerod and Éric Schost Solving structured linear systems with large displacement rank . . . . . . . . 155--181 Tian-Ming Bu and Xiaotie Deng and Qi Qi Arbitrage opportunities across sponsored search markets . . . . . . . . . . . . . 182--191 Pedro García and Manuel Vázquez de Parga and Gloria I. Álvarez and José Ruiz Universal automata and NFA learning . . 192--202 Leah Epstein and Meital Levy Online interval coloring with packing constraints . . . . . . . . . . . . . . 203--212 Alfredo De Santis and Anna Lisa Ferrara and Barbara Masucci New constructions for provably-secure time-bound hierarchical key assignment schemes . . . . . . . . . . . . . . . . 213--230 Sven O. Krumke and Willem E. de Paepe and Jörg Rambau and Leen Stougie Bincoloring . . . . . . . . . . . . . . 231--241 Andrew Beveridge and Tom Bohman and Alan Frieze and Oleg Pikhurko Game chromatic index of graphs with given restrictions on degrees . . . . . 242--249 Arto Salomaa Subword histories and associated matrices . . . . . . . . . . . . . . . . 250--257 Jonathan K. Lee and Jens Palsberg and Fernando Magno Quintão Pereira Aliased register allocation for straight-line programs is NP-complete 258--273 M. Chiarandini and I. S. Kotsireas and C. Koukouvinos and L. Paquete Heuristic algorithms for Hadamard matrices with two circulant cores . . . 274--277 Ond\vrej Klíma and Libor Polák On varieties of meet automata . . . . . 278--289 Élise Prieur and Thierry Lecroq On-line construction of compact suffix vectors and maximal repeats . . . . . . 290--301 A. L. Buchsbaum and R. Giancarlo and B. Racz New results for finding common neighborhoods in massive graphs in the data stream model . . . . . . . . . . . 302--309 Jiang Chen and Ke Yi A dynamic data structure for top-$k$ queries on uncertain data . . . . . . . 310--317 Jung-Sheng Fu Fault-free Hamiltonian cycles in twisted cubes with conditional link faults . . . 318--329 Marcin Kozik A finite set of functions with an EXPTIME-complete composition problem . . 330--341 C. A. A. Sanches and N. Y. Soma and H. H. Yanasse Parallel time and space upper-bounds for the subset-sum problem . . . . . . . . . 342--348 Hsiao-Fei Liu and Kun-Mao Chao Algorithms for finding the weight-constrained $k$-longest paths in a tree and the length-constrained $k$ maximum-sum segments of a sequence . . . 349--358 Elitza Maneva and Alistair Sinclair On the satisfiability threshold and clustering of solutions of random 3-SAT formulas . . . . . . . . . . . . . . . . 359--369 Guomin Yang and Jing Chen and Duncan S. Wong and Xiaotie Deng and Dongsheng Wang A new framework for the design and analysis of identity-based identification schemes . . . . . . . . . 370--388 Rongjun Chen and Wanzhen Huang and Guochun Tang Dense open-shop schedules with release times . . . . . . . . . . . . . . . . . 389--399 Katherine P. Benedetto and Nicholas A. Loehr Tiling problems, automata, and tiling graphs . . . . . . . . . . . . . . . . . 400--411 Paola Flocchini and Giuseppe Prencipe and Nicola Santoro and Peter Widmayer Arbitrary pattern formation by asynchronous, anonymous, oblivious robots . . . . . . . . . . . . . . . . . 412--447 Hans Kleine Büning and Xishun Zhao Computational complexity of quantified Boolean formulas with fixed maximal deficiency . . . . . . . . . . . . . . . 448--457 Matthieu Latapy Main-memory triangle computations for very large (sparse (power-law)) graphs 458--473 Kei Uchizawa and Eiji Takimoto Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity . . . . . . . . 474--487 J. Balogh and S. L. Bezrukov and L. H. Harper and A. Seress On the bandwidth of 3-dimensional Hamming graphs . . . . . . . . . . . . . 488--495 Qianchuan Zhao and Jianfeng Mao and Tao Ye Time separations of cyclic event rule systems with min--max timing constraints 496--510 Scott C.-H. Huang and Frances Yao and Minming Li and Weili Wu Lower bounds and new constructions on secure group communication schemes . . . 511--523 Hung-Lung Wang and Kun-Mao Chao The 2-radius and 2-radiian problems on trees . . . . . . . . . . . . . . . . . 524--531 Boting Yang and Yi Cao Monotonicity in digraph search problems 532--544 Hong-Yiu Lin and Yuh-Dauh Lyuu and Tak-Man Ma and Yen-Wu Ti Testing whether a digraph contains $H$-free $k$-induced subgraphs . . . . . 545--553 Jin-Ju Hong and Gen-Huey Chen Efficient on-line repetition detection 554--563 F. Cazals and C. Karande A note on the problem of reporting maximal cliques . . . . . . . . . . . . 564--568 Aldo de Luca and Amy Glen and Luca Q. Zamboni Rich, Sturmian, and trapezoidal words 569--573 Mieczys\law Borowiecki and Katarzyna Jesse-Józefczyk Matching cutsets in graphs of diameter 2 574--582 Ye Du On the complexity of deciding bimatrix games similarity . . . . . . . . . . . . 583--586 Benny Porat and Ely Porat and Asaf Zur Pattern matching with pair correlation distance . . . . . . . . . . . . . . . . 587--590 Gábor Horváth and Chrystopher L. Nehaniv and Csaba Szabó An assertion concerning functionally complete algebras and NP-completeness 591--595 Eero Lehtonen Two undecidable variants of Collatz's problems . . . . . . . . . . . . . . . . 596--600 Anonymous Editorial Board . . . . . . . . . . . . v--ix
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1--2 Muffy Calder and Stephen Gilmore Preface . . . . . . . . . . . . . . . . 3--3 Mark Girolami Bayesian inference for differential equations . . . . . . . . . . . . . . . 4--16 A. Credi and M. Garavelli and C. Laneve and S. Pradalier and S. Silvi and G. Zavattaro \tt nano$ \kappa $: a calculus for the modeling and simulation of nano devices 17--30 Raya Khanin and Desmond J. Higham Chemical Master Equation and Langevin regimes for a gene transcription model 31--40 Federica Ciocchetta and Jane Hillston and Martin Kos and David Tollervey Modelling co-transcriptional cleavage in the synthesis of yeast pre-rRNA . . . . 41--54 François Fages and Aurélien Rizk On temporal logic constraint solving for analyzing numerical data time series . . 55--65 Andrea Bracciali and Marcello Brunelli and Enrico Cataldo and Pierpaolo Degano Synapses as stochastic concurrent systems . . . . . . . . . . . . . . . . 66--82 L. Dematté and C. Priami and A. Romanel and O. Soyer Evolving BlenX programs to simulate the evolution of biological networks . . . . 83--96 Anonymous Preface . . . . . . . . . . . . . . . . v--ix
Nancy M. Amato and Der-Tsai Lee and Andrea Pietracaprina and Roberto Tamassia Preface . . . . . . . . . . . . . . . . 97--98 Franco P. Preparata The unpredictable deviousness of models 99--105 Alberto Apostolico and Claudia Tagliacollo Incremental discovery of the irredundant motif bases for all suffixes of a string in O . . . . . . . . . . . . . . . . . . 106--115 Luca Allulli and Giorgio Ausiello and Vincenzo Bonifaci and Luigi Laura On the power of lookahead in on-line server routing problems . . . . . . . . 116--128 Melanie Badent and Emilio Di Giacomo and Giuseppe Liotta Drawing colored graphs on colored points 129--142 Sandeep N. Bhatt and Gianfranco Bilardi and Geppino Pucci Area-time tradeoffs for universal VLSI circuits . . . . . . . . . . . . . . . . 143--150 Mary Ellen Bock and Claudio Garutti and Concettina Guerra Cavity detection and matching for binding site recognition . . . . . . . . 151--162 Jean-Daniel Boissonnat and Camille Wormser and Mariette Yvinec Anisotropic diagrams: Labelle Shewchuk approach revisited . . . . . . . . . . . 163--173 L. Castelli Aleardi and O. Devillers and G. Schaeffer Succinct representations of planar maps 174--187 Bruno Codenotti and Amin Saberi and Kasturi Varadarajan and Yinyu Ye The complexity of equilibria: Hardness results for economies via a correspondence with games . . . . . . . 188--198 Michael T. Goodrich Pipelined algorithms to detect cheating in long-term grid computations . . . . . 199--207 Kazuo Iwama and Hiroki Morizumi and Jun Tarui Reductions for monotone Boolean circuits 208--212 Irit Katriel and Claire Kenyon-Mathieu and Eli Upfal Commitment under uncertainty: Two-stage stochastic matching problems . . . . . . 213--223 Charalampos Papamanthou and Ioannis G. Tollis Algorithms for computing a parameterized st . . . . . . . . . . . . . . . . . . . 224--240 Eric Rachlin and John E. Savage Nanowire addressing with randomized-contact decoders . . . . . . 241--261
Peter Hines Machine semantics . . . . . . . . . . . 1--23 Stéphane Demri and Régis Gascon Verification of qualitative $ \mathbb {Z} $ constraints . . . . . . . . . . . 24--40 Alessandro Avellone and Guido Fiorino and Ugo Moscato Optimization techniques for propositional intuitionistic logic and their implementation . . . . . . . . . . 41--58 Lucia Acciai and Michele Boreale Responsiveness in process calculi . . . 59--93 Nicola Gambino and Richard Garner The identity type weak factorisation system . . . . . . . . . . . . . . . . . 94--109 Xiaojun Liu and Edward A. Lee CPO semantics of timed interactive actor networks . . . . . . . . . . . . . . . . 110--125 W. Reisig The computable kernel of Abstract State Machines . . . . . . . . . . . . . . . . 126--136 David A. Cohen and Peter G. Jeavons and Stanislav \vZivný The expressive power of valued constraints: Hierarchies and collapses 137--153 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Dario Andrea Bini and Victor Y. Pan and Jan Verschelde Preface . . . . . . . . . . . . . . . . 155--157 T. Bella and Y. Eidelman and I. Gohberg and V. Olshevsky Computations with quasiseparable polynomials and matrices . . . . . . . . 158--179 Annie Cuyt and Wen-shin Lee A new algorithm for sparse interpolation of multivariate polynomials . . . . . . 180--185 Ioannis Z. Emiris and Elias P. Tsigaridas Real algebraic numbers and polynomial systems of small degree . . . . . . . . 186--199 Bin Li and Jiawang Nie and Lihong Zhi Approximate GCDs of polynomials and sparse SOS relaxations . . . . . . . . . 200--210 Gregory Leibon and Daniel N. Rockmore and Wooram Park and Robert Taintor and Gregory S. Chirikjian A fast Hermite transform . . . . . . . . 211--228 Bernard Mourrain and Philippe Trébuchet Stable normal forms for polynomial system solving . . . . . . . . . . . . . 229--240 Marc Eric Normandin and Adam Vajda and Sree Ram Valluri Gravitational wave signal templates, pattern recognition, and reciprocal Eulerian gamma functions . . . . . . . . 241--254 V. Y. Pan and D. Grady and B. Murphy and G. Qian and R. E. Rosholt and A. D. Ruslanov Schur aggregation for linear systems and determinants . . . . . . . . . . . . . . 255--268 Helfried Peyrl and Pablo A. Parrilo Computing sum of squares decompositions with rational coefficients . . . . . . . 269--281 Hiroshi Sekigawa The nearest polynomial with a zero in a given domain . . . . . . . . . . . . . . 282--291 Vikram Sharma Complexity of real root isolation using continued fractions . . . . . . . . . . 292--310 Kiyoshi Shirayanagi and Hiroshi Sekigawa A new Gröbner basis conversion method based on stabilization techniques . . . 311--317 Zhonggang Zeng A numerical elimination method for polynomial computations . . . . . . . . 318--331
Edgar Fisher and Nándor Sieben Rectangular polyomino set weak (1, 2)-achievement games . . . . . . . . . . 333--340 Antoniy Ganchev and Lata Narayanan and Sunil Shende Games to induce specified equilibria . . 341--350 Mark Cieliebak and Alexander Hall and Riko Jacob and Marc Nunkesser Sequential vector packing . . . . . . . 351--363 Sarmad Abbasi and Numan Sheikh Complexity of question/answer games . . 364--381 J. L. Baril and J. M. Pallo The pruning-grafting lattice of binary trees . . . . . . . . . . . . . . . . . 382--393 Cees Elzinga and Sven Rahmann and Hui Wang Algorithms for subsequence combinatorics 394--404 Weigen Yan and Fuji Zhang A quadratic identity for the number of perfect matchings of plane graphs . . . 405--410 Alan Deckelbaum Simulating one-reversal multicounter machines by partially blind multihead finite automata . . . . . . . . . . . . 411--416 Cagdas E. Gerede and Oscar H. Ibarra and Bala Ravikumar and Jianwen Su Minimum-cost delegation in service composition . . . . . . . . . . . . . . 417--431 James D. Currie and Terry I. Visentin Long binary patterns are Abelian $2$-avoidable . . . . . . . . . . . . . 432--437 Amihood Amir and Tzvika Hartman and Oren Kapah and B. Riva Shalom and Dekel Tsur Generalized LCS . . . . . . . . . . . . 438--449 Ping-Ying Tsai and Jung-Sheng Fu and Gen-Huey Chen Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model . . . . . . . . . . . . . . 450--460 Christian Kassel and Christophe Reutenauer A palindromization map for the free group . . . . . . . . . . . . . . . . . 461--470 Stasys Jukna Expanders and time-restricted branching programs . . . . . . . . . . . . . . . . 471--476 Xiaojun Shen and Jianyu Lou and Weifa Liang and Junzhou Luo Deadline guaranteed packet scheduling for overloaded traffic in input-queued switches . . . . . . . . . . . . . . . . 477--485 Philip Bille and Martin Farach-Colton Fast and compact regular expression matching . . . . . . . . . . . . . . . . 486--496 A. Abouelaoualim and K. Ch. Das and L. Faria and Y. Manoussakis and C. Martinhon and R. Saad Paths and trails in edge-colored graphs 497--510 Petra Berenbrink and Tom Friedetzky and Zengjian Hu and Russell Martin On weighted balls-into-bins games . . . 511--520 Joseph Wun-Tat Chan and Tak-Wah Lam and Prudence W. H. Wong Dynamic bin packing of unit fractions items . . . . . . . . . . . . . . . . . 521--529 A. Fúster-Sabater and P. Caballero-Gil Strategic attack on the shrinking generator . . . . . . . . . . . . . . . 530--536 Pedro V. Silva Rational subsets of partially reversible monoids . . . . . . . . . . . . . . . . 537--548 Jérôme Leroux Structural Presburger digit vector automata . . . . . . . . . . . . . . . . 549--556 Emmanuel Jeandel and Nicolas Ollinger Playing with Conway's problem . . . . . 557--564 Peter R. J. Asveld Generating all permutations by context-free grammars in Greibach normal form . . . . . . . . . . . . . . . . . . 565--577 Amy Glen and Florence Levé and Gwénaël Richomme Quasiperiodic and Lyndon episturmian words . . . . . . . . . . . . . . . . . 578--600 Anne Berry and Elias Dahlhaus and Pinar Heggernes and Genevi\`eve Simonet Sequential and parallel triangulating algorithms for Elimination Game and new insights on Minimum Degree . . . . . . . 601--616 Maurice J. Jansen and Kenneth W. Regan A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle . . . . . 617--622
Pinar Heggernes and Charis Papadopoulos Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions . . . 1--15 Christian Choffrut and Serge Grigorieff Finite $n$-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al. . . . . . . . . . . 16--34 Karol Suchan and Ioan Todinca Minimal interval completion through graph exploration . . . . . . . . . . . 35--43 James D. Currie and Ali Aberkane A cyclic binary morphism avoiding Abelian fourth powers . . . . . . . . . 44--52 Michael R. Fellows and Danny Hermelin and Frances Rosamond and Stéphane Vialette On the parameterized complexity of multiple-interval graph problems . . . . 53--61 Maryam Shoaran and Alex Thomo Fault-tolerant computation of distributed regular path queries . . . . 62--77 Ruifang Liu and Zhonghua Lu and Jinlong Shu The minimal Laplacian spectral radius of trees with a given diameter . . . . . . 78--83 Surender Baswana and Vishrut Goyal and Sandeep Sen All-pairs nearly 2-approximate shortest paths in $ {\O }(n^2 \polylog n) $ time 84--93 Satoshi Ikeda and Izumi Kubo and Masafumi Yamashita The hitting and cover times of random walks on finite graphs using local degree information . . . . . . . . . . . 94--100 Piotr Faliszewski and Lane Hemaspaandra The complexity of power-index comparison 101--107 Tomá\vs Masopust On the descriptional complexity of scattered context grammars . . . . . . . 108--112 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Marcello Bonsangue and Einar Broch Johnsen and Amy Murphy and Jan Vitek Preface . . . . . . . . . . . . . . . . 113--113 Philippe Bidinger and Adriana Compagnoni Pict correctness revisited . . . . . . . 114--127 F. S. de Boer A shared-variable concurrency analysis of multi-threaded object-oriented programs . . . . . . . . . . . . . . . . 128--141 Sara Capecchi and Mario Coppo and Mariangiola Dezani-Ciancaglini and Sophia Drossopoulou and Elena Giachino Amalgamating sessions and methods in object-oriented languages with generics 142--167 John Field and Maria-Cristina Marinescu and Christian Stefansen Reactors: a data-oriented synchronous/asynchronous programming model for distributed applications . . . 168--201 Philipp Haller and Martin Odersky Scala Actors: Unifying thread-based and event-based programming . . . . . . . . 202--220 Jean-Marie Jacquet and Isabelle Linden Fully abstract models and refinements as tools to compare agents in timed coordination languages . . . . . . . . . 221--253 Peter Csaba Ölveczky and Stian Thorvaldsen Formal modeling, performance estimation, and model checking of wireless sensor network algorithms in Real-Time Maude 254--280
G. Rozenberg Preface . . . . . . . . . . . . . . . . 281--282 Paola Bonizzoni and S. Barry Cooper and Benedikt Löwe and Andrea Sorbi Foreword . . . . . . . . . . . . . . . . 283--284 Claudio Zandron Nadia Busi (1968--2007) . . . . . . . . 285--285 Nadia Busi and Claudio Zandron Computational expressiveness of Genetic Systems . . . . . . . . . . . . . . . . 286--293 Anne Condon and 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 A. Ehrenfeucht and G. Rozenberg Introducing time in reaction systems . . 310--322 Carmine Garzillo and Giuseppe Trautteur Computational virtuality in biological systems . . . . . . . . . . . . . . . . 323--331 Nata\vsa Jonoska and Gregory L. McColm Complexity classes for self-assembling flexible tiles . . . . . . . . . . . . . 332--346 Bjòrn Kjos-Hanssen and 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 and Jack H. Lutz and Scott M. Summers Strict self-assembly of discrete Sierpinski triangles . . . . . . . . . . 384--405 Remco Loos and Florin Manea and Victor Mitrana On small, reduced, and fast universal accepting networks of splicing processors . . . . . . . . . . . . . . . 406--416 Florin Manea and Victor Mitrana and Takashi Yokomori Two complementary operations inspired by the DNA hairpin formation: Completion and reduction . . . . . . . . . . . . . 417--425 P. D. Welch Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and Normal Form theorems . . . . . . . . . . . . . 426--442 Damien Woods and Turlough Neary The complexity of small universal Turing machines: a survey . . . . . . . . . . . 443--450 Anonymous Preface . . . . . . . . . . . . . . . . i--vi
Ivan Lavallée and Alexander A. Shvartsman Editors' preface . . . . . . . . . . . . 451--452 Baruch Awerbuch and Christian Scheideler Robust random number generation for peer-to-peer systems . . . . . . . . . . 453--466 Rida A. Bazzi and Young-ri Choi and Mohamed G. Gouda Hop chains: Secure routing and the establishment of distinct identities . . 467--480 Jurek Czyzowicz and Leszek G\kasieniec and Andrzej Pelc Gathering few fat mobile robots in the plane . . . . . . . . . . . . . . . . . 481--499 Murat Demirbas and Anish Arora and Vinodkrishnan Kulathumani \sc Glance: a lightweight querying service for wireless sensor networks . . 500--513 Shlomi Dolev and 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 and Rachid Guerraoui and Calvin Newport Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks . . . 546--569 Rachid Guerraoui and Maurice Herlihy and Bastian Pochon A topological treatment of early-deciding set-agreement . . . . . . 570--580 Colette Johnen and Le Huy Nguyen Robust self-stabilizing weight-based clustering algorithm . . . . . . . . . . 581--594 Marios Mavronicolas and Loizos Michael and Paul Spirakis Computing on a partially eponymous ring 595--613 Neeraj Mittal and Kuppahalli L. Phaneesh and 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
Deying Li and Hongwei Du and Peng-Jun Wan and Xiaofeng Gao and Zhao Zhang and Weili Wu Construction of strongly connected dominating sets in asymmetric multihop wireless networks . . . . . . . . . . . 661--669 M. Kiwi and M. Soto and C. 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 and Lawrence L. Larmore and Linda Morales and I. 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 and 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 A. C. Kaporis and P. G. Spirakis The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions . . . . . 745--755 Decheng Dai and Changyuan Yu A $ 5 + \epsilon $-approximation algorithm for minimum weighted dominating set in unit disk . . . . . . 756--765 Ping-Ying Tsai and Jung-Sheng Fu and Gen-Huey Chen Fault-free longest paths in star networks with conditional link faults 766--775 C. T. Ng and Zhiyi Tan and Yong He and T. C. E. Cheng Two semi-online scheduling problems on two uniform machines . . . . . . . . . . 776--792 F. Blanchet-Sadri and Robert Merca\cs and Geoffrey Scott A generalization of Thue freeness for partial words . . . . . . . . . . . . . 793--800 Tzu-Liang Kung and Cheng-Kuan Lin and Tyne Liang and Lih-Hsing Hsu and Jimmy J. M. Tan On the bipanpositionable bipanconnectedness of hypercubes . . . . 801--811 Zhao Zhang and Xiaofeng Gao and Weili Wu Algorithms for connected set cover problem and fault-tolerant connected set cover problem . . . . . . . . . . . . . 812--817 Jianer Chen and Iyad A. Kanj and Jie Meng and Ge Xia and Fenghui Zhang On the pseudo-achromatic number problem 818--829 Xianglai Qi and Shiguo Zhou and Jinjiang Yuan Single machine parallel-batch scheduling with deteriorating jobs . . . . . . . . 830--836 A\"\ida Ouangraoua and Pascal Ferraro A constrained edit distance algorithm between semi-ordered trees . . . . . . . 837--846 Mathilde Bouvel and Dominique Rossin A variant of the tandem duplication --- random loss model of genome rearrangement . . . . . . . . . . . . . 847--858 Vera Asodi and Christopher Umans The complexity of the matroid--greedoid partition problem . . . . . . . . . . . 859--866 Chi-Yuan Chan and Shan-Chyun Ku and Chi-Jen Lu and Biing-Feng Wang Efficient algorithms for two generalized 2-median problems and the group median problem on trees . . . . . . . . . . . . 867--876 Jianping Li and Weidong Li and Tongquan Zhang and Zhongxu Zhang The subdivision-constrained minimum spanning tree problem . . . . . . . . . 877--885 Alessandro Ferrante and Gennaro Parlato and Francesco Sorrentino and Carmine Ventre Fast payment schemes for truthful mechanisms with verification . . . . . . 886--899 Wataru Matsubara and Shunsuke Inenaga and Akira Ishino and Ayumi Shinohara and Tomoyuki Nakamura and 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 and Chang-Jen Tu Constructing edge-disjoint spanning trees in locally twisted cubes . . . . . 926--932 Spyros C. Kontogiannis and Paul G. Spirakis On the support size of stable strategies in random games . . . . . . . . . . . . 933--942 Vesa Halava and Tero Harju and Tomi Kärki and Patrice Séébold Overlap-freeness in infinite partial words . . . . . . . . . . . . . . . . . 943--948 Jean Cardinal and Stefan Langerman and Eythan Levy Improved approximation bounds for edge dominating set in dense graphs . . . . . 949--957 Travis Gagie Compressed depth sequences . . . . . . . 958--962 Sung-Pil Hong and Myoung-Ju Park and Soo Y. Chang Approximation of the $k$-batch consolidation problem . . . . . . . . . 963--967 F. Blanchet-Sadri and Raphaël M. Jungers and 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 and Valery S. Gordon and Dominique de Werra On the inapproximability of independent domination in 2 P . . . . . . . . . . . 977--982 Cinzia Pizzi k . . . . . . . . . . . . . . . . . . . 983--987 Tsung-Hsi Tsai Efficient computation of the iteration of functions . . . . . . . . . . . . . . 988--993 Martin Wahlén On the complexity of approximating the Hadwiger number . . . . . . . . . . . . 994--996 Juha Honkala On the simplification of infinite morphic words . . . . . . . . . . . . . 997--1000
S. Barry Cooper and Hong Zhu Preface: Algorithms, complexity and models of computation . . . . . . . . . 1001--1002 Vincent Danos and Linus J. Schumacher How liquid is biological signalling? . . 1003--1012 Minming Li and Ze Feng and Nan Zang and Ronald L. Graham and Frances F. Yao Approximately optimal trees for group key management with batch updates . . . 1013--1021 Wangsen Feng and Li'ang Zhang and Hanpin Wang Approximation algorithm for maximum edge coloring . . . . . . . . . . . . . . . . 1022--1029 Andreas Jakoby and Maciej Li\'skiewicz and Rüdiger Reischuk and Christian Schindelhauer Improving the average delay of sorting 1030--1041 Angsheng Li Elementary differences among jump classes . . . . . . . . . . . . . . . . 1042--1053 Hiroki Morizumi and Jun Tarui Linear-size log-depth negation-limited inverter for $k$-tonic binary sequences 1054--1060 Akifumi Kawaguchi and Hiroshi Nagamochi Drawing slicing graphs with face areas 1061--1072 He Sun and Chung Keung Poon Two improved range-efficient algorithms for $ F_0 $-estimation . . . . . . . . . 1073--1080 Yingchao Zhao and Shang-hua Teng Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces 1081--1092 Peng Zhang and Mingji Xia An approximation algorithm to the $k$-Steiner Forest problem . . . . . . . 1093--1098 Andrew C. C. Yao and Frances F. Yao and Yunlei Zhao A note on universal composable zero-knowledge in the common reference string model . . . . . . . . . . . . . . 1099--1108
Andrei Popescu and Traian Florin \cSerb\uanu\ct\ua and Grigore Ro\csu A semantic approach to interpolation . . 1109--1128 H. Peter Gumm Copower functors . . . . . . . . . . . . 1129--1142 Simone Bova and Franco Montagna The consequence relation in the logic of commutative GBL . . . . . . . . . . . . 1143--1158 Murdoch J. Gabbay A study of substitution, using nominal techniques and Fraenkel--Mostowksi sets 1159--1189 Robert Lorenz and Gabriel Juhás and Robin Bergenthum and Jörg Desel and Sebastian Mauser Executability of scenarios in Petri nets 1190--1216 Lutz Schröder and Till Mossakowski \sc HasCasl: Integrated higher-order specification and program development 1217--1260 J. A. Bergstra and Y. Hirshfeld and J. V. Tucker Meadows and the equational specification of division . . . . . . . . . . . . . . 1261--1271 Marta Kwiatkowska and Gethin Norman and David Parker and Maria Grazia Vigliotti Probabilistic Mobile Ambients . . . . . 1272--1303
Giuseppe Prencipe and Shmuel Zaks Preface . . . . . . . . . . . . . . . . 1305--1306 Nicolas Nisse and David Soguet Graph searching with advice . . . . . . 1307--1318 Hajo Broersma and Matthew Johnson and Daniël Paulusma Upper bounds and algorithms for parallel knock-out numbers . . . . . . . . . . . 1319--1327 Eli Gafni and Achour Mostéfaoui and Michel Raynal and Corentin Travers From adaptive renaming to set agreement 1328--1335 Fredrik Manne and Morten Mjelde and Laurence Pilard and Sébastien Tixeuil A new self-stabilizing maximal matching algorithm . . . . . . . . . . . . . . . 1336--1345 Peter Korteweg and Alberto Marchetti-Spaccamela and Leen Stougie and Andrea Vitaletti Data aggregation in sensor networks: Balancing communication and delay costs 1346--1354 Asaf Efrima and David Peleg Distributed algorithms for partitioning a swarm of autonomous mobile robots . . 1355--1368 Guy Even and Tamir Levi and Ami Litman Optimal conclusive sets for comparator networks . . . . . . . . . . . . . . . . 1369--1376 Rastislav Královi\vc and Richard Královi\vc Rapid almost-complete broadcasting in faulty networks . . . . . . . . . . . . 1377--1387 J. Czyzowicz and S. Dobrev and E. Kranakis and J. Opatrny and J. Urrutia Local edge colouring of Yao-like subgraphs of Unit Disk Graphs . . . . . 1388--1400 Amos Korman and Shay Kutten A note on models for graph representations . . . . . . . . . . . . 1401--1412
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1413--1414 Nata\vsa Jonoska and Jarkko Kari Preface . . . . . . . . . . . . . . . . 1415--1416 Sam Greenberg and Dana Randall Convergence rates of Markov chains for some self-assembly and non-saturated Ising models . . . . . . . . . . . . . . 1417--1427 John H. Reif and Sudheer Sahu Autonomous programmable DNA nanorobotic devices using DNAzymes . . . . . . . . . 1428--1439 N. E. Grayson and A. Taormina and R. Twarock DNA duplex cage structures with icosahedral symmetry . . . . . . . . . . 1440--1447 Nata\vsa Jonoska and Nadrian C. Seeman and Gang Wu On existence of reporter strands in DNA-based graph structures . . . . . . . 1448--1460 Yuriy Brun and Dustin Reishus Path finding in the tile assembly model 1461--1472
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1473--1474 Nata\vsa Jonoska and Jarkko Kari Preface . . . . . . . . . . . . . . . . 1475--1476 Marcella Anselmo and Maria Madonia Deterministic and unambiguous two-dimensional languages over one-letter alphabet . . . . . . . . . . 1477--1485 Robert Brijder and 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 Anonymous Preface . . . . . . . . . . . . . . . . i--vi
Paul G. Spirakis and Marios Mavronicolas and Spyros C. Kontogiannis Preface . . . . . . . . . . . . . . . . 1551--1551 Heiner Ackermann and Heiko Röglin and Berthold Vöcking Pure Nash equilibria in player-specific and weighted congestion games . . . . . 1552--1563 Davide Bil\`o and Luciano Gual\`a and Guido Proietti Dynamic mechanism design . . . . . . . . 1564--1572 Xi Chen and Li-Sha Huang and Shang-Hua Teng Market equilibria with hybrid linear-Leontief utilities . . . . . . . 1573--1580 Constantinos Daskalakis and Aranyak Mehta and Christos Papadimitriou A note on approximate Nash equilibria 1581--1588 Nicole Immorlica and Li (Erran) Li and Vahab S. Mirrokni and Andreas S. Schulz Coordination mechanisms for selfish scheduling . . . . . . . . . . . . . . . 1589--1598 Spyros C. Kontogiannis and Panagiota N. Panagopoulou and Paul G. Spirakis Polynomial algorithms for approximating Nash equilibria of bimatrix games . . . 1599--1606 Paolo Penna and Guido Proietti and Peter Widmayer Strongly polynomial-time truthful mechanisms in one shot . . . . . . . . . 1607--1615
Lars Arge and Christian Cachin and Andrzej Tarlecki Preface . . . . . . . . . . . . . . . . 1617--1617 Jin-Yi Cai and Pinyan Lu Holographic algorithms: The power of dimensionality resolved . . . . . . . . 1618--1628 Beno\^\it Larose and Pascal Tesson Universal algebra and hardness results for constraint satisfaction problems . . 1629--1647 Johannes Blömer and Stefanie Naewe Sampling methods for shortest vectors, closest vectors and successive minima 1648--1665 Albert Atserias and Andrei Bulatov and Anuj Dawar Affine systems of equations and counting infinitary logic . . . . . . . . . . . . 1666--1683 Manuel Bodirsky and Hubie Chen and Jan Kára and Timo von Oertzen Maximal infinite-valued constraint languages . . . . . . . . . . . . . . . 1684--1693 Bernard Boigelot and Julien Brusten A generalization of Cobham's theorem to automata over real numbers . . . . . . . 1694--1703 Marcelo Fiore and Chung-Kil Hur On the construction of free algebras for equational systems . . . . . . . . . . . 1704--1729 Yuval Ishai and Tal Malkin and Martin J. Strauss and Rebecca N. Wright Private multiparty sampling and approximation of vector combinations . . 1730--1745
Marcus Hutter and Rocco A. Servedio Preface . . . . . . . . . . . . . . . . 1747--1748 Markus Maier and Matthias Hein and 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 $ \mathbb {R}^d $ . . . . . . . . . . . . 1765--1780 Vladimir V. V'yugin On calibration error of randomized forecasting algorithms . . . . . . . . . 1781--1795 Sanjay Jain and Frank Stephan and 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 and Tetsuji Kuboyama Polynomial summaries of positive semidefinite kernels . . . . . . . . . . 1847--1862 John Case and Samuel E. Moelius III Parallelism increases iterative learning power . . . . . . . . . . . . . . . . . 1863--1875 Jean-Yves Audibert and Rémi Munos and Csaba Szepesvári Exploration--exploitation tradeoff using variance estimates in multi-armed bandits . . . . . . . . . . . . . . . . 1876--1902 Vitaly Feldman and Shrenik Shah Separating models of learning with faulty teachers . . . . . . . . . . . . 1903--1912
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1913--1914 Mika Hirvensalo Preface . . . . . . . . . . . . . . . . 1915--1915 Andris Ambainis and Nikolajs Nahimovs Improved constructions of quantum automata . . . . . . . . . . . . . . . . 1916--1922 R\=usi\cn\vs Freivalds and M\=aris Ozols and Laura Man\vcinska Improved constructions of mixed state quantum automata . . . . . . . . . . . . 1923--1931 Abuzer Yakaryìlmaz and A. C. Cem Say Efficient probability amplification in two-way quantum finite automata . . . . 1932--1941 Marats Golovkins and Maksim Kravtsev and Vasilijs Kravcevs On a class of languages recognizable by probabilistic reversible decide-and-halt automata . . . . . . . . . . . . . . . . 1942--1951 Ilze Dzelme-B\=erzi\cna Mathematical logic and quantum finite state automata . . . . . . . . . . . . . 1952--1959 Anonymous Preface . . . . . . . . . . . . . . . . i--vi
Alexander Meduna and Ji\vrí Techet An infinite hierarchy of language families generated by scattered context grammars with $n$-limited derivations 1961--1969 Pierre Fraigniaud and Cyril Gavoille and Adrian Kosowski and Emmanuelle Lebhar and Zvi Lotker Universal augmentation schemes for network navigability . . . . . . . . . . 1970--1981 Guanghui Wang and Guizhen Liu Paths, cycles and circular colorings in digraphs . . . . . . . . . . . . . . . . 1982--1985 Marcus Oswald and Gerhard Reinelt The simultaneous consecutive ones problem . . . . . . . . . . . . . . . . 1986--1992 Isaac Elias and Jens Lagergren Fast neighbor joining . . . . . . . . . 1993--2000 Jinn-Shyong Yang and Jou-Ming Chang and Shyue-Ming Tang and Yue-Li Wang On the independent spanning trees of recursive circulant graphs G . . . . . . 2001--2010 Christian Glaßer and Alan L. Selman and Stephen Travers and Liyu Zhang Non-mitotic sets . . . . . . . . . . . . 2011--2023 Wenbin Chen and Matthew C. Schmidt and Nagiza F. Samatova On parameterized complexity of the Multi-MCS problem . . . . . . . . . . . 2024--2032 Adrien Guignard and Éric Sopena Compound Node--Kayles on paths . . . . . 2033--2044 Herbert Fleischner and Egbert Mujuni and Daniël Paulusma and Stefan Szeider Covering graphs with few complete bipartite subgraphs . . . . . . . . . . 2045--2053 Stefan Dantchev and Barnaby Martin and Mark Rhodes Tight rank lower bounds for the Sherali--Adams proof system . . . . . . 2054--2063 Takayuki Nagoya and Seinosuke Toda Computational complexity of computing a partial solution for the Graph Automorphism problems . . . . . . . . . 2064--2071 Liliana Alcón and Luerbio Faria and Celina M. H. de Figueiredo and 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 and Yinfeng Xu and Chengbin Chu and Feifeng Zheng Online scheduling on two uniform machines to minimize the makespan . . . 2099--2109 Roberto Baldoni and Silvia Bonomi and Leonardo Querzoni and Sara Tucci Piergiovanni Investigating the existence and the regularity of Logarithmic Harary Graphs 2110--2121 Yuval Lando and Zeev Nutov Inapproximability of survivable networks 2122--2125 M.-A. Jacob-Da Col and P. Tellier Quasi-linear transformations and discrete tilings . . . . . . . . . . . . 2126--2134 A. Cherubini and A. Kisielewicz Collapsing words, permutation conditions and coherent colorings of trees . . . . 2135--2147 Daniel Reidenbach and Johannes C. Schneider Morphically primitive words . . . . . . 2148--2161 Xingwu Liu and Zhiwei Xu and Jianzhong Pan Classifying rendezvous tasks of arbitrary dimension . . . . . . . . . . 2162--2173 Amos Beimel and Boaz Ben-Moshe and Yehuda Ben-Shimol and Paz Carmi and Eldad Chai and Itzik Kitroser and Eran Omri Matrix columns allocation problems . . . 2174--2183 N. Bourgeois and B. Escoffier and V. Th. Paschos Efficient approximation of min set cover 2184--2195 Changyuan Yu Truthful mechanisms for two-range-values variant of unrelated scheduling . . . . 2196--2206 Stefano Galatolo and Mathieu Hoyrup and Cristóbal 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 and Frédéric Maffray and Bruce Reed and Nicolas Trotignon Coloring Artemis graphs . . . . . . . . 2234--2240 Hans-Joachim Böckenhauer and Joachim Kneis and 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 and Helmut Prodinger Moves and displacements of particular elements in Quicksort . . . . . . . . . 2279--2284 Shang-Wei Zhao and Xiao-Shan Gao Minimal achievable approximation ratio for MAX-MQ in finite fields . . . . . . 2285--2290 Ji Tian and Ruyan Fu and 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
Anonymous Preface . . . . . . . . . . . . . . . . 2301--2307 Artiom Alhazov and Ion Petre and Vladimir Rogojin The parallel complexity of signed graphs: Decidability results and an improved algorithm . . . . . . . . . . . 2308--2315 Ying Cai and Cunsheng Ding Binary sequences with optimal autocorrelation . . . . . . . . . . . . 2316--2322 Cristian S. Calude and Helmut Jürgensen and Ludwig Staiger Topology on words . . . . . . . . . . . 2323--2335 Cezar Câmpeanu and Nicolae Santean On the intersection of regex languages with regular languages . . . . . . . . . 2336--2344 Julien Cassaigne and Juhani Karhumäki and Petri Salmela Conjugacy of finite biprefix codes . . . 2345--2351 Matteo Cavaliere and Oscar H. Ibarra and Gheorghe P\uaun and Omer Egecioglu and Mihai Ionescu and Sara Woodworth Asynchronous spiking neural P systems 2352--2364 Shihyen Chen and Bin Ma and Kaizhong Zhang On the similarity metric and the distance metric . . . . . . . . . . . . 2365--2376 Michael Domaratzki and Alexander Okhotin State complexity of power . . . . . . . 2377--2392 Lila Kari and Kalpana Mahalingam and Shinnosuke Seki Twin-roots of words and their properties 2393--2400 Dalia Krieger and Avery Miller and Narad Rampersad and Bala Ravikumar and Jeffrey Shallit Decimations of languages and state complexity . . . . . . . . . . . . . . . 2401--2409 Shuai Cheng Li and Ming Li On two open problems of 2-interval patterns . . . . . . . . . . . . . . . . 2410--2423 Andrei P\uaun and Mihaela P\uaun and Alfonso Rodríguez-Patón On the Hopcroft's minimization technique for DFA and DFCA . . . . . . . . . . . . 2424--2430 Narad Rampersad and Nicolae Santean and Jeffrey Shallit and Bala Ravikumar State complexity of unique rational operations . . . . . . . . . . . . . . . 2431--2441 Hsu-Chun Yen and Chien-Liang Chen On minimal elements of upward-closed sets . . . . . . . . . . . . . . . . . . 2442--2452
G. Rozenberg Preface . . . . . . . . . . . . . . . . 2453--2454 Tobias Friedrich and Nils Hebbinghaus and Frank Neumann Comparison of simple diversity mechanisms on plateau functions . . . . 2455--2462 Rahul Jain and Shengyu Zhang New bounds on classical and quantum one-way communication complexity . . . . 2463--2477 Xingyi Zhang and Xiangxiang Zeng and Linqiang Pan On languages generated by asynchronous spiking neural P systems . . . . . . . . 2478--2488 Anne Broadbent and Elham Kashefi Parallelizing quantum circuits . . . . . 2489--2510 Dirk Sudholt The impact of parametrization in memetic evolutionary algorithms . . . . . . . . 2511--2528 Lvzhou Li and Daowen Qiu A note on quantum sequential machines 2529--2535 Anonymous Preface . . . . . . . . . . . . . . . . i--vi
Yo-Sub Han and Kai Salomaa State complexity of basic operations on suffix-free regular languages . . . . . 2537--2548 Petra Berenbrink and Colin Cooper and Zengjian Hu Energy efficient randomised communication in unknown AdHoc networks 2549--2561 Sanjay Jain and Efim Kinber One-shot learners using negative counterexamples and nearest positive examples . . . . . . . . . . . . . . . . 2562--2580 Chi-Shiang Su and Jason Chao-Hsien Pan and Tsung-Shin Hsu A new heuristic algorithm for the machine scheduling problem with job delivery coordination . . . . . . . . . 2581--2591 Mayur Thakur and Rahul Tripathi Linear connectivity problems in directed hypergraphs . . . . . . . . . . . . . . 2592--2618 Weiwei Wu and Minming Li and Enhong Chen Optimal tree structures for group key tree management considering insertion and deletion cost . . . . . . . . . . . 2619--2631 Jung-Heum Park and Sang Hyuk Son Conditional matching preclusion for hypercube-like interconnection networks 2632--2640 Jianer Chen and Iyad A. Kanj and Ge Xia On parameterized exponential time complexity . . . . . . . . . . . . . . . 2641--2648 David Harvey A cache-friendly truncated FFT . . . . . 2649--2658 Sanchit Garg and Éric Schost Interpolation of polynomials given by straight-line programs . . . . . . . . . 2659--2662 Bin Fu and Yumei Huo and Hairong Zhao Exponential inapproximability and FPTAS for scheduling with availability constraints . . . . . . . . . . . . . . 2663--2674 Soonjo Hong and Sujin Shin Cyclic renewal systems . . . . . . . . . 2675--2684 Jean B. Lasserre and Monique Laurent and Philipp Rostalski A prolongation--projection algorithm for computing the finite real variety of an ideal . . . . . . . . . . . . . . . . . 2685--2700 F. De Carli and A. Frosini and S. Rinaldi and A. Sorbi Lattices of local two-dimensional languages . . . . . . . . . . . . . . . 2701--2713 Ching-Lueh Chang and Yuh-Dauh Lyuu Spreading messages . . . . . . . . . . . 2714--2724 Josep Diaz and Fabrizio Grandoni and Alberto Marchetti Spaccamela Balanced cut approximation in random geometric graphs . . . . . . . . . . . . 2725--2731 Zhigang Cao and Xiaoguang Yang A PTAS for parallel batch scheduling with rejection and dynamic job arrivals 2732--2745 Hong Liu and Haodi Feng and Daming Zhu and Junfeng Luan Parameterized computational complexity of control problems in voting systems 2746--2753 Ali Husseinzadeh Kashan and Behrooz Karimi and 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 N. Ollinger and G. Richard Automata on the plane vs particles and collisions . . . . . . . . . . . . . . . 2767--2773 Mark Rhodes On the Chvátal rank of the Pigeonhole Principle . . . . . . . . . . . . . . . 2774--2778 L'ubomíra Balková and Edita Pelantová A note on symmetries in the Rauzy graph and factor frequencies . . . . . . . . . 2779--2783 Anonymous Editorial Board . . . . . . . . . . . . i--vi
Anonymous Preface . . . . . . . . . . . . . . . . 2785--2794 Jean-Paul Allouche and Narad Rampersad and Jeffrey Shallit Periodicity, repetitions, and orbits of an automatic sequence . . . . . . . . . 2795--2803 Pawe\l Baturo and Wojciech Rytter Compressed string-matching in standard Sturmian words . . . . . . . . . . . . . 2804--2810 Jean Berstel and Luc Boasson and Olivier Carton Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm . . . . . . . . . . . . . . . 2811--2822 Vincent D. Blondel and Julien Cassaigne and Raphaël M. Jungers On the number of $ \alpha $-power-free binary words for $ 2 < \alpha \leq 7 / 3$ 2823--2833 Dongbo Bu and Ming Li and Shuai Cheng Li and Jianbo Qian and Jinbo Xu Finding compact structural motifs . . . 2834--2839 Michelangelo Bucci and Aldo de Luca and Alessandro De Luca Characteristic morphisms of generalized episturmian words . . . . . . . . . . . 2840--2859 Michelangelo Bucci and Alessandro De Luca and Amy Glen and Luca Q. Zamboni A new characteristic property of rich words . . . . . . . . . . . . . . . . . 2860--2863 Yann Bugeaud and Christophe Reutenauer and Samir Siksek A Sturmian sequence related to the uniqueness conjecture for Markoff numbers . . . . . . . . . . . . . . . . 2864--2869 Christian Choffrut and Serge Grigorieff The ``equal last letter'' predicate for words on infinite alphabets and classes of multitape automata . . . . . . . . . 2870--2884 James Currie and Narad Rampersad Dejean's conjecture holds for $ n \geq 30 $ . . . . . . . . . . . . . . . . . . 2885--2888 Elena Czeizler and 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 and Gema M. Martín and Francisco J. Vico Some operations preserving primitivity of words . . . . . . . . . . . . . . . . 2910--2919 J. Díaz and L. Kirousis and D. Mitsche and X. Pérez-Giménez On the satisfiability threshold of formulas with three literals per clause 2920--2934 Volker Diekert and Dalia Krieger Some remarks about stabilizers . . . . . 2935--2946 A. E. Frid Simple equations on binary factorial languages . . . . . . . . . . . . . . . 2947--2956 Vesa Halava and Jarkko Kari and Yuri Matiyasevich On post correspondence problem for letter monotonic languages . . . . . . . 2957--2960 Yo-Sub Han and Kai Salomaa Nondeterministic state complexity of nested word automata . . . . . . . . . . 2961--2971 Juraj Hromkovi\vc and Holger Petersen and 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 and Andrei P\uaun and Alfonso Rodríguez-Patón Sequential SNP systems based on min/max spike number . . . . . . . . . . . . . . 2982--2991 I. A. Mikhailova and M. V. Volkov Pattern avoidance by palindromes . . . . 2992--2998 François Nicolas and Veli Mäkinen and Esko Ukkonen Efficient construction of maximal and minimal representations of motifs of a string . . . . . . . . . . . . . . . . . 2999--3005 Daowen Qiu and Sheng Yu Hierarchy and equivalence of multi-letter quantum finite automata . . 3006--3017 Antonio Restivo and Giovanna Rosone Burrows--Wheeler transform and palindromic richness . . . . . . . . . . 3018--3026 R. Tijdeman and L. Q. Zamboni Fine and Wilf words for any periods II 3027--3034 Anonymous Editorial Board . . . . . . . . . . . . i--vi Anonymous Juhani Karhumaki with a capercaillie . . xi--xi
G. Rozenberg Preface . . . . . . . . . . . . . . . . 3035--3036 Nicola Cannata and Emanuela Merelli Preface . . . . . . . . . . . . . . . . 3037--3038 Cristian Versari and Nadia Busi Stochastic biological modelling in the presence of multiple compartments . . . 3039--3064 Federica Ciocchetta and Jane Hillston Bio-PEPA: a framework for the modelling and analysis of biological systems . . . 3065--3084 Roberto Barbuti and Giulio Caravagna and Andrea Maggiolo-Schettini and 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 J. Barnat and L. Brim and I. \vCerná and S. Dra\vzan and J. Fabriková and D. \vSafránek On algorithmic analysis of transcriptional regulation by LTL model checking . . . . . . . . . . . . . . . . 3128--3148 E. Bartocci and F. Corradini and M. R. Di Berardini and E. Entcheva and S. A. Smolka and R. Grosu Modeling and simulation of cardiac tissue using hybrid I/O automata . . . . 3149--3165 Luca Cardelli and Emmanuelle Caron and Philippa Gardner and Ozan Kahramano\=gullarì and Andrew Phillips A process model of Rho GTP-binding proteins . . . . . . . . . . . . . . . . 3166--3185 Anonymous Preface . . . . . . . . . . . . . . . . i--vi
Cezar Câmpeanu and Giovanni Pighizzini Preface . . . . . . . . . . . . . . . . 3187--3187 Artiom Alhazov and Erzsébet Csuhaj-Varjú and Carlos Martín-Vide and Yurii Rogozhin On the size of computationally complete hybrid networks of evolutionary processors . . . . . . . . . . . . . . . 3188--3197 Franziska Biegler and Kai Salomaa On the synchronized derivation depth of context-free grammars . . . . . . . . . 3198--3208 Henning Bordihn and Markus Holzer and Martin Kutrib Determination of finite automata accepting subregular languages . . . . . 3209--3222 Janusz Brzozowski and Stavros Konstantinidis State-complexity hierarchies of uniform languages of alphabet-size length . . . 3223--3235 Janusz Brzozowski and Nicolae Santean Predictable semiautomata . . . . . . . . 3236--3249 Elena Czeizler and Eugen Czeizler and Lila Kari and Kai Salomaa On the descriptional complexity of Watson--Crick automata . . . . . . . . . 3250--3260 Jürgen Dassow and Ralf Stiebe and Bianca Truthe Two collapsing hierarchies of subregularly tree controlled languages 3261--3271 Zoltán Ésik and Yuan Gao and Guangwu Liu and Sheng Yu Estimation of state complexity of combined operations . . . . . . . . . . 3272--3280 Hermann Gruber and Markus Holzer Language operations with regular expressions of polynomial size . . . . . 3281--3289 Xiaoxue Piao and Kai Salomaa Operational state complexity of nested word automata . . . . . . . . . . . . . 3290--3302
Marios Mavronicolas Preface . . . . . . . . . . . . . . . . 3303--3304 Dimitris Fotakis and Spyros Kontogiannis and Elias Koutsoupias and Marios Mavronicolas and Paul Spirakis The structure and complexity of Nash equilibria for a selfish routing game 3305--3326 George Christodoulou and Elias Koutsoupias and Akash Nanavati Coordination mechanisms . . . . . . . . 3327--3336 Costas Busch and Malik Magdon-Ismail Atomic routing games on maximum congestion . . . . . . . . . . . . . . . 3337--3347 Vincenzo Auletta and Roberto De Prisco and Paolo Penna and Giuseppe Persiano On designing truthful mechanisms for online scheduling . . . . . . . . . . . 3348--3356 Simon Fischer and Berthold Vöcking Adaptive routing with stale information 3357--3371 B. Chitturi and W. Fahle and Z. Meng and L. Morales and C. O. Shields and I. H. Sudborough and W. Voit An $ (18 / 11) n $ upper bound for sorting by prefix reversals . . . . . . 3372--3390 Jaros\law Kuty\lowski and Friedhelm Meyer auf der Heide Optimal strategies for maintaining a chain of relays between an explorer and a base camp . . . . . . . . . . . . . . 3391--3405 Giorgio Ausiello and Paolo G. Franciosa and Giuseppe F. Italiano Small stretch $ (\alpha, \beta)$-spanners in the streaming model 3406--3413 R. Elsässer and T. Sauerwald On the runtime and robustness of randomized broadcasting . . . . . . . . 3414--3427 Hans-Joachim Böckenhauer and Juraj Hromkovi\vc and Richard Královi\vc and Tobias Mömke and Peter Rossmanith Reoptimization of Steiner trees: Changing the terminal set . . . . . . . 3428--3435
Jan Holub Preface . . . . . . . . . . . . . . . . 3437--3437 Kai Salomaa and Sheng Yu and Jinfeng Zan Deciding determinism of caterpillar expressions . . . . . . . . . . . . . . 3438--3446 Martin Kutrib and Andreas Malcher and Larissa Werlein Regulated nondeterminism in pushdown automata . . . . . . . . . . . . . . . . 3447--3460 Margareta Ackerman and Jeffrey Shallit Efficient enumeration of words in regular languages . . . . . . . . . . . 3461--3470 M. Crochemore and C. Epifanio and A. Gabriele and F. Mignosi From Nerode's congruence to suffix automata with mismatches . . . . . . . . 3471--3480 Manfred Droste and George Rahonis Weighted automata and weighted logics with discounting . . . . . . . . . . . . 3481--3494 Magnus Steinby and C\uat\ualin Ionu\ct T\^\irn\uauc\ua Defining syntax-directed translations by tree bimorphisms . . . . . . . . . . . . 3495--3503 Nata\vsa Jonoska and Joni B. Pirnot Finite state automata representing two-dimensional subshifts . . . . . . . 3504--3512 M. V. Volkov Synchronizing automata preserving a chain of partial orders . . . . . . . . 3513--3519 Marcella Anselmo and Dora Giammarresi and Maria Madonia A computational model for tiling recognizable two-dimensional languages 3520--3529 F. Mráz and F. Otto and M. 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 and Andreas Maletti and Jonathan May Backward and forward bisimulation minimization of tree automata . . . . . 3539--3552 Mehryar Mohri and Pedro Moreno and Eugene Weinstein General suffix automaton construction algorithm and space bounds . . . . . . . 3553--3562 Shmuel T. Klein and Miri Kopel Ben-Nissan Accelerating Boyer--Moore searches on binary texts . . . . . . . . . . . . . . 3563--3571
Yossi Moshe On the joint subword complexity of automatic sequences . . . . . . . . . . 3573--3588 Z. Masáková and E. Pelantová Relation between powers of factors and the recurrence function characterizing Sturmian words . . . . . . . . . . . . . 3589--3596 An Zhang and Yiwei Jiang and Zhiyi Tan Online parallel machines scheduling with two hierarchies . . . . . . . . . . . . 3597--3605 Johannes Müller and Christoph Spandl A Curtis--Hedlund--Lyndon theorem for Besicovitch and Weyl spaces . . . . . . 3606--3615 Marni Mishna and Andrew Rechnitzer Two non-holonomic lattice walks in the quarter plane . . . . . . . . . . . . . 3616--3630 Wolfgang Bein and Leah Epstein and Lawrence L. Larmore and John Noga Optimally competitive list batching . . 3631--3639 Christian Komusiewicz and Falk Hüffner and Hannes Moser and 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 and Vladimir Y. Protasov and Vincent D. Blondel Overlap-free words and spectra of matrices . . . . . . . . . . . . . . . . 3670--3684 Luigi Acerbi and Alberto Dennunzio and Enrico Formenti Conservation of some dynamical properties for operations on cellular automata . . . . . . . . . . . . . . . . 3685--3693 Reza Dorrigiv and Alejandro López-Ortiz and J. Ian Munro On the relative dominance of paging algorithms . . . . . . . . . . . . . . . 3694--3701 Toru Hasunuma and Toshimasa Ishii and Hirotaka Ono and Yushi Uno An $ O(n^{1.75}) $ $ L(2, 1) $-labeling of trees . . . . . . . . . . . . . . . . 3702--3710 Franziska Biegler and Mark Daley and Markus Holzer and Ian McQuillan On the uniqueness of shuffle on words and finite languages . . . . . . . . . . 3711--3724 Tamir Levi and Ami Litman Accelerating certain outputs of merging and sorting networks . . . . . . . . . . 3725--3732 \Lukasz Kowalik Improved edge-coloring with three colors 3733--3742 Dominique Foata and Guo-Niu Han New permutation coding and equidistribution of set-valued statistics . . . . . . . . . . . . . . . 3743--3750 Omid Amini and Stéphane Pérennes and Ignasi Sau Hardness and approximation of traffic grooming . . . . . . . . . . . . . . . . 3751--3760 Min Ji and T. C. E. Cheng Parallel-machine scheduling of simple linear deteriorating jobs . . . . . . . 3761--3768 Tao Jiang and Zevi Miller and Dan Pritikin Separation numbers of trees . . . . . . 3769--3781 Genevi\`eve Paquin On a generalization of Christoffel words: epichristoffel words . . . . . . 3782--3791 John Augustine and Sudarshan Banerjee and Sandy Irani Strip packing with precedence constraints and strip packing with release times . . . . . . . . . . . . . 3792--3803 Zi-Long Liu and Fang Tian and Jun-Ming Xu Probabilistic analysis of upper bounds for $2$-connected distance $k$-dominating sets in graphs . . . . . 3804--3813 Miki Hermann and Reinhard Pichler Complexity of counting the optimal solutions . . . . . . . . . . . . . . . 3814--3825 Dominik M. Wittmann and Daniel Schmidl and Florian Blöchl and Fabian J. Theis Reconstruction of graphs based on random walks . . . . . . . . . . . . . . . . . 3826--3838 Olaf Beyersdorff and Johannes Köbler and Jochen Messner Nondeterministic functions and the existence of optimal proof systems . . . 3839--3855 Peter Jonsson and Andrei Krokhin and Fredrik Kuivinen Hard constraint satisfaction problems have hard gaps at location 1 . . . . . . 3856--3874 Ming Liu and Chengbin Chu and Yinfeng Xu and Feifeng Zheng Online scheduling on $m$ uniform machines to minimize total (weighted) completion time . . . . . . . . . . . . 3875--3881 Qiang-Sheng Hua and Yuexuan Wang and Dongxiao Yu and 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 and Francesco Scarcello On the complexity of constrained Nash equilibria in graphical games . . . . . 3901--3924 Marek Tomasz Biskup and Wojciech Plandowski Shortest synchronizing strings for Huffman codes . . . . . . . . . . . . . 3925--3941 J. J. Liu and G. S. Huang and Y. L. Wang A fast algorithm for finding the positions of all squares in a run-length encoded string . . . . . . . . . . . . . 3942--3948 Andrei Bulatov and Martin Dyer and Leslie Ann Goldberg and Markus Jalsenius and David Richerby The complexity of weighted Boolean #CSP with mixed signs . . . . . . . . . . . . 3949--3961 Alberto Dennunzio and Pierre Guillon and Beno\^\it Masson Sand automata as cellular automata . . . 3962--3974 Kangbok Lee and Joseph Y.-T. Leung and Michael L. 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 and Lane A. Hemaspaandra and Jörg Rothe and Holger Spakowski Generalized juntas and NP-hard sets . . 3995--4000
Marco Carbone and Pawe\l Soboci\'nski and Frank D. Valencia Foreword: Festschrift for Mogens Nielsen's 60th birthday . . . . . . . . 4001--4005 Romain Beauxis and Catuscia Palamidessi Probabilistic and nondeterministic aspects of anonymity . . . . . . . . . . 4006--4025 N. Bene\vs and J. K\vretínský and K. G. Larsen and J. Srba On determinism in modal transition systems . . . . . . . . . . . . . . . . 4026--4043 Filippo Bonchi and Ugo Montanari Reactive systems, (semi-)saturated semantics and coalgebras on presheaves 4044--4066 Ehab ElSalamouny and Karl Tikjòb Krukow and Vladimiro Sassone An analysis of the exponential decay principle in probabilistic trust models 4067--4084 Gudmund Skovbjerg Frandsen and Peter Frands Frandsen Dynamic matrix rank . . . . . . . . . . 4085--4093 Thomas Gazagnaire and Blaise Genest and Lo\"\ic Hélouët and P. S. Thiagarajan and Shaofa Yang Causal Message Sequence Charts . . . . . 4094--4110 R. J. van Glabbeek and G. D. Plotkin Configuration structures, event structures and Petri nets . . . . . . . 4111--4159 Glynn Winskel Prime algebraicity . . . . . . . . . . . 4160--4168
Rohit Chadha and Mahesh Viswanathan Deciding branching time properties for asynchronous programs . . . . . . . . . 4169--4179 Peter Niebert and Doron Peled Efficient model checking for LTL with partial order snapshots . . . . . . . . 4180--4189 Lo\"\ic Colson and 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 and Luoshan Xu Meet continuity properties of posets . . 4234--4240 Rachid Hadjidj and Hanifa Boucheneb On-the-fly TCTL model checking for time Petri nets . . . . . . . . . . . . . . . 4241--4261 Georgios E. Fainekos and George J. Pappas Robustness of temporal logic specifications for continuous-time signals . . . . . . . . . . . . . . . . 4262--4291
Costas Iliopoulos and Wojciech Rytter Foreword: Special issue in honor of the 60th birthday of Prof. Maxime Crochemore 4293--4294 W. F. Smyth and Shu Wang A new approach to the periodicity lemma on strings with holes . . . . . . . . . 4295--4302 Shay Mozes and Dekel Tsur and Oren Weimann and Michal Ziv-Ukelson Fast algorithms for computing tree LCS 4303--4314 Oren Kapah and Gad M. Landau and Avivit Levy and Nitsan Oz Interchange rearrangement: The element-cost model . . . . . . . . . . . 4315--4326 Giovanni Battaglia and Davide Cangelosi and Roberto Grossi and 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 M. Salson and T. Lecroq and M. Léonard and L. Mouchard A four-stage algorithm for updating a Burrows--Wheeler transform . . . . . . . 4350--4359 Alberto Apostolico and Fabio Cunial The subsequence composition of a string 4360--4371 G. Castiglione and A. Restivo and M. Sciortino Circular Sturmian words and Hopcroft's algorithm . . . . . . . . . . . . . . . 4372--4381 Amihood Amir and Yonatan Aumann and Piotr Indyk and Avivit Levy and Ely Porat Efficient computations of $ \ell_1 $ and $ \ell_\infty $ rearrangement distances 4382--4390 Maria Federico and Nadia Pisanti Suffix tree characterization of maximal motifs in biological sequences . . . . . 4391--4401 Sunho Lee and Kunsoo Park Dynamic rank/select structures with applications to run-length encoded texts 4402--4413 Rodrigo González and Gonzalo Navarro Rank/select on dynamic compressed sequences and applications . . . . . . . 4414--4422 Marie-Pierre Béal and Dominique Perrin Completing codes in a sofic shift . . . 4423--4431 Ricardo Baeza-Yates and Véronique Bruy\`ere and Olivier Delgrange and Rodrigo Scheihing On the size of Boyer--Moore automata . . 4432--4443
Anna Gál Preface: Special Issue of ICALP 2006 --- dedicated to the memory of Ingo Wegener 4445--4445 Martin Dietzfelbinger In memoriam: Prof. Dr. math. Ingo Wegener, 1950--2008 . . . . . . . . . . 4446--4447 Xi Chen and Xiaotie Deng On the complexity of $2$D discrete fixed point problem . . . . . . . . . . . . . 4448--4456 Irene Finocchi and Fabrizio Grandoni and 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 and Satish Rao and Samantha Riesenfeld and 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
Rudolf Fleischer and Jinhui Xu Foreword . . . . . . . . . . . . . . . . 4533--4533 Eric Angel and Evripidis Bampis and Laurent Gourv\`es On the minimum hitting set of bundles problem . . . . . . . . . . . . . . . . 4534--4542 Zhi-Zhong Chen and Ruka Tanahashi Approximating maximum edge 2-coloring in simple graphs via local improvement . . 4543--4553 Nadja Betzler and Michael R. Fellows and Jiong Guo and Rolf Niedermeier and Frances A. Rosamond Fixed-parameter algorithms for Kemeny rankings . . . . . . . . . . . . . . . . 4554--4570 Gregory Gutin and Igor Razgon and Eun Jung Kim Minimum leaf out-branching and related problems . . . . . . . . . . . . . . . . 4571--4579 Nikhil Bansal and Ho-Leung Chan and Kirk Pruhs Speed scaling with a solar cell . . . . 4580--4587 Naoto Miyoshi and Takeya Shigezumi and Ryuhei Uehara and Osamu Watanabe Scale free interval graphs . . . . . . . 4588--4600
Moreno Falaschi and Maurizio Gabbrielli and 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 and Santiago Escobar and José Iborra Termination of narrowing revisited . . . 4608--4625 Gianluca Amato and James Lipton and Robert McGrail On the algebraic structure of declarative programming languages . . . 4626--4671 Roberto Bagnara and Patricia M. Hill and 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 and Manuel V. Hermenegildo Non-strict independence-based program parallelization using sharing and freeness information . . . . . . . . . . 4704--4723 Patrick Cousot and Radhia Cousot and Roberto Giacobazzi Abstract interpretation of resolution-based semantics . . . . . . . 4724--4746 Chuck Liang and 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
Ali Çivril and Malik Magdon-Ismail On selecting a maximum volume sub-matrix of a matrix and related problems . . . . 4801--4811 Daniel Bayer and Van Bang Le and H. N. de Ridder Probe threshold and probe trivially perfect graphs . . . . . . . . . . . . . 4812--4822 A. Dennunzio and P. Di Lena and E. Formenti and L. Margara On the directional dynamics of additive cellular automata . . . . . . . . . . . 4823--4833 Pim van 't Hof and Daniël Paulusma and Gerhard J. Woeginger Partitioning graphs into connected parts 4834--4843 Damien Regnault and Nicolas Schabanel and Éric Thierry Progresses in the analysis of stochastic $2$D cellular automata: a study of asynchronous $2$D minority . . . . . . . 4844--4855 Shisheng Li and 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 and Géza Horváth and 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^{b \omega } $-words of the form $ \tilde {w} \times w $ . . . . . . . . . . . . . . . . . . 4892--4904 Yingchao Zhao and Wei Chen and Shang-hua Teng The isolation game: a game of distances 4905--4919 Noga Alon and Uri Stav Hardness of edge-modification problems 4920--4927 V. Arvind and Johannes Köbler and Wolfgang Lindner Parameterized learnability of juntas . . 4928--4936 Clelia De Felice and Gabriele Fici and Rosalba Zizza A characterization of regular circular languages generated by marked splicing systems . . . . . . . . . . . . . . . . 4937--4960 Pedro García and Manuel Vázquez de Parga and Antonio Cano and Damián López On locally reversible languages . . . . 4961--4974 Gennaro Cordasco and Luisa Gargano Navigable Small-World networks with few random bits . . . . . . . . . . . . . . 4975--4988 Elisabeth Gassner and Johannes Hatzl and Sven O. Krumke and Heike Sperber and Gerhard J. Woeginger How hard is it to find extreme Nash equilibria in network congestion games? 4989--4999 \Lukasz Kowalik and Marcin Mucha Deterministic 7/8-approximation for the metric maximum TSP . . . . . . . . . . . 5000--5009 Jui-Yi Kao and Narad Rampersad and Jeffrey Shallit On NFAs where all states are final, initial, or both . . . . . . . . . . . . 5010--5021 Alan J. Cain Automaton semigroups . . . . . . . . . . 5022--5038 Ming Liu and Yinfeng Xu and Chengbin Chu and Feifeng Zheng Online scheduling to minimize modified total tardiness with an availability constraint . . . . . . . . . . . . . . . 5039--5046 Xingyu Chen and Leah Epstein and Zhiyi Tan Semi-online machine covering for two uniform machines . . . . . . . . . . . . 5047--5062 Lei Chen and Changhong Lu and Zhenbing Zeng Hardness results and approximation algorithms for (weighted) paired-domination in graphs . . . . . . 5063--5071 Lei Chen and Changhong Lu and Zhenbing Zeng Distance paired-domination problems on subclasses of chordal graphs . . . . . . 5072--5081 Tu\=gkan Batu and Petra Berenbrink and Christian Sohler A sublinear-time approximation scheme for bin packing . . . . . . . . . . . . 5082--5092 Eike Kiltz and David Galindo Direct chosen-ciphertext secure identity-based key encapsulation without random oracles . . . . . . . . . . . . . 5093--5111 Ji\vrí Sgall and Hadas Shachnai and Tami Tamir Periodic scheduling with obligatory vacations . . . . . . . . . . . . . . . 5112--5121 Soheir M. Khamis and Sameh S. Daoud and Hanaa A. E. Essa A randomized algorithm for determining dominating sets in graphs of maximum degree five . . . . . . . . . . . . . . 5122--5127 J. Spoerhase and H.-C. Wirth $ (r, p)$-centroid problems on paths and trees . . . . . . . . . . . . . . . . . 5128--5137 Jòrgen Bang-Jensen and Matthias Kriesell Disjoint directed and undirected paths and cycles in digraphs . . . . . . . . . 5138--5144 Cristina T\^\irn\uauc\ua and Satoshi Kobayashi Necessary and sufficient conditions for learning with correction queries . . . . 5145--5157 Flavio D'Alessandro and Benedetto Intrigila and Stefano Varricchio The Parikh counting functions of sparse context-free languages are quasi-polynomials . . . . . . . . . . . 5158--5181 Wenjie Li and Jinjiang Yuan and Jianfa Cao and 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 and Vladimir Kats and Eugene Levner A note on a quadratic algorithm for the 2-cyclic robotic scheduling problem . . 5188--5190 Art\=uras Dubickas Binary words with a given Diophantine exponent . . . . . . . . . . . . . . . . 5191--5195 Dongxiao Yu and Jianfeng Hou and Guizhen Liu and Bin Liu and Lan Xu Acyclic edge coloring of planar graphs with large girth . . . . . . . . . . . . 5196--5200
Lud\vek Ku\vcera Foreword . . . . . . . . . . . . . . . . 5201--5201 Markus Bläser and Andreas Meyer de Voltaire Semisimple algebras of almost minimal rank over the reals . . . . . . . . . . 5202--5214 Paul Bonsma and Luis Cereceda Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances . . . . . . . . . . . . . . . 5215--5226 Maxime Crochemore and Lucian Ilie and Wojciech Rytter Repetitions in strings: Algorithms and combinatorics . . . . . . . . . . . . . 5227--5235 William Duckworth and Michele Zito Large independent sets in random regular graphs . . . . . . . . . . . . . . . . . 5236--5243 Pascal Koiran and Sylvain Perifel VPSPACE and a transfer theorem over the complex field . . . . . . . . . . . . . 5244--5251 Luc Longpré and Pierre McKenzie The complexity of Solitaire . . . . . . 5252--5260 S. Nikoletseas and C. Raptopoulos and P. 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
Paolo Ferragina and Gad M. Landau Foreword . . . . . . . . . . . . . . . . 5299--5299 Anne Bergeron and Julia Mixtacki and Jens Stoye A new linear time algorithm to compute the genomic distance via the double cut and join distance . . . . . . . . . . . 5300--5316 Christian Hundt and Maciej Li\'skiewicz and Ragnar Nevries A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation . . . . . . . 5317--5333 Amihood Amir and Yonatan Aumann and Oren Kapah and Avivit Levy and Ely Porat Approximate string matching with address bit errors . . . . . . . . . . . . . . . 5334--5346 Orgad Keller and Tsvi Kopelowitz and Moshe Lewenstein On the longest common parameterized subsequence . . . . . . . . . . . . . . 5347--5353 Johannes Fischer and Veli Mäkinen and Gonzalo Navarro Faster entropy-bounded compressed suffix trees . . . . . . . . . . . . . . . . . 5354--5364 Roman Kolpakov and Gregory Kucherov Searching for gapped palindromes . . . . 5365--5373 Bin Ma Why greed works for shortest common superstring problem . . . . . . . . . . 5374--5381
Boting Yang and Cao An Wang Preface . . . . . . . . . . . . . . . . 5383--5383 Falk Hüffner and Christian Komusiewicz and Hannes Moser and Rolf Niedermeier Isolation concepts for clique enumeration: Comparison and computational experiments . . . . . . . 5384--5397 Zhao Zhang and Xiaofeng Gao and Weili Wu PTAS for connected vertex cover in unit disk graphs . . . . . . . . . . . . . . 5398--5402 Peter Danziger and Eric Mendelsohn and Lucia Moura and Brett Stevens Covering arrays avoiding forbidden edges 5403--5414 Zhipeng Cai and Zhi-Zhong Chen and Guohui Lin A $ 3.4713$-approximation algorithm for the capacitated multicast tree routing problem . . . . . . . . . . . . . . . . 5415--5424 Nadja Betzler and Johannes Uhlmann Parameterized complexity of candidate control in elections and related digraph problems . . . . . . . . . . . . . . . . 5425--5442 Andreas Brandstädt and Van Bang Le Simplicial powers of graphs . . . . . . 5443--5454 Marjan Marzban and Qian-Ping Gu and Xiaohua Jia Computational study on planar dominating set problem . . . . . . . . . . . . . . 5455--5466 S. Böcker and S. Briesemeister and Q. B. A. Bui and A. Truss Going weighted: Parameterized algorithms for cluster editing . . . . . . . . . . 5467--5480 Zhizhang Shen and Ke Qiu and Eddie Cheng On the surface area of the $ (n, k)$-star graph . . . . . . . . . . . . . 5481--5490 Jeannette Janssen and Pawe\l Pra\lat Protean graphs with a variety of ranking schemes . . . . . . . . . . . . . . . . 5491--5504 Peter Wagner and Andreas Brandstädt The complete inclusion structure of leaf power classes . . . . . . . . . . . . . 5505--5514 Binay Bhattacharya and Mike Burmester and Yuzhuang Hu and Evangelos Kranakis and Qiaosheng Shi and Andreas Wiese Optimal movement of mobile sensors for barrier coverage of a planar region . . 5515--5528
David Soloveichik and Erik Winfree Erratum to ``The computational power of Benenson automata'' [Theoret. Comput. Sci. 344 (2005) 279--297] . . . . . . . 6112--6113
Wei Ren and Qing Zhao A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem' . . . . . . 6451--6454
Achim Blumensath Erratum to ``On the structure of graphs in the Caucal hierarchy'' [Theoret. Comput. Sci. \bf 400 (2008) 19--45] . . 126--127
Franck van Breugel and Claudio Hermida and Michael Makkai and James Worrell Addendum to ``Recursively defined metric spaces without contraction'' [Theoret. Comput. Sci. \bf 380 (1/2) (2007) 143--163] . . . . . . . . . . . . . . . 117--122