Last update: Thu Oct 17 07:14:22 MDT 2024
Volume 47, Number 2, 1986M. Chrobak Finite automata and unary languages . . 149--158
Sergio De Agostino P-complete problems in data compression 181--186
Lane A. Hemaspaandra and Albrecht Hoene and Mitsunori Ogihara Reducibility classes of $P$-selective sets . . . . . . . . . . . . . . . . . . 447--457
Marco Bernardo and Roberto Gorrieri A tutorial on EMPA: A theory of concurrent processes with nondeterminism, priorities, probabilities and time . . . . . . . . . 1--54
Dieter Spreen On functions preserving levels of approximation: A refined model construction for various lambda calculi 261--303
B. Apolloni and C. Gentile $P$-sufficient statistics for PAC learning $k$-term-DNF formulas through enumeration . . . . . . . . . . . . . . 1--37 C. de la Higuera and F. Casacuberta Topology of strings: Median string is NP-complete . . . . . . . . . . . . . . 39--48 Klaus Sutner $ \sigma $-Automata and Chebyshev-polynomials . . . . . . . . . 49--73 Zhi-Zhong Chen Efficient algorithms for acyclic colorings of graphs . . . . . . . . . . 75--95 Nataliya Chekhova Covering numbers of rotations . . . . . 97--116 John T. Baldwin and Saharon Shelah On the classifiability of cellular automata . . . . . . . . . . . . . . . . 117--129 Ryuhei Uehara and Kensei Tsuchida and Ingo Wegener Identification of partial disjunction, parity, and threshold functions . . . . 131--147 Brunella Gerla Conditioning a state by a \Lukasiewicz event: a probabilistic approach to Ulam games . . . . . . . . . . . . . . . . . 149--166 Ferdinando Cicalese and Ugo Vaccaro Optimal strategies against a liar . . . 167--193 D. M. Breuker and J. W. H. M. Uiterwijk and H. J. van den Herik Solving $ 8 \times 8 $ Domineering . . . 195--206 J. Mark Ettinger A metric for positional games . . . . . 207--219 Rémy Malgouyres Homotopy in two-dimensional digital images . . . . . . . . . . . . . . . . . 221--233 S. Crvenkovi\'c and I. Dolinka and Z. Ésik The variety of Kleene algebras with conversion is not finitely based . . . . 235--245 Peter R. J. Asveld and Anton Nijholt The inclusion problem for some subclasses of context-free languages . . 247--256 Anonymous Index . . . . . . . . . . . . . . . . . 291--291 Anonymous Index . . . . . . . . . . . . . . . . . 293--299
Anonymous Editorial(s) . . . . . . . . . . . . . . 1--3 Pascal Caron LANGAGE: A Maple package for automaton characterization of regular languages 5--15 Mehryar Mohri and Fernando Pereira and Michael Riley The design principles of a weighted finite-state transducer library . . . . 17--32 Max Silberztein INTEX: an FST toolbox . . . . . . . . . 33--46 Helmut Lescow and Jens Vöge Minimal separating sets for acceptance conditions in Muller Automata . . . . . 47--57 A. N. Trahtman Optimal estimation on the order of local testability of finite automata . . . . . 59--74 D. Ziadi Sorting and doubling techniques for set partitioning and automata minimization problems . . . . . . . . . . . . . . . . 75--87 J.-L. Ponty An efficient null-free procedure for deciding regular language membership . . 89--101 K. Salomaa and X. Wu and S. Yu Efficient implementation of regular languages using reversed alternating finite automata . . . . . . . . . . . . 103--111 J. A. Brzozowski and R. Negulescu Automata of asynchronous behaviors . . . 113--128 Denis Maurel Pseudo-minimal transducer . . . . . . . 129--139
Anonymous Editorial(s) . . . . . . . . . . . . . . 141--142 Paolo Boldi and Sebastiano Vigna The Turing closure of an Archimedean field . . . . . . . . . . . . . . . . . 143--156 C. Ferretti and G. Mauri and S. Kobayashi and T. Yokomori On the universality of Post and splicing systems . . . . . . . . . . . . . . . . 157--170 C. Ferretti and G. Mauri and C. Zandron Nine test tubes generate any RE language 171--180 Katsunobu Imai and Kenichi Morita A computation-universal two-dimensional $8$-state triangular reversible cellular automaton . . . . . . . . . . . . . . . 181--191 Lila Kari and Greg Gloor and Sheng Yu Using DNA to solve the Bounded Post Correspondence Problem . . . . . . . . . 193--203 Arnaud Maes More on morphisms and almost-periodicity 205--215 Maurice Margenstern Frontier between decidability and undecidability: a survey . . . . . . . . 217--251 C. Michaux and C. Troestler Isomorphism theorem for BSS recursively enumerable sets over real closed fields 253--273 Gheorghe P\uaun DNA computing based on splicing: universality results . . . . . . . . . . 275--296 Hiroshi Sakamoto and Daisuke Ikeda Intractability of decision problems for finite-memory automata . . . . . . . . . 297--308 Géraud Sénizergues Complete formal systems for equivalence problems . . . . . . . . . . . . . . . . 309--334 Anonymous Index . . . . . . . . . . . . . . . . . 335--336
Anonymous Editorial(s) . . . . . . . . . . . . . . 1--4 Didier Galmiche and David J. Pym Proof-search in type-theoretic languages: an introduction . . . . . . . 5--53 James L. Caldwell and Ian P. Gent and Judith Underwood Search algorithms in type theory . . . . 55--90 Raymond McDowell and Dale Miller Cut-elimination for a logic with definitions and induction . . . . . . . 91--119 Toshiyasu Arai and Grigori Mints Extended normal form theorems for logical proofs from axioms . . . . . . . 121--132 Iliano Cervesato and Joshua S. Hodas and Frank Pfenning Efficient resource management for linear logic proof search . . . . . . . . . . . 133--163 M. W. Bunder Proof finding algorithms for implicational logics . . . . . . . . . . 165--186 Amy Felty The calculus of constructions as a framework for proof search with set variable instantiation . . . . . . . . . 187--229 D. Galmiche Connection methods in linear logic and proof nets construction . . . . . . . . 231--272 Gopalan Nadathur Correspondences between classical, intuitionistic and uniform provability 273--298 Eike Ritter and David Pym and Lincoln Wallen On the intuitionistic force of classical search . . . . . . . . . . . . . . . . . 299--333 Anonymous Index . . . . . . . . . . . . . . . . . 335--335
Angelo Monti and Adriano Peron Systolic tree $ \omega $-languages: the operational and the logical view . . . . 1--18 Kosaburo Hashiguchi New upper bounds to the limitedness of distance automata . . . . . . . . . . . 19--32 Tatsuya Akutsu and Magnús M. Halldórsson On the approximation of largest common subtrees and largest common point sets 33--50 D. Robilliard and D. Simplot Undecidability of existential properties in picture languages . . . . . . . . . . 51--74 Pascal Caron and Djelloul Ziadi Characterization of Glushkov automata 75--90 R. J. Gardner and P. Gritzmann and D. Prangenberg On the computational complexity of determining polyatomic structures by X-rays . . . . . . . . . . . . . . . . . 91--106 Kevin Cattell and Michael J. Dinneen and Rodney G. Downey and Michael R. Fellows and Michael A. Langston On computing graph minor obstruction sets . . . . . . . . . . . . . . . . . . 107--127 Yasuo Kawahara and Masao Mori A small final coalgebra theorem . . . . 129--145 Gianpiero Cattaneo and Enrico Formenti and Giovanni Manzini and Luciano Margara Ergodicity, transitivity, and regularity for linear cellular automata over $ Z_m $ . . . . . . . . . . . . . . . . . . . 147--164 Jean-Claude Bermond and Luisa Gargano and Stephan Perennes and Adele A. Rescigno and Ugo Vaccaro Efficient collective communication in optical networks . . . . . . . . . . . . 165--189 Alexandre V. Evfimievski A probabilistic algorithm for updating files over a communication link . . . . 191--199 Alberto Del Lungo and Francesco Del Ristoro and Jean-Guy Penaud Left ternary trees and non-separable rooted planar maps . . . . . . . . . . . 201--215 Christian Germain and Jean Pallo Langages rationnels définis avec une concaténation non-associative . . . . . . 217--231 Alexander Rabinovich Star free expressions over the reals . . 233--245 Yonatan Aumann and Judit Bar-Ilan and Uriel Feige On the cost of recomputing: Tight bounds on pebbling with faults . . . . . . . . 247--261 James Propp Three-player impartial games . . . . . . 263--278 T. Y. Nishida and A. Salomaa On slender 0L languages . . . . . . . . 279--286 Eric Goles and Erich Prisner Source reversal and chip firing on graphs . . . . . . . . . . . . . . . . . 287--295 Tomás Feder and Nimrod Megiddo and Serge A. Plotkin A sublinear parallel algorithm for stable matching . . . . . . . . . . . . 297--308 Marek Karpinski and Alf van der Poorten and Igor Shparlinski Zero testing of $p$-adic and modular polynomials . . . . . . . . . . . . . . 309--317 Bala Kalyanasundaram and Kirk R. Pruhs An optimal deterministic algorithm for online $b$-matching . . . . . . . . . . 319--325 Anonymous Index . . . . . . . . . . . . . . . . . 327--327
François Puitg and Jean-François Dufourd Formalizing mathematics in higher-order logic: A case study in geometric modelling . . . . . . . . . . . . . . . 1--57 Michel Habib and Ross McConnell and Christophe Paul and Laurent Viennot Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing . . . . . . . . 59--84 Rastislav Krá\vlovi\vc and Peter Ru\vzi\vcka and Daniel\vStefankovi\vc The complexity of shortest path and dilation bounded interval routing . . . 85--107 Klaus Weihrauch and Xizhong Zheng Computability on continuous, lower semi-continuous and upper semi-continuous real functions . . . . . 109--133 Dennis Pixton Splicing in abstract families of languages . . . . . . . . . . . . . . . 135--166 Kai Salomaa and Sheng Yu Alternating finite automata and star-free languages . . . . . . . . . . 167--176 Mehryar Mohri Minimization algorithms for sequential transducers . . . . . . . . . . . . . . 177--201 Dimitris Achlioptas and Marek Chrobak and John Noga Competitive analysis of randomized paging algorithms . . . . . . . . . . . 203--218 Cao An Wang and Binhai Zhu Three-dimensional weak visibility: Complexity and applications . . . . . . 219--232 Jean Françon and Yves Bertrand Topological 3D-manifolds: a statistical study of the cells . . . . . . . . . . . 233--254 Didier Arqu\`es and Alain Giorgetti Counting rooted maps on a surface . . . 255--272 A. Pavan and Alan L. Selman Complete distributional problems, hard languages, and resource-bounded measure 273--286 Z. Ésik A proof of the Krohn-Rhodes Decomposition Theorem . . . . . . . . . 287--300 Tanja Lange and Arne Winterhof Factoring polynomials over arbitrary finite fields . . . . . . . . . . . . . 301--308 Gérard Boudol On the semantics of the call-by-name CPS transform . . . . . . . . . . . . . . . 309--321 L. Hemaspaandra and A. Hoene and M. Ogihara Erratum to ``Reducibility classes of $P$-selective sets'' [Theoret. Comput. Sci 155(2) (1996) 447--457] . . . . . . 323--323 Sergio De Agostino Erratum to ``P-complete Problems in Data Compression'' [Theoret. Comput. Sci. 127 (1994) 181--186] . . . . . . . . . . . . 325--326 Anonymous Index . . . . . . . . . . . . . . . . . 399--399
Anonymous Editorial(s) . . . . . . . . . . . . . . 1--2 Eric Bach and Marcos Kiwi Threshold data structures and coding theory . . . . . . . . . . . . . . . . . 3--23 Avrim Blum and Goran Konjevod and R. Ravi and Santosh Vempala Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems . . . . . . . . . . . . . . . . 25--42 Joan Boyar and René Peralta and Denis Pochuev On the multiplicative complexity of Boolean functions over the basis (,,1) 43--57 Harry Buhrman and Tao Jiang and Ming Li and Paul Vitányi New applications of the incompressibility method: Part II . . . 59--70 Peter Bürgisser Cook's versus Valiant's hypothesis . . . 71--88 Bruno Codenotti and Pavel Pudlák and Giovanni Resta Some structural properties of low-rank matrices related to computational complexity . . . . . . . . . . . . . . . 89--107 Jeff Edmonds Scheduling in the dark . . . . . . . . . 109--141 Leonid A. Levin Self-stabilization of circular arrays of automata . . . . . . . . . . . . . . . . 143--144 J. Maurice Rojas Uncomputably large integral points on algebraic plane curves? . . . . . . . . 145--162 Joseph H. Silverman On the distribution of integer points on curves of genus zero . . . . . . . . . . 163--170 Fangmin Song and Yongsen Xu and Yuechen Qian The self-reduction in lambda calculus 171--181 A. N. Trahtman Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order 183--204 Vijay V. Vazirani Recent results on approximating the Steiner tree problem and its generalizations . . . . . . . . . . . . 205--216
Anonymous Editorial(s) . . . . . . . . . . . . . . 217--217 Hiroshi Era and Kenjiro Ogawa and Morimasa Tsuchiya On upper bound graphs with respect to operations on graphs . . . . . . . . . . 219--223 Masahiro Hachimori Constructible complexes and recursive division of posets . . . . . . . . . . . 225--237 Kenji Kashiwabara Extremality of submodular functions . . 239--256 Toru Kojima and Kiyoshi Ando Wide-diameter and minimum length of fan 257--266 Hiroshi Maehara Can a convex polyhedron have a developable face-cycle? . . . . . . . . 267--270 Tomoki Nakamigawa A generalization of diagonal flips in a convex polygon . . . . . . . . . . . . . 271--282 Michio Ozeki On covering radii and coset weight distributions of extremal binary self-dual codes of length 40 . . . . . . 283--308 Tadashi Sakuma Forced color classes, intersection graphs and the strong perfect graph conjecture . . . . . . . . . . . . . . . 309--324 Kokichi Sugihara Three-dimensional convex hull as a fruitful source of diagrams . . . . . . 325--337 Akihisa Tamura Perfect $ (0, \pm 1)$-matrices and perfect bidirected graphs . . . . . . . 339--356 Anonymous Index . . . . . . . . . . . . . . . . . 357--358
M. Dauchet Trees in Algebra and Programming . . . . 1--1 Egidio Astesiano and Gianna Reggio Formalism and method . . . . . . . . . . 3--34 Adel Bouhoula and Jean-Pierre Jouannaud and José Meseguer Specification and proof in membership equational logic . . . . . . . . . . . . 35--132 Thomas Arts and Jürgen Giesl Termination of term rewriting using dependency pairs . . . . . . . . . . . . 133--178 Anders Dessmark and Andrzej Lingas and Andrzej Proskurowski Maximum packing for $k$-connected partial $k$-trees in polynomial time . . 179--191 Daniel Leivant and Jean-Yves Marion A characterization of alternating log time by ramified recurrence . . . . . . 193--208 Toshiyuki Yamada and Jürgen Avenhaus and Carlos Loría-Sáenz and Aart Middeldorp Logicality of conditional rewrite systems . . . . . . . . . . . . . . . . 209--232 Anonymous Index . . . . . . . . . . . . . . . . . 233--233
Bruno Courcelle The monadic second-order logic of graphs XII: planar graphs and planar maps . . . 1--32 Yongge Wang Resource bounded randomness and computational complexity . . . . . . . . 33--55 Francesco Mario Malvestuto and Marina Moscarini Decomposition of a hypergraph by partial-edge separators . . . . . . . . 57--79 Jean-Camille Birget Reductions and functors from problems to word problems . . . . . . . . . . . . . 81--104 Petra Schuurman and Gerhard J. Woeginger A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem . . . . . . . . . . . . . . 105--122 Paola Alimonti and Viggo Kann Some APX-completeness results for cubic graphs . . . . . . . . . . . . . . . . . 123--134 Niculae Mandache On the computational power of context-free PC grammar systems . . . . 135--148 Andries van der Walt and Sigrid Ewert A shrinking lemma for random forbidding context languages . . . . . . . . . . . 149--158 Viliam Geffert and Jyrki Katajainen and Tomi Pasanen Asymptotically efficient in-place merging . . . . . . . . . . . . . . . . 159--181 Changwook Kim and Ivan Hal Sudborough Leftmove-bounded picture languages . . . 183--195 Rimli Sengupta and H. Venkateswaran Non-cancellative Boolean circuits: A generalization of monotone Boolean circuits . . . . . . . . . . . . . . . . 197--212 Siu-Wing Cheng The Steiner tree problem for terminals on the boundary of a rectilinear polygon 213--238 Jean Senellart Fast pattern matching in indexed texts 239--262 Alberto Apostolico and Valentin E. Brimkov Fibonacci arrays and their two-dimensional repetitions . . . . . . 263--273 Cristopher Moore and James P. Crutchfield Quantum automata and quantum grammars 275--306 Petr K\rurka and Alejandro Maass Realtime subshifts . . . . . . . . . . . 307--325 Chung Keung Poon A space lower bound for st-connectivity on node-named JAGs . . . . . . . . . . . 327--345 K. Lodaya and P. Weil Series-parallel languages and the bounded-width property . . . . . . . . . 347--380 Hiroaki Tohyama and Akeo Adachi Complexity of path discovery game problems . . . . . . . . . . . . . . . . 381--406 U. K. Sarkar On the design of a constructive algorithm to solve the multi-peg towers of Hanoi problem . . . . . . . . . . . . 407--421 Alexander Meduna Terminating left-hand sides of scattered context productions M. Nivat . . . . . . 423--427 Janos Simon and Shi-Chun Tsai On the bottleneck counting argument . . 429--437 James A. Anderson The intersection of retracts of A * . . 439--445 B. Litow On Hadamard square roots of unity . . . 447--454 Gonzalo Navarro Improved approximate pattern matching on hypertext . . . . . . . . . . . . . . . 455--463 Viliam Geffert A variant of inductive counting . . . . 465--475 Satyanarayana V. Lokam On the rigidity of Vandermonde matrices 477--483 Kazuo Iwama and Yahiko Kambayashi and Kazuya Takaki Tight bounds on the number of states of DFAs that are equivalent to $n$-state NFAs . . . . . . . . . . . . . . . . . . 485--494 Anonymous Index . . . . . . . . . . . . . . . . . 499--500
V. Sabelfeld The tree equivalence of linear recursion schemes . . . . . . . . . . . . . . . . 1--29 Prakash Panangaden and Clark Verbrugge Generating irregular partitionable data structures . . . . . . . . . . . . . . . 31--80 Markus Roggenbach and Mila Majster-Cederbaum Towards a unified view of bisimulation: a comparative study . . . . . . . . . . 81--130 Michael Codish and Vitaly Lagoon Type dependencies for logic programs using ACI-unification . . . . . . . . . 131--159 Ludwik Czaja Process languages and nets . . . . . . . 161--181 Delia Kesner Confluence of extensional and non-extensional $ \lambda $-calculi with explicit substitutions . . . . . . . . . 183--220 Giuliano Pacini and Maria I. Sessa Loop checking in SLD-derivations by well-quasi-ordering of goals . . . . . . 221--246 Sándor Vágvölgyi Congruential complements of ground term rewrite systems . . . . . . . . . . . . 247--274 Wim H. Hesselink and Albert Thijs Fixpoint semantics and simulation . . . 275--311 Michele Boreale and Luca Trevisan A complexity analysis of bisimilarity for value-passing processes . . . . . . 313--345 P. Savický and S.\vZák A read-once lower bound and a (1,+ k )-hierarchy for branching programs . . . 347--362 Ines Margaria and Maddalena Zacchi Generalized filter models . . . . . . . 363--387 Rocco De Nicola and Rosario Pugliese Linda-based applicative and imperative process algebras . . . . . . . . . . . . 389--437 Joost-Pieter Katoen and Albert Nymeyer Pattern-matching algorithms based on term rewrite systems . . . . . . . . . . 439--464 Mingsheng Ying Weak confluence and $ \tau $-inertness 465--475 Noriko H. Arai No feasible monotone interpolation for simple combinatorial reasoning . . . . . 477--482 Holger Naundorf Strictly causal functions have a unique fixed point . . . . . . . . . . . . . . 483--488 Ph. Besnard and T. Schaub What is a (non-constructive) non-monotone logical system? . . . . . . 489--494 P. Savický and Ji\vrí Sgall DNF tautologies with a limited number of occurrences of every variable . . . . . 495--498 Anonymous Index . . . . . . . . . . . . . . . . . 499--500
Anonymous Editorial(s) . . . . . . . . . . . . . . 1--2 Manfred Broy Algebraic specification of reactive systems . . . . . . . . . . . . . . . . 3--40 Bart Jacobs Object-oriented hybrid systems of coalgebras plus monoid actions . . . . . 41--95 Irek Ulidowski Finite axiom systems for testing preorder and De Simone process languages 97--139 M. R. K. Krishna Rao Some characteristics of strong innermost normalization . . . . . . . . . . . . . 141--164 E. Pascal Gribomont Simplification of boolean verification conditions . . . . . . . . . . . . . . . 165--185
Foto N. Afrati and Phokion G. Kolaitis Foreword . . . . . . . . . . . . . . . . 187--187 Jeffrey D. Ullman Information integration using logical views . . . . . . . . . . . . . . . . . 189--210 Chandra Chekuri and Anand Rajaraman Conjunctive query containment revisited 211--229 Serge Abiteboul and Victor Vianu Queries and computation on the web . . . 231--255 Jörg Flum and Max Kubierschky and Bertram Ludäscher Games and total Datalog $ \not = $ queries . . . . . . . . . . . . . . . . 257--276 Guozhu Dong and Leonid Libkin and Limsoon Wong Local properties of query languages . . 277--308 Ronald Fagin and Edward L. Wimmers A formula for incorporating weights into scoring rules . . . . . . . . . . . . . 309--338 Anonymous Index . . . . . . . . . . . . . . . . . 339--339
Daniel Le Métayer Foreword . . . . . . . . . . . . . . . . 1--2 M. M. Bonsangue and F. Arbab and J. W. de Bakker and J. J. M. M. Rutten and A. Scutell\`a and G. Zavattaro A transition system semantics for the control-driven coordination language MANIFOLD . . . . . . . . . . . . . . . . 3--47 Nadia Busi and Roberto Gorrieri and Gianluigi Zavattaro Comparing three semantics for Linda-like languages . . . . . . . . . . . . . . . 49--90 Eric J. Hedman and Joost N. Kok and Kaisa Sere Coordinating action systems . . . . . . 91--115 Suresh Jagannathan Continuation-based transformations for coordination languages . . . . . . . . . 117--146 Roberto M. Amadio On modelling mobility . . . . . . . . . 147--176 Luca Cardelli and Andrew D. Gordon Mobile ambients . . . . . . . . . . . . 177--213 Rocco De Nicola and GianLuigi Ferrari and Rosario Pugliese and Betti Venneri Types for access control . . . . . . . . 215--254
Anonymous Editorial(s) . . . . . . . . . . . . . . 255--255 Jin-Yi Cai and D. Sivakumar Resolution of Hartmanis' conjecture for NL-hard sparse sets . . . . . . . . . . 257--269 Vincent Berry and Olivier Gascuel Inferring evolutionary trees with strong combinatorial evidence . . . . . . . . . 271--298 Lin Chen A selected tour of the theory of identification matrices . . . . . . . . 299--318 Rüdiger Reischuk Can large fanin circuits perform reliable computations in the presence of faults? . . . . . . . . . . . . . . . . 319--335 Yuji Kobayashi and Friedrich Otto Repetitiveness of languages generated by morphisms . . . . . . . . . . . . . . . 337--378 Peter Eades and Xuemin Lin Spring algorithms and symmetry . . . . . 379--405 Md. Abul Kashem and Xiao Zhou and Takao Nishizeki Algorithms for generalized vertex-rankings of partial $k$-trees . . 407--427 Sheng-Lung Peng and Chin-Wen Ho and Tsan-sheng Hsu and Ming-Tat Ko and Chuan Yi Tang Edge and node searching problems on trees . . . . . . . . . . . . . . . . . 429--446 A. S. Poulakidas and A. Srinivasan and Ö. E\ugecio\uglu and O. Ibarra and T. Yang Image compression for fast wavelet-based subregion retrieval . . . . . . . . . . 447--469 Thomas Hofmeister and Matthias Krause and Hans U. Simon Contrast-optimal $k$ out of $n$ secret sharing schemes in visual cryptography 471--485 Fred S. Annexstein and Kenneth A. Berman and Tsan-Sheng Hsu and Ram Swaminathan A multi-tree routing scheme using acyclic orientations . . . . . . . . . . 487--494 Anonymous Index . . . . . . . . . . . . . . . . . 495--496 Anonymous Index . . . . . . . . . . . . . . . . . 497--503
Anonymous Editorial(s) . . . . . . . . . . . . . . 1--2 Paul Vitányi A discipline of evolutionary programming 3--23 Philip M. Long Improved bounds about on-line learning of smooth-functions of a single variable 25--35 Eiji Takimoto and Yoshifumi Sakai and Akira Maruoka The learnability of exclusive-or expansions based on monotone DNF formulas . . . . . . . . . . . . . . . . 37--50 V. Arvind and N. V. Vinodchandran Exact learning via teaching assistants 51--81 Atsuyoshi Nakamura Query learning of bounded-width OBDDs 83--114 John Case and Sanjay Jain and Frank Stephan Vacillatory and BC learning on noisy data . . . . . . . . . . . . . . . . . . 115--141 Sanjay Jain and Efim Kinber and Steffen Lange and Rolf Wiehagen and Thomas Zeugmann Learning languages and functions by erasing . . . . . . . . . . . . . . . . 143--189 Takeshi Shinohara and Hiroki Arimura Inductive inference of unbounded unions of pattern languages from positive data 191--209 M. R. K. Krishna Rao Some classes of Prolog programs inferable from positive data . . . . . . 211--234 Anonymous Index . . . . . . . . . . . . . . . . . 235--235
Sarit Kraus and Tatjana Plotkin Algorithms of distributed task allocation for cooperative agents . . . 1--27 Hsien-Kuei Hwang and Bo-Yin Yang and Yeong-Nan Yeh Presorting algorithms: An average-case point of view . . . . . . . . . . . . . 29--40 Klaus Meer Counting problems over the reals . . . . 41--58 Hing Leung and Detlef Wotschke On the size of parsers and LR(k)-grammars . . . . . . . . . . . . . 59--69 Antonín Ku\vcera Effective decomposability of sequential behaviours . . . . . . . . . . . . . . . 71--89 P. Hubert Suites équilibrées . . . . . . . . . . . . 91--108 Donatella Merlini and Renzo Sprugnoli and M. Cecilia Verri Strip tiling and regular grammars . . . 109--124 Priti Shankar and Amitranjan Gantait and A. R. Yuvaraj and Maya Madhavan A new algorithm for linear regular tree pattern matching . . . . . . . . . . . . 125--142 Friedrich Hubalek On the variance of the internal path length of generalized digital trees --- The Mellin convolution approach . . . . 143--168 Martha L. Escobar-Molano and Shahram Ghandeharizadeh On the complexity of coordinated display of multimedia objects . . . . . . . . . 169--197 V. Arvind and N. V. Vinodchandran The counting complexity of group-definable languages . . . . . . . 199--218 Cristian S. Calude and Elena Calude and Bakhadyr Khoussainov Finite nondeterministic automata: Simulation and minimality . . . . . . . 219--235 Samir Khuller and Robert Pless and Yoram J. Sussmann Fault tolerant $K$-center problems . . . 237--245 J.-C. Birget and S. Margolis and J. Meakin and P. Weil PSPACE-complete problems for subgroups of free groups and inverse finite automata . . . . . . . . . . . . . . . . 247--281 Drew Vandeth Sturmian words and words with a critical exponent . . . . . . . . . . . . . . . . 283--300 Martin Mundhenk On hard instances . . . . . . . . . . . 301--311 Conrado Martínez and Salvador Roura On the competitiveness of the move-to-front rule . . . . . . . . . . . 313--325 Lucian Ilie On lengths of words in context-free languages . . . . . . . . . . . . . . . 327--359 Pascal Caron Families of locally testable languages 361--376 Biing-Feng Wang Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences . . . . . . . . . . 377--401 Gennady S. Makanin and Tatiana A. Makanina Parametrisation of solutions of parametric equation in free monoid . . . 403--475 Pál Gyenizse and Sándor Vágvölgyi A property of left-linear rewrite systems preserving recognizability . . . 477--498 Anonymous Index . . . . . . . . . . . . . . . . . 499--500
Józef Winkowski Processes of timed Petri nets . . . . . 1--34 Roberto De Prisco and Butler Lampson and Nancy Lynch Revisiting the PAXOS algorithm . . . . . 35--91 Peter Padawitz Swinging types=functions+relations+transition systems . . . . . . . . . . . . . . . . 93--165 Anatoli Degtyarev and Yuri Gurevich and Paliath Narendran and Margus Veanes and Andrei Voronkov Decidability and complexity of simultaneous rigid $E$-unification with one variable and related results . . . . 167--184 Noriko H. Arai Tractability of Cut-free Gentzen-type propositional calculus with permutation inference II . . . . . . . . . . . . . . 185--197 Jonathan P. Seldin A Gentzen-style sequent calculus of constructions with expansion rules . . . 199--215 Shlomo Moran and Sagi Snir Simple and efficient network decomposition and synchronization . . . 217--241 Rida A. Bazzi Planar quorums . . . . . . . . . . . . . 243--268 K. B. Lakshmanan and Daniel J. Rosenkrantz and S. S. Ravi Alarm placement in systems with fault propagation . . . . . . . . . . . . . . 269--288 Lefteris M. Kirousis and Evangelos Kranakis and Danny Krizanc and Andrzej Pelc Power consumption in packet radio networks . . . . . . . . . . . . . . . . 289--305 Yuh-Jzer Joung Two decentralized algorithms for strong interaction fairness for systems with unbounded speed variability . . . . . . 307--338 David Meier and Beverly Sanders Composing leads-to properties . . . . . 339--361 Juan A. Garay and Rosario Gennaro and Charanjit Jutla and Tal Rabin Secure distributed storage and retrieval 363--389 Wan Fokkink Language preorder as a precongruence . . 391--408 Tuomas Aura and Johan Lilius A causal semantics for time Petri nets 409--447 Qing Zhou Grzegorczyk's hierarchy of computable analysis . . . . . . . . . . . . . . . . 449--466 A. Rabinovich Symbolic model checking for $ \mu $-calculus requires exponential time . . 467--475 Fabio Massacci The proof complexity of analytic and clausal tableaux . . . . . . . . . . . . 477--487 Alfons Geser On normalizing, non-terminating one-rule string rewriting systems . . . . . . . . 489--498 Anonymous Index . . . . . . . . . . . . . . . . . 499--499
Joachim Apel Computational ideal theory in finitely generated extension rings . . . . . . . 1--33 Jung-Heum Park and Kyung-Yong Chwa Recursive circulants and their embeddings among hypercubes . . . . . . 35--62 Bruno Courcelle The monadic second-order logic of graphs XIII: Graph drawings with edge crossings 63--94 Oya Ekin and Peter L. Hammer and Alexander Kogan Convexity and logical analysis of data 95--116 Juha Honkala On D0L power series . . . . . . . . . . 117--134 Matthias Ott and Frank Stephan Structural measures for games and process control in the branch learning model . . . . . . . . . . . . . . . . . 135--165 Hans L. Bodlaender and Michael R. Fellows and Michael T. Hallett and H. Todd Wareham and Tandy J. Warnow The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs . . . . 167--188 Peter Jonsson Boolean constraint satisfaction: complexity results for optimization problems with arbitrary weights . . . . 189--203 Lane A. Hemaspaandra and Jörg Rothe A second step towards complexity-theoretic analogs of Rice's Theorem . . . . . . . . . . . . . . . . 205--217 Gianpiero Cattaneo and Michele Finelli and Luciano Margara Investigating topological chaos by elementary cellular automata dynamics 219--241 Zsuzsanna Róka The firing squad synchronization problem on Cayley graphs . . . . . . . . . . . . 243--256 Lane A. Hemaspaandra and Jörg Rothe Characterizing the existence of one-way permutations . . . . . . . . . . . . . . 257--261 Eric Kern and Maurice Mignotte Applications of the representation of finite fields by matrices . . . . . . . 263--265 Juha Honkala A short solution for the HDT0L sequence equivalence problem . . . . . . . . . . 267--270 Michel Rigo Generalization of automatic sequences for numeration systems on a regular language . . . . . . . . . . . . . . . . 271--281 Dieter van Melkebeek The zero-one law holds for BPP . . . . . 283--288 Jozef Kelemen and Alica Kelemenová and Carlos Martín-Vide and Victor Mitrana Colonies with limited activation of components . . . . . . . . . . . . . . . 289--298 Anonymous Index . . . . . . . . . . . . . . . . . 299--299
Masami Ito and Chrystopher L. Nehaniv Foreword . . . . . . . . . . . . . . . . 1--1 J. A. Brzozowski Delay-insensitivity and ternary simulation . . . . . . . . . . . . . . . 3--25 Pál Dömösi and Chrystopher L. Nehaniv On complete systems of automata . . . . 27--54 Joseph Goguen and Grant Malcolm A hidden agenda . . . . . . . . . . . . 55--101 B. Imreh On the equivalence of the cube-product and the general product of automata . . 103--113 Masami Ito and Lila Kari and Gabriel Thierrin Shuffle and scattered deletion closure of languages . . . . . . . . . . . . . . 115--133 Alexis Maciel and Pierre Péladeau and Denis Thérien Programs over semigroups of dot-depth one . . . . . . . . . . . . . . . . . . 135--148
Bogdan S. Chlebus and Artur Czumaj and Leszek G\casieniec and Miros\law Kowaluk and Wojciech Plandowski Algorithms for the parallel alternating direction access machine . . . . . . . . 151--173 Brigitte Oesterdiekhoff Periodic comparator networks . . . . . . 175--202 Guillaume Fertin On the structure of minimum broadcast digraphs . . . . . . . . . . . . . . . . 203--216 Cyril Gavoille A survey on interval routing . . . . . . 217--253 Peter Ru\vzi\vcka and Daniel\vStefankovi\vc On the complexity of multi-dimensional interval routing schemes . . . . . . . . 255--280 Farhad Shahrokhi and Ondrej Sýkora and László A. Székely and Imrich Vrt'o A new lower bound for the bipartite crossing number with applications . . . 281--294 Anonymous Index . . . . . . . . . . . . . . . . . 295--295
Frank Drewes Tree-based picture generation . . . . . 1--51 Frank Nielsen Fast stabbing of boxes in high dimensions . . . . . . . . . . . . . . . 53--72 Reneta P. Barneva and Valentin E. Brimkov and Philippe Nehlig Thin discrete triangular meshes . . . . 73--105 Toshihiro Fujito Approximating minimum feedback vertex sets in hypergraphs . . . . . . . . . . 107--116 Jérôme O. Durand-Lose Reversible space-time simulation of cellular automata . . . . . . . . . . . 117--129 T. Y. Nishida and S. Seki Grouped partial ET0L systems and parallel multiple context-free grammars 131--150 Didier Arqu\`es and Jean-François Béraud Le Schéma de carte et ses applications. (French) [The sketch of a map and its applications] . . . . . . . . . . . . . 151--194 J. W. Sander and R. Tijdeman The complexity of functions on lattices 195--225 Yih-Kai Lin and Kuo-Liang Chung A space-efficient Huffman decoding algorithm and its parallelism . . . . . 227--238 Zhen Liu Dynamic scheduling of parallel computations . . . . . . . . . . . . . . 239--252 Pedro García and José Ruiz Right and left locally testable languages . . . . . . . . . . . . . . . 253--264 Martin Dyer and Catherine Greenhill Polynomial-time counting and sampling of two-rowed contingency tables . . . . . . 265--278 Alexander Meduna Generative power of three-nonterminal scattered context grammars . . . . . . . 279--284 Cunsheng Ding and David R. Kohel and San Ling Secret-sharing with a class of ternary codes . . . . . . . . . . . . . . . . . 285--298 Anonymous Index . . . . . . . . . . . . . . . . . 299--299
Manfred Droste and Paul Gastin and Dietrich Kuske Asynchronous cellular automata for pomsets . . . . . . . . . . . . . . . . 1--38 Thomas Ehrhard Parallel and serial hypercoherences . . 39--81 Ian Mackie Interaction nets for linear logic . . . 83--140 Catherine Oriat Detecting equivalence of modular specifications with categorical diagrams 141--190 Zoran Ognjanovic and Miodrag Ra\vskovic Some first-order probability logics . . 191--212 Yefim Dinitz and Tamar Eilam and Shlomo Moran and Shmuel Zaks On the total $k$-diameter of connection networks . . . . . . . . . . . . . . . . 213--228 Jens Blanck Domain representations of topological spaces . . . . . . . . . . . . . . . . . 229--255 Rym Mili and Jules Desharnais and Marc Frappier and Ali Mili Semantic distance between specifications 257--276 Sabine Broda and Luís Damas On principal types of combinators . . . 277--290 Wim H. Hesselink A generalization of Naundorf's fixpoint theorem . . . . . . . . . . . . . . . . 291--296 Anonymous Index . . . . . . . . . . . . . . . . . 299--299
Charles Consel Foreword . . . . . . . . . . . . . . . . 1--2 Luke Hornof and Jacques Noyé Accurate binding-time analysis for imperative languages: flow, context, and return sensitivity . . . . . . . . . . . 3--27 David Melski and Thomas Reps Interconvertibility of a class of set constraints and context-free-language reachability . . . . . . . . . . . . . . 29--98 Rogardt Heldal and John Hughes Extending a partial evaluator which supports separate compilation . . . . . 99--145 Brian Grant and Markus Mock and Matthai Philipose and Craig Chambers and Susan J. Eggers DyC: an expressive annotation-directed dynamic compiler for C . . . . . . . . . 147--199 Gilles Muller and Renaud Marlet and Eugen-Nicolae Volanschi Accurate program analyses for successful specialization of legacy system software 201--210 Walid Taha and Tim Sheard MetaML and multi-stage programming with explicit annotations . . . . . . . . . . 211--242 Olivier Danvy and Ulrik P. Schultz Lambda-dropping: transforming recursive equations into programs with block structure . . . . . . . . . . . . . . . 243--287 Anonymous Index . . . . . . . . . . . . . . . . . 289--289
Klaus Keimel and Michael Mislove and Constantine Tsinakis Foreword . . . . . . . . . . . . . . . . 1--1 J. J. M. M. Rutten Universal coalgebra: a theory of systems 3--80 Chantal Berline From computation to foundations via functions and application: The $ \lambda $-calculus and its webbed models . . . . 81--161 Frank J. Oles An application of lattice theory to knowledge representation . . . . . . . . 163--196 Antonino Salibra On the algebraic models of lambda calculus . . . . . . . . . . . . . . . . 197--240
Costas S. Iliopoulos Preface . . . . . . . . . . . . . . . . 241--241 Paul E. Dunne and Alan Gibbons and Michele Zito Complexity-theoretic models of phase transitions in search problems . . . . . 243--263 Aviezri S. Fraenkel Recent results and questions in combinatorial game complexities . . . . 265--288 Franti\vsek Fran\vek and Ay\cse Karaman and W. F. Smyth Repetitions in Sturmian strings . . . . 289--303 Jan Holub and Bo\vrivoj Melichar Approximate string matching using factor automata . . . . . . . . . . . . . . . . 305--311 Laurent Mouchard Normal forms of quasiperiodic strings 313--324 S. Ravindran and A. M. Gibbons and M. S. Paterson Dense edge-disjoint embedding of complete binary trees in interconnection networks . . . . . . . . . . . . . . . . 325--342 W. F. Smyth Repetitive perhaps, but certainly not boring . . . . . . . . . . . . . . . . . 343--355 Sanming Zhou Bounding the bandwidths for graphs . . . 357--368 Anonymous Index . . . . . . . . . . . . . . . . . 369--369
Ina Koch Enumerating all connected maximal common subgraphs in two graphs . . . . . . . . 1--30 Joanna J\cedrzejowicz and Andrzej Szepietowski Shuffle languages are in P . . . . . . . 31--53 Satoshi Okawa and Sadaki Hirose Homomorphic characterizations of recursively enumerable languages with very small language classes . . . . . . 55--69 Christophe Prieur How to decide continuity of rational functions on infinite words . . . . . . 71--82 S. Caporaso and M. Zito and N. Galesi A predicative and decidable characterization of the polynomial classes of languages . . . . . . . . . . 83--99 Wolfgang Merkle Structural properties of bounded relations with an application to NP optimization problems . . . . . . . . . 101--124 Jean R. S. Blair and Pinar Heggernes and Jan Arne Telle A practical algorithm for making filled graphs minimal . . . . . . . . . . . . . 125--141 Giuseppe Ateniese and Carlo Blundo and Alfredo De Santis and Douglas R. Stinson Extended capabilities for visual cryptography . . . . . . . . . . . . . . 143--161 Valeria Mihalache and Arto Salomaa Language-theoretic aspects of DNA complematarity . . . . . . . . . . . . . 163--178 Judit Bar-Ilan and Guy Kortsarz and David Peleg Generalized submodular cover problems and applications . . . . . . . . . . . . 179--200 Paolo Giulio Franciosa and Daniele Frigioni and Roberto Giaccio Semi-dynamic breadth-first search in digraphs . . . . . . . . . . . . . . . . 201--217 Z. Fülöp and S. Vágvölgyi Restricted ground tree transducers . . . 219--233 Gerth Stòting Brodal and M. Cristina Pinotti Comparator networks for binary heap construction . . . . . . . . . . . . . . 235--245 Changwook Kim Double Greibach operator grammars . . . 247--264 S. Labhalla and H. Lombardi and E. Moutai Espaces métriques rationnellement présentés et complexité, le cas de l'espace des fonctions réelles uniformément continues sur un intervalle compact . . . . . . . 265--332 Timo Knuutila Re-describing an algorithm by Hopcroft 333--363 Colin M. Campbell and Edmund F. Robertson and Nikola Ru\vskuc and Richard M. Thomas Automatic semigroups . . . . . . . . . . 365--391 Anonymous Index . . . . . . . . . . . . . . . . . 393--394 Anonymous Index . . . . . . . . . . . . . . . . . 395--401 Giorgio Ausiello and Donald Sannella and Michael Mislove 25 Years . . . . . . . . . . . . . . . . xv--xvi Maurice Nivat 25 Years . . . . . . . . . . . . . . . . xi--xiii
Géraud Sénizergues $ L(A) = L(B) $? decidability results from complete formal systems . . . . . . 1--166 Anonymous Index . . . . . . . . . . . . . . . . . 167--167
H. Jaap van den Herik and Hiroyuki Iida Foreword . . . . . . . . . . . . . . . . 1--3 Aviezri S. Fraenkel and Dmitri Zusman A new heap game . . . . . . . . . . . . 5--12 Aviezri S. Fraenkel and Ofer Rahat Infinite cyclic impartial games . . . . 13--22 William L. Spight Extended thermography for multiple kos in go . . . . . . . . . . . . . . . . . 23--43 Steven Willmott and Julian Richardson and Alan Bundy and John Levine Applying adversarial planning techniques to Go . . . . . . . . . . . . . . . . . 45--82 Xinbo Gao and Hiroyuki Iida and Jos W. H. M. Uiterwijk and H. Jaap van den Herik Strategies anticipating a difference in search depth using opponent-model search 83--104 Donald F. Beal and Martin C. Smith Temporal difference learning applied to game playing and the results of application to shogi . . . . . . . . . . 105--119 Dennis M. Breuker and H. Jaap van den Herik and Jos W. H. M. Uiterwijk and L. Victor Allis A solution to the GHI problem for best-first search . . . . . . . . . . . 121--149 Andreas Junghanns and Jonathan Schaeffer Sokoban: improving the search with relevance cuts . . . . . . . . . . . . . 151--175 Yngvi Björnsson and Tony A. Marsland Multi-cut $ \alpha, \beta $-pruning in game-tree search . . . . . . . . . . . . 177--196 Wim Pijls and Arie de Bruin Game tree algorithms and solution trees 197--215 Ian Frank and David Basin A theoretical and empirical investigation of search in imperfect information games . . . . . . . . . . . 217--256 Anonymous Index . . . . . . . . . . . . . . . . . 257--257
Miquel Bertran and Teodor Rus Preface . . . . . . . . . . . . . . . . 1--1 Manfred Broy Refinement of time . . . . . . . . . . . 3--26 Nikolaj S. Bjòrner and Zohar Manna and Henny B. Sipma and Tomás E. Uribe Deductive verification of real-time systems using STeP . . . . . . . . . . . 27--60 Henning Dierks PLC-automata: a new class of implementable real-time automata . . . . 61--93 Sérgio Vale Aguiar Campos and Edmund Clarke The Verus language: representing time efficiently with BDDs . . . . . . . . . 95--118 Zhiming Liu and Mathai Joseph Verification, refinement and scheduling of real-time programs . . . . . . . . . 119--152
Laura Recalde and Enrique Teruel and Manuel Silva Structure theory of multi-level deterministically synchronized sequential processes . . . . . . . . . . 1--33 Anna Ingólfsdóttir and Andrea Schalk A fully abstract denotational model for observational precongruence . . . . . . 35--61 François Monin and Marianne Simonot An ordinal measure based procedure for termination of functions . . . . . . . . 63--94 Pedro Resende Quantales, finite observations and strong bisimulation . . . . . . . . . . 95--149 Tristan Crolard Subtractive logic . . . . . . . . . . . 151--185 R. Ramesh and I. V. Ramakrishnan and R. C. Sekar Automata-driven efficient subterm unification . . . . . . . . . . . . . . 187--223 Jan Springintveld and Frits Vaandrager and Pedro R. D'Argenio Testing timed automata . . . . . . . . . 225--257 Christophe Raffalli Completeness, minimal logic and programs extraction . . . . . . . . . . . . . . . 259--271 Salvatore Ruggieri $ \exists $-Universal termination of logic programs . . . . . . . . . . . . . 273--296 Rachid Guerraoui and André Schiper Genuine atomic multicast in asynchronous distributed systems . . . . . . . . . . 297--316 Stefano Guerrini and Andrea Masini Parsing MELL proof nets . . . . . . . . 317--335 Xiao Jun Chen and Rocco De Nicola Algebraic characterizations of trace and decorated trace equivalences over tree-like structures . . . . . . . . . . 337--361 Jan Van den Bussche Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions 363--377 Lars Jenner and Walter Vogler Fast asynchronous systems in dense time 379--422 Luc Vandeurzen and Marc Gyssens and Dirk Van Gucht On the expressiveness of linear-constraint query languages for spatial databases . . . . . . . . . . . 423--463 Konstantinos Sagonas and Terrance Swift and David S. Warren The limits of fixed-order computation 465--499 Joost-Pieter Katoen and Christel Baier and Diego Latella Metric semantics for true concurrent real time . . . . . . . . . . . . . . . 501--542 Marcelo F. Frias and Roger D. Maddux Completeness of a relational calculus for program schemes . . . . . . . . . . 543--556 B. Thomsen and S. Abramsky A fully abstract denotational semantics for the calculus of higher-order communicating systems . . . . . . . . . 557--589 Paul Spruit and Roel Wieringa and John-Jules Meyer Regular database update logics . . . . . 591--661 P. Rondogiannis Stratified negation in temporal logic programming and the cycle-sum test . . . 663--676 Dieter Probst and Thomas Studer How to normalize the Jay . . . . . . . . 677--681 Mark Levene and George Loizou Guaranteeing no interaction between functional dependencies and tree-like inclusion dependencies . . . . . . . . . 683--690 Marco Bernardo and Roberto Gorrieri Corrigendum to ``A tutorial on EMPA: a theory of concurrent processes with nondeterminism, priorities, probabilities and time'' --- [Theoret. Comput. Sci. 202 (1998) 1--54] . . . . . 691--694 Anonymous Author index volume 254 (2001) . . . . . 699--700
Colin Stirling Decidability of DPDA equivalence . . . . 1--31 Thomas Erlebach and Klaus Jansen The complexity of path coloring and call scheduling . . . . . . . . . . . . . . . 33--50 Srinivasa R. Arikati and Anders Dessmark and Andrzej Lingas and Madhav V. Marathe Approximation algorithms for maximum two-dimensional pattern matching . . . . 51--62 Ivo Düntsch and Hui Wang and Steve McCloskey A relation-algebraic approach to the region connection calculus . . . . . . . 63--83 S. S. Yu Post-plus languages . . . . . . . . . . 85--105 Sanjay Jain Branch and bound on the network model 107--123 Cristian S. Calude and Peter H. Hertling and Bakhadyr Khoussainov and Yongge Wang Recursively enumerable reals and Chaitin $ \Omega $ numbers . . . . . . . . . . . 125--149 Jean Néraud and Carla Selmi On codes with a finite deciphering delay: constructing uncompletable words 151--162 Dietmar Wätjen Parallel communicating limited and uniformly limited 0L systems . . . . . . 163--191 Vesa Halava and Mika Hirvensalo and Ronald de Wolf Marked PCP is decidable . . . . . . . . 193--204 V. Arvind and Johannes Köbler On pseudorandomness and resource-bounded measure . . . . . . . . . . . . . . . . 205--221 Olivier Finkel Locally finite languages . . . . . . . . 223--261 Tiziana Calamoneri and Annalisa Massini Optimal three-dimensional layout of interconnection networks . . . . . . . . 263--279 Tomás Feder Fanout limitations on constraint systems 281--293 B. Apolloni and D. Malchiodi Gaining degrees of freedom in subsymbolic learning . . . . . . . . . . 295--321 Luis-Miguel Lopez and Philippe Narbel Substitutions and interval exchange transformations of rotation class . . . 323--344 Jean-Guy Penaud and Elisa Pergola and Renzo Pinzani and Olivier Roques Chemins de Schröder et hiérarchies aléatoires. (French). [Schröder paths and aleatory hierarchies] . . . . . . . . . 345--361 Jacques Justin and Giuseppe Pirillo Fractional powers in Sturmian words . . 363--376 George Rahonis Alphabetic and synchronized tree transducers . . . . . . . . . . . . . . 377--399 Jukka A. Koskinen Non-injective knapsack public-key cryptosystems . . . . . . . . . . . . . 401--422 Paul F. Fischer and Franco P. Preparata and John E. Savage Generalized scans and tridiagonal systems . . . . . . . . . . . . . . . . 423--436 C. Picouleau Reconstruction of domino tiling from its two orthogonal projections . . . . . . . 437--447 Guohua Jin and Zhiyuan Li and Fujie Chen A theoretical foundation for program transformations to reduce cache thrashing due to true data sharing . . . 449--481 Sabrina Mantaci and Antonio Restivo Codes and equations on trees . . . . . . 483--509 Erzsébet Csuhaj-Varjú and György Vaszil On context-free parallel communicating grammar systems: synchronization, communication, and normal forms . . . . 511--538 Xavier Droubay and Jacques Justin and Giuseppe Pirillo Episturmian words and some constructions of de Luca and Rauzy . . . . . . . . . . 539--553 Guoliang Xue A cost optimal parallel algorithm for computing force field in $N$-body simulations on a CREW PRAM . . . . . . . 555--568 Jorge Almeida and Pedro V. Silva SC-hyperdecidability of $R$ . . . . . . 569--591 Felipe Cucker On weak and weighted computations over the real closure of $Q$ . . . . . . . . 593--600 Roberto Incitti The growth function of context-free languages . . . . . . . . . . . . . . . 601--605 Hervé Fournier Sparse NP-complete problems over the reals with addition . . . . . . . . . . 607--610 Olga Sokratova The Mal'cev Lemma and rewriting on semirings . . . . . . . . . . . . . . . 611--614 M. Nikolskaia and L. Nikolskaia Size of OBDD representation of $2$-level redundancies functions . . . . . . . . . 615--625 Subhas C. Nandy and Tomohiro Harayama and Tetsuo Asano Dynamically maintaining the widest $k$-dense corridor . . . . . . . . . . . 627--639 S. Ravi Kumar and D. Sivakumar On the unique shortest lattice vector problem . . . . . . . . . . . . . . . . 641--648 Yu-Wei Chen and Kuo-Liang Chung Improved fault-tolerant sorting algorithm in hypercubes . . . . . . . . 649--658 Chiuyuan Chen and Kaiping Wu Disproving a conjecture on planar visibility graphs . . . . . . . . . . . 659--665 Juha Honkala On Parikh slender context-free languages 667--677 E. Barcucci and S. Rinaldi Some linear recurrences and their combinatorial interpretation by means of regular languages . . . . . . . . . . . 679--686 Vincent D. Blondel and Olivier Bournez and Pascal Koiran and Christos H. Papadimitriou and John N. Tsitsiklis Deciding stability and mortality of piecewise affine dynamical systems . . . 687--696 A. N. Trahtman Erratum to ``Optimal estimation on the order of local testability of finite automata'' --- [Theoret. Comput. Sci. 231 (2000) 59--74] . . . . . . . . . . . 697--697 Anonymous Author index volume 255 (2001) . . . . . 699--700
Ahmed Bouajjani Preface . . . . . . . . . . . . . . . . 1--2 Yoram Hirshfeld and Faron Moller Pushdown automata, multiset automata, and Petri nets . . . . . . . . . . . . . 3--21 Petr Jan\vcar Nonprimitive recursive complexity and undecidability for Petri net equivalences . . . . . . . . . . . . . . 23--30 Richard Mayr Decidability of model checking with the temporal logic EF . . . . . . . . . . . 31--62 A. Finkel and Ph. Schnoebelen Well-structured transition systems everywhere! . . . . . . . . . . . . . . 63--92 Y. Kesten and O. Maler and M. Marcus and A. Pnueli and E. Shahar Symbolic model checking with rich assertional languages . . . . . . . . . 93--112 David Lesens and Nicolas Halbwachs and Pascal Raymond Automatic verification of parameterized networks of processes . . . . . . . . . 113--144 Parosh Aziz Abdulla and Bengt Jonsson Ensuring completeness of symbolic verification methods for infinite-state systems . . . . . . . . . . . . . . . . 145--167 Anonymous Author index volume 256 (2001) . . . . . 169--169
J.-P. Ressayre Weak Arithmetics . . . . . . . . . . . . 1--15 Denis Richard What are weak arithmetics? . . . . . . . 17--29 Anonymous Conference . . . . . . . . . . . . . . . 31--49 Patrick Cegielski and Denis Richard Decidability of the theory of the natural integers with the Cantor pairing function and the successor . . . . . . . 51--77 C. Dimitracopoulos On end extensions of models of subsystems of Peano arithmetic . . . . . 79--84 J. Duparc and O. Finkel and J.-P. Ressayre Computer science and the fine structure of Borel sets . . . . . . . . . . . . . 85--105 Henri-Alex Esbelin Counting modulo finite semigroups . . . 107--114 Ivan Korec A list of arithmetical structures complete with respect to the first-order definability . . . . . . . . . . . . . . 115--151 Maurice Margenstern On quasi-unilateral universal Turing machines . . . . . . . . . . . . . . . . 153--166 Yuri Matiyasevich Some arithmetical restatements of the Four Color Conjecture . . . . . . . . . 167--183 Olivier Sudac The prime number theorem is PRA-provable 185--239 Olivier Teytaud Decidability of the halting problem for Matiyasevich deterministic machines . . 241--251 Anonymous Author index volume 257 (2001) . . . . . 253--253
Franck van Breugel An introduction to metric semantics: operational and denotational models for programming and specification languages 1--98 Manfred Broy and Gheorghe\cStef\uanescu The algebra of stream processing functions . . . . . . . . . . . . . . . 99--129 Joost Engelfriet and Tjalling Gelsema Structural inclusion in the pi-calculus with replication . . . . . . . . . . . . 131--168 Ken Mano and Mizuhito Ogawa Unique normal form property of compatible term rewriting systems: a new proof of Chew's theorem . . . . . . . . 169--208 Athanassios Tzouvaras Objects and their lambda calculus . . . 209--232 Gaétan Hains and Frédéric Loulergue and John Mullins Concrete data structures and functional parallel programming . . . . . . . . . . 233--267 Giorgio Delzanno and Maurizio Martelli Proofs as computations in linear logic 269--297 Lars Birkedal and Mads Tofte A constraint-based region inference algorithm . . . . . . . . . . . . . . . 299--392 Flavio Corradini and Dino Di Cola On testing urgency through laziness over processes with durational actions . . . 393--407 Petr Jan\vcar and Antonín Ku\vcera and Richard Mayr Deciding bisimulation-like equivalences with finite-state processes . . . . . . 409--433 Bernhard Gramlich On interreduction of semi-complete term rewriting systems . . . . . . . . . . . 435--451 Franck Seynhaeve and Sophie Tison and Marc Tommasi and Ralf Treinen Grid structures and undecidable constraint theories . . . . . . . . . . 453--490 E. Allen Emerson and Charanjit S. Jutla and A. Prasad Sistla On model checking for the $ \mu $-calculus and its fragments . . . . . . 491--522 Stefan Brass and Jürgen Dix and Ilkka Niemelä and Teodor C. Przymusinski On the equivalence of the static and disjunctive well-founded semantics and its computation . . . . . . . . . . . . 523--553 Shashi Shekhar and Weili Wu Optimal placement of data replicas in distributed database with majority voting protocol . . . . . . . . . . . . 555--571 Philippe Darondeau On the Petri net realization of context-free graphs . . . . . . . . . . 573--598 Anonymous Author index volume 258 (2001) . . . . . 599--599
Lothar M. Schmitt Theory of genetic algorithms . . . . . . 1--61 Paola Bonizzoni and Gianluca Della Vedova The complexity of multiple sequence alignment with SP-score that is a metric 63--79 Marek Chrobak and Christoph Dürr Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms . . . . . . . . . 81--98 Maurice Margenstern and Kenichi Morita NP problems are tractable in the space of cellular automata in the hyperbolic plane . . . . . . . . . . . . . . . . . 99--128 Kojiro Kobayashi On time optimal solutions of the firing squad synchronization problem for two-dimensional paths . . . . . . . . . 129--143 Arturo Carpi and Aldo de Luca Words and special factors . . . . . . . 145--182 Ines Klimann New types of automata to solve fixed point problems . . . . . . . . . . . . . 183--197 Paul Trow Determining presentations of sofic shifts . . . . . . . . . . . . . . . . . 199--216 Maria Serna and Fatos Xhafa On the parallel approximability of a subclass of quadratic programming . . . 217--231 Chính T. Ho\`ang and R. Sritharan Finding houses and holes in graphs . . . 233--244 Marie-Andrée Jacob-Da Col Applications quasi-affines et pavages du plan discret . . . . . . . . . . . . . . 245--269 J.-C. Dubacq and B. Durand and E. Formenti Kolmogorov complexity and cellular automata classification . . . . . . . . 271--285 Daniele Frigioni and Alberto Marchetti-Spaccamela and Umberto Nanni Dynamic algorithms for classes of constraint satisfaction problems . . . . 287--305 Andreas Goerdt The giant component threshold for random regular graphs with edge faults . . . . 307--321 Dawei Hong and Jean-Camille Birget Approximation of some NP-hard optimization problems by finite machines, in probability . . . . . . . . 323--339 Paola Bonizzoni and Ross M. McConnell Nesting of prime substructures in $k$-ary relations . . . . . . . . . . . 341--357 Gianluca De Marco and Luisa Gargano and Ugo Vaccaro Concurrent multicast in weighted networks . . . . . . . . . . . . . . . . 359--377 A. Barbé and G. Skordev Decimation-invariant sequences and their automaticity . . . . . . . . . . . . . . 379--403 H. Fernau and M. Holzer and R. Freund Hybrid modes in cooperating distributed grammar systems: internal versus external hybridization . . . . . . . . . 405--426 Susanne Kaufmann and Frank Stephan Robust learning with infinite additional information . . . . . . . . . . . . . . 427--454 John Case and Keh-Jiann Chen and Sanjay Jain Costs of general purpose learning . . . 455--473 Jianliang Xu and Tsunehiro Yoshinaga and Katsushi Inoue and Yue Wang and Akira Ito Alternation for sublogarithmic space-bounded alternating pushdown automata . . . . . . . . . . . . . . . . 475--492 Annalisa De Bonis and Luisa Gargano and Ugo Vaccaro Efficient algorithms for chemical threshold testing problems . . . . . . . 493--511 Guo-Hui Lin and Guoliang Xue Signed genome rearrangement by reversals and transpositions: models and approximations . . . . . . . . . . . . . 513--531 Stephen L. Bloom and Christian Choffrut Long words: the theory of concatenation and omega-power . . . . . . . . . . . . 533--548 David Guijarro and Víctor Lavín and Vijay Raghavan Monotone term decision lists . . . . . . 549--575 M. Aldaz and G. Matera and J. L. Montaña and L. M. Pardo A new method to obtain lower bounds for polynomial evaluation . . . . . . . . . 577--596 V. Arvind and Jacobo Torán A nonadaptive NC checker for permutation group intersection . . . . . . . . . . . 597--611 Dima Grigoriev Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity . . . . . . . . . . . . . . . 613--622 Peter Kirrinnis Fast algorithms for the Sylvester equation $ A X - X B^T = C $ . . . . . . 623--638 Gerald A. Heuer Three-part partition games on rectangles 639--661 Ji\vrí Sgall Solution of David Gale's lion and man problem . . . . . . . . . . . . . . . . 663--670 Anton Stiglic Computations with a deck of cards . . . 671--678 A. Fúster-Sabater and L. J. García-Villalba An efficient algorithm to generate binary sequences for cryptographic purposes . . . . . . . . . . . . . . . . 679--688 Juha Honkala and Arto Salomaa Watson--Crick D0L systems with regular triggers . . . . . . . . . . . . . . . . 689--698 Anonymous Author index volume 259 (2001) . . . . . 699--700
Bart Jacobs and Larry Moss and Horst Reichel and Jan Rutten Foreword . . . . . . . . . . . . . . . . 1--1 Corina C\^\irstea Semantic constructions for the specification of objects . . . . . . . . 3--25 Andrea Corradini and Martin Große-Rhode and Reiko Heckel A coalgebraic presentation of structured transition systems . . . . . . . . . . . 27--55 H. Peter Gumm Equational and implicational classes of coalgebras . . . . . . . . . . . . . . . 57--69 H. Peter Gumm and Tobias Schröder Covarieties and complete covarieties . . 71--86 Peter Johnstone and John Power and Toru Tsujishita and Hiroshi Watanabe and James Worrell On the structure of categories of coalgebras . . . . . . . . . . . . . . . 87--117 Alexander Kurz Specifying coalgebras with modal logic 119--138 Lawrence S. Moss Parametric corecursion . . . . . . . . . 139--163 Alberto Pardo Fusion of recursive programs with computational effects . . . . . . . . . 165--207 Martin Rö From modal logic to terminal coalgebras 209--228 Grigore Ro\csu Equational axiomatizability for coalgebra . . . . . . . . . . . . . . . 229--247 Anonymous Author index volume 260 (2001) . . . . . 249--249 Anonymous Master index volumes 251-260 . . . . . . 251--259
Ming Li Foreword . . . . . . . . . . . . . . . . 1--1 Sanjay Jain and Steffen Lange and Jochen Nessel On the learnability of recursively enumerable languages from good examples 3--29 John Case and Sanjay Jain and Arun Sharma Synthesizing noise-tolerant language learners . . . . . . . . . . . . . . . . 31--56 V. Vovk Probability theory for the Brier game 57--79 Leonid Gurvits A note on a scale-sensitive dimension of linear bounded functionals in Banach spaces . . . . . . . . . . . . . . . . . 81--90 Andris Ambainis and Kalvis Aps\=\itis and R\=usi\cn\vs Freivalds and Carl H. Smith Hierarchies of probabilistic and team FIN-learning . . . . . . . . . . . . . . 91--117 Thomas Erlebach and Peter Rossmanith and Hans Stadtherr and Angelika Steger and Thomas Zeugmann Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries . . . . 119--156 Wolfgang Maass On the relevance of time in neural computation and learning . . . . . . . . 157--178 Eiji Takimoto and Akira Maruoka and Volodya Vovk Predicting nearly as well as the best pruning of a decision tree through dynamic programming scheme . . . . . . . 179--209
Wen-Lian Hsu and Ming-Yang Kao Foreword . . . . . . . . . . . . . . . . 211--211 Fan Chung and Ronald Graham Dynamic location problems with limited look-ahead . . . . . . . . . . . . . . . 213--226 Kazuo Iwama and Eiji Miyano and Satoshi Tajima and Hisao Tamaki Efficient randomized routing algorithms on the two-dimensional mesh of buses . . 227--239 Dongsoo S. Kim and Ding-Zhu Du Multirate multicast switching networks 241--251 Marcos Kiwi and Daniel A. Spielman and Shang-Hua Teng Min-max-boundary domain decomposition 253--266 Alejandro López-Ortiz and Sven Schuierer The ultimate strategy to search on $m$ rays? . . . . . . . . . . . . . . . . . 267--295 Chi-Jen Lu An exact characterization of symmetric functions in $ q A C^0 [2] $ . . . . . . 297--303 Steffen Reith and Klaus W. Wagner On boolean lowness and boolean highness 305--321 Kuo-Hui Tsai and Da-Wei Wang and Frank Hwang Lower bounds for wide-sense nonblocking Clos network . . . . . . . . . . . . . . 323--328 Anonymous Author index volume 261 (2001) . . . . . 333--334
Juraj Hromkovi\vcand Georg Schnitger On the power of Las Vegas II: Two-way finite automata . . . . . . . . . . . . 1--24 \vSt\vepán Holub Local and global cyclicity in free semigroups . . . . . . . . . . . . . . . 25--36 David Lee and Henryk Wo\'zniakowski Approximate evaluations of characteristic polynomials of Boolean functions . . . . . . . . . . . . . . . 37--68 Alberto Bertoni and Marco Carpentieri Analogies and differences between quantum and stochastic automata . . . . 69--81 Donghui Chen and Ding-Zhu Du and Xiao-Dong Hu and Guo-Hui Lin and Lusheng Wang and Guoliang Xue Approximations for Steiner trees with minimum number of Steiner points . . . . 83--99 Ming-Yang Kao and Jie Wang Minimizing roundoff errors of prefix sums via dynamic construction of Huffman trees . . . . . . . . . . . . . . . . . 101--115 Satoshi Kobayashi and Victor Mitrana and Gheorghe P\uaun and Grzegorz Rozenberg Formal properties of PA-matching . . . . 117--131 K. Kalorkoti and D. H. Tulley Priority queues with binary priorities 133--144 Bengt Aspvall and Magnús M. Halldórsson and Fredrik Manne Approximations for the general block distribution of a matrix . . . . . . . . 145--160 Bhaskar DasGupta and Eduardo D. Sontag A polynomial-time algorithm for checking equivalence under certain semiring congruences motivated by the state-space isomorphism problem for hybrid systems 161--189 Oliver Jenkinson Strong cocycle triviality for $ Z^2 $ subshifts . . . . . . . . . . . . . . . 191--213 Sun-Yuan Hsieh and Gen-Huey Chen and Chin-Wen Ho Longest fault-free paths in star graphs with vertex faults . . . . . . . . . . . 215--227 G. Dányi and Z. Fülöp The component hierarchy of chain-free cooperating distributed regular tree grammars . . . . . . . . . . . . . . . . 229--240 Stephen Fenner and Steven Homer and Randall Pruim and Marcus Schaefer Hyper-polynomial hierarchies and the polynomial jump . . . . . . . . . . . . 241--256 Bing Lu and Jun Gu and Xiaodong Hu and Eugene Shragowitz Wire segmenting for buffer insertion based on RSTP-MSP . . . . . . . . . . . 257--267 J.-P. Duval and F. Mignosi and A. Restivo Recurrence and periodicity in infinite words from local periods . . . . . . . . 269--284 Ekkart Kindler and Hagen Völzer Algebraic nets with flexible arcs . . . 285--310 Enno Ohlebusch Implementing conditional term rewriting by graph rewriting . . . . . . . . . . . 311--331 Nguyen Huong Lam Finite maximal solid codes . . . . . . . 333--347 Doris Fiebig and Ulf-Rainer Fiebig and Nata\vsa Jonoska Multiplicities of covers for sofic shifts . . . . . . . . . . . . . . . . . 349--375 Frank Drewes Tree-based generation of languages of fractals . . . . . . . . . . . . . . . . 377--414 Heejin Park and Kunsoo Park Parallel algorithms for red-black trees 415--435 Steven S. Seiden Preemptive multiprocessor scheduling with rejection . . . . . . . . . . . . . 437--458 Siu-Wing Cheng and Yin-Feng Xu Onbeta-skeleton as a subgraph of the minimum weight triangulation . . . . . . 459--471 Dieter Spreen Representations versus numberings: on the relationship of two computability notions . . . . . . . . . . . . . . . . 473--499 Bernd Borchert and Riccardo Silvestri Dot operators . . . . . . . . . . . . . 501--523 Matthieu Latapy and Roberto Mantaci and Michel Morvan and Ha Duong Phan Structure of some sand piles model . . . 525--556 Jeong Seop Sim and Costas S. Iliopoulos and Kunsoo Park and W. F. Smyth Approximate periods of strings . . . . . 557--568 Artur Czumaj and Ian Finch and Leszek G\kasieniec and Alan Gibbons and Paul Leng and Wojciech Rytter and Michele Zito Efficient Web searching using temporal factors . . . . . . . . . . . . . . . . 569--582 Yuji Kobayashi and Masashi Katsura and Kayoko Shikishima-Tsuji Termination and derivational complexity of confluent one-rule string-rewriting systems . . . . . . . . . . . . . . . . 583--632 Yasuhiko Takenaga and Kouji Nakajima and Shuzo Yajima Tree-shellability of Boolean functions 633--647 Jeannette Janssen and Lata Narayanan Approximation algorithms for channel assignment with constraints . . . . . . 649--667 Olivier Finkel Topological properties of omega context-free languages . . . . . . . . . 669--697 Anonymous Author index volume 262 (2001) . . . . . 699--700
Gerard Chang and Michel Deza and Yannis Manoussakis and Jean-Marc Steyaert Preface . . . . . . . . . . . . . . . . 1--1 Hong-Gwa Yeh and Gerard J. Chang Weighted connected $k$-domination and weighted $k$-dominating clique in distance-hereditary graphs . . . . . . . 3--8 Komei Fukuda and Alain Prodon and Tadashi Sakuma Notes on acyclic orientations and the shelling lemma . . . . . . . . . . . . . 9--16 Frank Nielsen On point covers of $c$-oriented polygons 17--29 Philippe Cara and Serge Lehman and Dimitrii V. Pasechnik On the number of inductively minimal geometries . . . . . . . . . . . . . . . 31--35 Dmitrii V. Pasechnik On computing Hilbert bases via the Elliot-MacMahon algorithm . . . . . . . 37--46 Reinhardt Euler Characterizing bipartite Toeplitz graphs 47--58 V. Yegnanarayanan Graph colourings and partitions . . . . 59--74 Yannis Manoussakis and Zsolt Tuza Ramsey numbers for tournaments . . . . . 75--85 Gyula Károlyi and Vera Rosta Generalized and geometric Ramsey numbers for cycles . . . . . . . . . . . . . . . 87--98 Guillaume Damiand and Michel Habib and Christophe Paul A simple paradigm for graph recognition: application to cographs and distance hereditary graphs . . . . . . . . . . . 99--111 Bor-Kuan Lu and Fang-Rong Hsu and Chuan Yi Tang Finding the shortest boundary guard of a simple polygon . . . . . . . . . . . . . 113--121 E. G. Belaga Mod $3$ arithmetic on triangulated Riemann surfaces . . . . . . . . . . . . 123--137 Li-Da Tong and Frank K. Hwang and Gerard J. Chang Channel graphs of bit permutation networks . . . . . . . . . . . . . . . . 139--143 Hsien-Kuei Hwang Uniform asymptotics of some Abel sums arising in coding theory . . . . . . . . 145--158 Eric Angel and Vassilis Zissimopoulos On the landscape ruggedness of the quadratic assignment problem . . . . . . 159--172 Rabah Harbane and Marie-Claude Heydemann Efficient reconfiguration algorithms of de Bruijn and Kautz networks into linear arrays . . . . . . . . . . . . . . . . . 173--189 A. Quilliot Convexity and global optimization: a theoretical link . . . . . . . . . . . . 191--204 Seiya Negami Note on Ramsey theorems for spatial graphs . . . . . . . . . . . . . . . . . 205--210 F. K. Hwang A complementary survey on double-loop networks . . . . . . . . . . . . . . . . 211--229 Bruno Martin A simulation of cellular automata on hexagons by cellular automata on rings 231--234 Patrice Calégari and Frédéric Guidec and Pierre Kuonen and Frank Nielsen Combinatorial optimization algorithms for radio network planning . . . . . . . 235--245 O. Favaron and Y. Redouane Neighborhood unions and regularity in graphs . . . . . . . . . . . . . . . . . 247--254 Cristina Bazgan and Amel Harkat-Benhamdine and Hao Li and Mariusz Wo\'zniak Partitioning vertices of $1$-tough graphs into paths . . . . . . . . . . . 255--261 C. Indermitte and Th. M. Liebling and M. Troyanov and H. Clémençon Voronoi diagrams on piecewise flat surfaces and an application to biological growth . . . . . . . . . . . 263--274 Roger K. Yeh Finite-dimensional T-colorings of graphs 275--281 Mordecai J. Golin A combinatorial approach to Golomb forests . . . . . . . . . . . . . . . . 283--304 Yasuko Matsui and Tomomi Matsui NP-completeness for calculating power indices of weighted majority games . . . 305--310 Michio Ozeki On the covering radius problem for ternary self-dual codes . . . . . . . . 311--332 Hao Li and Jianping Li Independent triangles covering given vertices of a graph . . . . . . . . . . 333--344 H. Maehara and N. Tokushige When does a planar bipartite framework admit a continuous deformation? . . . . 345--354 Szu-En Cheng and Ko-Wei Lih An improvement on a spernerity proof of Horrocks . . . . . . . . . . . . . . . . 355--377 Anonymous Author index volume 263 (2001) . . . . . 379--380
R\=usi\cn\vs Freivalds and Juraj Hromkovi\vc and George P\uaun and Walter Unger Foreword . . . . . . . . . . . . . . . . 1--2 Satoshi Kobayashi and Yasubumi Sakakibara Multiple splicing systems and the universal computability . . . . . . . . 3--23 Vincenzo Manca Logical string rewriting . . . . . . . . 25--51 Lali Barri\`ere and Johanne Cohen and Margarida Mitjana Gossiping in chordal rings under the line model . . . . . . . . . . . . . . . 53--64 Hans-Joachim Böckenhauer Communication in the two-way listen-in vertex-disjoint paths mode . . . . . . . 65--90 Andreas Goerdt Random regular graphs with edge faults: Expansion through cores . . . . . . . . 91--125 Farid Ablayev and Marek Karpinski and Rustam Mubarakzjanov On BPP versus NP coNP for ordered read-once branching programs . . . . . . 127--137 Michele Mosca Counting by quantum eigenvalue estimation . . . . . . . . . . . . . . . 139--153 Andris Ambainis Probabilistic inductive inference: a survey . . . . . . . . . . . . . . . . . 155--167
O. Dubois and R. Monasson and B. Selman and R. Zecchina Editorial . . . . . . . . . . . . . . . 1--1 Olivier C. Martin and Rémi Monasson and Riccardo Zecchina Statistical mechanics methods and phase transitions in optimization problems . . 3--67 Michel Talagrand Rigorous results for mean field models for spin glasses . . . . . . . . . . . . 69--77 Stephan Mertens A physicist's approach to number partitioning . . . . . . . . . . . . . . 79--108 Dimitris Achlioptas and Lefteris M. Kirousis and Evangelos Kranakis and Danny Krizanc Rigorous results for random $ (2 + p)$-SAT . . . . . . . . . . . . . . . . 109--129 W. Fernandez de la Vega Random $2$-SAT: results and problems . . 131--146 John Franco Results related to threshold phenomena research in satisfiability: lower bounds 147--157 Dimitris Achlioptas Lower bounds for random $3$-SAT via differential equations . . . . . . . . . 159--185 Olivier Dubois Upper bounds on the satisfiability threshold . . . . . . . . . . . . . . . 187--197 Alexander K. Hartmann and Martin Weigt Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs . . . 199--225 Joseph Culberson and Ian Gent Frozen development in graph coloring . . 227--264 Barbara M. Smith Constructing an asymptotic phase transition in random binary constraint satisfaction problems . . . . . . . . . 265--283 Andreas Engel Complexity of learning in artificial neural networks . . . . . . . . . . . . 285--306 Anonymous Author index volume 265 (2001) . . . . . 307--307
Carsten Schürmann and Joëlle Despeyroux and Frank Pfenning Primitive recursion for higher-order abstract syntax . . . . . . . . . . . . 1--57 Tatsuru Matsushita and Colin Runciman The accepting power of unary string logic programs . . . . . . . . . . . . . 59--79 G. Aguilera and I. P. de Guzmán and M. Ojeda-Aciego and A. Valverde Reductions for non-clausal theorem proving . . . . . . . . . . . . . . . . 81--112 Klaus U. Schulz and Stephan Kepser Combination of constraint systems II: Rational amalgamation . . . . . . . . . 113--157 René David On the asymptotic behaviour of primitive recursive algorithms . . . . . . . . . . 159--193 Karl Lermer and Paul Strooper Refinement and state machine abstraction 195--235 Michele Boreale and Rocco De Nicola and Rosario Pugliese Divergence in testing and readiness semantics . . . . . . . . . . . . . . . 237--248 Masatomo Hashimoto and Atsushi Ohori A typed context calculus . . . . . . . . 249--272 David Aspinall and Adriana Compagnoni Subtyping dependent types . . . . . . . 273--309 Manolis Koubarakis Tractable disjunctions of linear constraints: basic results and applications to temporal reasoning . . . 311--339 Ralph Loader Finitary PCF is not decidable . . . . . 341--364 Duminda Wijesekera and M. Ganesh and Jaideep Srivastava and Anil Nerode Normal forms and syntactic completeness proofs for functional independencies . . 365--405 César Muñoz Proof-term synthesis on dependent-type systems via explicit substitutions . . . 407--440 Yi-Dong Shen and Li-Yan Yuan and Jia-Huai You Loop checks for logic programs with functions . . . . . . . . . . . . . . . 441--461 Michel Bauderon and Hél\`ene Jacquet Node rewriting in graphs and hypergraphs: a categorical framework . . 463--487 Susumu Yamasaki and Yoshinori Kurose A sound and complete procedure for a general logic program in non-floundering derivations with respect to the $3$-valued stable model semantics . . . 489--512 A. K. McIver and Carroll Morgan Partial correctness for probabilistic demonic programs . . . . . . . . . . . . 513--541 Riccardo Pucella and Prakash Panangaden On the expressive power of first-order boolean functions in PCF . . . . . . . . 543--567 Cédric Fournet and Cosimo Laneve Bisimulations in the join-calculus . . . 569--603 Ji\vrí Srba Basic process algebra with deadlocking states . . . . . . . . . . . . . . . . . 605--630 Jan Friso Groote and Jos van Wamel The parallel composition of uniform processes with data . . . . . . . . . . 631--652 Uri Abraham and Shlomi Dolev and Ted Herman and Irit Koll Self-stabilizing $l$-exclusion . . . . . 653--692 James Riely and Matthew Hennessy Distributed processes and location failures . . . . . . . . . . . . . . . . 693--735 Zurab Khasidashvili On the longest perpetual reductions in orthogonal expression reduction systems 737--772 Gilles Barthe and John Hatcliff and Morten Heine B. Sòrensen An induction principle for pure type systems . . . . . . . . . . . . . . . . 773--818 Karl Schlechta and Jürgen Dix Explaining updates by minimal sums . . . 819--838 Mingsheng Ying and Martin Wirsing Recursive equations in higher-order process calculi . . . . . . . . . . . . 839--852 Robert Goldblatt What is the coalgebraic analogue of Birkhoff's variety theorem? . . . . . . 853--886 Vincenzo Auletta and Ioannis Caragiannis and Luisa Gargano and Christos Kaklamanis and Pino Persiano Sparse and limited wavelength conversion in all-optical tree networks . . . . . . 887--934 M. E. Majster-Cederbaum Underspecification for a simple process algebra of recursive processes . . . . . 935--950 Raymond Turner Type inference for set theory . . . . . 951--974 Thierry Joly Constant time parallel computations in $ \lambda $-calculus . . . . . . . . . . . 975--985 Thomas Krantz and Virgile Mogbil Encoding Hamiltonian circuits into multiplicative linear logic . . . . . . 987--996 Dieter Spreen Corrigendum to ``On functions preserving levels of approximation: a refined model construction for various lambda calculi'' [Theoret. Comput. Sci. 212 (1999) 261--303] . . . . . . . . . . . . 997--998 Anonymous Author index volume 266 (2001) . . . . . 999--1000
Jean-Marc Champarnaud and Denis Maurel and Djelloul Ziadi Foreword . . . . . . . . . . . . . . . . 1--1 C. Câmpeanu and N. Sântean and S. Yu Minimal cover-automata for finite languages . . . . . . . . . . . . . . . 3--16 J.-M. Champarnaud Subset construction complexity for homogeneous automata, position automata and ZPC-structures . . . . . . . . . . . 17--34 Jürgen Albert and Dora Giammarresi and Derick Wood Normal form algorithms for extended context-free grammars . . . . . . . . . 35--47 Norbert Blum On parsing LL-languages . . . . . . . . 49--59 Heiko Goeman On parsing and condensing substrings of LR languages in linear time . . . . . . 61--82 Matti Nykänen Using acceptors as transducers . . . . . 83--104 G. Duchamp and M. Flouret and É. Laugerotte and J.-G. Luque Direct and dual laws for automata with multiplicities . . . . . . . . . . . . . 105--120 Denis Maurel and Brigitte Le Pévédic The syntactic prediction with token automata: application to HandiAS system 121--129 T. Poibeau Parsing natural language idioms with bidirectional finite-state machines . . 131--140 Dominique L'Her and Philippe Le Parc and Lionel Marcé Proving sequential function chart programs using timed automata . . . . . 141--155 Anonymous Author index volume 267 (2001) . . . . . 157--157
Stefano Leonardi and Alberto Marchetti-Spaccamela Preface . . . . . . . . . . . . . . . . 1--1 Christoph Ambühl and Bernd Gärtner and Bernhard von Stengel A new lower bound for the list update problem in the partial cost model . . . 3--16 Yossi Azar and Oded Regev On-line bin-stretching . . . . . . . . . 17--41 Yair Bartal and Moses Charikar and Piotr Indyk On page migration and other relaxed task systems . . . . . . . . . . . . . . . . 43--66 Stefan Bischof and Ernst W. Mayr On-line scheduling of parallel jobs with runtime restrictions . . . . . . . . . . 67--90 Esteban Feuerstein and Leen Stougie On-line single-server dial-a-ride problems . . . . . . . . . . . . . . . . 91--105 W\lodzimierz G\lazek Online algorithms for page replication in rings . . . . . . . . . . . . . . . . 107--117 Tracy Kimbrel Online paging and file caching with expiration times . . . . . . . . . . . . 119--131 John Noga and Steven S. Seiden An optimal online algorithm for scheduling two machines with release times . . . . . . . . . . . . . . . . . 133--143 Marco Riedel Online request server matching . . . . . 145--160 Rudolf Fleischer On the Bahncard problem . . . . . . . . 161--174
R. Wiehagen and T. Zeugmann Foreword . . . . . . . . . . . . . . . . 175--177 M. R. K. Krishna Rao and A. Sattar Polynomial-time learnability of logic programs with local variables from entailment . . . . . . . . . . . . . . . 179--198 Marc Fischlin Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions . . . . . . . . . 199--219 Frank Stephan and Yuri Ventsov Learning algebraic structures from text 221--273 Léa Meyer Aspects of complexity of probabilistic learning under monotonicity constraints 275--322 John Case and Sanjay Jain and Susanne Kaufmann and Arun Sharma and Frank Stephan Predictive learning models for concept drift . . . . . . . . . . . . . . . . . 323--349 Eiju Hirowatari and Setsuo Arikawa A comparison of identification criteria for inductive inference of recursive real-valued functions . . . . . . . . . 351--366 Kalvis Aps\=\itis and R\=usi\cn\vs Freivalds and Raimonds Simanovskis and Juris Smotrovs Closedness properties in ex-identification . . . . . . . . . . . 367--393 Anonymous Author index volume 268 (2001) . . . . . 395--395
Rei Safavi-Naini and Huaxiong Wang Broadcast authentication for group communication . . . . . . . . . . . . . 1--21 Rainer Kerth On the construction of stable models of untyped $ \lambda $-calculus . . . . . . 23--46 Flavio Corradini and GianLuigi Ferrari and Marco Pistore On the semantics of durational actions 47--82 Paola Quaglia Explicit substitutions for pi-congruences . . . . . . . . . . . . . 83--134 Oege de Moor and Ganesh Sittampalam Higher-order matching for program transformation . . . . . . . . . . . . . 135--162 Yaron Riany and Nir Shavit and Dan Touitou Towards a practical snapshot algorithm 163--201 Jan A. Bergstra and Alban Ponse Non-regular iterators in process algebra 203--229 Simone Tini An axiomatic semantics for Esterel . . . 231--282 Olivier Finkel Wadge hierarchy of omega context-free languages . . . . . . . . . . . . . . . 283--315 Gilles Barthe and John Hatcliff and Morten Heine Sòrensen Weak normalization implies strong normalization in a class of non-dependent pure type systems . . . . 317--361 Joaquín Mateos Lago and Mario Rodríguez Artalejo A declarative framework for object-oriented programming with genetic inheritance . . . . . . . . . . . . . . 363--417 Dragan Ma\vsulovi\'cand Bo\vza Tasi\'c Operators on classes of coalgebras . . . 419--431 Ingo Lepper Derivation lengths and order types of Knuth--Bendix orders . . . . . . . . . . 433--450 Ivo Düntsch and Szabolcs Mikulás Cylindric structures and dependencies in relational databases . . . . . . . . . . 451--468 Michel Rigo Numeration systems on a regular language: arithmetic operations, recognizability and formal power series 469--498 Anonymous Author index volume 269 (2001) . . . . . 499--499
Oliver Matz Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures . . . . . . . . 1--70 Andrzej Pelc Searching games with errors---fifty years of coping with liars . . . . . . . 71--109 F. K. Hwang and Y. C. Yao and B. Dasgupta Some permutation routing algorithms for low-dimensional hypercubes . . . . . . . 111--124 W. M. P. van der Aalst and T. Basten Inheritance of workflows: an approach to tackling problems related to change . . 125--203 Ménard Bourgade Calculs sur les structures de langage dénombrable . . . . . . . . . . . . . . . 205--222 J. R. B. Cockett and Stephen Lack Restriction categories I: categories of partial maps . . . . . . . . . . . . . . 223--259 William Lenhart and Giuseppe Liotta The drawability problem for minimum weight triangulations . . . . . . . . . 261--286 John Case and Sanjay Jain and Mandayam Suraj Control structures in hypothesis spaces: the influence on learning . . . . . . . 287--308 Kieran T. Herley and Andrea Pietracaprina and Geppino Pucci Deterministic parallel backtrack search 309--324 Tak-Wah Lam and Hing-Fung Ting and Kar-Keung To and Wai-Ha Wong On-line load balancing of temporary tasks revisited . . . . . . . . . . . . 325--340 Luca Becchetti and Paola Bertolazzi and Carlo Gaibisso and Giorgio Gambosi On the design of efficient ATM routing schemes . . . . . . . . . . . . . . . . 341--359 Ioannis Caragiannis and Christos Kaklamanis and Pino Persiano Edge coloring of bipartite graphs with constraints . . . . . . . . . . . . . . 361--399 F. Blanchet-Sadri and Robert A. Hegstrom Partial words and a theorem of Fine and Wilf revisited . . . . . . . . . . . . . 401--419 Kikuo Fujimura Time-minimal paths amidst moving obstacles in three dimensions . . . . . 421--440 Markus E. Nebel The stack-size of tries: a combinatorial study . . . . . . . . . . . . . . . . . 441--461 Alessandra Cherubini and Stefano Crespi Reghizzi and Pierluigi San Pietro Associative language descriptions . . . 463--491 Thomas Eiter and Toshihide Ibaraki and Kazuhisa Makino Decision lists and related Boolean functions . . . . . . . . . . . . . . . 493--524 Jean Mairesse and Laurent Vuillon Asymptotic behavior in a heap model with two pieces . . . . . . . . . . . . . . . 525--560 Cécile Murat and Vangelis Th. Paschos A priori optimization for the probabilistic maximum independent set problem . . . . . . . . . . . . . . . . 561--590 Clifford Bergman and Giora Slutzki Computational complexity of some problems involving congruences on algebras . . . . . . . . . . . . . . . . 591--608 Dinesh Mehta and Vijay Raghavan Decision tree approximations of Boolean functions . . . . . . . . . . . . . . . 609--623 Arnaud Durand and Miki Hermann and Laurent Juban On the complexity of recognizing the Hilbert basis of a linear Diophantine system . . . . . . . . . . . . . . . . . 625--642 E. Pergola and R. Pinzani and S. Rinaldi Approximating algebraic functions by means of rational ones . . . . . . . . . 643--657 Jeffrey Shallit and Ming-wei Wang On two-sided infinite fixed points of morphisms . . . . . . . . . . . . . . . 659--675 Antonín Ku\vcera and Richard Mayr Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time . . . . . . 677--700 Jürgen Dassow and Victor Mitrana and Arto Salomaa Operations and language generating devices suggested by the genome evolution . . . . . . . . . . . . . . . 701--738 Lan Zhang and Katsushi Inoue and Akira Ito and Yue Wang Probabilistic rebound Turing machines 739--760 Georg Gottlob and Nicola Leone and Francesco Scarcello Computing LOGCFL certificates . . . . . 761--777 Carlos Martín-Vide and Gheorghe P\uaun and Grzegorz Rozenberg Membrane systems with carriers . . . . . 779--796 Chuzo Iwamoto and Tomonobu Hatsuyama and Kenichi Morita and Katsunobu Imai Constructible functions in cellular automata and their applications to hierarchy results . . . . . . . . . . . 797--809 Costas Busch and Neophytos Demetriou and Maurice Herlihy and Marios Mavronicolas Threshold counters with increments and decrements . . . . . . . . . . . . . . . 811--826 Eric Goles and Michel Morvan and Ha Duong Phan The structure of a linear chip firing game and related models . . . . . . . . 827--841 Jens Stoye and Dan Gusfield Simple and flexible detection of contiguous repeats using a suffix tree 843--856 J. W. Sander and R. Tijdeman The rectangle complexity of functions on two-dimensional lattices . . . . . . . . 857--863 András Pluhár The accelerated $k$-in-a-row game . . . 865--875 Ferdinando Cicalese and Daniele Mundici and Ugo Vaccaro Least adaptive optimal search with unreliable tests . . . . . . . . . . . . 877--893 Gary William Flake and Eric B. Baum Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants'' . . . . . . . . . . . . . . 895--911 Michael Drmota The variance of the height of binary search trees . . . . . . . . . . . . . . 913--919 Shigeki Akiyama and Attila Peth\Ho On canonical number systems . . . . . . 921--933 Doris Fiebig and Ulf-Rainer Fiebig Compact factors of countable state Markov shifts . . . . . . . . . . . . . 935--946 Verónica Becher and Santiago Figueira An example of a computable absolutely normal number . . . . . . . . . . . . . 947--958 Sigrid Ewert and Andries van der Walt A pumping lemma for random permitting context languages . . . . . . . . . . . 959--967 Changwook Kim Two undecidability results for chain code picture languages . . . . . . . . . 969--976 Anonymous Author index . . . . . . . . . . . . . . 977--979 Anonymous Master index . . . . . . . . . . . . . . 981--992
Bruno Durand Foreword . . . . . . . . . . . . . . . . 1--1 Cristian S. Calude A characterization of c.e. random reals 3--14 Andrej A. Muchnik and Semen Ye. Positselsky Kolmogorov entropy in the context of computability theory . . . . . . . . . . 15--35 Bruno Durand and Sylvain Porrot Comparison between the complexity of a function and the complexity of its graph 37--46 Bruno Durand and Alexander Shen and Nikolai Vereshchagin Descriptive complexity of computable sequences . . . . . . . . . . . . . . . 47--58 Nikolai K. Vereshchagin Kolmogorov complexity conditional to large integers . . . . . . . . . . . . . 59--67 Alexei Chernov and Andrej Muchnik and Andrei Romashchenko and Alexander Shen and Nikolai Vereshchagin Upper semi-lattice of binary strings with the relation ``x is simple conditional to y'' . . . . . . . . . . . 69--95 Andrej A. Muchnik Conditional complexity and codes . . . . 97--109 A. Romashchenko and A. Shen and N. Vereshchagin Combinatorial interpretation of Kolmogorov complexity . . . . . . . . . 111--123 Alexander Shen and Nikolai Vereshchagin Logical operations and Kolmogorov complexity . . . . . . . . . . . . . . . 125--129 Nikolai K. Vereshchagin and Michael V. Vyugin Independent minimum length programs to translate between given strings . . . . 131--143 Mikhail V. Vyugin Information distance and conditional complexities . . . . . . . . . . . . . . 145--150 Serge Grigorieff and Jean-Yves Marion Kolmogorov complexity and non-determinism . . . . . . . . . . . . 151--180 Yuri Kalnishkan General linear relations between different types of predictive complexity 181--200 Anonymous Author index . . . . . . . . . . . . . . 201--201
Mariangiola Dezani-Ciancaglini and Mitsu Okada and Masako Takahashi Preface . . . . . . . . . . . . . . . . 1--2 Steffen van Bakel and Franco Barbanera and Mariangiola Dezani-Ciancaglini and Fer-Jan de Vries Intersection types for $ \lambda $-trees 3--40 Frédéric Blanqui and Jean-Pierre Jouannaud and Mitsuhiro Okada Inductive-data-type systems . . . . . . 41--68 Mario Coppo and Ferruccio Damiani and Paola Giannini Strictness, totality, and non-standard-type inference . . . . . . 69--112 Ryu Hasegawa Two applications of analytic functors 113--175 Susumu Hayashi and Ryosuke Sumitomo and Ken-ichiro Shii Towards the animation of proofs --- testing proofs by examples . . . . . . . 177--195 Hajime Ishihara and Toshihiko Kurata Completeness of intersection and union type assignment systems for call-by-value $ \lambda $-models . . . . 197--221 Yukiyoshi Kameyama and Masahiko Sato Strong normalizability of the non-deterministic catch/throw calculi 223--245 Andrew D. Ker and Hanno Nickau and C.-H. Luke Ong Innocent game models of untyped $ \lambda $-calculus . . . . . . . . . . . 247--292 Martijn Oostdijk and Herman Geuvers Proof by computation in the Coq system 293--314 Tarmo Uustalu and Varmo Vene Least and greatest fixed points in intuitionistic natural deduction . . . . 315--339 Hirofumi Yokouchi Completeness of type assignment systems with intersection, union, and type quantifiers . . . . . . . . . . . . . . 341--398 Anonymous Author index . . . . . . . . . . . . . . 399--399
J. Neraud Preface . . . . . . . . . . . . . . . . 1--3 Tom C. Brown Applications of standard Sturmian words to elementary number theory . . . . . . 5--9 Flavio D'Alessandro A combinatorial problem on Trapezoidal words . . . . . . . . . . . . . . . . . 11--33 Alex Heinis The $ P(n) / n $-function for bi-infinite words . . . . . . . . . . . 35--46 Jean Berstel and Luc Boasson Shuffle factorization is unique . . . . 47--67 Christian Choffrut and Juhani Karhumäki and Nicolas Ollinger The commutation of finite sets: a challenging problem . . . . . . . . . . 69--79 Juhani Karhumäki and Ján Ma\vnuch Multiple factorizations of words and defect effect . . . . . . . . . . . . . 81--97 F. Mignosi and A. Restivo and M. Sciortino Words and forbidden factors . . . . . . 99--117 G. Richomme and F. Wlazinski Some results on $k$-power-free morphisms 119--142 Aldo de Luca Some combinatorial results on Bernoulli sets and codes . . . . . . . . . . . . . 143--165 Yannick Guesnet On maximal codes with a finite interpreting delay . . . . . . . . . . . 167--183 Jean Néraud and Carla Selmi Locally complete sets and finite decomposable codes . . . . . . . . . . . 185--196 Valérie Berthé and Robert Tijdeman Balance properties of multi-dimensional words . . . . . . . . . . . . . . . . . 197--224 Zoltán Ésik Axiomatizing the subsumption and subword preorders on finite and infinite partial words . . . . . . . . . . . . . . . . . 225--248 Christian Mauduit Finite and infinite pseudorandom binary words . . . . . . . . . . . . . . . . . 249--261 V. Malyshev Quantum evolution of words . . . . . . . 263--269 M. Bigotte and G. Jacob and N. E. Oussous and M. Petitot Lyndon words and shuffle algebras for generating the coloured multiple zeta values relations tables . . . . . . . . 271--282 G. Duchamp and É. Laugerotte and J.-G. Luque On the support of graph Lie algebras . . 283--294 Sylvia Encheva and Gérard Cohen Frameproof codes against limited coalitions of pirates . . . . . . . . . 295--304 Anonymous Author index . . . . . . . . . . . . . . 305--305
Davide Sangiorgi and Robert de Simone Editorial . . . . . . . . . . . . . . . 1--1 F. S. de Boer A Hoare logic for dynamic networks of asynchronously communicating deterministic processes . . . . . . . . 3--41 Holger Hermanns and Ulrich Herzog and Joost-Pieter Katoen Process algebra for performance evaluation . . . . . . . . . . . . . . . 43--87 D. Lugiez and Ph. Schnoebelen The regular viewpoint on PA-processes 89--115 P. Madhusudan and P. S. Thiagarajan Branching time controllers for discrete event systems . . . . . . . . . . . . . 117--149 P.-Y. Schobbens and J.-F. Raskin and T. A. Henzinger Axioms for real-time logics . . . . . . 151--182 Peter Sewell From rewrite rules to bisimulation congruences . . . . . . . . . . . . . . 183--230 Nobuko Yoshida Minimality and separation results on asynchronous mobile processes --- representability theorems by concurrent combinators . . . . . . . . . . . . . . 231--276 Anonymous Author index volume 274 (2002) . . . . . 277--277
Mingsheng Ying Bisimulation indexes and their applications . . . . . . . . . . . . . . 1--68 Bruce S. Burdick A note on iterated duals of certain topological spaces . . . . . . . . . . . 69--77 Ernest G. Manes Taut Monads and T0-spaces . . . . . . . 79--109 A. Rabinovich Finite variability interpretation of monadic logic of order . . . . . . . . . 111--125 Nadia Busi Analysis issues in Petri nets with inhibitor arcs . . . . . . . . . . . . . 127--177 Serge Abiteboul and Sophie Cluet and Tova Milo Correspondence and translation for heterogeneous data . . . . . . . . . . . 179--213 Dominic Duggan and John Ophel Open and closed scopes for constrained genericity . . . . . . . . . . . . . . . 215--258 Pierpaolo Degano and Fabio Gadducci and Corrado Priami A causal semantics for CCS via rewriting logic . . . . . . . . . . . . . . . . . 259--282 Iain A. Stewart Program schemes, arrays, Lindström quantifiers and zero-one laws . . . . . 283--310 Igor Walukiewicz Monadic second-order logic on tree-like structures . . . . . . . . . . . . . . . 311--346 Dani\`ele Beauquier and Anatol Slissenko Decidable verification for reducible timed automata specified in a first order logic with time . . . . . . . . . 347--388 Maria I. Sessa Approximate reasoning by similarity-based SLD resolution . . . . 389--426 J. Adámek and M. Hébert and J. Rosický On abstract data types presented by multiequations . . . . . . . . . . . . . 427--462 Sergei Vorobyov $ \forall \exists^5$-equational theory of context unification is undecidable 463--479 Mingsheng Ying Additive models of probabilistic processes . . . . . . . . . . . . . . . 481--519 Agostino Cortesi and Agostino Dovier and Elisa Quintarelli and Letizia Tanca Operational and abstract semantics of the query language G-Log . . . . . . . . 521--560 Ernst Zimmermann Peirce's Rule in Natural Deduction . . . 561--574 Felice Cardone A coinductive completeness proof for the equivalence of recursive types . . . . . 575--587 Walter Vogler Efficiency of asynchronous systems, read arcs, and the MUTEX-problem . . . . . . 589--631 Frank Neven and Thomas Schwentick Query automata over finite trees . . . . 633--674 Adel Bouhoula and Michaël Rusinowitch Observational proofs by rewriting . . . 675--698 Anonymous Author index volume 275 (2002) . . . . . 699--699
Robert Cori and Dominique Rossin and Bruno Salvy Polynomial ideals for sandpiles and their Gröbner bases . . . . . . . . . . . 1--15 Vincent Bouchitté and Ioan Todinca Listing all potential maximal cliques of a graph . . . . . . . . . . . . . . . . 17--32 Gruia C\ualinescu and Peng-Jun Wan Splittable traffic partition in WDM/SONET rings to minimize SONET ADMs 33--50 Stefan Droste and Thomas Jansen and Ingo Wegener On the analysis of the $ (1 + 1) $ evolutionary algorithm . . . . . . . . . 51--81 Amber Settle and Janos Simon Smaller solutions for the firing squad 83--109 Bin Ma and Lusheng Wang and Kaizhong Zhang Computing similarity between RNA structures . . . . . . . . . . . . . . . 111--132 Subhamoy Maitra and Palash Sarkar Cryptographically significant Boolean functions with five valued Walsh spectra 133--146 Harumichi Nishimura and Masanao Ozawa Computational complexity of uniform quantum circuit families and quantum Turing machines . . . . . . . . . . . . 147--181 Vesa Halava and Tero Harju and Mika Hirvensalo Binary (generalized) Post Correspondence Problem . . . . . . . . . . . . . . . . 183--204 Erzsébet Csuhaj-Varjú and György Vaszil Parallel communicating grammar systems with bounded resources . . . . . . . . . 205--219 Z. Fülöp and A. Terlutte Iterated relabeling tree transducers . . 221--244 Kai Salomaa and Sheng Yu Decidability of EDT0L structural equivalence . . . . . . . . . . . . . . 245--259 David F. Manlove and Robert W. Irving and Kazuo Iwama and Shuichi Miyazaki and Yasufumi Morita Hard variants of stable marriage . . . . 261--279 Jacques Justin and Giuseppe Pirillo Episturmian words and episturmian morphisms . . . . . . . . . . . . . . . 281--313 Serafino Cicerone and Gabriele Di Stefano and Michele Flammini Static and dynamic low-congested interval routing schemes . . . . . . . . 315--354 Stavros Konstantinidis and Amber O'Hearn Error-detecting properties of languages 355--375 Henning Fernau and Ralf Stiebe Sequential grammars and automata with valences . . . . . . . . . . . . . . . . 377--405 V. V. V'yugin Note: Does snooping help? . . . . . . . 407--415 Chiuyuan Chen Note: A necessary condition for a graph to be the visibility graph of a simple polygon . . . . . . . . . . . . . . . . 417--424 Gregorio Malajovich Note: Lower bounds for some decision problems over C . . . . . . . . . . . . 425--434 J. M. Robson Note: Constant bounds on the moments of the height of binary search trees . . . 435--444 Christophe Prieur Note: How to decide continuity of rational functions on infinite words . . 445--447 Yongge Wang Note: A comparison of two approaches to pseudorandomness . . . . . . . . . . . . 449--459 Anonymous Author index volume 276 (2002) . . . . . 465--466
Pascal Van Hentenryck Editorial . . . . . . . . . . . . . . . 1--2 Roberto Bagnara and Patricia M. Hill and Enea Zaffanella Set-sharing is redundant for pair-sharing . . . . . . . . . . . . . . 3--46 Patrick Cousot Constructive design of a hierarchy of semantics of a transition system by abstract interpretation . . . . . . . . 47--103 Alexandre Frey Satisfying subtype inequalities in polynomial space . . . . . . . . . . . . 105--117 G. Ramalingam On sparse evaluation representations . . 119--147 Francesca Scozzari Logical optimality of groundness analysis . . . . . . . . . . . . . . . . 149--184 Kwangkeun Yi and Sukyoung Ryu A cost-effective estimation of uncaught exceptions in Standard ML programs . . . 185--217 Anonymous Author index volume 277 (2002) . . . . . 223
Stephen Brookes and Michael Mislove Foreword . . . . . . . . . . . . . . . . 1--2 Peter Freyd Cartesian logic . . . . . . . . . . . . 3--21 Stephen Brooks and Michael Mislove Dedication . . . . . . . . . . . . . . . 23 Melvin Fitting Fixpoint semantics for logic programming a survey . . . . . . . . . . . . . . . . 25--51 Matthew Hennessy A fully abstract denotational semantics for the $ \pi $-calculus . . . . . . . . 53--89 Antonio Bucciarelli and Pasquale Malacaria Relative definability of boolean functions via hypergraphs . . . . . . . 91--110 Adrian Fiech and David A. Schmidt Polymorphic lambda calculus and subtyping . . . . . . . . . . . . . . . 111--140 Robert C. Flagg and Philipp Sünderhauf The essence of ideal completion in quantitative form . . . . . . . . . . . 141--158 H. P. Künzi and M. P. Schellekens On the Yoneda completion of a quasi-metric space . . . . . . . . . . . 159--194 Paul Gastin and Dan Teodosiu Resource traces: a domain for processes sharing exclusive resources . . . . . . 195--221 V. Gupta and R. Jagadeesan and V. A. Saraswat Truly concurrent constraint programming 223--255 P. S. Mulry Lifting results for categories of algebras . . . . . . . . . . . . . . . . 257--269 David A. Naumann Soundness of data refinement for a higher-order imperative language . . . . 271--301 John Power Premonoidal categories as categories with algebraic structure . . . . . . . . 303--321 John Power and Giuseppe Rosolini Fixpoint operators for domain equations 323--333 Anonymous Author index volume 278 (2002) . . . . . 335
Jean-Marie Chesneaux and Christiane Frougny and Jean-Michel Muller Foreword: Real Numbers . . . . . . . . . 1--2 Daniel Etiemble Computer arithmetic and hardware: ``off the shelf'' microprocessors versus ``custom hardware'' . . . . . . . . . . 3--27 Peter R. Turner Residue polynomial systems . . . . . . . 29--49 David Lester and Scott Chambers and Heoi Lee Lu A constructive algorithm for finding the exact roots of polynomials with computable real coefficients . . . . . . 51--64 Reinhold Heckmann Contractivity of linear fractional transformations . . . . . . . . . . . . 65--82 Peter Hertling A lower bound for range enclosure in interval arithmetic . . . . . . . . . . 83--95 Anonymous Author index volume 279 (2002) . . . . . 97
Bart Jacobs and Jan Rutten Foreword . . . . . . . . . . . . . . . . 1 Uwe Wolter CSP, partial automata, and coalgebras 3--34 Corina C\^\irstea A coalgebraic equational approach to specifying observational structures . . 35--68 Alexander Kurz and Rolf Hennicker On institutions for modular coalgebraic specifications . . . . . . . . . . . . . 69--103 D. Pavlovi and V. Pratt The continuum as a final coalgebra . . . 105--122 S\lawomir Lasota Coalgebra morphisms subsume open maps 123--135 John Power and Hiroshi Watanabe Combining a monad and a comonad . . . . 137--162 Andrea Corradini and Reiko Heckel and Ugo Montanari Compositional SOS and beyond: a coalgebraic view of open systems . . . . 163--192 Anonymous Author index . . . . . . . . . . . . . . 193 Anonymous Master index . . . . . . . . . . . . . . 195--200
G. Ausiello Preface . . . . . . . . . . . . . . . . 1 Pierre-Louis Curien Une br\`eve biographie scientifique de Maurice Nivat. (French) [A brief scientific biography of Maurice Nivat] 3--23 Grzegorz Rozenberg and Arto Salomaa ICALP, EATCS and Maurice Nivat . . . . . 25--30 André Arnold Nivat's processes and their synchronization . . . . . . . . . . . . 31--36 Cyril Banderier and Philippe Flajolet Basic analytic combinatorics of directed lattice paths . . . . . . . . . . . . . 37--80 Dani\`ele Beauquier and Jean-Claude Fournier Groups and tilings . . . . . . . . . . . 81--97 Jean Berstel and Laurent Vuillon Coding rotations on intervals . . . . . 99--107 Gérard Boudol and Ilaria Castellani Noninterference for concurrent programs and thread systems . . . . . . . . . . . 109--130 Roberto Bruni and Ugo Montanari Dynamic connectors for concurrency . . . 131--176 Bruno Courcelle and Teodor Knapik The evaluation of first-order substitution is monadic second-order compatible . . . . . . . . . . . . . . . 177--206 Guy Cousineau Tilings as a programming exercise . . . 207--217 Max Dauchet and Sophie Tison and Marc Tommasi Réduction de la non-linéarité des morphismes d'arbres. (French) [Recognizable tree-languages and non-linear morphisms] . . . . . . . . . 219--233 Alberto Del Lungo Reconstructing permutation matrices from diagonal sums . . . . . . . . . . . . . 235--249 Marianne Delorme and Jacques Mazoyer Reconnaissance parall\`ele des langages rationnels sur automates cellulaires plans. (French) [Parallel recognition of rational languages on planar cellular automata] . . . . . . . . . . . . . . . 251--289 Josep Díaz and Maria Serna and Dimitrios M. Thilikos Counting $H$-colorings of partial $k$-trees . . . . . . . . . . . . . . . 291--309 Bruno Durand De la logique aux pavages. (French) [On the logic of tiling] . . . . . . . . . . 311--324 A. Ehrenfeucht and T. Harju and G. Rozenberg Gene assembly through cyclic graph decomposition . . . . . . . . . . . . . 325--349 Luca Ferrari and Elisa Pergola and Renzo Pinzani and Simone Rinaldi An algebraic characterization of the set of succession rules . . . . . . . . . . 351--367 Paul Gastin and Michael Mislove A truly concurrent semantics for a process algebra using resource pomsets 369--421 Serge Grigorieff Modelization of deterministic rational relations . . . . . . . . . . . . . . . 423--453 Peter Gritzmann and Sven de Vries On the algorithmic inversion of the discrete Radon transform . . . . . . . . 455--469 Mitsuhiro Okada A uniform semantic proof for cut-elimination and completeness of various first and higher order logics 471--498 Teodor Rus A unified language processing methodology . . . . . . . . . . . . . . 499--536 Arto Salomaa Uni-transitional Watson--Crick D0L systems . . . . . . . . . . . . . . . . 537--553 Géraud Sénizergues L(A)=L(B)? A simplified decidability proof . . . . . . . . . . . . . . . . . 555--608 Gérard Huet \'Sr\=\i Yantra Geometry . . . . . . . . 609--628 Anonymous Author index . . . . . . . . . . . . . . 629--630
Joost-Pieter Katoen Foreword . . . . . . . . . . . . . . . . 1--3 Mario Bravetti and Roberto Gorrieri The theory of interactive generalized semi-Markov processes . . . . . . . . . 5--32 Bengt Jonsson and Wang Yi Testing preorders for probabilistic processes can be characterized by simulations . . . . . . . . . . . . . . 33--51 Paul Z. Kolano Proof assistance for real-time systems using an interactive theorem prover . . 53--99 Marta Kwiatkowska and Gethin Norman and Roberto Segala and Jeremy Sproston Automatic verification of real-time systems with discrete probability distributions . . . . . . . . . . . . . 101--150 Karl Lermer and Colin Fidge A formal model of real-time program compilation . . . . . . . . . . . . . . 151--190 A. K. McIver Quantitative program logic and expected time bounds in probabilistic distributed algorithms . . . . . . . . . . . . . . . 191--219
Elena Lodi and Linda Pagli and Nicola Santoro Foreword . . . . . . . . . . . . . . . . 221--222 F. Luccio Algorithms, nymphs, and shepherds . . . 223--229 David Peleg Local majorities, coalitions and monopolies in graphs: a review . . . . . 231--257 Paolo Boldi and Massimo Santini and Sebastiano Vigna Measuring with jugs . . . . . . . . . . 259--270 Aviezri S. Fraenkel Arrays, numeration systems and Frankenstein games . . . . . . . . . . . 271--284 Alberto Pedrotti Playing by searching: two strategies against a linearly bounded liar . . . . 285--302 Alon Itai and Michael Rodeh and Hadas Shachnai The passport control problem or how to keep a dynamic service system load balanced? . . . . . . . . . . . . . . . 303--318 Alain Daurat and Yan Gérard and Maurice Nivat The chords' problem . . . . . . . . . . 319--336 Donatella Merlini and Renzo Sprugnoli and M. Cecilia Verri A strip-like tiling algorithm . . . . . 337--352 Ronald Becker and Bruno Simeone and Yen-I Chiang A shifting algorithm for continuous tree partitioning . . . . . . . . . . . . . . 353--380 Steve Seiden A manifesto for the computational method 381--395 Anonymous Author index . . . . . . . . . . . . . . 397
Gilles Bertrand and Rémy Malgouyres Preface . . . . . . . . . . . . . . . . 1 T. Y. Kong Topological adjacency relations on $ Z^n $ . . . . . . . . . . . . . . . . . . . 3--28 R. Ayala and E. Domínguez and A. R. Francés and A. Quintero Weak lighting functions and strong 26-surfaces . . . . . . . . . . . . . . 29--66 Rémy Malgouyres and Malika More On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology . . . . . . . . . . . . . . . . 67--108 Sébastien Fourey and Rémy Malgouyres Intersection number and topology preservation within digital surfaces . . 109--150 Valentin E. Brimkov and Reneta P. Barneva Graceful planes and lines . . . . . . . 151--170 Yan Gérard Periodic graphs and connectivity of the rational digital hyperplanes . . . . . . 171--182 Marie-Andrée Jacob-Da Col About local configurations in arithmetic planes . . . . . . . . . . . . . . . . . 183--201 Olivier Devillers and Pierre-Marie Gandoin Rounding Voronoi diagram . . . . . . . . 203--221 Attila Kuba and Emese Balogh Reconstruction of convex 2D discrete sets in polynomial time . . . . . . . . 223--242 Mohamed Tajine and Christian Ronse Topological properties of Hausdorff discretization, and comparison to other discretization schemes . . . . . . . . . 243--268
Roberto Gorrieri Editorial . . . . . . . . . . . . . . . 269--270 Chiara Bodei and Pierpaolo Degano and Riccardo Focardi and Corrado Priami Primitives for authentication in process algebras . . . . . . . . . . . . . . . . 271--304 Ewen Denney and Thomas Jensen Correctness of Java card method lookup via logical relations . . . . . . . . . 305--331 Joshua D. Guttman and F. Javier Thayer Authentication tests and the structure of bundles . . . . . . . . . . . . . . . 333--380 Flemming Nielson and Hanne Riis Nielson and René Rydhof Hansen Validating firewalls using flow logics 381--418 Vitaly Shmatikov and John C. Mitchell Finite-state analysis of two contract signing protocols . . . . . . . . . . . 419--450 Anonymous Author index . . . . . . . . . . . . . . 451
Paul Fischer and Hans Simon and Carl Smith Foreword . . . . . . . . . . . . . . . . 1--2 András Antos Lower bounds for the rate of convergence in nonparametric pattern recognition . . 3--24 Shai Fine and Ran Gilad-Bachrach and Eli Shamir Query by committee, linear separation and random walks . . . . . . . . . . . . 25--51 Peter L. Bartlett and Shai Ben-David Hardness results for neural network approximation problems . . . . . . . . . 53--66 Nigel Duffy and David Helmbold A geometric approach to leveraging weak learners . . . . . . . . . . . . . . . . 67--108 D. P. Helmbold and S. Panizza and M. K. Warmuth Direct and indirect algorithms for on-line learning of disjunctions . . . . 109--142 Sanjay Jain and Arun Sharma Mind change complexity of learning logic programs . . . . . . . . . . . . . . . . 143--160 Matthias Ott and Frank Stephan Avoiding coding tricks by hyperrobust learning . . . . . . . . . . . . . . . . 161--180 Márta Pintér On the rate of convergence of error estimates for the partitioning classification rule . . . . . . . . . . 181--196
Ker-l Ko and Anil Nerode and Klaus Weihrauch Foreword . . . . . . . . . . . . . . . . 197 Markus Bläser Uniform computational complexity of the derivatives of $C$-functions . . . . . . 199--206 J. Blanck and V. Stoltenberg-Hansen and J. V. Tucker Domain representations of partial functions, with applications to spatial objects and constructive volume geometry 207--240 Vasco Brattka and Peter Hertling Topological properties of real number representations . . . . . . . . . . . . 241--257 Douglas S. Bridges and Nicholas Dudley Ward Kernels of seminorms in constructive analysis . . . . . . . . . . . . . . . . 259--267 Cristian S. Calude Chaitin numbers, Solovay machines, and Gödel incompleteness . . . . . . . . . . 269--277 Douglas Cenzer and Jeffrey B. Remmel Effectively closed sets and graphs of computable real functions . . . . . . . 279--318 Abbas Edalat and André Lieutier Foundation of a computable solid modelling . . . . . . . . . . . . . . . 319--345 Armin Hemmerling Effective metric spaces and representations of the reals . . . . . . 347--372 Michal Kone\vcný Real functions computable by finite automata using affine representations 373--396 Vladimir N. Krupski Effective simultaneous approximability of reals . . . . . . . . . . . . . . . . 397--417 Takakazu Mori On the computability of Walsh functions 419--436 Dag Normann Exact real number computations relative to hereditarily total functionals . . . 437--453 Ludwig Staiger The Kolmogorov complexity of real numbers . . . . . . . . . . . . . . . . 455--466 Hideki Tsuiki Real number computation through Gray code embedding . . . . . . . . . . . . . 467--485 Atsushi Yoshikawa Interpolation functor and computability 487--498 Xizhong Zheng The closure properties on real numbers under limits and computable operators 499--518 Matthias Schröder Extended admissibility . . . . . . . . . 519--538 Rodney G. Downey and Geoffrey L. LaForte Presentations of computably enumerable reals . . . . . . . . . . . . . . . . . 539--555 Anonymous Author index volume 284 (2002) . . . . . 557--558
Giancarlo Bongiovanni and Giorgio Gambosi and Rossella Petreschi Foreword . . . . . . . . . . . . . . . . 1 Hans-Joachim Böckenhauer and Juraj Hromkovi and Ralf Klasing and Sebastian Seibert and Walter Unger Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem 3--24 D. Cantone and G. Cincotti QuickHeapsort, an efficient mix of classical sorting algorithms . . . . . . 25--42 Peter Damaschke Online strategies for backups . . . . . 43--53 Irit Dinur Approximating SVP to within almost-polynomial factors is NP-hard . . 55--71 Donatella Merlini and Renzo Sprugnoli and M. Cecilia Verri Modified binary searching for static tables . . . . . . . . . . . . . . . . . 73--88 Sebastian Seibert and Walter Unger The hardness of placing street names in a Manhattan type map . . . . . . . . . . 89--99 K. Steinhöfel and A. Albrecht and C. K. Wong The convergence of stochastic algorithms solving flow shop scheduling . . . . . . 101--117
Narciso Martí-Oliet and José Meseguer Preface . . . . . . . . . . . . . . . . 119--120 Narciso Martí-Oliet and José Meseguer Rewriting logic: roadmap and bibliography . . . . . . . . . . . . . . 121--154 Peter Borovanský and Claude Kirchner and Hél\`ene Kirchner and Pierre-Etienne Moreau ELAN from a rewriting logic point of view . . . . . . . . . . . . . . . . . . 155--185 M. Clavel and F. Durán and S. Eker and P. Lincoln and N. Martí-Oliet and J. Meseguer and J. F. Quesada Maude: specification and programming in rewriting logic . . . . . . . . . . . . 187--243 Manuel Clavel and José Meseguer Reflection in conditional rewriting logic . . . . . . . . . . . . . . . . . 245--288 R\uazvan Diaconescu and Kokichi Futatsugi Logical foundations of CafeOBJ . . . . . 289--318 Fabio Gadducci and Ugo Montanari Comparing logics for rewriting: rewriting logic, action calculi and tile logic . . . . . . . . . . . . . . . . . 319--358 Peter Csaba Ölveczky and José Meseguer Specification of real-time and hybrid systems in rewriting logic . . . . . . . 359--405 Isabel Pita and Narciso Martí-Oliet A Maude specification of an object-oriented model for telecommunication networks . . . . . . . 407--439 Carolyn Talcott Actor theories in rewriting logic . . . 441--485 Patrick Viry Equational rules for rewriting logic . . 487--517 Martin Wirsing and Alexander Knapp A formal approach to object-oriented software engineering . . . . . . . . . . 519--560 Anonymous Author index . . . . . . . . . . . . . . 563--564
Peter Ru\vzi\vcka Preface . . . . . . . . . . . . . . . . 1 Foto Afrati and Ir\`ene Guessarian and Michel de Rougemont The expressiveness of DAC . . . . . . . 3--32 Walter Vogler Partial order semantics and read arcs 33--63 Zurab Khasidashvili and John Glauert Relating conflict-free stable transition and event models via redex families . . 65--95 Markus Holzer Multi-head finite automata: data-independent versus data-dependent computations . . . . . . . . . . . . . . 97--116 Christian Choffrut and Giovanni Pighizzini Distances between languages and reflexivity of relations . . . . . . . . 117--138 Drago Krznaric and Christos Levcopoulos Optimal algorithms for complete linkage clustering in d dimensions . . . . . . . 139--149 Anonymous Editorial board . . . . . . . . . . . . v--ix
J. L. Fiadeiro Preface . . . . . . . . . . . . . . . . 151 Egidio Astesiano and Michel Bidoit and Hél\`ene Kirchner and Bernd Krieg-Brückner and Peter D. Mosses and Donald Sannella and Andrzej Tarlecki CASL: the Common Algebraic Specification Language . . . . . . . . . . . . . . . . 153--196 Tomasz Borzyszkowski Logical systems for structured specifications . . . . . . . . . . . . . 197--245 Roberto Bruni and Fabio Gadducci and Ugo Montanari Normal forms for algebras of connections 247--292 Andrea Corradini and Fabio Gadducci A functorial semantics for multi-algebras and partial algebras, with applications to syntax . . . . . . 293--322 Beata Konikowska Rasiowa-Sikorski deduction systems in computer science applications . . . . . 323--366 Till Mossakowski Relating CASL with other specification languages: the institution level . . . . 367--475 Anonymous Author index . . . . . . . . . . . . . . 477
G. Rozenberg and A. E. Eiben and J. N. Kok Preface . . . . . . . . . . . . . . . . 1--2 Martyn Amos and Gheorghe P\uaun and Grzegorz Rozenberg and Arto Salomaa Topics in the theory of DNA computing 3--38 Arwen Brenneman and Anne Condon Strand design for biomolecular computation . . . . . . . . . . . . . . 39--58 Masami Hagiya and John A. Rose and Ken Komiya and Kensaku Sakamoto Complexity analysis of the SAT engine: DNA algorithms as probabilistic algorithms . . . . . . . . . . . . . . . 59--71 Gheorghe P\uaun and Grzegorz Rozenberg A guide to membrane computing . . . . . 73--100 Hans-Georg Beyer and Hans-Paul Schwefel and Ingo Wegener How to analyse evolutionary algorithms 101--130 Stefan Droste and Thomas Jansen and Ingo Wegener Optimization with randomized search heuristics the (A)NFL theorem, realistic scenarios, and difficult functions . . . 131--144 H. Mühlenbein and Th. Mahnig Evolutionary computation and Wright's equation . . . . . . . . . . . . . . . . 145--165 B. Naudts and L. Schoofs GA performance distributions and randomly generated binary constraint satisfaction problems . . . . . . . . . 167--185 Erkki Oja Unsupervised learning in neural computation . . . . . . . . . . . . . . 187--207 Alex Gammerman and Volodya Vovk Prediction algorithms and confidence measures based on algorithmic randomness theory . . . . . . . . . . . . . . . . . 209--217 Tom Heskes and Bart Bakker and Bert Kappen Approximate algorithms for neural-Bayesian approaches . . . . . . . 219--238 Robert A. Legenstein and Wolfgang Maass Neural circuits for pattern recognition with small total wire length . . . . . . 239--249 Thomas Natschläger and Wolfgang Maass Spiking neurons and the induction of finite state machines . . . . . . . . . 251--265 Mika Hirvensalo Computing with quanta impacts of quantum theory on computation . . . . . . . . . 267--298 Andris Ambainis and John Watrous Two-way finite automata with quantum and classical states . . . . . . . . . . . . 299--311 Barbara M. Terhal Detecting quantum entanglement . . . . . 313--335 Ronald de Wolf Quantum communication and complexity . . 337--353 Anonymous Editorial board . . . . . . . . . . . . v--ix
Jaroslav Ne\vset\vril Preface . . . . . . . . . . . . . . . . 355--357 Ali Akhavi Random lattices, threshold phenomena and efficient reduction algorithms . . . . . 359--385 Eric Anderson and Marek Chrobak and John Noga and Ji í Sgall and Gerhard J. Woeginger Solution of a problem in DNA computing 387--391 Eric J. Anderson and Kirsten Hildrum and Anna R. Karlin and April Rasala and Michael Saks On list update and work function algorithms . . . . . . . . . . . . . . . 393--418 Yossi Azar and Oded Regev and Ji í Sgall and Gerhard J. Woeginger Off-line temporary tasks assignment . . 419--428 Luca Becchetti and Miriam Di Ianni and Alberto Marchetti-Spaccamela Approximation algorithms for routing and call scheduling in all-optical chains and rings . . . . . . . . . . . . . . . 429--448 Krzysztof Diks and Evangelos Kranakis and Danny Krizanc and Andrzej Pelc The impact of information on broadcasting time in linear radio networks . . . . . . . . . . . . . . . . 449--471 Limor Drori and David Peleg Faster exact solutions for some NP-hard problems . . . . . . . . . . . . . . . . 473--499 Daniele V. Finocchiaro and Marco Pellegrini On computing the diameter of a point set in high dimensional Euclidean space . . 501--514 P. Flajolet and K. Hatzis and S. Nikoletseas and P. Spirakis On the robustness of interconnections in random graphs: a symbolic approach . . . 515--534 Yair Frankel and Philip MacKenzie and Moti Yung Adaptively secure distributed public-key systems . . . . . . . . . . . . . . . . 535--561 Arlette Gaillard and Heinz Groeflin and Alan J. Hoffman and William R. Pulleyblank On the submodular matrix representation of a digraph . . . . . . . . . . . . . . 563--570 Eduardo Sany Laber and Ruy Luiz Milidiú and Artur Alves Pessoa A strategy for searching with different access costs . . . . . . . . . . . . . . 571--584 Jaroslav Ne\vset\vril and Claude Tardif Density via duality . . . . . . . . . . 585--591 Pierre Nicod\`eme and Bruno Salvy and Philippe Flajolet Motif statistics . . . . . . . . . . . . 593--617 Anonymous Author index . . . . . . . . . . . . . . 619--620
G. Moser Foreword . . . . . . . . . . . . . . . . 1 Arnold Beckmann Notations for exponentiation . . . . . . 3--19 Harry Buhrman and Ronald de Wolf Complexity measures and decision tree complexity: a survey . . . . . . . . . . 21--43 A. Carbone Streams and strings in formal proofs . . 45--83 P. Crescenzi and G. Rossi On the Hamming distance of constraint satisfaction problems . . . . . . . . . 85--100 Thomas Eiter and Helmut Veith On the complexity of data disjunctions 101--128 Erich Grädel Guarded fixed point logics and the monadic theory of countable trees . . . 129--152 Leonid Libkin and Limsoon Wong Lower bounds for invariant queries in logics with counting . . . . . . . . . . 153--180 Zenon Sadowski On an optimal propositional proof system and the structure of easy subsets of TAUT . . . . . . . . . . . . . . . . . . 181--193 Anonymous Editorial board . . . . . . . . . . . . v--ix
Osamu Watanabe and Arun Sharma Preface . . . . . . . . . . . . . . . . 195--196 José L. Balcázar and Jorge Castro and David Guijarro and Hans-Ulrich Simon The consistency dimension and distribution-dependent learning from queries . . . . . . . . . . . . . . . . 197--215 Eiji Takimoto and Manfred K. Warmuth Predicting nearly as well as the best pruning of a planar decision graph . . . 217--235 Sally A. Goldman and Stephen S. Kwek On learning unions of pattern languages and tree patterns in the mistake bound model . . . . . . . . . . . . . . . . . 237--254 Nader H. Bshouty and Nadav Eiron and Eyal Kushilevitz PAC learning with nasty noise . . . . . 255--275 Steffen Lange and Gunter Grieser On the power of incremental learning . . 277--307 Frank Stephan and Thomas Zeugmann Learning classes of approximations to non-recursive functions . . . . . . . . 309--341 Anonymous Author index . . . . . . . . . . . . . . 343
Reiner Durchholz A generic causal model for place latency 1--49 Peter J. Grabner and Helmut Prodinger Sorting algorithms for broadcast communications: mathematical analysis 51--67 Evgeny Dantsin and Andreas Goerdt and Edward A. Hirsch and Ravi Kannan and Jon Kleinberg and Christos Papadimitriou and Prabhakar Raghavan and Uwe Schöning A deterministic $ (2 - 2 / (k + 1))^n $ algorithm for $k$-SAT based on local search . . . . . . . . . . . . . . . . . 69--83 T. Eilam and S. Moran and S. Zaks The complexity of the characterization of networks supporting shortest-path interval routing . . . . . . . . . . . . 85--104 A. Barbé and F. von Haeseler Symmetries of decimation invariant sequences and digit sets . . . . . . . . 105--136 J.-M. Champarnaud and D. Ziadi Canonical derivatives, partial derivatives and finite automaton constructions . . . . . . . . . . . . . 137--163 Oscar H. Ibarra and Jianwen Su and Zhe Dang and Tevfik Bultan and Richard A. Kemmerer Counter Machines and Verification Problems . . . . . . . . . . . . . . . . 165--189 Oscar H. Ibarra and Jianwen Su Augmenting the discrete timed automaton with other data structures . . . . . . . 191--204 M. D. Atkinson and M. M. Murphy and N. Ru\vskuc Sorting with two ordered stacks in series . . . . . . . . . . . . . . . . . 205--223 Marie-Pierre Béal and Olivier Carton Determinization of transducers over finite and infinite words . . . . . . . 225--251 Andreas Klein and Martin Kutrib Deterministic Turing machines in the range between real-time and linear-time 253--275 Wei Chen and Koichi Wada and Kimio Kawaguchi Robust algorithms for constructing strongly convex hulls in parallel . . . 277--295 F. Blanchet-Sadri and D. K. Luhmann Conjugacy on partial words . . . . . . . 297--312 Kuo-Liang Chung and Wen-Ming Yan and Jung-Gen Wu Load-balanced parallel banded-system solvers . . . . . . . . . . . . . . . . 313--334 Wolfgang W. Bein and Marek Chrobak and Lawrence L. Larmore The $3$-server problem in the plane . . 335--354 Vincenzo Auletta and Ioannis Caragiannis and Christos Kaklamanis and Pino Persiano Randomized path coloring on binary trees 355--399 Hagit Brit and Shlomo Moran and Gadi Taubenfeld Public data structures: counters as a special case . . . . . . . . . . . . . . 401--423 Henning Fernau Even linear simple matrix languages: formal language properties and grammatical inference . . . . . . . . . 425--456 Leslie G. Valiant Expressiveness of matchgates . . . . . . 457--471 Uriel Feige and Giora Rayzman On the drift of short schedules . . . . 473--484 Petr Sosík Universal computation with Watson--Crick D0L systems . . . . . . . . . . . . . . 485--501 Herbert Fleischner and Oliver Kullmann and Stefan Szeider Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference . . . . . . . 503--516 Niklas Eriksen $ (1 + \epsilon)$-Approximation of sorting by reversals and transpositions 517--529 Sini\vsa Crvenkovi\'c and Igor Dolinka On axioms for commutative regular equations without addition . . . . . . . 531--551 Liming Cai and David Juedes and Iyad Kanj The inapproximability of non-NP-hard optimization problems . . . . . . . . . 553--571 Vincent D. Blondel and Julien Cassaigne and Codrin Nichitiu On the presence of periodic configurations in Turing machines and in counter machines . . . . . . . . . . . . 573--590 Robert Baumgartner and Georg Gottlob Propositional default logics made easier: computational complexity of model checking . . . . . . . . . . . . . 591--627 Dirk V. Arnold and Hans-Georg Beyer Performance analysis of evolution strategies with multi-recombination in high-dimensional $ R^N $-search spaces disturbed by noise . . . . . . . . . . . 629--647 Charles Knessl and Wojciech Szpankowski The height of a binary search tree: the limiting distribution perspective . . . 649--703 Juhani Karhumäki and Ion Petre Conway's problem for three-word sets . . 705--725 Pedro V. Silva and Benjamin Steinberg Extensions and submonoids of automatic monoids . . . . . . . . . . . . . . . . 727--754 Antonio Restivo and Pedro V. Silva On the lattice of prefix codes . . . . . 755--782 Honghui Wan and John C. Wootton Algorithms for computing lengths of chains in integral partition lattices 783--800 Gabriel Ciobanu and Mihai Rotaru Molecular interaction . . . . . . . . . 801--827 Wolfgang Slany Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete . . . . . . . . . . . . 829--843 Peter Damaschke Two short notes on the on-line travelling salesman: handling times and lookahead . . . . . . . . . . . . . . . 845--852 Kosaburo Hashiguchi Algorithms for determining the smallest number of nonterminals (states) sufficient for generating (accepting) a regular language R with $ R_1 \subseteq R \subseteq R_2 $ for given regular languages $ R_1 $, $ R_2 $ . . . . . . . 853--859 John M. Hitchcock MAX3SAT is exponentially hard to approximate if NP has positive dimension 861--869 M. Ageev Martin's game: a lower bound for the number of sets . . . . . . . . . . . . . 871--876 Anonymous Editorial board . . . . . . . . . . . . v--ix
Dingzhu Du and Peter Eades and Xuemin Lin Foreword . . . . . . . . . . . . . . . . 877 Franz Aurenhammer and Naoki Katoh and Hiromichi Kojima and Makoto Ohsaki and Yinfeng Xu Approximating uniform triangular meshes in polygons . . . . . . . . . . . . . . 879--895 Giuseppe Di Battista and Giuseppe Liotta and Anna Lubiw and Sue Whitesides Embedding problems for paths with direction constrained edges . . . . . . 897--917 Carmen Hernando and Michael E. Houle and Ferran Hurtado On local transformation of polygons with visibility properties . . . . . . . . . 919--937 Satoshi Fujita and Takeshi Hada Two-dimensional on-line bin packing problem with rotatable items . . . . . . 939--952 Magnús M. Halldórsson and Kazuo Iwama and Shuichi Miyazaki and Shiro Taketomi Online independent sets . . . . . . . . 953--962 Tomohiro Yamasaki and Hirotada Kobayashi and Yuuki Tokunaga and Hiroshi Imai One-way probabilistic reversible and quantum one-counter automata . . . . . . 963--976 Hirotaka Ono and Kazuhisa Makino and Toshihide Ibaraki Logical analysis of data with decomposable structures . . . . . . . . 977--995 Subhash Khot and Venkatesh Raman Parameterized complexity of finding subgraphs with hereditary properties . . 997--1008 Yuriy A. Reznik Some results on tries with adaptive branching . . . . . . . . . . . . . . . 1009--1026 Anonymous Author index . . . . . . . . . . . . . . 1027--1029
Marios Mavronicolas and Nikos Papadakis Trade-off results for connection management . . . . . . . . . . . . . . . 1--57 Frank Stomp Correctness of substring-preprocessing in Boyer--Moore's pattern matching algorithm . . . . . . . . . . . . . . . 59--78 Didier Caucal On infinite transition graphs having a decidable monadic theory . . . . . . . . 79--115 Marco Bernardo and Mario Bravetti Performance measure sensitive congruences for Markovian process algebras . . . . . . . . . . . . . . . . 117--160 Olivier Laurent Polarized proof-nets and $ \mu $-calculus . . . . . . . . . . . . . . . 161--188 Silvio Valentini A cartesian closed category in Martin-Löf's intuitionistic type theory 189--219 Madhavan Mukund and K. Narayan Kumar and Milind Sohoni Bounded time-stamping in message-passing systems . . . . . . . . . . . . . . . . 221--239 Parosh Aziz Abdulla and Bengt Jonsson Model checking of systems with many identical timed processes . . . . . . . 241--264 Dorel Lucanu Relaxed models for rewriting logic . . . 265--289 Cesare Tinelli and Christophe Ringeissen Unions of non-disjoint theories and combinations of satisfiability procedures . . . . . . . . . . . . . . . 291--353 M. Bravetti and A. Aldini Discrete time generative-reactive probabilistic processes with different advancing speeds . . . . . . . . . . . . 355--406 Franco Barbanera and Stefano Berardi A full continuous model of polymorphism 407--428 Koji Nakazawa Confluency and strong normalizability of call-by-value $ \mu $-calculus . . . . . 429--463 Andrea Maggiolo-Schettini and Adriano Peron and Simone Tini A comparison of Statecharts step semantics . . . . . . . . . . . . . . . 465--498 Carlos Iván Chesñevar and Jürgen Dix and Frieder Stolzenburg and G. R. Guillermo Ricardo Simari Relating defeasible and normal logic programming through transformation properties . . . . . . . . . . . . . . . 499--529 Patrick Cousot and Radhia Cousot Parsing as abstract interpretation of grammar semantics . . . . . . . . . . . 531--544 Zhaohui Zhu and Bin Li and Xi'an Xiao and Shifu Chen and Wujia Zhu A representation theorem for recovering contraction relations satisfying wci . . 545--564 Luca de Alfaro and Arjun Kapur Hybrid diagrams . . . . . . . . . . . . 565--597 Fabio Alessi and Paolo Baldan and Furio Honsell A category of compositional domain-models for separable Stone spaces 599--635 Luca Bernardinello and Carlo Ferigato and Lucia Pomello An algebraic model of observable properties in distributed systems . . . 637--668 T. Calders and J. Paredaens Axiomatization of frequent itemsets . . 669--693 Roberto M. Amadio and Denis Lugiez and Vincent Vanack\`ere On the symbolic reduction of processes with cryptographic functions . . . . . . 695--740 Cosimo Laneve A type system for JVM threads . . . . . 741--778 Yuxi Fu and Zhenrong Yang Understanding the mismatch combinator in chi calculus . . . . . . . . . . . . . . 779--830 Michael R. Laurence and Sebastian Danicic and Mark Harman and Rob Hierons and John Howroyd Equivalence of conservative, free, linear program schemas is decidable . . 831--862 Roberta Gori An abstract interpretation framework to reason on finite failure and other properties of finite and infinite computations . . . . . . . . . . . . . . 863--936 Mauno Rönkkö and Anders P. Ravn and Kaisa Sere Hybrid action systems . . . . . . . . . 937--973 Steffen van Bakel and Maribel Fernández Normalization, approximation, and semantics for combinator systems . . . . 975--1019 Reinhard Pichler Explicit versus implicit representations of subsets of the Herbrand universe . . 1021--1056 Fabio Martinelli Analysis of security protocols as open systems . . . . . . . . . . . . . . . . 1057--1106 Thierry Coquand A syntactical proof of the Marriage Lemma . . . . . . . . . . . . . . . . . 1107--1113 Anonymous Editorial board . . . . . . . . . . . . v--ix
G. Motet and J.-C. Geffroy Dependable computing: an overview . . . 1115--1126 Guohong Cao and Mukesh Singhal Checkpointing with mutable checkpoints 1127--1148 Antonio Caruso and Stefano Chessa and Piero Maestrini and Paolo Santi Fault-diagnosis of grid structures . . . 1149--1174 Christopher Colby and Karl Crary and Robert Harper and Peter Lee and Frank Pfenning Automated techniques for provably safe mobile code . . . . . . . . . . . . . . 1175--1199 I. S. W. B. Prasetya and S. D. Swierstra Factorizing fault tolerance . . . . . . 1201--1222 C. J. Walter and N. Suri The customizable fault/error model for dependable distributed systems . . . . . 1223--1251
Evripidis Bampis and Rodolphe Giroudeau and Jean-Claude König An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications 1883--1895
Shay Kutten and Paul Spirakis Preface . . . . . . . . . . . . . . . . 1 Jean-Claude Bermond and Nausica Marlin and David Peleg and Stéphane Perennes Directed virtual path layouts in ATM networks . . . . . . . . . . . . . . . . 3--28 Paola Flocchini and Bernard Mans and Nicola Santoro Sense of direction in distributed computing . . . . . . . . . . . . . . . 29--53 Maurice Herlihy and Sergio Rajsbaum A classification of wait-free loop agreement tasks . . . . . . . . . . . . 55--77 Fernando Pedone and André Schiper Optimistic atomic broadcast: a pragmatic viewpoint . . . . . . . . . . . . . . . 79--101 Jeremy Sussman and Keith Marzullo The Bancomat problem: an example of resource allocation in a partitionable asynchronous system . . . . . . . . . . 103--131 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Peter Kornerup and Jean-Claude Bajard and Christiane Frougny and Jean-Michel Muller Preface: Real Numbers and Computers . . 133--134 G. Hanrot and J. Rivat and G. Tenenbaum and P. Zimmermann Density results on floating-point invertible numbers . . . . . . . . . . . 135--141 Marc Daumas and Philippe Langlois Additive symmetries: the non-negative case . . . . . . . . . . . . . . . . . . 143--157 David W. Matula and Lee D. McFearin A $ p \times p $ bit fraction model of binary floating point division and extremal rounding cases . . . . . . . . 159--182 Abraham Ziv and Laurent Fournier Solving the generalized mask constraint for test generation of binary floating point add operation . . . . . . . . . . 183--201 David Lester and Paul Gowland Using PVS to validate the algorithms of an exact arithmetic . . . . . . . . . . 203--218
Cesare Tinelli and Teodor Rus Preface . . . . . . . . . . . . . . . . 219--221 Kamel Adi and Mourad Debbabi and Mohamed Mejri A new logic for electronic commerce protocols . . . . . . . . . . . . . . . 223--283 Riccardo Focardi and Roberto Gorrieri and Fabio Martinelli A comparison of three authentication properties . . . . . . . . . . . . . . . 285--327 Bart Jacobs and Erik Poll Coalgebras and monads in the semantics of Java . . . . . . . . . . . . . . . . 329--349 Eric Van Wyk Specification languages in algebraic compilers . . . . . . . . . . . . . . . 351--385 Anonymous Author index . . . . . . . . . . . . . . 387--388
Patrice Séébold Foreword . . . . . . . . . . . . . . . . 1--1 Anonymous Publications of Jean Berstel . . . . . . 3--7 Jean-Paul Allouche and Michael Baake and Julien Cassaigne and David Damanik Palindrome complexity . . . . . . . . . 9--31 Holger Austinat and Volker Diekert and Ulrich Hertrampf A structural property of regular frequency computations . . . . . . . . . 33--43 Marie-Pierre Béal and Olivier Carton and Christophe Prieur and Jacques Sakarovitch Squaring transducers: an efficient procedure for deciding functionality and sequentiality . . . . . . . . . . . . . 45--63 Dani\`ele Beauquier On probabilistic timed automata . . . . 65--84 Sre\vcko Brlek and Christophe Reutenauer On a valuation of rational subsets of $ Z^k $ Dédié \`a Jean Berstel . . . . . . . 85--96 Véronique Bruy\`ere Cumulative defect . . . . . . . . . . . 97--109 Arturo Carpi and Aldo de Luca Semiperiodic words and root-conjugacy 111--130 Christian Choffrut Minimizing subsequential transducers: a survey . . . . . . . . . . . . . . . . . 131--143 Philippe Chrétienne and Francis Sourd PERT scheduling with convex cost functions . . . . . . . . . . . . . . . 145--164 Robert Cori and Gilles Schaeffer Description trees and Tutte formulas . . 165--183 Maxime Crochemore Reducing space for index implementation 185--197 Andrzej Ehrenfeucht and Tero Harju and Ion Petre and David M. Prescott and Grzegorz Rozenberg Formal systems for gene assembly in ciliates . . . . . . . . . . . . . . . . 199--219 Christiane Frougny On-line digit set conversion in real base . . . . . . . . . . . . . . . . . . 221--235 Juhani Karhumäki and Ján Ma\vnuch and Wojciech Plandowski A defect theorem for bi-infinite words 237--243 Filippo Mignosi and Antonio Restivo and Pedro V. Silva On Fine and Wilf's theorem for bidimensional words . . . . . . . . . . 245--262 Arto Salomaa Composition sequences for functions over a finite domain . . . . . . . . . . . . 263--281 Patrice Séébold On some generalizations of the Thue--Morse morphism . . . . . . . . . . 283--298 Wolfgang Thomas Uniform and nonuniform recognizability 299--316 Jean-Eric Pin Algebraic tools for the concatenation product . . . . . . . . . . . . . . . . 317--342 Anonymous Editorial board . . . . . . . . . . . . v--ix
S. Arikawa and K. Furukawa and S. Morishita and H. Motoda Preface . . . . . . . . . . . . . . . . 343--344 Petr Hájek and Martin Hole a Formal logics of discovery and hypothesis formation by machine . . . . 345--357 Steffen Lange and Gunter Grieser Variants of iterative learning . . . . . 359--376 Yosuke Hayashi and Satoshi Matsumoto and Ayumi Shinohara and Masayuki Takeda Uniform characterizations of polynomial-query learnabilities . . . . 377--385 Yoshimitsu Kudoh and Makoto Haraguchi and Yoshiaki Okubo Data abstractions for decision tree induction . . . . . . . . . . . . . . . 387--416 João Gama Iterative Bayes . . . . . . . . . . . . 417--430 Genshiro Kitagawa and Tomoyuki Higuchi and Fumiyo N. Kondo Smoothness prior approach to explore mean structure in large-scale time series . . . . . . . . . . . . . . . . . 431--446 Eiji Takimoto and Akira Maruoka Top-down decision tree learning as information based boosting . . . . . . . 447--464 Masahiro Hirao and Hiromasa Hoshino and Ayumi Shinohara and Masayuki Takeda and Setsuo Arikawa A practical algorithm to find the best subsequence patterns . . . . . . . . . . 465--479 Tatsuya Akutsu and Satoru Miyano and Satoru Kuhara A simple greedy algorithm for finding functional relations: efficient implementation and average case analysis 481--495 Masayuki Takeda and Tomoko Fukuda and Ichiro Nanri and Mayumi Yamasaki and Koichi Tamari Discovering instances of poetic allusion from anthologies of classical Japanese poems . . . . . . . . . . . . . . . . . 497--524 Masayuki Takeda and Tetsuya Matsumoto and Tomoko Fukuda and Ichiro Nanri Discovering characteristic expressions in literary works . . . . . . . . . . . 525--546 Hayato Ohwada and Fumio Mizoguchi Integrating information visualization and retrieval for WWW information discovery . . . . . . . . . . . . . . . 547--571
André Berthiaume and John D. Rogers Foreword . . . . . . . . . . . . . . . . 573--573 John Watrous PSPACE has constant-round quantum interactive proof systems . . . . . . . 575--588 Pawel Horodecki and John A. Smolin and Barbara M. Terhal and Ashish V. Thapliyal Rank two bipartite bound entangled states do not exist . . . . . . . . . . 589--596 Lance Fortnow One complexity theorist's view of quantum computing . . . . . . . . . . . 597--610 A. Ehrenfeucht and G. Rozenberg Forbidding--enforcing systems . . . . . 611--638 Hermann Jung and Maria Serna and Paul Spirakis An efficient deterministic parallel algorithm for two processors precedence constraint scheduling . . . . . . . . . 639--652 G. Rozenberg and H. Spaink DNA computing by blocking . . . . . . . 653--665 Wei-Mei Chen and Gen-Huey Chen Divide-and-conquer recurrences associated with generalized heaps, optimal merge, and related structures 667--677 Xuemin Lin and Peter Eades Towards area requirements for drawing hierarchically planar graphs . . . . . . 679--695 Yuliang Zheng and Xian-Mo Zhang Connections among nonlinearity, avalanche and correlation immunity . . . 697--710 Andrés Moreira Universality and decidability of number-conserving cellular automata . . 711--721 Jack Jie Dai A stronger Kolmogorov zero-one law for resource-bounded measure . . . . . . . . 723--732 Anonymous Author index . . . . . . . . . . . . . . 733--735
Stephane Gaubert and Jean-Jacques Loiseau and Jean Mairesse and Maurice Nivat and Jean-Eric Pin Foreword . . . . . . . . . . . . . . . . 1--2 R. A. Cuninghame-Green and P. Butkovic The equation $ A \otimes x = B \otimes y $ over (max,$+$) . . . . . . . . . . . . 3--12 Jacob van der Woude and Subiono Conditions for the structural existence of an eigenvalue of a bipartite (min,max,+)-system . . . . . . . . . . . 13--24 Pierre Bernhard Minimax---or feared value---$ L^1 / L^\infty $ control . . . . . . . . . . . 25--44 Karel Zimmermann Disjunctive optimization, max-separable problems and extremal algebras . . . . . 45--54 Flavio d'Alessandro and Jacques Sakarovitch The finite power property in free groups 55--82 Nami Kobayashi Some properties of recognizable $ \mathcal {Z} $-subsets . . . . . . . . . 83--113 Ines Klimann A solution to the problem of $ (A, B) $-invariance for series . . . . . . . . 115--139 Jeremy Gunawardena From max-plus algebra to nonexpansive mappings: a nonlinear theory for discrete event systems . . . . . . . . . 141--167 Luca Aceto and Zoltán Ésik and Anna Ingólfsdóttir The max-plus algebra of the natural numbers has no finite equational basis 169--188 J.-P. Comet Application of Max-Plus algebra to biological sequence comparisons . . . . 189--217 Bertrand Ducourthial and Sébastien Tixeuil Self-stabilization with path algebra . . 219--236 Anonymous Editorial board . . . . . . . . . . . . v--ix
A. Nijholt and G. Scollo and D. Heylen Editorial . . . . . . . . . . . . . . . 237--241 Aravind K. Joshi A note on the strong and weak generative powers of formal systems . . . . . . . . 243--259 Hans-Peter Kolb and Jens Michaelis and Uwe Mönnich and Frank Morawietz An operational and denotational approach to non-context-freeness . . . . . . . . 261--289 James Rogers wMSO theories as grammar formalisms . . 291--320 Denys Duchier Dominance constraints with Boolean connectives: a model-eliminative treatment . . . . . . . . . . . . . . . 321--343 Edward P. Stabler and Edward L. Keenan Structural similarity within and among languages . . . . . . . . . . . . . . . 345--363 Karl-Michael Schneider Tabular parsing and algebraic transformations . . . . . . . . . . . . 365--389 P. Boullier Counting with range concatenation grammars . . . . . . . . . . . . . . . . 391--416 Peter R. J. Asveld Algebraic aspects of families of fuzzy languages . . . . . . . . . . . . . . . 417--445 D. Cantone and A. Formisano and E. G. Omodeo and C. G. Zarba Compiling dyadic first-order specifications into map algebra . . . . 447--475
Colin Fidge Foreword . . . . . . . . . . . . . . . . 477--477 Salvatore La Torre and Margherita Napoli Finite automata on timed $ \omega $-trees . . . . . . . . . . . . . . . . 479--505 Annabelle McIver and Carroll Morgan Almost-certain eventualities and abstract probabilities in the quantitative temporal logic qTL . . . . 507--534 Shane Saunders and Tadao Takaoka Improved shortest path algorithms for nearly acyclic graphs . . . . . . . . . 535--556 Peter Schachte Precise goal-independent abstract interpretation of constraint logic programs . . . . . . . . . . . . . . . . 557--577 Anonymous Author index . . . . . . . . . . . . . . 583--584
Ji í Adámek and Martín Escardó and Martin Hofmann Preface . . . . . . . . . . . . . . . . 1--1 Ji í Adámek On final coalgebras of continuous functors . . . . . . . . . . . . . . . . 3--29 Anna Bucalo and Carsten Führmann and Alex Simpson An equational notion of lifting monad 31--60 J. R. B. Cockett and Stephen Lack Restriction categories II: partial map classification . . . . . . . . . . . . . 61--102 Camillo Fiorentini and Silvio Ghilardi Combining word problems through rewriting in categories with products 103--149 Thomas T. Hildebrandt Towards categorical models for fairness: fully abstract presheaf semantics of SCCS with finite delay . . . . . . . . . 151--181 Martin Hyland and Andrea Schalk Glueing and orthogonality for models of linear logic . . . . . . . . . . . . . . 183--231 Lawrence S. Moss Recursion and corecursion have the same equational logic . . . . . . . . . . . . 233--267 A. S. Murawski and C.-H. L. Ong Exhausting strategies, joker games and full completeness for IMLL with Unit . . 269--305 Hideki Tsuiki A domain-theoretic semantics of lax generic functions . . . . . . . . . . . 307--331 Anonymous Editorial board . . . . . . . . . . . . v--ix
Jean-Yves Girard and Mitsuhiro Okada and Andre Scedrov Preface . . . . . . . . . . . . . . . . 333--333 V. Michele Abrusci Towards a semantics of proofs for non-commutative logic: multiplicatives and additives . . . . . . . . . . . . . 335--351 Vincent Danos and Jean-Baptiste Joinet and Harold Schellinx Computational isomorphisms in classical logic . . . . . . . . . . . . . . . . . 353--378 Stefano Guerrini and Simone Martini and Andrea Masini Coherence for sharing proof-nets . . . . 379--409 Raymond McDowell and Dale Miller and Catuscia Palamidessi Encoding transition systems in sequent calculus . . . . . . . . . . . . . . . . 411--437 Vaughan Pratt Chu spaces as a semantic bridge between linear logic and mathematics . . . . . . 439--471 Christian Retoré Handsome proof-nets: perfect matchings and cographs . . . . . . . . . . . . . . 473--488 Lorenzo Tortora de Falco Additives of linear logic and normalization---Part I: A (restricted) Church--Rosser property . . . . . . . . 489--524 Max I. Kanovich and Mitsuhiro Okada and Andre Scedrov Phase semantics for light linear logic 525--549 Misao Nagayama and Mitsuhiro Okada A graph-theoretic characterization theorem for multiplicative fragment of non-commutative linear logic . . . . . . 551--573 Anonymous Author index . . . . . . . . . . . . . . 575--576
Ji\vrí Sgall and Ale Pultr Foreword . . . . . . . . . . . . . . . . 1--1 Andris Ambainis and Arnolds \kKikusts Exact results for accepting probabilities of quantum automata . . . 3--25 Albert Atserias Improved bounds on the Weak Pigeonhole Principle and infinitely many primes from weaker axioms . . . . . . . . . . . 27--39 Chris Barrett and Harry B. Hunt III and Madhav V. Marathe and S. S. Ravi and Daniel J. Rosenkrantz and Richard E. Stearns Reachability problems for sequential dynamical systems with threshold functions . . . . . . . . . . . . . . . 41--64 Markus Bläser The complexity of bivariate power series arithmetic . . . . . . . . . . . . . . . 65--83 Ahmed Bouajjani and Peter Habermehl and Richard Mayr Automatic verification of recursive procedures with one integer parameter 85--106 Sabin Cautis and Filippo Mignosi and Jeffrey Shallit and Ming-wei Wang and Soroosh Yazdani Periodicity, morphisms, and matrices . . 107--121 Giovanni Di Crescenzo Sharing one secret vs. sharing many secrets . . . . . . . . . . . . . . . . 123--140 Pavol \vDuri and Ján Ma\vnuch On the computational complexity of infinite words . . . . . . . . . . . . . 141--151 Hervé Fournier Quantifier rank for parity of embedded finite models . . . . . . . . . . . . . 153--169 Viliam Geffert Space hierarchy theorem revised . . . . 171--187 Viliam Geffert and Carlo Mereghetti and Giovanni Pighizzini Converting two-way nondeterministic unary automata into simpler automata . . 189--203 Thanh Minh Hoang and Thomas Thierauf The complexity of the characteristic and the minimal polynomial . . . . . . . . . 205--222 Jarkko Kari Synchronizing finite automata on Eulerian digraphs . . . . . . . . . . . 223--232 Andreas Klein and Martin Kutrib Fast one-way cellular automata . . . . . 233--250 Chiu-Yuen Koo and Tak-Wah Lam and Tsuen-Wan Ngan and Kunihiko Sadakane and Kar-Keung To On-line scheduling with tight deadlines 251--261 Daniel Král' and Jan Kratochvíl and Heinz-Jürgen Voss Mixed hypergraphs with bounded degree: edge-coloring of mixed multigraphs . . . 263--278 Sven O. Krumke and Willem E. de Paepe and Diana Poensgen and Leen Stougie News from the online traveling repairman 279--294 Nir Piterman and Moshe Y. Vardi From bidirectionality to alternation . . 295--321 Pavel Pudlák On reducibility and symmetry of disjoint NP pairs . . . . . . . . . . . . . . . . 323--339 Luigi Santocanale On the equational definition of the least prefixed point . . . . . . . . . . 341--370 K. Sutner The size of power automata . . . . . . . 371--386 Martin Thimm On the approximability of the Steiner tree problem . . . . . . . . . . . . . . 387--402 Anonymous Author index . . . . . . . . . . . . . . 403--404 Anonymous Editorial board . . . . . . . . . . . . v--ix
Jie Wang Preface . . . . . . . . . . . . . . . . 1--2 Oswin Aichholzer and Franz Aurenhammer and Ferran Hurtado and Hannes Krasser Towards compatible triangulations . . . 3--13 Jin-Yi Cai and Eric Bach On testing for zero polynomials by a set of points with bounded precision . . . . 15--25 Wun-Tat Chan and Tak-Wah Lam and Hing-Fung Ting and Prudence W. H. Wong On-line stream merging in a general setting . . . . . . . . . . . . . . . . 27--46 Otfried Cheong and Chan-Su Shin and Antoine Vigneron Computing farthest neighbors on a convex polytope . . . . . . . . . . . . . . . . 47--58 Zhe Dang and Oscar H. Ibarra and Richard A. Kemmerer Generalized discrete timed automata: decidable approximations for safety verification . . . . . . . . . . . . . . 59--74 Rob Duncan and Jianbo Qian and Antoine Vigneron and Binhai Zhu Polynomial time algorithms for three-label point labeling . . . . . . . 75--87 Liying Kang and Hong Qiao and Erfang Shan and Dingzhu Du Lower bounds on the minus domination and $k$-subdomination numbers . . . . . . . 89--98 Wen-Lian Hsu and Ross M. McConnell PC trees and circular-ones arrangements 99--116 Michal Koucký Log-space constructible universal traversal sequences for cycles of length $ O(n^{4.03}) $ . . . . . . . . . . . . 117--144 Xiang-Yang Li Generating well-shaped $d$-dimensional Delaunay Meshes . . . . . . . . . . . . 145--165 Enrico Nardelli and Guido Proietti and Peter Widmayer Finding the most vital node of a shortest path . . . . . . . . . . . . . 167--177 Bodo Manthey Non-approximability of weighted multiple sequence alignment . . . . . . . . . . . 179--192 Anonymous Editorial board . . . . . . . . . . . . v--ix
Maurice Margenstern Foreword . . . . . . . . . . . . . . . . 193--194 Didier Caucal On the transition graphs of Turing machines . . . . . . . . . . . . . . . . 195--223 Henning Fernau Nonterminal complexity of programmed grammars . . . . . . . . . . . . . . . . 225--251 D. Besozzi and G. Mauri and G. P\uaun and C. Zandron Gemmating P systems: collapsing hierarchies . . . . . . . . . . . . . . 253--267 Pierluigi Frisco Direct constructions of universal extended H systems . . . . . . . . . . . 269--293 Carlos Martín-Vide and Gheorghe P\uaun and Juan Pazos and Alfonso Rodríguez-Patón Tissue P systems . . . . . . . . . . . . 295--326 Francine Herrmann and Maurice Margenstern A universal cellular automaton in the hyperbolic plane . . . . . . . . . . . . 327--364 K. Sutner Cellular automata and intermediate degrees . . . . . . . . . . . . . . . . 365--375
Jan Van den Bussche and Victor Vianu Foreword . . . . . . . . . . . . . . . . 377--377 Leonid Libkin Expressive power of SQL . . . . . . . . 379--404 Marcelo Arenas and Leopoldo Bertossi and Jan Chomicki and Xin He and Vijay Raghavan and Jeremy Spinrad Scalar aggregation in inconsistent databases . . . . . . . . . . . . . . . 405--434 Jeff Edmonds and Jarek Gryz and Dongming Liang and Renée J. Miller Mining for empty spaces in large data sets . . . . . . . . . . . . . . . . . . 435--452 Gösta Grahne and Alex Thomo Algebraic rewritings for optimizing regular path queries . . . . . . . . . . 453--471 William Hesse The dynamic complexity of transitive closure is in DynTC$^0$ . . . . . . . . 473--485 Chung Keung Poon Dynamic orthogonal range queries in OLAP 487--510 Rakesh K. Sinha and Randeep Bhatia and Chung-Min Chen Asymptotically optimal declustering schemes for $2$-dim range queries . . . 511--534 Anonymous Author index . . . . . . . . . . . . . . 535--536
A. Viola Preface . . . . . . . . . . . . . . . . 1--1 Ali Akhavi The optimal LLL algorithm is still polynomial in fixed dimension . . . . . 3--23 Pedro Berrizbeitia and Mauricio Odremán and Juan Tena Ayuso Primality test for numbers $M$ with a large power of $5$ dividing $ M^4 - 1$ 25--36 Olivier Carton and Max Michel Unambiguous Büchi automata . . . . . . . 37--81 Serafino Cicerone and Gabriele Di Stefano and Daniele Frigioni and Umberto Nanni A fully dynamic algorithm for distributed shortest paths . . . . . . . 83--102 Myra B. Cohen and Charles J. Colbourn Optimal and pessimal orderings of Steiner triple systems in disk arrays 103--117 Sylvie Corteel and Mario Valencia-Pabon and Dani\`ele Gardy and Dominique Barth and Alain Denise The permutation-path coloring problem on trees . . . . . . . . . . . . . . . . . 119--143 Celina M. H. de Figueiredo and João Meidanis and Célia Picinin de Mello and Carmen Ortiz Decompositions for the edge colouring of reduced indifference graphs . . . . . . 145--155 Maribel Fernández and Ian Mackie Operational equivalence for interaction nets . . . . . . . . . . . . . . . . . . 157--181 David Fernández-Baca Decomposable multi-parameter matroid optimization problems . . . . . . . . . 183--198 Joachim von zur Gathen and Thomas Lücking Subresultants revisited . . . . . . . . 199--239 Andreas Goerdt and Mike Molloy Analysis of edge deletion processes on faulty random regular graphs . . . . . . 241--260 Peter J. Grabner and Arnold Knopfmacher and Helmut Prodinger Combinatorics of geometrically distributed random variables: run statistics . . . . . . . . . . . . . . . 261--270 Claudio Gutiérrez Equations in free semigroups with involution and their relation to equations in free groups . . . . . . . . 271--280 Valentine Kabanets Almost $k$-wise independence and hard Boolean functions . . . . . . . . . . . 281--295 F. Laroussinie and Ph. Schnoebelen and M. Turuani On the expressivity and complexity of quantitative branching-time temporal logics . . . . . . . . . . . . . . . . . 297--315 Guy Louchard and John W. Turner Generalized covariances of multi-dimensional Brownian excursion local times . . . . . . . . . . . . . . 317--336 Richard Mayr Undecidable problems in unreliable computations . . . . . . . . . . . . . . 337--354 F. K. Miyazawa and Y. Wakabayashi Cube packing . . . . . . . . . . . . . . 355--366 Lucia Moura Rank inequalities and separation algorithms for packing designs and sparse triple systems . . . . . . . . . 367--384 Jaroslav Opatrny Uniform multi-hop all-to-all optical routings in rings . . . . . . . . . . . 385--397 Brett Stevens The anti-Oberwolfach solution: pancyclic $2$-factorizations of complete graphs 399--424 Stephen Taylor and Marianne Durand Emerging behavior as binary search trees are symmetrically updated . . . . . . . 425--445 Brigitte Vallée Dynamical analysis of a class of Euclidean algorithms . . . . . . . . . . 447--486 Michele Zito Small maximal matchings in random graphs 487--507 Anonymous Author index . . . . . . . . . . . . . . 509--510 Anonymous Editorial board . . . . . . . . . . . . v--ix
Takeshi Shinohara and Carl H. Smith and Thomas Zeugmann Foreword . . . . . . . . . . . . . . . . 1--4 Akihiro Yamamoto Hypothesis finding based on upward refinement of residue hypotheses . . . . 5--19 Hiroshi Sakamoto and Kouichi Hirata and Hiroki Arimura Learning elementary formal systems with queries . . . . . . . . . . . . . . . . 21--50 Steffen Lange and Gunter Grieser and Klaus P. Jantke Advanced elementary formal systems . . . 51--70 Steffen Lange and Jochen Nessel Decision lists over regular patterns . . 71--87 Yasuhito Mukouchi and Masako Sato Refutable language learning with a neighbor system . . . . . . . . . . . . 89--110 Sanjay Jain and Efim Kinber and Rolf Wiehagen and Thomas Zeugmann On learning of functions refutably . . . 111--143 Wolfgang Merkle and Frank Stephan Refuting learning revisited . . . . . . 145--177 Takashi Yokomori Polynomial-time identification of very simple grammars from positive data . . . 179--206 Seishi Okamoto and Nobuhiro Yugami Effects of domain characteristics on instance-based learning algorithms . . . 207--233 Tatsuya Akutsu and Satoru Kuhara and Osamu Maruyama and Satoru Miyano Identification of genetic networks by strategic gene disruptions and gene overexpressions under a boolean model 235--251 Takuya Kida and Tetsuya Matsumoto and Yusuke Shibata and Masayuki Takeda and Ayumi Shinohara and Setsuo Arikawa Collage system: a unifying framework for compressed pattern matching . . . . . . 253--272 Anonymous Editorial board . . . . . . . . . . . . v--ix
David Wolfram Preface . . . . . . . . . . . . . . . . 273--273 Mariangiola Dezani-Ciancaglini and Paula Severi and Fer-Jan de Vries Infinitary lambda calculus and discrimination of Berarducci trees . . . 275--302 Rod Downey and Lance Fortnow Uniformly hard languages . . . . . . . . 303--315 Michael R. Fellows and Catherine McCartin On the parametric complexity of schedules to minimize tardy tasks . . . 317--324 Bakhadyr Khoussainov On algebraic and logical specifications of classes of regular languages . . . . 325--346 Padmanabhan Krishnan Automatic synthesis of a subclass of schedulers in timed systems . . . . . . 347--363 Eric Martin and Arun Sharma and Frank Stephan Learning power and language expressiveness . . . . . . . . . . . . . 365--383
Furio Honsell and Marino Miculan Preface . . . . . . . . . . . . . . . . 385--386 Martín Abadi and Bruno Blanchet Secrecy types for asymmetric communication . . . . . . . . . . . . . 387--415 Luca Aceto and Zoltán Ésik and Anna Ingólfsdóttir Equational theories of tropical semirings . . . . . . . . . . . . . . . 417--469 Michel Bidoit and Rolf Hennicker and Alexander Kurz Observational logic, constructor-based logic, and their duality . . . . . . . . 471--510 Miko\laj Boja\'nczyk The finite graph problem for two-way alternating automata . . . . . . . . . . 511--528 Nadia Busi and Gianluigi Zavattaro Expired data collection in shared dataspaces . . . . . . . . . . . . . . . 529--556 Cristiano Calcagno and Peter O'Hearn and Richard Bornat Program logic and equivalence in the presence of garbage collection . . . . . 557--581 Gerwin Klein and Tobias Nipkow Verified bytecode verifiers . . . . . . 583--626 Anonymous Author index . . . . . . . . . . . . . . 627--628
Bruno Courcelle The monadic second-order logic of graphs XIV: uniformly sparse graphs and edge set quantifications . . . . . . . . . . 1--36 Letizia Magnoni and Massimo Mirolli and Franco Montagna and Giulia Simi PAC learning of probability distributions over a discrete domain . . 37--63 Julio Aracena and Eric Goles Complexity of perceptron recognition for a class of geometric patterns . . . . . 65--79 M. Kiwi Algebraic testing and weight distributions of codes . . . . . . . . . 81--106 F. K. Hwang A survey on multi-loop networks . . . . 107--121 Chiara Epifanio and Michel Koskas and Filippo Mignosi On a conjecture on bidimensional words 123--150 David R. Wood Optimal three-dimensional orthogonal graph drawing in the general position model . . . . . . . . . . . . . . . . . 151--178 Miklós Bartha and Miklós Krész Structuring the elementary components of graphs having a perfect internal matching . . . . . . . . . . . . . . . . 179--210 Zhi-Zhong Chen and Tao Jiang and Guohui Lin and Jianjun Wen and Dong Xu and Jinbo Xu and Ying Xu Approximation algorithms for NMR spectral peak assignment . . . . . . . . 211--229 R. Baeza-Yates and J. Gabarró and X. Messeguer Fringe analysis of synchronized parallel insertion algorithms in $2$--$3$ Trees 231--271 Subhas C. Nandy and Sandip Das and Partha P. Goswami An efficient $k$ nearest neighbors searching algorithm for a query line . . 273--288 Dahlia Malkhi and Yishay Mansour and Michael K. Reiter Diffusion without false rumors: on propagating updates in a Byzantine environment . . . . . . . . . . . . . . 289--306 Markus Holzer and Pierre McKenzie Alternating and empty alternating auxiliary stack automata . . . . . . . . 307--326 Olivier Finkel On omega context free languages which are Borel sets of infinite rank . . . . 327--346 Dietrich Kuske Towards a language theory for infinite N-free pomsets . . . . . . . . . . . . . 347--386 Kjell Lemström and Lauri Hella Approximate pattern matching and transitive closure logics . . . . . . . 387--412 Zhe Dang and Pierluigi San Pietro and Richard A. Kemmerer Presburger liveness verification of discrete timed automata . . . . . . . . 413--438 Leah Epstein and Rob van Stee Lower bounds for on-line single-machine scheduling . . . . . . . . . . . . . . . 439--450 Michaël Rusinowitch and Mathieu Turuani Protocol insecurity with a finite number of sessions and composed keys is NP-complete . . . . . . . . . . . . . . 451--475 Francesca Fiorenzi Cellular automata and strongly irreducible shifts of finite type . . . 477--493 Shankara Narayanan Krishna and Raghavan Rama Breaking DES using P systems . . . . . . 495--508 Bruce W. Watson A new regular grammar pattern matching algorithm . . . . . . . . . . . . . . . 509--521 Bruno Durand and Enrico Formenti and Zsuzsanna Róka Number-conserving cellular automata I: decidability . . . . . . . . . . . . . . 523--535 Lars Engebretsen and Jonas Holmerin Towards optimal lower bounds for clique and chromatic number . . . . . . . . . . 537--584 Alain Giorgetti An asymptotic study for path reversal 585--602 Marcel Wild Idempotent and co-idempotent stack filters and min--max operators . . . . . 603--631 H. Fernau and M. Holzer and R. Freund Hybrid modes in cooperating distributed grammar systems: combining the $t$-mode with the modes $ \leq k$ and $ = k$ . . 633--662 Alexander Okhotin On the closure properties of linear conjunctive languages . . . . . . . . . 663--685 Oscar H. Ibarra and Zhe Dang Eliminating the storage tape in reachability constructions . . . . . . . 687--706 Adam L. Buchsbaum and Raffaele Giancarlo and Jeffery R. Westbrook On finding common neighborhoods in massive graphs . . . . . . . . . . . . . 707--718 Michael U. Gerber and Daniel Kobler Algorithms for vertex-partitioning problems on graphs with fixed clique-width . . . . . . . . . . . . . . 719--734 P.-C. Héam Some complexity results for polynomial rational expressions . . . . . . . . . . 735--741 Y. J. Liu Regular component decomposition of regular languages . . . . . . . . . . . 743--749 Andrea E. F. Clementi and Miriam Di Ianni and Riccardo Silvestri The minimum broadcast range assignment problem on linear multi-hop wireless networks . . . . . . . . . . . . . . . . 751--761 Wojciech Rytter On maximal suffixes and constant-space linear-time versions of KMP algorithm 763--774 Pedro García and José Ruiz and Manuel Vazquez de Parga Bilateral locally testable languages . . 775--783 Erzsébet Csuhaj-Varjú and Gheorghe P\uaun and György Vaszil PC grammar systems with five context-free components generate all recursively enumerable languages . . . . 785--794 Leslie G. Valiant Corrigendum to ``Expressiveness of matchgates'': [Theoret. Comput. Sci. 289(1) (2002) 457--471] . . . . . . . . 795--795 Anonymous Author index . . . . . . . . . . . . . . 797--799 Anonymous Editorial board . . . . . . . . . . . . v--ix
Peter Aczel and Ji í Adámek and Stefan Milius and Ji í Velebil Infinite trees and completely iterative theories: a coalgebraic view . . . . . . 1--45 Gian Luca Cattani and Glynn Winskel Presheaf models for CCS-like languages 47--89 Stacy E. Finkelstein and Peter Freyd and James Lipton A new framework for declarative programming . . . . . . . . . . . . . . 91--160 Otmane A\"\it Mohamed and Xiaoyu Song and Eduard Cerny On the non-termination of M-based abstract state enumeration . . . . . . . 161--179 Axel Wabenhorst Induction in the Timed Interval Calculus 181--207 Sándor Vágvölgyi Intersection of finitely generated congruences over term algebra . . . . . 209--234 Stéphane Demri A polynomial space construction of tree-like models for logics with local chains of modal connectives . . . . . . 235--258 Raymond Devillers and Hanna Klaudel and Robert-C. Riemann General parameterised refinement and recursion for the M-net calculus . . . . 259--300 Abdelwaheb Ayari and David Basin and Felix Klaedtke Decision procedures for inductive Boolean functions based on alternating automata . . . . . . . . . . . . . . . . 301--329 Alexander Rabinovich Automata over continuous time . . . . . 331--363 Lorenzo Carlucci A new proof-theoretic proof of the independence of Kirby--Paris' Hydra Theorem . . . . . . . . . . . . . . . . 365--378 Andrew D. Gordon and Alan Jeffrey Typing correspondence assertions for communication protocols . . . . . . . . 379--409 Luca Aceto and Patricia Bouyer and Augusto Burgueño and Kim G. Larsen The power of reachability testing for timed automata . . . . . . . . . . . . . 411--475 R. David Decidability results for primitive recursive algorithms . . . . . . . . . . 477--504 Anonymous Author index . . . . . . . . . . . . . . 505--505 Anonymous Master index . . . . . . . . . . . . . . 507--519 Anonymous Editorial board . . . . . . . . . . . . v--ix
Yiannis N. Moschovakis On primitive recursive algorithms and the greatest common divisor function . . 1--30 A. V. Kelarev and O. V. Sokratova On congruences of automata defined by directed graphs . . . . . . . . . . . . 31--43 Martin Sauerhoff Approximation of boolean functions by combinatorial rectangles . . . . . . . . 45--78 Masashi Katsura and Yuji Kobayashi and Friedrich Otto Undecidable properties of monoids with word problem solvable in linear time. Part II. Cross sections and homological and homotopical finiteness conditions 79--101 Kyriakos N. Sgarbas and Nikos D. Fakotakis and George K. Kokkinakis Optimal insertion in deterministic DAWGs 103--117 Alexandros V. Gerbessiotis and Constantinos J. Siniolakis Architecture independent parallel selection with applications to parallel priority queues . . . . . . . . . . . . 119--142 Richard Nock Complexity in the case against accuracy estimation . . . . . . . . . . . . . . . 143--165 Véronique Terrier Two-dimensional cellular automata and deterministic on-line tessalation automata . . . . . . . . . . . . . . . . 167--186 Arto Salomaa and Petr Sosík Watson--Crick D0L systems: the power of one transition . . . . . . . . . . . . . 187--200 Claudio Ferretti and Giancarlo Mauri and Gheorghe P\uaun and Claudio Zandron On three variants of rewriting P systems 201--215 Olivier Finkel Ambiguity in omega context free languages . . . . . . . . . . . . . . . 217--270 R. Boliac and V. Lozin Independent domination in finitely defined classes of graphs . . . . . . . 271--284 Manfred Peter The asymptotic distribution of elements in automatic sequences . . . . . . . . . 285--312 Andries van der Walt and Sigrid Ewert A property of random context picture grammars . . . . . . . . . . . . . . . . 313--320 John Ellis and Frank Ruskey and Joe Sawada and Jamie Simpson Euclidean strings . . . . . . . . . . . 321--340 Enrico Formenti On the sensitivity of additive cellular automata in Besicovitch topologies . . . 341--354 Paola Flocchini and Alessandro Roncato and Nicola Santoro Computing on anonymous networks with sense of direction . . . . . . . . . . . 355--379 Chin Lung Lu and Sheng-Lung Peng and Chuan Yi Tang Efficient minus and signed domination in graphs . . . . . . . . . . . . . . . . . 381--397 Nguyen Huong Lam Completing comma-free codes . . . . . . 399--415 Igor Dolinka The multiplicative fragment of the Yanov equational theory . . . . . . . . . . . 417--425 Leonidas Georgiadis Arborescence optimization problems solvable by Edmonds' algorithm . . . . . 427--437 Marcy Barge and Beverly Diamond and Charles Holton Asymptotic orbits of primitive substitutions . . . . . . . . . . . . . 439--450 Kazuo Iwama and Akihiro Matsuura and Mike Paterson A family of NFAs which need $ 2^n$-deterministic states . . . . . . . 451--462 Van Bang Le and Bert Randerath On stable cutsets in line graphs . . . . 463--475 Joe Sawada A fast algorithm to generate necklaces with fixed content . . . . . . . . . . . 477--489 L. H. Harper On the bandwidth of a Hamming graph . . 491--498 Anonymous Author index . . . . . . . . . . . . . . 499--500 Anonymous Editorial board . . . . . . . . . . . . v--ix
G. Richomme Conjugacy and episturmian morphisms . . 1--34 Peter Damaschke Nearly optimal strategies for special cases of on-line capital investment . . 35--44 Alois Panholzer Analysis of multiple quickselect variants . . . . . . . . . . . . . . . . 45--91 Zhe Dang Pushdown timed automata: a binary reachability characterization and safety verification . . . . . . . . . . . . . . 93--121 Jerzy Mycka -Recursion and infinite limits . . . . . 123--133 Sándor Vágvölgyi Term rewriting restricted to ground terms . . . . . . . . . . . . . . . . . 135--165 S. Brlek and A. Ladouceur A note on differentiable palindromes . . 167--178 Rocco De Nicola and Anna Labella Nondeterministic regular expressions as solutions of equational systems . . . . 179--189 Jingchao Chen Optimizing stable in-place merging . . . 191--210 Wojciech Rytter Application of Lempel--Ziv factorization to the approximation of grammar-based compression . . . . . . . . . . . . . . 211--222 Dong Kyue Kim and Yoo Ah Kim and Kunsoo Park Generalizations of suffix arrays to multi-dimensional matrices . . . . . . . 223--238 Klaus Jansen Approximate strong separation with application in fractional graph coloring and preemptive scheduling . . . . . . . 239--256 George Karakostas and Richard J. Lipton and Anastasios Viglas On the complexity of intersecting finite state automata and versus . . . . . . . 257--274 Zhuhan Jiang and Olivier de Vel and Bruce Litow Unification and extension of weighted finite automata applicable to image compression . . . . . . . . . . . . . . 275--294 Pál Dömösi and Chrystopher L. Nehaniv and John L. Rhodes Finite semigroups, feedback, and the Letichevsky criteria on non-empty words in finite automata . . . . . . . . . . . 295--317 Aleksei V. Fishkin and Guochuan Zhang On maximizing the throughput of multiprocessor tasks . . . . . . . . . . 319--335 Andrea E. F. Clementi and Angelo Monti and Riccardo Silvestri Distributed broadcast in radio networks of unknown topology . . . . . . . . . . 337--364 Alexander Okhotin A recognition and parsing algorithm for arbitrary conjunctive grammars . . . . . 365--399 Dong Kyue Kim and Yoo Ah Kim and Kunsoo Park Generalizations of suffix arrays to multi-dimensional matrices . . . . . . . 401--416 Nadia Creignou and Hervé Daudé Generalized satisfiability problems: minimal elements and phase transitions 417--430 Alberto Bertoni and Christian Choffrut and Massimiliano Goldwurm and Violetta Lonati On the number of occurrences of a symbol in words of regular languages . . . . . 431--456 Lane A. Hemaspaandra and Harald Hempel P-immune sets with holes lack self-reducibility properties . . . . . . 457--466 Till Tantau Query complexity of membership comparable sets . . . . . . . . . . . . 467--474 Therese Biedl and Jonathan F. Buss and Erik D. Demaine and Martin L. Demaine and Mohammadtaghi Hajiaghayi and Tomá Vina Palindrome recognition using a multidimensional tape . . . . . . . . . 475--480 Juha Honkala Decidability results for Watson--Crick D0L systems with nonregular triggers . . 481--488 Artur Czumaj and Leszek G\casieniec and Daya Ram Gaur and Ramesh Krishnamurti and Wojciech Rytter and Michele Zito On polynomial-time approximation algorithms for the variable length scheduling problem . . . . . . . . . . . 489--495 Marek Chrobak Errata to: ``Finite Automata and Unary Languages'': [Theoret. Comput. Sci. 47 (1986) 149--158] . . . . . . . . . . . . 497--498 Anonymous Author index . . . . . . . . . . . . . . 499--500 Anonymous Editorial board . . . . . . . . . . . . v--ix
Dani\`ele Beauquier and Yuri Matijassevich Foreword . . . . . . . . . . . . . . . . 1--1 Dani\`ele Beauquier and Dimitri Grigoriev and Yuri Matiyasevich Biography of A. O. Slissenko . . . . . . 3--5 A. Arnold and A. Vincent and I. Walukiewicz Games for synthesis of controllers with partial observation . . . . . . . . . . 7--34 A. Carbone and M. Gromov Functional labels and syntactic entropy on DNA strings and proteins . . . . . . 35--51 Patrick Cégielski and François Heroult and Denis Richard On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity 53--62 Michael Dekhtyar and Alexander Dikovsky and Mars Valiev On feasible cases of checking multi-agent systems behavior . . . . . . 63--81 Dima Grigoriev and Edward A. Hirsch Algebraic proof systems over formulas 83--102 Ir\`ene Guessarian and Eugénie Foustoucos and Theodore Andronikos and Foto Afrati On temporal logic versus datalog . . . . 103--133 Roman Kolpakov and Gregory Kucherov Finding approximate repetitions under Hamming distance . . . . . . . . . . . . 135--156 J. A. Makowsky and J. P. Mariño Tree-width and the monadic quantifier hierarchy . . . . . . . . . . . . . . . 157--170 L. Maksimova Complexity of some problems in positive and related calculi . . . . . . . . . . 171--185 G. Mints A termination proof for epsilon substitution using partial derivations 187--213 Damian Niwi\'nski and Igor Walukiewicz A gap property of deterministic tree languages . . . . . . . . . . . . . . . 215--231 Alexander A. Razborov Resolution lower bounds for the weak functional pigeonhole principle . . . . 233--243 Sergei Soloviev and Vladimir Orevkov On categorical equivalence of Gentzen-style derivations in IMLL . . . 245--260 Anonymous Editorial board . . . . . . . . . . . . v--ix
B. Durand and L. Vuillon Foreword . . . . . . . . . . . . . . . . 265--265 James Propp Generalized domino-shuffling . . . . . . 267--301 Igor Pak Tile invariants: new horizons . . . . . 303--331 J. C. Fournier Combinatorics of perfect matchings in plane bipartite graphs and application to tilings . . . . . . . . . . . . . . . 333--351 Nicolas Thiant An $ O(n \log n) $-algorithm for finding a domino tiling of a plane picture whose number of holes is bounded . . . . . . . 353--374 Sébastien Desreux An algorithm to generate exactly once every tiling with lozenges of a domain 375--408 Fumei Lam and Lior Pachter Forcing numbers of stop signs . . . . . 409--416 Dani\`ele Beauquier and Maurice Nivat A codicity undecidable problem in the plane . . . . . . . . . . . . . . . . . 417--430 Olaf Delgado-Friedrichs Data structures and algorithms for tilings I . . . . . . . . . . . . . . . 431--445 Thomas L. Fitzkee and Kevin G. Hockett and E. Arthur Robinson, Jr. A weakly mixing tiling dynamical system with a smooth model . . . . . . . . . . 447--462 Daniel Lenz Hierarchical structures in Sturmian dynamical systems . . . . . . . . . . . 463--490 Christiane Frougny and Jean-Pierre Gazeau and Rudolf Krejcar Additive and multiplicative properties of point sets based on beta-integers . . 491--516 Krzysztof Lorys and Katarzyna E. Paluch New approximation algorithm for RTILE problem . . . . . . . . . . . . . . . . 517--537 Kari Eloranta The bounded eight-vertex model . . . . . 539--552 Anonymous Author index . . . . . . . . . . . . . . 553--554
An. Muchnik and A. Semenov and M. Ushakov Almost periodic sequences . . . . . . . 1--33 Sara Brunetti and Alain Daurat An algorithm reconstructing convex lattice sets . . . . . . . . . . . . . . 35--57 Guy Louchard and Helmut Prodinger Ascending runs of sequences of geometrically distributed random variables: a probabilistic analysis . . 59--86 Joong Chae Na and Alberto Apostolico and Costas S. Iliopoulos and Kunsoo Park Truncated suffix trees and their application to data compression . . . . 87--101 Marco Carpentieri On the simulation of quantum Turing machines . . . . . . . . . . . . . . . . 103--128 Maciej Li\'skiewicz and Mitsunori Ogihara and Seinosuke Toda The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes . . . . . . . . . . 129--156 Antonín Ku\vcera The complexity of bisimilarity-checking for one-counter processes . . . . . . . 157--183 Jia Lee and Katsunobu Imai and Kenichi Morita Simulation of one-dimensional cellular automata by uniquely parallel parsable grammars . . . . . . . . . . . . . . . . 185--200 Li Sheng $2$-Role assignments on triangulated graphs . . . . . . . . . . . . . . . . . 201--214 Joan Feigenbaum and Arvind Krishnamurthy and Rahul Sami and Scott Shenker Hardness results for multicast cost sharing . . . . . . . . . . . . . . . . 215--236 Guangting Chen and Guoliang Xue A PTAS for weight constrained Steiner trees in series--parallel graphs . . . . 237--247 Karell Bertet and Jens Gustedt and Michel Morvan Weak-order extensions of an order . . . 249--268 Enrico Formenti and Aristide Grange Number conserving cellular automata II: dynamics . . . . . . . . . . . . . . . . 269--290 Kosaburo Hashiguchi and Yoshito Wada and Shuji Jimbo Regular binoid expressions and regular binoid languages . . . . . . . . . . . . 291--313 Zoltán Fülöp and Zsolt Gazdag Shape preserving top-down tree transducers . . . . . . . . . . . . . . 315--339 Pilu Crescenzi and Alberto Del Lungo and Roberto Grossi and Elena Lodi and Linda Pagli and Gianluca Rossi Text sparsification via local maxima . . 341--364 Wei-Ting Cao and Zhi-Ying Wen Some properties of the factors of Sturmian sequences . . . . . . . . . . . 365--385 Masahiko Fukuyama A Nim game played on graphs . . . . . . 387--399 Masahiko Fukuyama A Nim game played on graphs II . . . . . 401--419 Yassine Hacha\"\ichi A descriptive complexity approach to the linear hierarchy . . . . . . . . . . . . 421--429 John M. Hitchcock Fractal dimension and logarithmic loss unpredictability . . . . . . . . . . . . 431--441 V. Y. Popov The approximate period problem for DNA alphabet . . . . . . . . . . . . . . . . 443--447 Sándor Vágvölgyi On ground tree transformations and congruences induced by tree automata . . 449--459 Xiaoyan Cheng and Xiufeng Du and Manki Min and Hung Q. Ngo and Lu Ruan and Jianhua Sun and Weili Wu Super link-connectivity of iterated line digraphs . . . . . . . . . . . . . . . . 461--469 Erik D. Demaine and Alejandro López-Ortiz and J. Ian Munro On universally easy classes for NP-complete problems . . . . . . . . . . 471--476 William Gasarch and Evan Golub and Aravind Srinivasan When does a random Robin Hood win? . . . 477--484 Pablo Dartnell and Alejandro Maass and Fernando Schwartz Combinatorial constructions associated to the dynamics of one-sided cellular automata . . . . . . . . . . . . . . . . 485--497 Anonymous Author index . . . . . . . . . . . . . . 499--500 Anonymous Editorial board . . . . . . . . . . . . v--ix
Ralph Kopperman and Michael B. Smyth and Dieter Spreen Foreword . . . . . . . . . . . . . . . . 1--2 Nina Amenta and Thomas J. Peters and Alexander C. Russell Computational topology: ambient isotopic approximation of $2$-manifolds . . . . . 3--15 Vasco Brattka Recursive quasi-metric spaces . . . . . 17--42 Vasco Brattka and Gero Presser Computability on subsets of metric spaces . . . . . . . . . . . . . . . . . 43--76 Thierry Coquand and Guo-Qiang Zhang A representation of stably compact spaces, and patch topology . . . . . . . 77--84 Giovanni Curi Constructive metrisability in point-free topology . . . . . . . . . . . . . . . . 85--109 Antony Galton A generalized topological view of motion in discrete space . . . . . . . . . . . 111--134 K. A. Hardie and S. Salbany and J. J. C. Vermeulen and P. J. Witbooi A non-Hausdorff quaternion multiplication . . . . . . . . . . . . . 135--158 Reinhold Heckmann A non-topological view of dcpos as convergence spaces . . . . . . . . . . . 159--186 Pascal Hitzler and Anthony Karel Seda Generalized metrics and uniquely determined logic programs . . . . . . . 187--219 T. Yung Kong The Khalimsky topologies are precisely those simply connected topologies on $ \mathbb {Z}^n $ whose connected sets include all $ 2^n$-connected sets but no $ (3^n - 1)$-disconnected sets . . . . . 221--235 Ralph Kummetz and Dietrich Kuske The topology of Mazurkiewicz traces . . 237--258 Jimmie D. Lawson and Bin Lu Riemann and Edalat integration on domains . . . . . . . . . . . . . . . . 259--275 Keye Martin Ideal models of spaces . . . . . . . . . 277--297 Keye Martin The regular spaces with countably based models . . . . . . . . . . . . . . . . . 299--310 Pedro Resende and Steven Vickers Localic sup-lattices and tropological systems . . . . . . . . . . . . . . . . 311--346 Giovanni Sambin Some points in formal topology . . . . . 347--408 M. P. Schellekens A characterization of partial metrizability: domains are quantifiable 409--432 Peter M. Schuster Unique existence, approximate solutions, and countable choice . . . . . . . . . . 433--455 J. \vSlapal Closure operations for digital topology 457--471 L. S. V\^\i and D. S. Bridges A constructive theory of point-set nearness . . . . . . . . . . . . . . . . 473--489 Julian Webster Cell complexes, oriented matroids and digital geometry . . . . . . . . . . . . 491--502 Anonymous Author index . . . . . . . . . . . . . . 503--503 Anonymous Editorial board . . . . . . . . . . . . v--ix
G. E. Farr The Go polynomials of a graph . . . . . 1--18 Mark Daley and Oscar H. Ibarra and Lila Kari Closure and decidability properties of some language classes with respect to ciliate bio-operations . . . . . . . . . 19--38 Dietmar Wätjen Function-dependent teams in eco-grammar systems . . . . . . . . . . . . . . . . 39--53 Chin Lung Lu and Chuan Yi Tang and Richard Chia-Tung Lee The full Steiner tree problem . . . . . 55--67 József Balogh and János A. Csirik and Yuval Ishai and Eyal Kushilevitz Private computation using a PEZ dispenser . . . . . . . . . . . . . . . 69--84 M. H. Albert and M. D. Atkinson and N. Ru\vskuc Regular closed sets of permutations . . 85--100 Petr Sosík Watson--Crick D0L systems: generative power and undecidable problems . . . . . 101--112 \cStefan Andrei and Salvador Valerio Cavadini and Wei-Ngan Chin A new algorithm for regularizing one-letter context-free grammars . . . . 113--122 Liang Zhang and K. P. Shum and Shou-Li Peng Completion of codes with finite bi-decoding delays . . . . . . . . . . . 123--137 Tetsu Iwata and Tomonobu Yoshino and Kaoru Kurosawa Non-cryptographic primitive for pseudorandom permutation . . . . . . . . 139--154 Nissim Francez and Michael Kaminski An algebraic characterization of deterministic regular languages over infinite alphabets . . . . . . . . . . . 155--175 Klaus Ambos-Spies and Wolfgang Merkle and Jan Reimann and Sebastiaan A. Terwijn Almost complete sets . . . . . . . . . . 177--194 L. A. Bunimovich and D. M. Kreslavskiy Lorentz gas cellular automata on graphs 195--221 Annalisa De Bonis and Ugo Vaccaro Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels . . . . . . . . 223--243 Laurent Rosaz The word problem for congruences is NP-hard . . . . . . . . . . . . . . . . 245--268 Alexis Bienvenüe and Olivier François Global convergence for evolution strategies in spherical problems: some simple proofs and difficulties . . . . . 269--289 Sylvain Gravier and Mehdi Mhalla and Eric Tannier On a modular domination game . . . . . . 291--303 Leah Epstein and Csanád Imreh and Rob van Stee More on weighted servers or F is better than L . . . . . . . . . . . . . . . . . 305--317 Eric Angel and Evripidis Bampis and Alexander Kononov On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems . . . . . . . . . . 319--338 Ruy Luiz Milidiú and Artur Alves Pessoa and Eduardo Sany Laber The complexity of makespan minimization for pipeline transportation . . . . . . 339--351 Ji\vrí \vSíma and Pekka Orponen Exponential transients in continuous-time Liapunov systems . . . . 353--372 Lucian Ilie and Sheng Yu Reducing NFAs by invariant equivalences 373--390 Vânia M. F. Dias and Guilherme D. da Fonseca and Celina M. H. de Figueiredo and Jayme L. Szwarcfiter The stable marriage problem with restricted pairs . . . . . . . . . . . . 391--405 Patricia A. Evans and Andrew D. Smith and H. Todd Wareham On the complexity of finding common approximate substrings . . . . . . . . . 407--430 Magnús M. Halldórsson and Robert W. Irving and Kazuo Iwama and David F. Manlove and Shuichi Miyazaki and Yasufumi Morita and Sandy Scott Approximability results for stable marriage problems with ties . . . . . . 431--447 Alexander Meduna and Martin \vSvec Forbidding ET0L grammars . . . . . . . . 449--469 Serge Dulucq and Laurent Tichit RNA secondary structure comparison: exact analysis of the Zhang--Shasha tree edit algorithm . . . . . . . . . . . . . 471--484 Víctor Dalmau and Peter Jeavons Learnability of quantified formulas . . 485--511 René Ndoundam and Maurice Tchuente Exponential transient length generated by a neuronal recurrence equation . . . 513--533 A. E. Frid Arithmetical complexity of symmetric D0L words . . . . . . . . . . . . . . . . . 535--542 Klaus Jansen and Roberto Solis-Oba An asymptotic fully polynomial time approximation scheme for bin covering 543--551 Anonymous Author index . . . . . . . . . . . . . . 553--554 Anonymous Editorial board . . . . . . . . . . . . v--x
J. Néraud Preface . . . . . . . . . . . . . . . . 1--1 Jean-Paul Allouche and Jeffrey Shallit The ring of $k$-regular sequences, II 3--29 Ali Aberkane Words whose complexity satisfies . . . . 31--46 Boris Adamczewski Balances for fixed points of primitive substitutions . . . . . . . . . . . . . 47--75 D. S. Ananichev and A. Cherubini and M. V. Volkov Image reducing words and subgroups of free groups . . . . . . . . . . . . . . 77--92 Tullio Ceccherini-Silberstein and Antonio Mach\`\i and Fabio Scarabotti On the entropy of regular languages . . 93--102 Tullio Ceccherini-Silberstein and Wolfgang Woess Growth-sensitivity of context-free languages . . . . . . . . . . . . . . . 103--116 Wit Fory and Tomasz Krawczyk and James A. Anderson Semiretracts---a counterexample and some results . . . . . . . . . . . . . . . . 117--127 Yannick Guesnet On maximal synchronous codes . . . . . . 129--138 Tero Harju and Dirk Nowotka On the independence of equations in three variables . . . . . . . . . . . . 139--172 Christophe Hohlweg and Christophe Reutenauer Lyndon words, permutations and trees . . 173--178 Patrice Séébold Lyndon factorization of the Prouhet words . . . . . . . . . . . . . . . . . 179--197 Pedro V. Silva The homomorphism problem for trace monoids . . . . . . . . . . . . . . . . 199--215 Anonymous Editorial board . . . . . . . . . . . . v--x
Elena Barcucci and Alberto Del Lungo Preface . . . . . . . . . . . . . . . . 219--220 Didier Arqu\`es and Anne Micheli A generalization of the language of ukasiewicz coding rooted planar hypermaps . . . . . . . . . . . . . . . 221--239 Nicolas Bonichon and Mohamed Mosbah Watermelon uniform random generation with applications . . . . . . . . . . . 241--256 Mireille Bousquet-Mélou and Marko Petkov\vsek Walks confined in a quadrant are not always D-finite . . . . . . . . . . . . 257--276 Michel Bousquet and Cedric Chauve and Gilbert Labelle and Pierre Leroux Two bijective proofs for the arborescent form of the Good--Lagrange formula and some applications to colored rooted trees and cacti . . . . . . . . . . . . 277--302 L. S. Chandran and L. Ibarra and F. Ruskey and J. Sawada Generating and characterizing the perfect elimination orderings of a chordal graph . . . . . . . . . . . . . 303--317 Emeric Deutsch and Helmut Prodinger A bijection between directed column-convex polyominoes and ordered trees of height at most three . . . . . 319--325 L. Ferrari and E. Grazzini and E. Pergola and S. Rinaldi Some bijective results about the area of Schröder paths . . . . . . . . . . . . . 327--335 G. Labelle and C. Lamathe and P. Leroux A classification of plane and planar $2$-trees . . . . . . . . . . . . . . . 337--363 Marc Noy Graphs determined by polynomial invariants . . . . . . . . . . . . . . . 365--384 Dominique Poulalhon and Gilles Schaeffer A bijection for triangulations of a polygon with interior points and multiple edges . . . . . . . . . . . . . 385--401 Louis W. Shapiro Bijections and the Riordan group . . . . 403--413 Vincent Vajnovszki A loopless algorithm for generating the permutations of a multiset . . . . . . . 415--431 Markus Vöge and Anthony J. Guttmann On the number of hexagonal polyominoes 433--453
Josep Díaz and Tom Payne Foreword . . . . . . . . . . . . . . . . 455--455 L. H. Harper Accidental combinatorist, an autobiography . . . . . . . . . . . . . 457--472 Sergei L. Bezrukov and Robert Elsässer Edge-isoperimetric problems for cartesian powers of regular graphs . . . 473--492 Béla Bollobás and Imre Leader Union of shadows . . . . . . . . . . . . 493--502 Tiziana Calamoneri and Annalisa Massini and Imrich Vrt'o New results on edge-bandwidth . . . . . 503--513 E. Rodney Canfield Integer partitions and the Sperner property . . . . . . . . . . . . . . . . 515--529 J. Díaz and N. Do and M. J. Serna and N. C. Wormald Bounds on the max and min bisection of random cubic and random $4$-regular graphs . . . . . . . . . . . . . . . . . 531--547 R. Elsässer and R. Královi and B. Monien Sparse topologies with small spectrum size . . . . . . . . . . . . . . . . . . 549--565 David Muradian The bandwidth minimization problem for cyclic caterpillars with hair length $1$ is NP-complete . . . . . . . . . . . . . 567--572 Anonymous Author index . . . . . . . . . . . . . . 573--574
J. J. M. M. Rutten Behavioural differential equations: a coinductive calculus of streams, automata, and power series . . . . . . . 1--53 Yuxi Fu and Zhenrong Yang Tau laws for pi calculus . . . . . . . . 55--130 H. Peter Gumm and Jesse Hughes and Tobias Schröder Distributivity of categories of coalgebras . . . . . . . . . . . . . . . 131--143 Walter Keller Clustering for Petri nets . . . . . . . 145--197 Foto Afrati and Manolis Gergatsoulis and Francesca Toni Linearisability on datalog programs . . 199--226 Karim Nour and Christophe Raffalli Simple proof of the completeness theorem for second-order classical and intuitionistic logic by reduction to first-order mono-sorted logic . . . . . 227--237 Olivier Danvy and Lasse R. Nielsen A first-order one-pass CPS transformation . . . . . . . . . . . . . 239--257 Jean-Louis Krivine Dependent choice, `quote' and the clock 259--276 Witold Charatonik and Silvano Dal Zilio and Andrew D. Gordon and Supratik Mukhopadhyay and Jean-Marc Talbot Model checking mobile ambients . . . . . 277--331 Andrew D. Ker and Hanno Nickau and C.-H. Luke Ong Adapting innocent game models for the Böhm tree $ \lambda $-theory . . . . . . 333--366 Yifeng Chen A fixpoint theory for non-monotonic parallelism . . . . . . . . . . . . . . 367--392 P. Mateus and M. Morais and C. Nunes and A. Pacheco and A. Sernadas and C. Sernadas Categorical foundations for randomly timed automata . . . . . . . . . . . . . 393--427 Yann Loyer and Nicolas Spyratos and Daniel Stamate Parametrized semantics of logic programs---a unifying framework . . . . 429--447 Uri Abraham Self-stabilizing timestamps . . . . . . 449--515 Anonymous Author index . . . . . . . . . . . . . . 517--517 Anonymous Editorial board . . . . . . . . . . . . v--x
Thomas Ehrhard and Laurent Regnier The differential lambda-calculus . . . . 1--41 Peter Selinger Order-incompleteness and finite lambda reduction models . . . . . . . . . . . . 43--63 Vashti Galpin A format for semantic equivalence comparison . . . . . . . . . . . . . . . 65--109 Thomas Forster Better-quasi-orderings and coinduction 111--123 Claudio Hermida and Paulo Mateus Paracategories I: internal paracategories and saturated partial algebras . . . . . . . . . . . . . . . . 125--156 Paul Gardiner Power simulation and its relation to traces and failures refinement . . . . . 157--176 Dirk Pattinson Coalgebraic modal logic: soundness, completeness and decidability of local consequence . . . . . . . . . . . . . . 177--193 Sándor Vágvölgyi Right-linear half-monadic term rewrite systems . . . . . . . . . . . . . . . . 195--211 Lutz Straßburger MELL in the calculus of structures . . . 213--285 Zhaohui Zhu and Xian Xiao and Yong Zhou and Wujia Zhu Normal conditions for inference relations and injective models . . . . . 287--311 Jan A. Bergstra and Alban Ponse and Mark B. van der Zwaag Branching time and orthogonal bisimulation equivalence . . . . . . . . 313--355 Francisco Durán and José Meseguer Structured theories and institutions . . 357--380 Daniel Kirsten and Jerzy Marcinkowski Two techniques in the area of the star problem in trace monoids . . . . . . . . 381--412 Bernard Boigelot On iterating linear transformations over recognizable sets of integers . . . . . 413--468 Dan R. Ghica and Guy McCusker The regular-language semantics of second-order idealized A$_{\mbox {lgol}}$ . . . . . . . . . . . . . . . . 469--502 Ruggero Lanotte and Andrea Maggiolo-Schettini and Simone Tini Concurrency in timed automata . . . . . 503--527 Markus Lohrey Realizability of high-level message sequence charts: closing the gaps . . . 529--554 Anonymous Author index . . . . . . . . . . . . . . 555--555 Anonymous Editorial Board . . . . . . . . . . . . v--x
Jack J. Dai and James I. Lathrop and Jack H. Lutz and Elvira Mayordomo Finite-state dimension . . . . . . . . . 1--33 Marc Chemillier Synchronization of musical words . . . . 35--60 Savio S. H. Tse and Francis C. M. Lau New bounds for multi-label interval routing . . . . . . . . . . . . . . . . 61--77 Olivier Serre Vectorial languages and linear temporal logic . . . . . . . . . . . . . . . . . 79--116 Annie Choquet-Geniet and Emmanuel Grolleau Minimal schedulability interval for real-time systems of periodic tasks with offsets . . . . . . . . . . . . . . . . 117--134 Eric Angel and Evripidis Bampis and Laurent Gourv\`es Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem . . . . . . . . . . . . . . . . 135--146 Hing Leung and Viktor Podolskiy The limitedness problem on distance automata: Hashiguchi's method revisited 147--158 Ron Lavi and Noam Nisan Competitive analysis of incentive compatible on-line auctions . . . . . . 159--180 Lothar M. Schmitt Theory of Genetic Algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling . . . . . . . . . . . . . 181--231 Traian-Florin \cSerb\uanu\ct\ua Extending Parikh matrices . . . . . . . 233--246 Oliver Jenkinson and Luca Q. Zamboni Characterisations of balanced words via orderings . . . . . . . . . . . . . . . 247--271 Wai-Fong Chuan Moments of conjugacy classes of binary words . . . . . . . . . . . . . . . . . 273--285 Therese Biedl and Brov\vna Brejová and Erik D. Demaine and Ang\`ele M. Hamel and Alejandro López-Ortiz and Tomá\vs Vina\vr Finding hidden independent sets in interval graphs . . . . . . . . . . . . 287--307 Richard Groult and Martine Léonard and Laurent Mouchard Speeding up the detection of evolutive tandem repeats . . . . . . . . . . . . . 309--328 Andreas Brandstädt and Feodor F. Dragan and Ho\`ang-Oanh Le and Van Bang Le Tree spanners on chordal graphs: complexity and algorithms . . . . . . . 329--354 Anton Mityagin On the complexity of finding a local maximum of functions on discrete planar subsets . . . . . . . . . . . . . . . . 355--363 Henrik Björklund and Sven Sandberg and Sergei Vorobyov Memoryless determinacy of parity and mean payoff games: a simple proof . . . 365--378 Yoshifumi Manabe and Naka Tajima $ (h, k)$-Arbiters for $h$-out-of-$k$ mutual exclusion problem . . . . . . . . 379--392 Michal Kunc Undecidability of the trace coding problem and some decidable cases . . . . 393--456 Hee-Kap Ahn and Siu-Wing Cheng and Otfried Cheong and Mordecai Golin and René van Oostrum Competitive facility location: the Voronoi game . . . . . . . . . . . . . . 457--467 Julien Cervelle and Bruno Durand Tilings: recursivity and regularity . . 469--477 P. Dukes and Alan C. H. Ling A combinatorial error bound for $t$-point-based sampling . . . . . . . . 479--488 Jérémie Chalopin and Hing Leung On factorization forests of finite height . . . . . . . . . . . . . . . . . 489--499 Sanming Zhou A channel assignment problem for optical networks modelled by Cayley graphs . . . 501--511 Michael Alekhnovich Mutilated chessboard problem is exponentially hard for resolution . . . 513--525 Alejandro López-Ortiz and Sven Schuierer On-line parallel heuristics, processor scheduling and robot searching under the competitive framework . . . . . . . . . 527--537 Anonymous Author index . . . . . . . . . . . . . . 539--540 Anonymous Master index . . . . . . . . . . . . . . 541--553 Anonymous Editorial Board . . . . . . . . . . . . v--x
A. J. Kfoury and J. B. Wells Principality and type inference for intersection types using expansion variables . . . . . . . . . . . . . . . 1--70 Claudio Hermida and P. Mateus Paracategories II: adjunctions, fibrations and examples from probabilistic automata theory . . . . . 71--103 Felix Joachimski Confluence of the coinductive $ \lambda $-calculus . . . . . . . . . . . . . . . 105--119 Atsushi Igarashi and Naoki Kobayashi A generic type system for the Pi-calculus . . . . . . . . . . . . . . 121--163 Li Jiao and To-Yat Cheung and Weiming Lu On liveness and boundedness of asymmetric choice nets . . . . . . . . . 165--197 Yohji Akama Limiting partial combinatory algebras 199--220 Agostino Dovier and Carla Piazza and Alberto Policriti An efficient algorithm for computing bisimulation equivalence . . . . . . . . 221--256 J. Adámek and H.-E. Porst On tree coalgebras and coalgebra presentations . . . . . . . . . . . . . 257--283 Ernst-Erich Doberkat and Eugenio G. Omodeo ER modelling from first relational principles . . . . . . . . . . . . . . . 285--323 Markus Müller-Olm Precise interprocedural dependence analysis of parallel programs . . . . . 325--388 James Bailey and Guozhu Dong and Kotagiri Ramamohanarao On the decidability of the termination problem of active database systems . . . 389--437 R\uazvan Diaconescu Interpolation in Grothendieck Institutions . . . . . . . . . . . . . . 439--461 Rob van Glabbeek and Ursula Goltz Well-behaved flow event structures for parallel composition and action refinement . . . . . . . . . . . . . . . 463--478 María Alpuente and Moreno Falaschi and Ginés Moreno and Germán Vidal Rules $+$ strategies for transforming lazy functional logic programs . . . . . 479--525 Stacy E. Finkelstein and Peter Freyd and James Lipton Erratum to: ``A new framework for declarative programming'': [Theoret. Comput. Sci. 300 (2003) 91--160] . . . . 527--527 Anonymous Author index . . . . . . . . . . . . . . 529--529 Anonymous Editorial Board . . . . . . . . . . . . v--x
Stephan Eidenbenz and Matthew Hennessy and Rafael Morales and Francisco Triguero and Peter Widmayer and Ricardo Conejo Preface . . . . . . . . . . . . . . . . 1--2 Moses Charikar and Kevin Chen and Martin Farach-Colton Finding frequent items in data streams 3--15 Lars Engebretsen and Jonas Holmerin and Alexander Russell Inapproximability results for equations over finite groups . . . . . . . . . . . 17--45 Seth Pettie A new approach to all-pairs shortest paths on real-weighted graphs . . . . . 47--74 Tomasz Radzik Improving time bounds on maximum generalised flow computations by contracting the network . . . . . . . . 75--97 Keye Martin and Michael Mislove and James Worrell Measuring the probabilistic powerdomain 99--119 C.-H. L. Ong and P. Di Gianantonio Games characterizing Levy--Longo trees 121--142 Anonymous Editorial Board . . . . . . . . . . . . v--x
Rudolf Freund and Carlos Martín-Vide and Gheorghe P\uaun From regulated rewriting to computing with membranes: collapsing hierarchies 143--188 Nageswara S. V. Rao Probabilistic quickest path algorithm 189--201 Véronique Terrier Two-dimensional cellular automata and their neighborhoods . . . . . . . . . . 203--222 Stéphane Vialette On the computational complexity of $2$-interval pattern matching problems 223--249 Kosaburo Hashiguchi and Naoto Sakakibara and Shuji Jimbo Equivalence of regular binoid expressions and regular expressions denoting binoid languages over free binoids . . . . . . . . . . . . . . . . 251--266 Yoshiyuki Karuno and Hiroshi Nagamochi An approximability result of the multi-vehicle scheduling problem on a path with release and handling times . . 267--280 Zhang Yi Global exponential convergence of recurrent neural networks with variable delays . . . . . . . . . . . . . . . . . 281--293 Pierluigi Frisco The conformon-P system: a molecular and cell biology-inspired computability model . . . . . . . . . . . . . . . . . 295--319 Chuan-Kun Wu and Ed Dawson Correlation immunity and resiliency of symmetric Boolean functions . . . . . . 321--335 Jochen Alber and Jens Gramm and Jiong Guo and Rolf Niedermeier Computing the similarity of two sequences with nested arc annotations 337--358 Oscar H. Ibarra and Zhe Dang On two-way FA with monotonic counters and quadratic Diophantine equations . . 359--378 Oscar H. Ibarra and Zhe Dang and Omer Egecioglu Catalytic P systems, semilinear sets, and vector addition systems . . . . . . 379--399 M. Habib and L. Nourine and O. Raynaud and E. Thierry Computational aspects of the $2$-dimension of partially ordered sets 401--431 Antonio Cano Gómez and Jean-Éric Pin Shuffle on positive varieties of languages . . . . . . . . . . . . . . . 433--461 Benjamin Doerr Typical rounding problems . . . . . . . 463--477 Daowen Qiu and Mingsheng Ying Characterizations of quantum automata 479--489 Anonymous Author index . . . . . . . . . . . . . . 491--492
Bruce W. Watson and Derick Wood Introduction . . . . . . . . . . . . . . 1--1 Anne Bergeron and Sylvie Hamel From cascade decompositions to bit-vector algorithms . . . . . . . . . 3--16 Bernard Boigelot and Louis Latour Counting the solutions of Presburger equations without enumerating them . . . 17--29 Jean-Marc Champarnaud and Gérard Duchamp Derivatives of rational expressions and related theorems . . . . . . . . . . . . 31--44 Jan Daciuk and Gertjan van Noord Finite automata for compact representation of tuple dictionaries . . 45--56 Zhe Dang and Tevfik Bultan and Oscar H. Ibarra and Richard A. Kemmerer Past pushdown timed automata and safety verification . . . . . . . . . . . . . . 57--71 Jacques Farré and J. Fortes Gálvez Bounded-connect noncanonical discriminating-reverse parsers . . . . . 73--91 N. Friburger and D. Maurel Finite-state transducer cascades to extract named entities in texts . . . . 93--104 Tamás Gaál Deciding sequentiability of finite-state transducers by finite-state pattern-matching . . . . . . . . . . . . 105--117 Dominique Geniet and Jean-Philippe Dubernard Scheduling hard sporadic tasks with regular languages and generating functions . . . . . . . . . . . . . . . 119--132 F. Katritzke and W. Merzenich and M. Thomas Enhancements of partitioning techniques for image compression using weighted finite automata . . . . . . . . . . . . 133--144 André Kempe Extraction and recoding of input-$ \epsilon $-cycles in finite state transducers . . . . . . . . . . . . . . 145--158 Lynette van Zijl Generalized acceptance, succinctness and supernondeterministic finite automata 159--172 Anonymous Editorial Board . . . . . . . . . . . . v--ix
N. Abe and R. Khardon Foreword . . . . . . . . . . . . . . . . 173--174 Dana Angluin Queries revisited . . . . . . . . . . . 175--194 Yuri Kalnishkan and Volodya Vovk and Michael V. Vyugin Loss functions, complexities, and the Legendre transformation . . . . . . . . 195--207 Sanjay Jain and Frank Stephan Learning how to separate . . . . . . . . 209--228 Sandra Zilles Separation of uniform learning classes 229--265 François Denis and Aurélien Lemay and Alain Terlutte Learning regular languages using RFSAs 267--294 C. de la Higuera and J. C. Janodet Inference of $ \omega $-languages from prefixes . . . . . . . . . . . . . . . . 295--312
Rudolf Fleischer and Richard J. Nowakowski Preface . . . . . . . . . . . . . . . . 313--313 Ingo Althöfer Improved game play by multiple computer hints . . . . . . . . . . . . . . . . . 315--324 Erik D. Demaine and Martin L. Demaine and Rudolf Fleischer Solitaire Clobber . . . . . . . . . . . 325--338 Benjamin Doerr European tenure games . . . . . . . . . 339--351 Ioana Dumitriu and Joel Spencer A Halfliar's game . . . . . . . . . . . 353--369 Peter L. Erd\Hos and Ulrich Faigle and Winfried Hochstättler and Walter Kern Note on the game chromatic index of trees . . . . . . . . . . . . . . . . . 371--376 Sándor P. Fekete and Rudolf Fleischer and Aviezri Fraenkel and Matthias Schmitt Traveling salesmen in the presence of competition . . . . . . . . . . . . . . 377--392 Aviezri S. Fraenkel Complexity, appeal and challenges of combinatorial games . . . . . . . . . . 393--415 J. P. Grossman Periodicity in one-dimensional peg duotaire . . . . . . . . . . . . . . . . 417--425 F. Harary and W. Slany and O. Verbitsky On the lengths of symmetry breaking--preserving games on graphs . . 427--446 Markus Holzer and Stefan Schwoon Assembling molecules in ATOMIX is hard 447--462 S. Howse and R. J. Nowakowski Periodicity and arithmetic-periodicity in hexadecimal games . . . . . . . . . . 463--472 Daniel Král' and Vladan Majerech and Ji\vrí Sgall and Tomá\vs Tichý and Gerhard Woeginger It is tough to be a plumber . . . . . . 473--484 U. Lorenz and B. Monien Error analysis in minimax trees . . . . 485--498 Raymond Georg Snatzke New results of exhaustive search in the game Amazons . . . . . . . . . . . . . . 499--509 Mark H. M. Winands and Jos W. H. M. Uiterwijk and H. Jaap van den Herik An effective two-level proof-number search algorithm . . . . . . . . . . . . 511--525 David Wolfe and William Fraser Counting the number of games . . . . . . 527--532 J. P. Grossman Appendix A: Report on the First International Clobber Tournament . . . . 533--537 Erik D. Demaine and Rudolf Fleischer and Aviezri S. Fraenkel and Richard J. Nowakowski Appendix B: Open problems at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory . . . . . . . 539--543 Anonymous Author index . . . . . . . . . . . . . . 545--546
Tomás Feder and Florent Madelaine and Iain A. Stewart Dichotomies for classes of homomorphism problems involving unary functions . . . 1--43 Christian Deppe Strategies for the Renyi--Ulam Game with fixed number of lies . . . . . . . . . . 45--55 Enrica Duchi and Jean-Marc Fedou and Simone Rinaldi From object grammars to ECO systems . . 57--95 Shinya Sano and Naoto Miyoshi and Ryohei Kataoka $m$-Balanced words: A generalization of balanced words . . . . . . . . . . . . . 97--120 Vlady Ravelomanana and Loÿs Thimonier Forbidden subgraphs in connected graphs 121--171 Amihood Amir and Ayelet Butman and Maxime Crochemore and Gad M. Landau and Mary Schaps Two-dimensional pattern matching with rotations . . . . . . . . . . . . . . . 173--187 F. Blanchet-Sadri and Ajay Chriscoe Local periods and binary partial words: an algorithm . . . . . . . . . . . . . . 189--216 Fabrizio Angiulli and Giovambattista Ianni and Luigi Palopoli On the complexity of inducing categorical and quantitative association rules . . . . . . . . . . . . . . . . . 217--249 Jia-Yan Yao Some properties of Ising automata . . . 251--279 A. Rybalov On the P--NP problem over real matrix rings . . . . . . . . . . . . . . . . . 281--285 Serge Burckel and Marianne Morillon Sequential computation of linear Boolean mappings . . . . . . . . . . . . . . . . 287--292 Jun Gu and Xiao-Dong Hu and Xiaohua Jia and Mu-Hong Zhang Routing algorithm for multicast under multi-tree model in optical networks . . 293--301 Anonymous Editorial Board . . . . . . . . . . . . v--ix
Kenichiro Noguchi Simple $8$-state minimal time solution to the firing squad synchronization problem . . . . . . . . . . . . . . . . 303--334 Nicola Dimitri Efficiency and equilibrium in the electronic mail game; the general case 335--349 Annalisa De Bonis and Alfredo De Santis Randomness in secret sharing and visual cryptography schemes . . . . . . . . . . 351--374 F. H. Chang and J. Y. Guo and F. K. Hwang and C. K. Lin Wide-sense nonblocking for symmetric or asymmetric $3$-stage Clos networks under various routing strategies . . . . . . . 375--386 Zoltán Fülöp and Zsolt Gazdag and Heiko Vogler Hierarchies of tree series transformations . . . . . . . . . . . . 387--429 Chang-Hsiung Tsai Linear array and ring embeddings in conditional faulty hypercubes . . . . . 431--443 Henning Bordihn Context-freeness of the power of context-free languages is undecidable 445--449 Michael Domaratzki and Alexander Okhotin Representing recursively enumerable languages by iterated deletion . . . . . 451--457 Amr Elmasry On the sequential access theorem and deque conjecture for splay trees . . . . 459--466 Anonymous Author index . . . . . . . . . . . . . . 467--468
Michael Mislove Mathematical Foundations of Programming Semantics: Papers from MFPS 14 and MFPS 16 . . . . . . . . . . . . . . . . . . . 1--2 S. Berardi and C. Berline Building continuous webbed models for system F . . . . . . . . . . . . . . . . 3--34 Andrej Bauer and Lars Birkedal and D. S. Dana S. Scott Equilogical spaces . . . . . . . . . . . 35--59 Cristiano Calcagno Two-level languages for program optimization . . . . . . . . . . . . . . 61--81 Andrea Schalk and Valeria de Paiva Poset-valued sets or how to build models for linear logics . . . . . . . . . . . 83--107 Michal Kone\vcný Real functions incrementally computable by finite automata . . . . . . . . . . . 109--133 M. P. Schellekens The correspondence between partial metrics and semivaluations . . . . . . . 135--149 Zhe Yang Encoding types in ML-like languages . . 151--190 Z. Füredi and R. P. Kurshan Minimal length test vectors for multiple-fault detection . . . . . . . . 191--208 Gavin Lowe Semantic models for information flow . . 209--256 David J. Pym and P. W. Peter W. O'Hearn and Hongseok Yang Possible worlds and resources: the semantics of BI . . . . . . . . . . . . 257--305 Anonymous Editorial board . . . . . . . . . . . . v--ix
Ioannis Z. Emiris and Bernard Mourrain and Victor Y. Pan Preface . . . . . . . . . . . . . . . . 307--308 Zheng-Jian Bai and R. H. Raymond H. Chan Inverse eigenproblem for centrosymmetric and centroskew matrices and their approximation . . . . . . . . . . . . . 309--318 D. A. Bini and L. Gemignani Bernstein--Bezoutian matrices . . . . . 319--333 A. Bompadre and G. Matera and R. Wachenchauzer and A. Waissbein Polynomial equation solving by lifting procedures for ramified fibers . . . . . 335--369 D. Burago and D. Grigoriev and A. Slissenko Approximating shortest path for the skew lines problem in time doubly logarithmic in $ 1 / \epsilon $ . . . . . . . . . . 371--404 Ernie Croot and Ren-Cang Li and H. J. Hui June Zhu The abc conjecture and correctly rounded reciprocal square roots . . . . 405--417 J. Joachim von zur Gathen and Michael Nöcker Fast arithmetic with general Gauß periods 419--452 Georg Heinig and K. Karla Rost Split algorithms for skewsymmetric Toeplitz matrices with arbitrary rank profile . . . . . . . . . . . . . . . . 453--468 Igor Kaporin The aggregation and cancellation techniques as a practical tool for faster matrix multiplication . . . . . . 469--510 Fu-Rong Lin and Wai-Ki Ching and M. K. Michael K. Ng Fast inversion of triangular Toeplitz matrices . . . . . . . . . . . . . . . . 511--523 Gregorio Malajovich and J. M. J. Maurice Rojas High probability analysis of the condition number of sparse polynomial systems . . . . . . . . . . . . . . . . 525--555 D. Noutsos and S. Serra Capizzano and P. Vassalos Matrix algebra preconditioners for multilevel Toeplitz systems do not insure optimal convergence rate . . . . 557--579 Victor Y. Pan and M. Marc Van Barel and Xinmao Wang and Gianni Codevico Iterative inversion of structured matrices . . . . . . . . . . . . . . . . 581--592 Luis Miguel Pardo and J. S. Jorge San Martín Deformation techniques to solve generalised Pham systems . . . . . . . . 593--625 Sonia Pérez-Díaz and Juana Sendra and J. R. J. Rafael Sendra Parametrization of approximate algebraic curves by lines . . . . . . . . . . . . 627--650 Andrew J. Sommese and Jan Verschelde and C. W. Charles W. Wampler Numerical factorization of multivariate complex polynomials . . . . . . . . . . 651--669 Anonymous Author index . . . . . . . . . . . . . . 671--672
Lars Birkedal and Martín Escardó and Achim Jung and Giuseppe Rosolini Preface . . . . . . . . . . . . . . . . 1--2 Ji\vrí Adámek and Stefan Milius and Ji\vrí Velebil On coalgebra based on classes . . . . . 3--23 Fabio Alessi and Mariangiola Dezani-Ciancaglini and Stefania Lusin Intersection types and domain operators 25--47 Mariangiola Dezani-Ciancaglini and Silvia Ghilezan and Silvia Likavec Behavioural inverse limit $ \lambda $-models . . . . . . . . . . . . . . . . 49--74 J. D. Jimmie D. Lawson Idempotent analysis and continuous semilattices . . . . . . . . . . . . . . 75--87 J. D. Jimmie D. Lawson and Luoshan Xu Posets having continuous intervals . . . 89--103 F. W. F. William Lawvere Left and right adjoint operations on spaces and data types . . . . . . . . . 105--111 M. A. M. Andrew Moshier On the relationship between compact regularity and Gentzen's cut rule . . . 113--136 Dag Normann Hierarchies of total functionals over the reals . . . . . . . . . . . . . . . 137--151 Mikkel Nygaard and Glynn Winskel Domain theory for concurrency . . . . . 153--190 Bernhard Reus and Thomas Streicher Semantics and logic of object calculi 191--213 Ivar Rummelhoff Polynat in PER models . . . . . . . . . 215--224 C. F. Townsend Presenting locale pullback via directed complete posets . . . . . . . . . . . . 225--258 Steven Vickers Entailment systems for stably locally compact locales . . . . . . . . . . . . 259--296 S. J. Vickers and C. F. Townsend A universal characterization of the double powerlocale . . . . . . . . . . . 297--321 Anonymous Author index . . . . . . . . . . . . . . 323--323 Anonymous Editorial board . . . . . . . . . . . . v--ix
Mark Burgin and Allen Klinger Three aspects of super-recursive algorithms and hypercomputation or finding black swans . . . . . . . . . . 1--11 Peter Kugel Toward a theory of intelligence . . . . 13--30 Mark Burgin Algorithmic complexity of recursive and inductive algorithms . . . . . . . . . . 31--60 Ji\vrí Wiedermann Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines . . . . 61--69 Mark Burgin and Allen Klinger Experience, generations, and limits in machine learning . . . . . . . . . . . . 71--91 T. D. Tien D. Kieu Hypercomputation with quantum adiabatic processes . . . . . . . . . . . . . . . 93--104 Oron Shagrir Super-tasks, accelerating Turing machines and uncomputability . . . . . . 105--114 B. J. Bruce J. MacLennan Natural computation and non-Turing models of computation . . . . . . . . . 115--145 M. L. Manuel Lameiras Campagnolo Continuous-time computation with restricted integration capabilities . . 147--165 Selmer Bringsjord and Konstantine Arkoudas The modal argument for hypercomputing minds . . . . . . . . . . . . . . . . . 167--190 Benjamin Wells Hypercomputation by definition . . . . . 191--207 C. E. Carol E. Cleland The concept of computability . . . . . . 209--225 K. T. Kevin T. Kelly Uncomputability: the problem of induction internalized . . . . . . . . . 227--249 B. J. B. Jack Copeland Hypercomputation: philosophical issues 251--267 Anonymous Author index . . . . . . . . . . . . . . 269--269 Anonymous Editorial board . . . . . . . . . . . . v--ix
Jean-Yves Marion Editorial . . . . . . . . . . . . . . . 1--1 Klaus Aehlig and Ulrich Berger and Martin Hofmann and Helmut Schwichtenberg An arithmetic for non-size-increasing polynomial-time computation . . . . . . 3--27 Patrick Baillot Stratified coherence spaces: a denotational semantics for light linear logic . . . . . . . . . . . . . . . . . 29--55 S. Bellantoni and I. Oitavem Separating NC along the $ \delta $ axis 57--78 R. Ralph Benzinger Automated higher-order complexity analysis . . . . . . . . . . . . . . . . 79--103 N. Danner and C. Pollett Minimization and NP multifunctions . . . 105--119 M. Hofmann and P. J. Scott Realizability models for BLL-like languages . . . . . . . . . . . . . . . 121--137 L. Kristiansen and K.-H. Niggl On the computational complexity of imperative programming languages . . . . 139--161 Yves Lafont Soft linear logic and polynomial time 163--180 Daniel Leivant Intrinsic reasoning about functional programs II: unipolar induction and primitive-recursion . . . . . . . . . . 181--196 A. S. Murawski and C.-H. L. Ong On an interpretation of safe recursion in light affine logic . . . . . . . . . 197--223 J. S. (James S.) Royer On the computational complexity of Longley's $H$ functional . . . . . . . . 225--241 Anonymous Editorial board . . . . . . . . . . . . v--ix
Mila Majster-Cederbaum and Frank Salger Towards the hierarchical verification of reactive systems . . . . . . . . . . . . 243--296 Rajeev Alur and Salvatore La Torre and George J. Pappas Optimal paths in weighted timed automata 297--322 Josée Desharnais and Vineet Gupta and Radha Jagadeesan and Prakash Panangaden Metrics for labelled Markov processes 323--354 Georg Karner Continuous monoids and semirings . . . . 355--372 Sabine Broda and Luís Damas and Marcelo Finger and Paulo Silva e Silva The decidability of a fragment of BB'IW-logic . . . . . . . . . . . . . . 373--408 Ugo Dal Lago and Simone Martini Phase semantics and decidability of elementary affine logic . . . . . . . . 409--433 R. N. Banerjee and A. Bujosa A geometric interpretation of LD-resolution . . . . . . . . . . . . . 435--470 Anonymous Author index . . . . . . . . . . . . . . 471--471
L. Vuillon Foreword . . . . . . . . . . . . . . . . 1--1 Michael Korn and Igor Pak Tilings of rectangles with T-tetrominoes 3--27 E. H. Eric H. Kuo Applications of graphical condensation for enumerating matchings and tilings 29--57 Olivier Bodini and Eric Rémila Tilings with trichromatic colored-edges triangles . . . . . . . . . . . . . . . 59--70 N. Destainville and R. Mosseri and F. Bailly A formula for the number of tilings of an octagon by rhombi . . . . . . . . . . 71--81 S. Sébastien Desreux and Martin Matamala and Ivan Rapaport and Eric Rémila Domino tilings and related models: space of configurations of domains with holes 83--101 Francis Oger Algebraic and model-theoretic properties of tilings . . . . . . . . . . . . . . . 103--126 Jean-Charles Delvenne and V. D. Vincent D. Blondel Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines . . . 127--143 Pierre Arnoux and Valérie Berthé and Anne Siegel Two-dimensional iterated morphisms and discrete planes . . . . . . . . . . . . 145--176 Valérie Berthé and Robert Tijdeman Lattices and multi-dimensional words . . 177--202 Valentin E. Brimkov and R. P. Reneta P. Barneva Connectivity of discrete planes . . . . 203--227 Anthony Quas and Luca Zamboni Periodicity and local complexity . . . . 229--240 E. O. Harriss and J. S. W. Lamb Canonical substitutions tilings of Ammann--Beenker type . . . . . . . . . . 241--279 Avi Elkharrat and Christiane Frougny and Jean-Pierre Gazeau and J.-L. Jean-Louis Verger-Gaugry Symmetry groups for beta-lattices . . . 281--305 P. J. Peter J. Grabner and Clemens Heuberger and Helmut Prodinger Distribution results for low-weight binary representations for pairs of integers . . . . . . . . . . . . . . . . 307--331 Svjetlan Fereti\c' A $q$-enumeration of convex polyominoes by the festoon approach . . . . . . . . 333--356 Zoltán Füredi and J.-H. Jeong-Hyun Kang Distance graph on $ \mathbb {Z}^n $ with $ \ell_1 $ norm . . . . . . . . . . . . 357--366 Codrin Nichitiu and Christophe Papazian and Eric Rémila Leader election in plane cellular automata, only with left--right global convention . . . . . . . . . . . . . . . 367--384 Katherine Humphreys and Heinrich Niederhausen Counting lattice paths taking steps in infinitely many directions under special access restrictions . . . . . . . . . . 385--409 Marc Daniel and Sylvain Gravier and Julien Moncel Identifying codes in some subgraphs of the square lattice . . . . . . . . . . . 411--421 F. Aguiló and D. Arteaga and I. Diego A symbolical algorithm on additive basis and double-loop networks . . . . . . . . 423--439 J. D. James D. Currie The number of binary words avoiding abelian fourth powers grows exponentially . . . . . . . . . . . . . 441--446 A. Frosini and G. Simi The NP-completeness of a tomographical problem on bicolored domino tilings . . 447--454 R. Régis Barbanchon On unique graph $3$-colorability and parsimonious reductions in the plane . . 455--482 Anonymous Author index . . . . . . . . . . . . . . 483--484 Anonymous Editorial board . . . . . . . . . . . . v--ix
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1--2 Joshua J. Arulanandham and Cristian S. Calude and M. J. Michael J. Dinneen A fast natural algorithm for searching 3--13 Eli Biham and Gilles Brassard and Dan Kenigsberg and T. Tal Mor Quantum computing without entanglement 15--33 Anne Condon and Beth Davy and Baharak Rastegari and Shelly Zhao and Finbarr Tarrant Classifying RNA pseudoknotted structures 35--50 Mark Daley and Lila Kari and Ian McQuillan Families of languages defined by ciliate bio-operations . . . . . . . . . . . . . 51--69 Michelangelo Diligenti and Marco Gori and Marco Maggini Neural computation, social networks, and topological spectra . . . . . . . . . . 71--87 O. H. Oscar H. Ibarra On the computational complexity of membrane systems . . . . . . . . . . . . 89--109 V. R. Vicente Ruiz de Angulo and Carme Torras Neural learning methods yielding functional invariance . . . . . . . . . 111--121 Tobias Storch and Ingo Wegener Real royal road functions for constant population size . . . . . . . . . . . . 123--134 Adam Prügel-Bennett When a genetic algorithm outperforms hill-climbing . . . . . . . . . . . . . 135--153 Anonymous Editorial board . . . . . . . . . . . . v--ix
S. Bezrukov and R. Elsässer and B. Monien and R. Preis and J.-P. Tillich New spectral lower bounds on the bisection width of graphs . . . . . . . 155--174 G. Z. Gillian Z. Elston and Gretchen Ostheimer On groups whose word problem is solved by a counter automaton . . . . . . . . . 175--185 Ch. Choffrut and Y. Haddad String-matching with OBDDs . . . . . . . 187--198 J. J. Yuan and Z. H. Liu and C. T. Ng and T. C. E. Cheng The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan . . . . . . . . . . . . . . . . 199--212 A. André Berthiaume and Todd Bittner and Ljubomir Perkovi\'c and Amber Settle and Janos Simon Bounding the firing synchronization problem on a ring . . . . . . . . . . . 213--228 Olivier Powell A note on measuring in P . . . . . . . . 229--246 Martin Middendorf and D. F. David F. Manlove Combined super-/substring and super-/subsequence problems . . . . . . 247--267 Carlo Blundo and Paolo D'Arco and Vanessa Daza and Carles Padró Bounds and constructions for unconditionally secure distributed key distribution schemes for general access structures . . . . . . . . . . . . . . . 269--291 Michael Domaratzki Deletion along trajectories . . . . . . 293--313 Arto Salomaa and Derick Wood and Sheng Yu On the state complexity of reversals of regular languages . . . . . . . . . . . 315--329 Patrick Healy and Ago Kuusik Algorithms for multi-level graph planarity testing and layout . . . . . . 331--344 Simona Cocco and R. Rémi Monasson Heuristic average-case analysis of the backtrack resolution of random $3$-satisfiability instances . . . . . . 345--372 Vilhelm Dahllöf and Peter Jonsson and Richard Beigel Algorithms for four variants of the exact satisfiability problem . . . . . . 373--394 M.-P. Marie-Pierre Béal and Anne Bergeron and Sylvie Corteel and Mathieu Raffinot An algorithmic view of gene teams . . . 395--418 Alexander Okhotin On the number of nonterminals in linear conjunctive grammars . . . . . . . . . . 419--448 Asa Ben-Hur and Alexander Roitershtein and H. T. Hava T. Siegelmann On probabilistic analog automata . . . . 449--464 Markus Hunziker and António Machiavelo and Jihun Park Chebyshev polynomials over finite fields and reversibility of $ \sigma $-automata on square grids . . . . . . . . . . . . 465--483 Liying Kang and M. Y. Moo Young Sohn and T. C. E. Cheng Paired-domination in inflated graphs . . 485--494 J. M. John M. Hitchcock The size of SPP . . . . . . . . . . . . 495--503 Anonymous Author index . . . . . . . . . . . . . . 505--506 Anonymous Master index . . . . . . . . . . . . . . 507--518
J. A. Juan A. Garay and Sergio Rajsbaum Preface . . . . . . . . . . . . . . . . 1--3 Michael A. Bender and M. Martín Farach-Colton The Level Ancestor Problem simplified 5--12 C. F. Claudson F. Bornstein and Santosh Vempala Flow metrics . . . . . . . . . . . . . . 13--24 Hervé Brönnimann and John Iacono and Jyrki Katajainen and Pat Morin and Jason Morrison and Godfried Toussaint Space-efficient planar convex hull algorithms . . . . . . . . . . . . . . . 25--40 R. Carmo and J. Donadelli and Y. Kohayakawa and E. Laber Searching in random partially ordered sets . . . . . . . . . . . . . . . . . . 41--57 Theodoulos Garefalakis The generalized Weil pairing and the discrete logarithm problem on elliptic curves . . . . . . . . . . . . . . . . . 59--72 Alejandro Hevia and Marcos Kiwi Electronic jury voting protocols . . . . 73--94 S. Muthukrishnan and S. Cenk Sahinalp An efficient algorithm for sequence comparison with block reversals . . . . 95--101 Hadas Shachnai and Tami Tamir Tight bounds for online class-constrained packing . . . . . . . 103--123 Brett Stevens and Eric Mendelsohn Packing arrays . . . . . . . . . . . . . 125--148 Mario Szegedy and Xiaomin Chen Computing Boolean functions from multiple faulty copies of input bits . . 149--170 Anonymous Editorial board . . . . . . . . . . . . v--ix
Cláudia Linhares Sales and Frédéric Maffray On dart-free perfectly contractile graphs . . . . . . . . . . . . . . . . . 171--194 Keqin Li Analysis of randomized load distribution for reproduction trees in linear arrays and rings . . . . . . . . . . . . . . . 195--214 Jason J. Holdsworth Graph traversal and graph transformation 215--231 Matteo Cavaliere and Peter Leupold Evolution and observation---a non-standard way to generate formal languages . . . . . . . . . . . . . . . 233--248 Rodney G. Downey and Evan J. Griffiths and Stephanie Reid On Kurtz randomness . . . . . . . . . . 249--270 Martin Klazar On the least exponential growth admitting uncountably many closed permutation classes . . . . . . . . . . 271--281 Gonzalo Navarro and Kimmo Fredriksson Average complexity of exact and approximate multiple string matching . . 283--290 Patricia Bouyer and Catherine Dufourd and Emmanuel Fleury and Antoine Petit Updatable timed automata . . . . . . . . 291--345 Juan Luis Esteban and Nicola Galesi and Jochen Messner On the complexity of resolution with bounded conjunctions . . . . . . . . . . 347--370 Richard Nock and Frank Nielsen On domain-partitioning induction criteria: worst-case bounds for the worst-case based . . . . . . . . . . . . 371--382 B. Ravikumar Peg-solitaire, string rewriting systems and finite automata . . . . . . . . . . 383--394 Dong Pyo Chi and DoYong Kwon Sturmian words, $ \beta $-shifts, and transcendence . . . . . . . . . . . . . 395--404 Michael H. Albert and Alexander Golynski and Ang\`ele M. Hamel and Alejandro López-Ortiz and S. Srinivasa Rao and Mohammad Ali Safari Longest increasing subsequences in sliding windows . . . . . . . . . . . . 405--414 Gerhard J. Woeginger Seventeen lines and one-hundred-and-one points . . . . . . . . . . . . . . . . . 415--421 Anonymous Author index . . . . . . . . . . . . . . 423--424
Patrick Cégielski and Malika More Foreword . . . . . . . . . . . . . . . . 1--3 Zofia Adamowicz and Leszek Aleksander Ko\lodziejczyk Well-behaved principles alternative to bounded induction . . . . . . . . . . . 5--16 Anatoly Petrivich Beltiukov A strong induction scheme that leads to polynomially computable realizations . . 17--39 A. Chateau On the complexity of decision using destinies in $H$-bounded structures . . 41--67 Olivier Finkel Closure properties of locally finite $ \omega $-languages . . . . . . . . . . . 69--84 Verónica Becher and Serge Grigorieff Recursion and topology on $ 2^{\leq \omega } $ for possibly infinite computations . . . . . . . . . . . . . . 85--136 Yassine Hacha\"\ichi Arithmetical definability and computational complexity . . . . . . . . 137--146 Andrea Formisano and Eugenio G. Omodeo and Alberto Policriti Three-variable statements of set-pairing 147--173 Jean-Pierre Ressayre Winning strategies for infinite games: from large cardinals to computer science extended abstract . . . . . . . . . . . 175--179 K. Shahbazyan and Yu. Shoukourian EMSO-logic and automata related to homogeneous flow event structures . . . 181--201 Alan R. Woods Subset sum ``cubes'' and the complexity of primality testing . . . . . . . . . . 203--219 I. D. Zaslavsky On some generalizations of the primitive recursive arithmetic . . . . . . . . . . 221--230 Anonymous Editorial board . . . . . . . . . . . . v--ix
J. Demongeot and J. Mazoyer Discrete applied problems, cellular automata and lattices: florilegium for E. Goles . . . . . . . . . . . . . . . . 231--232 M. Nivat For the $ 50 $ th anniversary of Eric Goles: A few words by Maurice Nivat . . 233--235 Julio Aracena and Jacques Demongeot and Eric Goles On limit cycles of monotone functions with symmetric connection graph . . . . 237--244 Mourad Ba\"\iou and Michel Balinski Student admissions and faculty recruitment . . . . . . . . . . . . . . 245--265 A. Gajardo and E. Goles Dynamics of a class of ants on a one-dimensional lattice . . . . . . . . 267--283 Eric Goles Folding and tiling . . . . . . . . . . . 285--296 Andrés Moreira Genetic algorithms for the imitation of genomic styles in protein backtranslation . . . . . . . . . . . . 297--312 Georges Weil and Kamel Heus and Thomas Faraut and Jacques Demongeot The cyclic genetic code as a constraint satisfaction problem . . . . . . . . . . 313--334 M. Delorme and J. Mazoyer Real-time recognition of languages on an two-dimensional Archimedean thread . . . 335--354 Christoph Dürr and Ivan Rapaport and Guillaume Theyssier Cellular automata and communication complexity . . . . . . . . . . . . . . . 355--368 Martín Matamala and Eduardo Moreno Dynamic of cyclic automata over $ \mathbb {Z}^2 $ . . . . . . . . . . . . 369--381 Éric Goles and Matthieu Latapy and Clémence Magnien and Michel Morvan and Ha Duong Phan Sandpile models and lattices: a comprehensive survey . . . . . . . . . . 383--407 Eric Rémila The lattice structure of the set of domino tilings of a polygon . . . . . . 409--422
Vladimiro Sassone Preface . . . . . . . . . . . . . . . . 423--426 Martín Abadi and Cédric Fournet Private authentication . . . . . . . . . 427--476 Nadia Busi and Gianluigi Zavattaro On the expressive power of movement and restriction in pure mobile ambients . . 477--515 Luís Caires and Luca Cardelli A spatial logic for concurrency---II . . 517--565 Tom Chothia and Dominic Duggan Abstractions for fault-tolerant global computing . . . . . . . . . . . . . . . 567--613 Matthew Hennessy and Massimo Merro and Julian Rathke Towards a behavioural theory of access and mobility control in distributed systems . . . . . . . . . . . . . . . . 615--669 Anonymous Author index . . . . . . . . . . . . . . 671--672
Alan Jeffrey and Julian Rathke A theory of bisimulation for a fragment of concurrent ML with local names . . . 1--48 C. Raffalli Getting results from programs extracted from classical proofs . . . . . . . . . 49--70 Serenella Cerrito and Delia Kesner Pattern matching as cut elimination . . 71--127 P. Baldan and N. Busi and A. Corradini and G. M. Pinna Domain and event structure semantics for Petri nets with read and inhibitor arcs 129--189 R. M. Hierons and M. Harman Testing conformance of a deterministic implementation against a non-deterministic stream X-machine . . . 191--233 Timothy Porter Interpreted systems and Kripke models for multiagent systems from a categorical perspective . . . . . . . . 235--266 Nicolas Peltier The first order theory of primal grammars is decidable . . . . . . . . . 267--320 Guo-Qiang Zhang and William C. Rounds Reasoning with power defaults . . . . . 321--350 Christophe Dehlinger and Jean-François Dufourd Formalizing generalized maps in Coq . . 351--397 Christophe Dehlinger and Jean-François Dufourd Formalizing the trading theorem in Coq 399--442 Pascal Urso and Emmanuel Kounalis Sound generalizations in mathematical induction . . . . . . . . . . . . . . . 443--471 Christian Urban and Andrew M. Pitts and Murdoch J. Gabbay Nominal unification . . . . . . . . . . 473--497 Anonymous Author index . . . . . . . . . . . . . . 499--499 Anonymous Editorial board . . . . . . . . . . . . v--ix
Masami Ito Foreword . . . . . . . . . . . . . . . . 1--1 Zoltán Ésik and Werner Kuich Inductive $^*$-semirings . . . . . . . . 3--33 Tero Harju and Juhani Karhumäki Many aspects of defect theorems . . . . 35--54 Mizuhito Ogawa Well-quasi-orders and regular$ \omega $-languages . . . . . . . . . . . . . . 55--60 Gheorghe P\uaun and Yasuhiro Suzuki and Hiroshi Tanaka and Takashi Yokomori On the power of membrane division in $P$ systems . . . . . . . . . . . . . . . . 61--85 Tatjana Petkovi\'c and Miroslav \'Ciri\'c and Stojan Bogdanovi\'c Unary algebras, semigroups and congruences on free semigroups . . . . . 87--105 René Schott and Jean-Claude Spehner Two optimal parallel algorithms on the commutation class of a word . . . . . . 107--131 Anonymous Editorial board . . . . . . . . . . . . v--ix
Amos Fiat and Sandy Irani Foreword . . . . . . . . . . . . . . . . 133--135 Avrim Blum and Vijay Kumar and Atri Rudra and Felix Wu Online learning in online auctions . . . 137--146 John E. Augustine and Steven Seiden Linear time approximation schemes for vehicle scheduling problems . . . . . . 147--160 Alexander Kesselman and Yishay Mansour Harmonic buffer management policy for shared memory switches . . . . . . . . . 161--182 M. Mendel and Steven S. Seiden Online companion caching . . . . . . . . 183--200 Tomás Feder and Rajeev Motwani and Rina Panigrahy and Steve Seiden and Rob van Stee and An Zhu Combining request scheduling with web caching . . . . . . . . . . . . . . . . 201--218 Rudolf Fleischer and W\lodzimierz G\lazek and Steve Seiden New results for online page replication 219--251 Ronny Lempel and Shlomo Moran Competitive caching of query results in search engines . . . . . . . . . . . . . 253--271 Prosenjit Bose and Pat Morin Competitive online routing in geometric graphs . . . . . . . . . . . . . . . . . 273--288 Marek Chrobak and Ji\vrí Sgall The weighted $2$-server problem . . . . 289--312 Baruch Awerbuch and Yossi Azar and Yair Bartal On-line generalized Steiner problem . . 313--324 Luca Becchetti and Stefano Leonardi and Alberto Marchetti-Spaccamela and Kirk Pruhs Semi-clairvoyant scheduling . . . . . . 325--335 Yair Bartal and Elias Koutsoupias On the competitive ratio of the work function algorithm for the $k$-server problem . . . . . . . . . . . . . . . . 337--345 Elias Koutsoupias and David Scot Taylor The CNN problem and other $k$-server variants . . . . . . . . . . . . . . . . 347--359 Peter Chen and Guoli Ding The best expert versus the smartest algorithm . . . . . . . . . . . . . . . 361--380 Anonymous Author index . . . . . . . . . . . . . . 381--382
Corrado Priami Preface . . . . . . . . . . . . . . . . 1--2 Damien Eveillard and Delphine Ropers and Hidde de Jong and Christiane Branlant and Alexander Bockmayr A multi-scale constraint programming model of alternative splicing regulation 3--24 Nathalie Chabrier-Rivier and Marc Chiaverini and Vincent Danos and François Fages and Vincent Schächter Modeling and querying biomolecular interaction networks . . . . . . . . . . 25--44 M. Antoniotti and C. Piazza and A. Policriti and M. Simeoni and B. Mishra Taming the complexity of biochemical models through bisimulation and collapsing: theory and practice . . . . 45--67 Vincent Danos and Cosimo Laneve Formal molecular biology . . . . . . . . 69--110 M. Curti and P. Degano and C. Priami and C. T. Baldari Modelling biochemical pathways through enhanced $ \pi $-calculus . . . . . . . 111--140 Aviv Regev and Ekaterina M. Panina and William Silverman and Luca Cardelli and Ehud Shapiro BioAmbients: an abstraction for biological compartments . . . . . . . . 141--167 Anonymous Editorial board . . . . . . . . . . . . v--ix
Jarkko Kari Preface . . . . . . . . . . . . . . . . 169--169 A. Barbé and F. von Haeseler The Pascal matroid as a home for generating sets of cellular automata configurations defined by quasigroups 171--214 Tim Boykett Efficient exhaustive listings of reversible one dimensional cellular automata . . . . . . . . . . . . . . . . 215--247 Gianpiero Cattaneo and Alberto Dennunzio and Luciano Margara Solution of some conjectures about topological properties of linear cellular automata . . . . . . . . . . . 249--271 Eugen Czeizler On the size of the inverse neighborhoods for one-dimensional reversible cellular automata . . . . . . . . . . . . . . . . 273--284 Andrés Moreira and Nino Boccara and Eric Goles On conservative and monotone one-dimensional cellular automata and their particle representation . . . . . 285--316 K. Sutner The complexity of reversible cellular automata . . . . . . . . . . . . . . . . 317--328 Tommaso Toffoli and Silvio Capobianco and Patrizia Mentrasti How to turn a second-order cellular automaton into a lattice gas: a new inversion scheme . . . . . . . . . . . . 329--344
Tandy Warnow and Binhai Zhu Preface . . . . . . . . . . . . . . . . 345--346 Mark Marron and Krister M. Swenson and Bernard M. E. Moret Genomic distances under deletions and insertions . . . . . . . . . . . . . . . 347--360 Zhi-Zhong Chen and Yong Gao and Guohui Lin and Robert Niewiadomski and Yang Wang and Junfeng Wu A space-efficient algorithm for sequence alignment with inversions and reversals 361--372 Martin Kutz The complexity of Boolean matrix root computation . . . . . . . . . . . . . . 373--390 Eric J. Schwabe and Ian M. Sutherland Efficient data mappings for parity-declustered data layouts . . . . 391--407 Francis Y. L. Chin and Xiaotie Deng and Qizhi Fang and Shanfeng Zhu Approximate and dynamic rank aggregation 409--424 Tetsuo Asano and Naoki Katoh and Hisao Tamaki and Takeshi Tokuyama The structure and number of global roundings of a graph . . . . . . . . . . 425--437 Magnús M. Halldórsson and Kazuo Iwama and Shuichi Miyazaki and Hiroki Yanagisawa Randomized approximation of the stable marriage problem . . . . . . . . . . . . 439--465 Francis Y. L. Chin and Stanley P. Y. Fung Improved competitive algorithms for online scheduling with partial job values . . . . . . . . . . . . . . . . . 467--478 Jae-Hoon Kim and Kyung-Yong Chwa Scheduling broadcasts with deadlines . . 479--488 Anonymous Author index . . . . . . . . . . . . . . 489--490
Lane A. Hemaspaandra and Mayur Thakur Lower bounds and the hardness of counting properties . . . . . . . . . . 1--28 Cedric Chauve and Guillaume Fertin On maximal instances for the original syntenic distance . . . . . . . . . . . 29--43 Pascal Michel Small Turing machines and generalized busy beaver competition . . . . . . . . 45--56 Friedrich Eisenbrand and Fabrizio Grandoni On the complexity of fixed parameter clique and dominating set . . . . . . . 57--67 James Allen Fill and Nevin Kapur Limiting distributions for additive functionals on Catalan trees . . . . . . 69--102 Yashar Ganjali and MohammadTaghi Hajiaghayi Characterization of networks supporting multi-dimensional linear interval routing schemes . . . . . . . . . . . . 103--116 Tomomi Matsui and Yasuko Matsui and Yoko Ono Random generation of $ 2 \times 2 \cdots {} \times 2 \times J $ contingency tables . . . . . . . . . . . . . . . . . 117--135 Hans-Joachim Böckenhauer and Dirk Bongartz and Juraj Hromkovi\vc and Ralf Klasing and Guido Proietti and Sebastian Seibert and Walter Unger On the hardness of constructing minimal $2$-connected spanning subgraphs in complete graphs with sharpened triangle inequality . . . . . . . . . . . . . . . 137--153 Teofilo F. Gonzalez and David Serena Complexity of pairwise shortest path routing in the grid . . . . . . . . . . 155--185 Martin Ziegler and Vasco Brattka Computability in linear algebra . . . . 187--211 Svante Janson and Stefano Lonardi and Wojciech Szpankowski On average sequence complexity . . . . . 213--227 Jean-Pierre Duval and Roman Kolpakov and Gregory Kucherov and Thierry Lecroq and Arnaud Lefebvre Linear-time computation of local periods 229--240 Marcia Edson and Luca Q. Zamboni On representations of positive integers in the Fibonacci base . . . . . . . . . 241--260 Ji\vrí Fiala and Aleksei V. Fishkin and Fedor Fomin On distance constrained labeling of disk graphs . . . . . . . . . . . . . . . . . 261--292 Predrag R. Jelenkovi\'c and Ana Radovanovi\'c Least-recently-used caching with dependent requests . . . . . . . . . . . 293--327 Marcos Kiwi and Alexander Russell The Chilean Highway Problem . . . . . . 329--342 Anders Dessmark and Andrzej Pelc Optimal graph exploration without good maps . . . . . . . . . . . . . . . . . . 343--362 Xun Yi Authenticated key agreement in dynamic peer groups . . . . . . . . . . . . . . 363--382 Thorsten Bernholt and Paul Fischer The complexity of computing the MCD-estimator . . . . . . . . . . . . . 383--398 Minming Li and Shawn L. Huang and Xiaoming Sun and Xiao Huang Performance evaluation for energy efficient topologic control in ad hoc wireless networks . . . . . . . . . . . 399--408 Alan Gibbons and Paul Sant Rotation sequences and edge-colouring of binary tree pairs . . . . . . . . . . . 409--418 Qi Cheng On the ultimate complexity of factorials 419--429 Stefano Leonardi and Guido Schäfer Cross-monotonic cost sharing methods for connected facility location games . . . 431--442 Anonymous Author index . . . . . . . . . . . . . . 443--444 Anonymous Editorial board . . . . . . . . . . . . v--ix
H. Peter Gumm Preface . . . . . . . . . . . . . . . . 1--2 Falk Bartels and Ana Sokolova and Erik de Vink A hierarchy of probabilistic system types . . . . . . . . . . . . . . . . . 3--22 Hubie Chen and Riccardo Pucella A coalgebraic approach to Kleene algebra with tests . . . . . . . . . . . . . . . 23--44 Corina C\^\irstea A compositional approach to defining logics for coalgebras . . . . . . . . . 45--69 Jesse Hughes and Bart Jacobs Simulations in coalgebra . . . . . . . . 71--108 Clemens Kupke and Alexander Kurz and Yde Venema Stone coalgebras . . . . . . . . . . . . 109--134 Marina Lenisa and John Power and Hiroshi Watanabe Category theory for operational semantics . . . . . . . . . . . . . . . 135--154 Ralph Matthes and Tarmo Uustalu Substitution in non-wellfounded syntax with variable binding . . . . . . . . . 155--174 Alessandra Palmigiano A coalgebraic view on positive modal logic . . . . . . . . . . . . . . . . . 175--195 Grigore Ro\csu Behavioral abstraction is hiding information . . . . . . . . . . . . . . 197--221 Anonymous Editorial board . . . . . . . . . . . . v--ix
Zoltán Ésik and Zoltán Fülöp Foreword . . . . . . . . . . . . . . . . 223--224 D. S. Ananichev and M. V. Volkov Synchronizing monotonic automata . . . . 225--239 J.-M. Champarnaud and F. Coulon NFA reduction algorithms by means of regular inequalities . . . . . . . . . . 241--253 Flavio D'Alessandro and Stefano Varricchio Well quasi-orders and context-free grammars $^,$ . . . . . . . . . . . . . 255--268 Diego de Falco and Massimiliano Goldwurm and Violetta Lonati Frequency of symbol occurrences in bicomponent stochastic models . . . . . 269--300 Dieter Hofbauer and Johannes Waldmann Deleting string rewriting systems preserve regularity . . . . . . . . . . 301--317 Markus Holzer and Barbara König On deterministic finite automata and syntactic monoid size . . . . . . . . . 319--347 Ines Klimann and Sylvain Lombardy and Jean Mairesse and Christophe Prieur Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton . . . . . . . . . . . . . . . 349--373 Andreas Malcher Minimizing finite automata is computationally hard . . . . . . . . . . 375--390 Anonymous Author index . . . . . . . . . . . . . . 391--392
Oscar H. Ibarra Editorial . . . . . . . . . . . . . . . 1--1 Cyril Allauzen and Mehryar Mohri An optimal pre-determinization algorithm for weighted transducers . . . . . . . . 3--18 Xiang Fu and Tevfik Bultan and Jianwen Su Conversation protocols: a formalism for specification and verification of reactive electronic services . . . . . . 19--37 Franck Guingne and Florent Nicart and André Kempe Acyclic networks maximizing the printing complexity . . . . . . . . . . . . . . . 39--51 Dietrich Kuske and Ingmar Meinecke Branching automata with costs --- a way of reflecting parallelism in costs . . . 53--75 Sylvain Lombardy and Yann Régis-Gianas and Jacques Sakarovitch Introducing VAUCANSON . . . . . . . . . 77--96 Satoru Miyamoto and Shunsuke Inenaga and Masayuki Takeda and Ayumi Shinohara Ternary directed acyclic word graphs . . 97--111 B. Ravikumar and G. Eisman Weak minimization of DFA --- an algorithm and applications . . . . . . . 113--133 Hellis Tamm and Esko Ukkonen Bideterministic automata and minimal representations of regular languages . . 135--149 A. N. Trahtman Reducing the time complexity of testing for local threshold testability . . . . 151--160 Lynette van Zijl On binary $ \oplus $-NFAs and succinct descriptions of regular languages . . . 161--170 M. Vilares and V. M. Darriba and J. Vilares and F. J. Ribadas A formal frame for robust parsing . . . 171--186 Farn Wang and Hsu-Chun Yen Reachability solution characterization of parametric real-time systems . . . . 187--201 Gaoyan Xie and Cheng Li and Zhe Dang Linear reachability problems and minimal solutions to linear Diophantine equation systems . . . . . . . . . . . . . . . . 203--219 Anonymous Editorial board . . . . . . . . . . . . v--ix
Mauricio Alvarez-Manilla and Achim Jung and Klaus Keimel The probabilistic powerdomain for stably compact spaces . . . . . . . . . . . . . 221--244 Hejiao Huang and To-yat Cheung and Wai Ming Mak Structure and behavior preservation by Petri-net-based refinements in system design . . . . . . . . . . . . . . . . . 245--269 Yi-Dong Shen and Jia-Huai You and Li-Yan Yuan Enhancing global SLS-resolution with loop cutting and tabling mechanisms . . 271--287 Patrick Baillot Type inference for light affine logic via constraints on words . . . . . . . . 289--323 Reiner Hähnle and Neil V. Murray and Erik Rosenthal Linearity and regularity with negation normal form . . . . . . . . . . . . . . 325--354 John Foy A dynamical system which must be stable whose stability cannot be proved . . . . 355--361 Anonymous Author index . . . . . . . . . . . . . . 363--364
Amin Coja-Oghlan and Andreas Goerdt and André Lanka and Frank Schädlich Techniques from combinatorial approximation algorithms yield efficient algorithms for random $ 2 k$-SAT . . . . 1--45 Michael Drmota On Robson's convergence and boundedness conjectures concerning the height of binary search trees . . . . . . . . . . 47--70 Hana Chockler and Orna Kupferman $ \omega $-Regular languages are testable with a constant number of queries . . . . . . . . . . . . . . . . 71--92 Peter Jonsson and Andrei Krokhin Recognizing frozen variables in constraint satisfaction problems . . . . 93--113 Tamás Hornung and Sándor Vágvölgyi Storage-to-tree transducers with look-ahead . . . . . . . . . . . . . . . 115--158 Thomas Strahm A proof-theoretic characterization of the basic feasible functionals . . . . . 159--176 F. Blanchet-Sadri Codes, orderings, and partial words . . 177--202 Yasuhiro Tajima and Etsuji Tomita and Mitsuo Wakatsuki and Matsuaki Terada Polynomial time learning of simple deterministic languages via queries and a representative sample . . . . . . . . 203--221 Alin Bostan and Éric Schost On the complexities of multipoint evaluation and interpolation . . . . . . 223--235 Gembu Morohashi and Shigeki Iwata Some minimum merging networks . . . . . 237--250 Jacques Peyri\`ere and Bo Tan and Zhi-Xiong Wen and Jun Wu The factor composition matrix of sequences . . . . . . . . . . . . . . . 251--269 Leonid Kontorovich Uniquely decodable $n$-gram embeddings 271--284 Grzegorz Malewicz A tight analysis and near-optimal instances of the algorithm of Anderson and Woll . . . . . . . . . . . . . . . . 285--301 Tobias Brueggemann and Walter Kern An improved deterministic local search algorithm for 3-SAT . . . . . . . . . . 303--313 Víctor Dalmau and Peter Jonsson The complexity of counting homomorphisms seen from the other side . . . . . . . . 315--323 Lu Ruan and Hongwei Du and Xiaohua Jia and Weili Wu and Yingshu Li and Ker-I Ko A greedy approximation for minimum connected dominating sets . . . . . . . 325--330 Yuliang Zheng and Xian-Mo Zhang The Generalized XOR Lemma . . . . . . . 331--337 Anonymous Author index . . . . . . . . . . . . . . 339--340 Anonymous Editorial board . . . . . . . . . . . . v--ix
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
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
Takashi Yokomori Erratum to ``Polynomial-time identification of very simple grammars from positive data'' [Theoret. Comput. Sci. 298 (2003) 179--206] . . . . . . . 282--283
Frédéric Blanqui and Jean-Pierre Jouannaud and Mitsuhiro Okada Corrigendum to ``Inductive-data-type systems'' [Theoret. Comput. Sci. \bf 272 (1--2) (2002) 41--68] . . . . . . . . . 81--82