Last update:
Tue Dec 20 16:20:35 MST 2011
M. 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,\pm1)$-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 $AX-XB^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\vsFreivalds 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 $qAC^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
\vS\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\vsFreivalds 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 and
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
Co