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