Last update:
Sat Oct 14 17:53:39 MDT 2017
Armando B. Matos Periodic sets of integers . . . . . . . 287--312
Fernando Botelho and
Max Garzon Boolean neural nets are observable . . . 51--61
Didier Galmiche and
Guy Perrier On proof normalization in linear logic 67--110
Masami Hagiya A typed $\lambda$-calculus for
proving-by-example and bottom-up
generalization procedure . . . . . . . . 3--23
Klaus P. Jantke and
Steffen Lange Case-based representation and learning
of pattern languages . . . . . . . . . . 25--51
Yasuhito Mukouchi and
Setsuo Arikawa Towards a mathematical theory of machine
discovery from facts . . . . . . . . . . 53--84
Sanjay Jain and
Arun Sharma On aggregating teams of learning
machines . . . . . . . . . . . . . . . . 85--108
Akito Sakurai On the VC-dimension of depth four
threshold circuits and the complexity of
Boolean-valued functions . . . . . . . . 109--127
Ayumi Shinohara Complexity of computing
Vapnik--Chervonenkis dimension and some
generalized dimensions . . . . . . . . . 129--144
Susumu Hasegawa and
Hiroshi Imai and
Masaki Ishiguro $\varepsilon$-approximations of
$k$-label spaces . . . . . . . . . . . . 145--157
Atsuyoshi Nakamura and
Naoki Abe Exact learning of linear combinations of
monotone terms from function value
queries . . . . . . . . . . . . . . . . 159--176
Henning Fernau Valuations of languages, with
applications to fractal geometry . . . . 177--217
Stéphane Fabre Substitutions et syst\`emes de
numération. (French) [Substitutions and
beta numbering systems] . . . . . . . . 219--236
Z. Ésik and
L. Bernátsky Equational properties of Kleene algebras
of relations with conversion . . . . . . 237--251
Atsushi Takahashi and
Shuichi Ueno and
Yoji Kajitani Mixed searching and proper-path-width 253--268
Dany Breslauer Fast parallel string prefix-matching . . 269--278
Vikraman Arvind and
Johannes Köbler and
Uwe Schöning and
Rainer Schuler If NP has polynomial-size circuits, then
MA$=$AM . . . . . . . . . . . . . . . . 279--282
R. Alur and
C. Courcoubetis and
N. Halbwachs and
T. A. Henzinger and
P.-H. Ho and
X. Nicollin and
A. Olivero and
J. Sifakis and
S. Yovine The algorithmic analysis of hybrid
systems . . . . . . . . . . . . . . . . 3--34
Eugene Asarin and
Oded Maler and
Amir Pnueli Reachability analysis of dynamical
systems having piecewise-constant
derivatives . . . . . . . . . . . . . . 35--65
Michael S. Branicky Universal computation and other
capabilities of hybrid and continuous
dynamical systems . . . . . . . . . . . 67--100
R. L. Grossman and
R. G. Larson An algebraic approach to hybrid systems 101--112
Michael R. Hansen and
Paritosh K. Pandya and
Zhou Chaochen Finite divergence . . . . . . . . . . . 113--139
Wolf Kohn and
Anil Nerode and
Jeffrey B. Remmel and
Alexander Yakhnis Viability in hybrid systems . . . . . . 141--168
Yassine Lakhneche and
Jozef Hooman Metric temporal logic with durations . . 169--199
Michael Lemmon and
Panos J. Antsaklis Inductively inferring valid logical
models of continuous-state dynamical
systems . . . . . . . . . . . . . . . . 201--210
Ying Zhang and
Alan K. Mackworth Constraint nets: a semantic model for
hybrid dynamic systems . . . . . . . . . 211--239
Jim Davies and
Steve Schneider A brief history of Timed CSP . . . . . . 243--271
M. W. Mislove and
A. W. Roscoe and
S. A. Schneider Fixed points without completeness . . . 273--314
Gavin Lowe Probabilistic and prioritized models of
timed CSP . . . . . . . . . . . . . . . 315--352
M. Hennessy and
H. Lin Symbolic bisimulations . . . . . . . . . 353--389
Rocco De Nicola and
Roberto Segala A process algebraic view of input/output
automata . . . . . . . . . . . . . . . . 391--423
G. Michele Pinna and
Axel Poigné On the nature of events: another
perspective in concurrency . . . . . . . 425--454
Ian Hodkinson On Gabbay's temporal fixed point
operator . . . . . . . . . . . . . . . . 1--25
Peter Päppinghaus On the logic of UNITY . . . . . . . . . 27--67
J. Robin B. Cockett and
Dwight Spencer Strong categorical datatypes. II. A term
logic for categorical programming . . . 69--113
Michael Barr Nonsymmetric $*$-autonomous categories 115--130
Giorgio Ghelli Divergence of $F_<$ type checking . . . . 131--162
Anne Bergeron Sharing out control in distributed
processes . . . . . . . . . . . . . . . 163--186
Pasquale Malacaria Studying equivalences of transition
systems with algebraic tools . . . . . . 187--205
Daniel J. Dougherty and
Patricia Johann A combinatory logic approach to
higher-order E-unification . . . . . . . 207--242
Yiannis N. Moschovakis Computable concurrent processes . . . . 243--273
Gilles Bernot and
Michel Bidoit and
Teodor Knapik Observational specifications and the
indistinguishability assumption . . . . 275--314
P. Inverardi and
M. Nesi Deciding observational congruence of
finite-state CCS expressions by
rewriting . . . . . . . . . . . . . . . 315--354
Andreas Weiermann Termination proofs for term rewriting
systems by lexicographic path orderings
imply multiply recursive derivation
lengths . . . . . . . . . . . . . . . . 355--362
Don Pigozzi and
Antonino Salibra Lambda abstraction algebras:
representation theorems . . . . . . . . 5--52
F. Laroussinie and
S. Pinchinat and
Ph. Schnoebelen Translations between modal logics of
reactive systems . . . . . . . . . . . . 53--71
Roberto Gorrieri and
Marco Roccetti and
Enrico Stancampiano A theory of processes with durational
Actions . . . . . . . . . . . . . . . . 73--94
Abdelillah Mokkedem and
Dominique Méry On using temporal logic for refinement
and compositional verification of
concurrent systems . . . . . . . . . . . 95--138
Marisa Navarro and
Fernando Orejas and
Ana Sánchez On the correctness of modular systems 139--177
E. G. Wagner On the role of memory in object-based
and object-oriented languages . . . . . 179--199
Abhi Dattasharma and
S. Sathiya Keerthi An augmented Voronoi roadmap for $3$D
translational motion planning for a
convex polyhedron moving amidst convex
polyhedral obstacles . . . . . . . . . . 205--230
Majid Sarrafzadeh and
Sanjeev R. Maddila Discrete warehouse problem . . . . . . . 231--247
L. Prasad and
S. S. Iyengar A note on the combinatorial structure of
the visibility graph in simple polygons 249--263
Nageswara S. V. Rao On fast planning of suboptimal paths
amidst polygonal obstacles in plane . . 265--289
R. Sridhar and
K. Han and
N. Chandrasekharan Efficient algorithms for shortest
distance queries on special classes of
polygons . . . . . . . . . . . . . . . . 291--300
Mark de Berg and
Leonidas Guibas and
Dan Halperin and
Mark Overmars and
Otfried Schwarzkopf and
Micha Sharir and
Monique Teillaud Reaching a goal with directional
uncertainty . . . . . . . . . . . . . . 301--317
Guna Seetharaman A simplified design strategy for mapping
image processing algorithms on a SIMD
torus . . . . . . . . . . . . . . . . . 319--331
Sa\"\id Bettayeb On the $k$-ary hypercube . . . . . . . . 333--339
Frédéric Gruau and
Jean-Yves Ratajszczak and
Gilles Wiber Fundamental study: a neural compiler . . 1--52
Peter Johansen On-line string matching with feedback 53--67
David E. Muller and
Paul E. Schupp Simulating alternating tree automata by
nondeterministic automata: New results
and new proofs of the theorems of Rabin,
McNaughton and Safra . . . . . . . . . . 69--107
Rod G. Downey and
Michael R. Fellows Fixed-parameter tractability and
completeness II: On completeness for
$W[1]$ . . . . . . . . . . . . . . . . . 109--131
Andrew Chi-Chih Yao Algebraic decision trees and Euler
characteristics . . . . . . . . . . . . 133--150
Shyam Kapur and
Gianfranco Bilardi Language learning without
overgeneralization . . . . . . . . . . . 151--162
Alberto Apostolico and
Dany Breslauer and
Zvi Galil Parallel detection of all palindromes in
a string . . . . . . . . . . . . . . . . 163--173
Birgit Jenner and
Jacobo Torán Computing functions with parallel
queries to NP . . . . . . . . . . . . . 175--193
Roberto Gorrieri and
Ugo Montanari On the implementation of concurrent
calculi in net calculi: two case studies 195--252
Lila Kari and
Alexandru Mateescu and
Gheorghe P\uaun and
Arto Salomaa Multi-pattern languages . . . . . . . . 253--268
Johan Håstad and
Alexander Razborov and
Andrew Yao On the shrinkage exponent for read-once
formulae . . . . . . . . . . . . . . . . 269--282
Detlef Sieling and
Ingo Wegener Graph driven BDDs --- a new data
structure for Boolean functions . . . . 283--310
Yoshihiro Mizoguchi and
Yasuo Kawahara Relational graph rewritings . . . . . . 311--328
H. Petersen A remark on a paper by A. B. Matos . . . 329--330
Véronique Terrier On real time one-way cellular array . . 331--335
Anders Dessmark and
Andrzej Lingas and
Anil Maheshwari Multi-list layering: Complexity and
applications . . . . . . . . . . . . . . 337--350
J. Justin and
G. Pirillo On a question about factorization
forests . . . . . . . . . . . . . . . . 351--355
J. Maluszynski and
M. Wirsing Preface . . . . . . . . . . . . . . . . 1
Annika Aasa Precedences in specifications and
implementations of programming languages 3--26
María Alpuente and
Moreno Falaschi and
Giorgio Levi Incremental constraint satisfaction for
equational logic programming . . . . . . 27--57
Rita Loogen and
Stephan Winkler Dynamic detection of determinism in
functional logic languages . . . . . . . 59--87
Maurizio Proietti and
Alberto Pettorossi Unfolding--definition--folding, in this
order, for avoiding unnecessary
variables in logic programs . . . . . . 89--124
Ulf Nilsson Abstract interpretation: a kind of magic 125--138
C. Kirchner Editorial . . . . . . . . . . . . . . . 139
Christopher Lynch and
Wayne Snyder Redundancy criteria for constrained
completion . . . . . . . . . . . . . . . 141--177
Nachum Dershowitz and
Charles Hoot Natural termination . . . . . . . . . . 179--207
Albert Rubio and
Robert Nieuwenhuis A total AC-compatible ordering based on
RPO . . . . . . . . . . . . . . . . . . 209--227
Franz Baader and
Klaus U. Schulz Combination techniques and decision
problems for disunification . . . . . . 229--255
Géraud Sénizergues Some undecidable termination problems
for semi-Thue systems . . . . . . . . . 257--276
Andrea Asperti and
Cosimo Laneve Paths, computations and labels in the
lambda-calculus . . . . . . . . . . . . 277--297
Jean Gallier Proving properties of typed
$\lambda$-terms using realizability and
covers, and sheaves . . . . . . . . . . 299--368
Do Long Van and
B. Le Saec and
I. Litovsky Characterizations of rational
$\omega$-languages by means of right
congruences . . . . . . . . . . . . . . 1--21
Kamala Krithivasan and
Meena Mahajan Nondeterministic, probabilistic and
alternating computations on cellular
array models . . . . . . . . . . . . . . 23--49
Valentin M. Antimirov and
Peter D. Mosses Rewriting extended regular expressions 51--72
Michael A. Bender and
Michel Gastaldo and
Michel Morvan Parallel interval order recognition and
construction of interval representations 73--91
Arthur S. Goldstein and
Edward M. Reingold The complexity of pursuit on a graph . . 93--112
Tao Jiang and
Vadim G. Timkovsky Shortest consistent superstrings
computable in polynomial time . . . . . 113--122
Akira Ito and
Katsushi Inoue and
Itsuo Takanami and
Yue Wang Optimal simulation of two-dimensional
alternating finite automata by three-way
nondeterministic Turing machines . . . . 123--135
Tao Jiang and
Lusheng Wang and
Kaizhong Zhang Alignment of trees --- an alternative to
tree edit . . . . . . . . . . . . . . . 137--148
David W. Juedes and
Jack H. Lutz Weak completeness in $E$ and $E_2$ . . . 149--158
Pierluigi Crescenzi and
Christos H. Papadimitriou Reversible simulation of space-bounded
computations . . . . . . . . . . . . . . 159--165
Peter Bro Miltersen On the cell probe complexity of
polynomial evaluation . . . . . . . . . 167--174
Roberto De Prisco and
Giuseppe Parlati and
Giuseppe Persiano Minimal path length of trees with known
fringe . . . . . . . . . . . . . . . . . 175--188
Rémy Malgouyres Graphs generalizing closed curves with
linear construction of the Hamiltonian
cycle. Parametrization of discretized
curves . . . . . . . . . . . . . . . . . 189--249
Martín Matamala Recursive construction of periodic
steady state for neural networks . . . . 251--267
John Harrison Dynamical properties of PWD$0$L systems 269--284
Giora Slutzki and
Sándor Vágvölgyi Deterministic top-down tree transducers
with iterated look-ahead . . . . . . . . 285--308
Zhi-Zhong Chen The maximal $f$-dependent set problem
for planar graphs is in NC . . . . . . . 309--318
Aviezri S. Fraenkel and
Alan Jaffray and
Anton Kotzig and
Gert Sabidussi Modular Nim (mathematical game) . . . . 319--333
Xaver Gubá\vs and
Juraj Hromkovi\vc and
Juraj Waczulík A nonlinear lower bound on the practical
combinational complexity . . . . . . . . 335--342
Wojciech Rytter Context-free recognition via shortest
paths computation: a version of
Valiant's algorithm . . . . . . . . . . 343--352
Louxin Zhang On the approximation of longest common
nonsupersequences and shortest common
nonsubsequences . . . . . . . . . . . . 353--362
H. Prodinger and
W. Szpankowski Preface . . . . . . . . . . . . . . . . 1
Philippe Flajolet and
Xavier Gourdon and
Philippe Dumas Mellin transforms and asymptotics:
Harmonic sums . . . . . . . . . . . . . 3--58
François Bergeron and
Ulrike Sattler Constructible differentially finite
algebraic series in several variables 59--65
Michael Drmota and
Mich\`ele Soria Marking in combinatorial constructions:
Generating functions and limiting
distributions . . . . . . . . . . . . . 67--99
Philippe Flajolet and
Robert Sedgewick Mellin transforms and asymptotics:
Finite differences and Rice's integrals 101--124
Dani\`ele Gardy and
Guy Louchard Dynamic analysis of some relational
databases parameters . . . . . . . . . . 125--159
Philippe Jacquet and
Wojciech Szpankowski Asymptotic behavior of the Lempel--Ziv
parsing scheme and digital search trees 161--197
Peter Kirschenhofer and
Conrado Martínez and
Helmut Prodinger Analysis of an optimized search
algorithm for skip lists . . . . . . . . 199--220
Hosam M. Mahmoud and
Robert T. Smythe Probabilistic analysis of bucket
recursive trees . . . . . . . . . . . . 221--249
Werner Schachinger On the variance of a class of inductive
valuations of data structures for
digital search . . . . . . . . . . . . . 251--275
U. Schmid Random trees in queueing systems with
deadlines . . . . . . . . . . . . . . . 277--314
G. Braga and
G. Cattaneo and
P. Flocchini and
C. Quaranta Vogliotti Pattern growth in elementary cellular
automata . . . . . . . . . . . . . . . . 1--26
G. Srikrishna and
C. Pandu Rangan Optimal parallel algorithms for path
problems on planar graphs . . . . . . . 27--43
Y. Breitbart and
H. Hunt, III and
D. Rosenkrantz On the size of binary decision diagrams
representing Boolean functions . . . . . 45--69
Ernst L. Leiss Implicit language equations: existence
and uniqueness of solutions . . . . . . 71--93
Krzysztof Diks and
Evangelos Kranakis and
Adam Malinowski and
Andrzej Pelc Anonymous wireless rings . . . . . . . . 95--109
Nadia Creignou The class of problems that are linearly
equivalent to Satisfiability or a
uniform method for proving
NP-completeness . . . . . . . . . . . . 111--145
Iain A. Stewart Complete problems for monotone NP . . . 147--157
F. Drewes and
A. Habel and
H.-J. Kreowski and
S. Taubenberger Generating self-affine fractals by
collage grammars . . . . . . . . . . . . 159--187
Jiazhen Cai and
Robert Paige Using multiset discrimination to solve
language processing problems without
hashing . . . . . . . . . . . . . . . . 189--228
Christophe Reutenauer and
Marcel Paul Schützenberger Variétés et fonctions rationnelles.
(French) [Varieties and rational
functions] . . . . . . . . . . . . . . . 229--240
Ker-I Ko A polynomial-time computable curve whose
interior has a nonrecursive measure . . 241--270
Ofer Biran and
Shlomo Moran and
Shmuel Zaks Tight bounds on the round complexity of
distributed $1$-solvable tasks . . . . . 271--290
Seymour Ginsburg and
Katsumi Tanaka Interval queries on object histories . . 291--316
Martin Middendorf On finding various minimal, maximal, and
consistent sequences over a binary
alphabet . . . . . . . . . . . . . . . . 317--327
B. Jamison and
S. Olariu A linear-time recognition algorithm for
$P_4$-reducible graphs . . . . . . . . . 329--344
Liang Zhang and
Zhonghui Shen Completion of recognizable bifix codes 345--355
Gary Benson A space efficient algorithm for finding
the best nonoverlapping alignment score 357--369
Lane A. Hemaspaandra and
Zhigen Jiang P-selectivity: Intersections and indices 371--380
Shang-Hua Teng Independent sets versus perfect
matchings . . . . . . . . . . . . . . . 381--390
Oded Maler A decomposition theorem for
probabilistic transition systems . . . . 391--396
Andre Scedrov and
Dennis DeTurk and
Wolfgang Ziller Moez Alimohamed, 1967--1994 . . . . . . 1--3
Moez Alimohamed A characterization of lambda
definability in categorical models of
implicit polymorphism . . . . . . . . . 5--23
Bard Bloom Structural operational semantics for
weak bisimulations . . . . . . . . . . . 25--68
Zena M. Ariola and
Arvind XXX Properties of a first-order functional
language with sharing . . . . . . . . . 69--108
Franck Cassez and
Olivier Roux Compilation of the ELECTRE reactive
language into finite transition systems 109--143
David B. Kemp and
Divesh Srivastava and
Peter J. Stuckey Bottom-up evaluation and query
optimization of well-founded models . . 145--184
Rudolf Berghammer and
Birgit Elbl and
Ulf Schmerl Formalizing Dijkstra's predicate
transformer wp in weak second-order
logic . . . . . . . . . . . . . . . . . 185--197
Maria Paola Bonacina and
Jieh Hsiang Towards a foundation of completion
procedures as semidecision procedures 199--242
Rolf Backofen and
Gert Smolka A complete and recursive feature theory 243--268
J. F. Naughton and
R. Ramakrishnan and
Y. Sagiv and
J. D. Ullman Argument reduction by factoring . . . . 269--310
Fabio Alessi and
Paolo Baldan and
Gianna Bell\`e A fixed-point theorem in a category of
compact metric spaces . . . . . . . . . 311--320
Yuji Kobayashi A finitely presented monoid which has
solvable word problem but has no regular
complete presentation . . . . . . . . . 321--329
Guo-Qiang Zhang On maximal stable functions . . . . . . 331--339
Anna Ingólfsdóttir Late and early semantics coincide for
testing . . . . . . . . . . . . . . . . 341--349
E. Bampis and
J.-C König and
D. Trystram Optimal parallel execution of complete
binary trees and grids into most popular
interconnection networks . . . . . . . . 1--18
Leszek G\kasieniec and
Wojciech Plandowski and
Wojciech Rytter The zooming method: a recursive approach
to time-space efficient string-matching 19--30
Hans L. Bodlaender and
Rodney G. Downey and
Michael R. Fellows and
Harold T. Wareham The parameterized complexity of sequence
alignment and consensus . . . . . . . . 31--54
Claude Sureson NP$\not=$co-NP and models of arithmetic 55--67
Klaus Jansen and
Haiko Müller The minimum broadcast time problem for
several processor networks . . . . . . . 69--85
Taishin Y. Nishida Quasi-deterministic $0$L systems and
their representation . . . . . . . . . . 87--116
Allan Cheng and
Javier Esparza and
Jens Palsberg Complexity results for $1$-safe nets . . 117--136
Marius Zimand On the topological size of
$p$-$m$-complete degrees . . . . . . . . 137--147
Gerhard Schurz Most general first order theorems are
not recursively enumerable . . . . . . . 149--163
Philippe Aigrain and
Dani\`ele Beauquier Polyomino tilings, cellular automata and
codicity . . . . . . . . . . . . . . . . 165--180
Edoardo Amaldi and
Viggo Kann The complexity and approximability of
finding maximum feasible subsystems of
linear relations . . . . . . . . . . . . 181--210
Didier Arqu\`es and
Olivier Grange A fast scan-line algorithm for
topological filling of well-nested
objects in $2.5$D digital pictures . . . 211--248
Chang-Wu Yu and
Gen-Huey Chen Efficient parallel algorithms for doubly
convex-bipartite graphs . . . . . . . . 249--265
Joël Blot and
Wenceslas Fernandez de la Vega and
Vangelis Th Paschos and
Rachid Saad Average case analysis of greedy
algorithms for optimisation problems on
set systems . . . . . . . . . . . . . . 267--298
P. Diamond and
P. Kloeden and
V. Kozyakin and
A. Pokrovskii On the fragmentary complexity of
symbolic sequences . . . . . . . . . . . 1--17
Bruno Durand A Random NP-complete problem for
inversion of $2$D cellular automata . . 19--32
Liming Cai and
Jianer Chen On input read-modes of alternating
Turing machines . . . . . . . . . . . . 33--55
Takayoshi Shoudai and
Satoru Miyano Using maximal independent sets to solve
problems in parallel . . . . . . . . . . 57--65
Ratnesh Kumar and
Vijay K. Garg Extremal solutions of inequations over
lattices with applications to
supervisory control . . . . . . . . . . 67--92
Hans L. Bodlaender and
Klaus Jansen Restrictions of graph partition
problems. Part I . . . . . . . . . . . . 93--109
Ingo Althöfer and
Jörg Bültermann Superlinear period lengths in some
subtraction games . . . . . . . . . . . 111--119
André Arnold An initial semantics for the
$\mu$-calculus on trees and Rabin's
complementation theorem . . . . . . . . 121--132
Devdatt P. Dubhashi and
Grammati E. Pantziou and
Paul G. Spirakis and
Christos D. Zaroliagis The fourth moment in Luby's distribution 133--140
Don Kimber and
Philip M. Long On-line learning of smooth functions of
a single variable . . . . . . . . . . . 141--156
Kenichi Morita Reversible simulation of one-dimensional
irreversible cellular automata . . . . . 157--163
Uri Zwick The smallest networks on which the
Ford-Fulkerson maximum flow procedure
may fail to terminate . . . . . . . . . 165--170
Maria Cristina Pinotti and
Geppino Pucci Parallel algorithms for priority queue
operations . . . . . . . . . . . . . . . 171--180
P. Enjalbert and
E. W. Mayr and
K. W. Wagner Preface . . . . . . . . . . . . . . . . 181
Carme \`Alvarez and
Birgit Jenner On adaptive DLOGTIME and POLYLOGTIME
reductions . . . . . . . . . . . . . . . 183--205
Bernd Borchert On the acceptance power of regular
languages . . . . . . . . . . . . . . . 207--225
Véronique Bruy\`ere and
Clelia De Felice and
Giovanna Guaiana On some decision problems for trace
codings . . . . . . . . . . . . . . . . 227--260
Kousha Etessami and
Neil Immerman Reachability and the power of local
ordering . . . . . . . . . . . . . . . . 261--279
Petr Jan\vcar Undecidability of bisimilarity for Petri
nets and some related problems . . . . . 281--301
F. Laroussinie and
Ph. Schnoebelen A hierarchy of temporal logics with past 303--324
Ashish V. Naik and
Kenneth W. Regan and
D. Sivakumar On quasilinear-time complexity theory 325--349
R. Hull Foreword . . . . . . . . . . . . . . . . 1
Peter Buneman and
Shamim Naqvi and
Val Tannen and
Limsoon Wong Principles of programming with complex
objects and collection types . . . . . . 3--48
Jan Van den Bussche and
Dirk Van Gucht The expressive power of
cardinality-bounded set values in
object-based data models . . . . . . . . 49--66
Stéphane Grumbach and
Christophe Tollu On the expressive power of counting . . 67--99
Serge Abiteboul and
Moshe Y. Vardi and
Victor Vianu Computing with infinitary logic . . . . 101--128
Jyrki Kivinen and
Heikki Mannila Approximate inference of functional
dependencies from relations . . . . . . 129--149
Alan Fekete and
Nancy Lynch and
William E. Weihl Hybrid atomicity for nested transactions 151--178
Man Hon Wong and
Divyakant Agrawal Context-specific synchronization for
atomic data types in object-based
databases . . . . . . . . . . . . . . . 179--199
Antonio Brogi and
Franco Turini Fully abstract compositional semantics
for an algebra of logic programs . . . . 201--229
Stefania Costantini Contributions to the stable model
semantics of logic programs with
negation . . . . . . . . . . . . . . . . 231--255
Uri Abraham On interprocess communication and the
implementation of multi-writer atomic
registers . . . . . . . . . . . . . . . 257--298
Ugo Montanari and
Daniel Yankelevich Location equivalence in a parametric
setting . . . . . . . . . . . . . . . . 299--332
Jules Desharnais and
Nadir Belkhiter and
Salah Ben Mohamed Sghaier and
Fairouz Tchier and
Ali Jaoua and
Ali Mili and
Nejib Zaguia Embedding a demonic semilattice in a
relation algebra . . . . . . . . . . . . 333--360
Manfred Schmidt-Schauß and
Massimo Marchiori and
Sven Eric Panitz Modular termination of $r$-consistent
and left-linear term rewriting systems 361--374
G. Ausiello and
P. Crescenzi and
M. Protasi Approximate solution of NP optimization
problems . . . . . . . . . . . . . . . . 1--55
Ji\vrí Adámek and
Václav Koubek On the greatest fixed point of a set
functor . . . . . . . . . . . . . . . . 57--75
Manfred Droste Recognizable languages in concurrency
monoids . . . . . . . . . . . . . . . . 77--109
David A. Naumann Predicate transformers and higher-order
programs . . . . . . . . . . . . . . . . 111--159
P. H. B. Gardiner Algebraic proofs of consistency and
completeness . . . . . . . . . . . . . . 161--191
M. Hazewinkel Editorial to the Subject Index Volumes
101--150 . . . . . . . . . . . . . . . . 195
Anonymous Subject Index Volumes 101--150 . . . . . 197
Anonymous Reference List of Indexed Articles . . . 315
Anonymous Cumulative Index Volumes 101--150 . . . 339
Anonymous Workshop on Topology and Completion in
Semantics . . . . . . . . . . . . . . . ??
P. Gastin and
J. J. M. M. Rutten Preface . . . . . . . . . . . . . . . . 1
Simon Ambler and
Marta Kwiatkowska and
Nicholas Measor Duality and the completeness of the
modal $\mu$-calculus . . . . . . . . . . 3--27
André Arnold A topological property of rational
$\omega$-languages . . . . . . . . . . . 29--36
Frank S. de Boer and
Alessandra Di Pierro and
Catuscia Palamidessi Nondeterminism and infinite computations
in constraint programming . . . . . . . 37--78
Marcello M. Bonsangue and
Bart Jacobs and
Joost N. Kok Duality beyond sober spaces: Topological
spaces and observation frames . . . . . 79--124
Bruno Courcelle The monadic second-order logic of graphs
IX: Machines and their behaviours . . . 125--162
Abbas Edalat Domain theory and integration . . . . . 163--193
S. G. Matthews An extensional treatment of lazy data
flow deadlock . . . . . . . . . . . . . 195--205
Michael W. Mislove and
Frank J. Oles Full abstraction and recursion . . . . . 207--256
M. B. Smyth Semi-metrics, closure spaces and digital
topology . . . . . . . . . . . . . . . . 257--276
Philipp Sünderhauf A faithful computational model of the
real numbers . . . . . . . . . . . . . . 277--294
R. K. Shyamasundar Foreword . . . . . . . . . . . . . . . . 295
Giuseppe Castagna A meta-language for typed
object-oriented languages . . . . . . . 297--352
Hassan A\"\it-Kaci and
Jacques Garrigue Label-selective $\lambda$-calculus
syntax and confluence . . . . . . . . . 353--383
Steffen van Bakel Intersection type assignment systems . . 385--435
Kohei Honda and
Nobuko Yoshida On reduction-based process semantics . . 437--486
M. R. K. Krishna Rao Modular proofs for completeness of
hierarchical term rewriting systems . . 487--512
Daniel Fredholm Intensional aspects of function
definitions . . . . . . . . . . . . . . 1--66
Wilfrid Hodges The meaning of specifications I: Domains
and initial models . . . . . . . . . . . 67--89
Egidio Astesiano and
Maura Cerioli Free objects and equational deduction
for partial conditional specifications 91--138
Masahito Kurihara and
Azuma Ohuchi Modularity in noncopying term rewriting 139--169
Albert Benveniste and
Bernard C. Levy and
Eric Fabre and
Paul Le Guernic A calculus of stochastic systems for the
specification, simulation, and hidden
state estimation of mixed
stochastic/non-stochastic systems . . . 171--217
Karen Seidel Probabilistic communicating processes 219--249
Luca Aceto and
Alan Jeffrey A complete axiomatization of timed
bisimulation for a class of timed
regular behaviours . . . . . . . . . . . 251--268
Rakesh M. Verma Transformations and confluence for
rewrite systems . . . . . . . . . . . . 269--283
Paola Inverardi and
Monica Nesi Infinite normal forms for non-linear
term rewriting systems . . . . . . . . . 285--303
R. Banach Locating the contractum in the double
pushout approach . . . . . . . . . . . . 305--320
M. Mislove and
M. Nivat and
C. Papadimitnou Editorial on the Electronic Notes in
Theoretical Computer Science . . . . . . 321
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1
C. A. Petri Nets, time and space . . . . . . . . . . 3--48
J. Desel and
K.-P. Neuendorf and
M.-D. Radola Proving nonreachability by
modulo-invariants . . . . . . . . . . . 49--64
Joost Engelfriet A multiset semantics for the pi-calculus
with replication . . . . . . . . . . . . 65--94
Javier Esparza and
Glenn Bruns Trapping mutual exclusion in the box
calculus . . . . . . . . . . . . . . . . 95--128
P. W. Hoogers and
H. C. M. Kleijn and
P. S. Thiagarajan An event structure semantics for general
Petri nets . . . . . . . . . . . . . . . 129--170
José Meseguer and
Ugo Montanari and
Vladimiro Sassone Process versus unfolding semantics for
Place/Transition Petri nets . . . . . . 171--210
Mogens Nielsen and
Glynn Winskel Petri nets and bisimulation . . . . . . 211--244
Einar Smith On the border of causality: Contact and
confusion . . . . . . . . . . . . . . . 245--270
Enrique Teruel and
Manuel Silva Structure theory of equal conflict
systems . . . . . . . . . . . . . . . . 271--300
A. Lingas Preface . . . . . . . . . . . . . . . . 1
Artur Czumaj and
Alan Gibbons Guthrie's problem: new equivalences and
rapid reductions . . . . . . . . . . . . 3--22
Marek Karpinski and
Rutger Verbeek On randomized versus deterministic
computation . . . . . . . . . . . . . . 23--39
Jerzy W. Jaromczyk and
Grzegorz \'Swia\ctek A theory of even functionals and their
algorithmic applications . . . . . . . . 41--56
David M. Cohen and
Michael L. Fredman Products of finite state machines with
full coverage . . . . . . . . . . . . . 57--65
Werner Ebinger and
Anca Muscholl Logical definability on infinite traces 67--84
Thomas Wilke An algebraic characterization of
frontier testable tree languages . . . . 85--106
Lalita Jategaonkar and
Albert R. Meyer Deciding true concurrency equivalences
on safe, finite nets . . . . . . . . . . 107--143
Claude Sureson P, NP, Co-NP and weak systems of
arithmetic . . . . . . . . . . . . . . . 145--163
Christophe Fiorio and
Jens Gustedt Two linear time Union Find strategies
for image processing . . . . . . . . . . 165--181
Victor Mitrana and
Gheorghe P\uaun and
Grzegorz Rozenberg and
Arto Salomaa Pattern systems . . . . . . . . . . . . 183--201
Ramana M. Idury and
Alejandro A. Schäffer Multiple matching of parameterized
patterns . . . . . . . . . . . . . . . . 203--224
Joseph F. JáJá and
Kwan Woo Ryu and
Uzi Vishkin Sorting strings and constructing digital
search trees in parallel . . . . . . . . 225--245
J. Engelfriet and
T. Harju and
A. Proskurowski and
G. Rozenberg Characterization and complexity of
uniformly nonprimitive labeled
$2$-structures . . . . . . . . . . . . . 247--282
Carlo Blundo and
Alfredo De Santis and
Luisa Gargano and
Ugo Vaccaro On the information rate of secret
sharing schemes . . . . . . . . . . . . 283--306
Cristian Calude and
Marius Zimand Effective category and measure in
abstract complexity theory . . . . . . . 307--327
N. Lafaye de Micheaux and
C. Rambaud Confluence for graph transformations . . 329--348
Rana Barua and
S. Ramakrishnan $\sigma$-game, $\sigma^+$-game and
two-dimensional additive cellular
automata . . . . . . . . . . . . . . . . 349--366
Lane A. Hemaspaandra and
Leen Torenvliet Optimal advice . . . . . . . . . . . . . 367--377
S. Ramesh and
Bommadevara N. Srinivas A direct characterization of completion 379--385
J. Justin and
G. Pirillo On a combinatorial property of Sturmian
words . . . . . . . . . . . . . . . . . 387--394
Stephen L. Bloom and
Zoltán Ésik Fixed point operations on CCC's. Part I 1--38
Davide Sangiorgi Locality and interleaving semantics in
calculi for mobile processes . . . . . . 39--83
Fairouz Kamareddine and
Rob Nederpelt A useful $\lambda$-notation . . . . . . 85--109
Neil Immerman and
Sushant Patnaik and
David Stemple The expressiveness of a family of finite
set languages . . . . . . . . . . . . . 111--140
Jean-Michel Fourneau and
Erol Gelenbe and
Rina Suros $G$-networks with multiple classes of
negative and positive customers . . . . 141--156
Vadim Kagan and
Anil Nerode and
V. S. Subrahmanian Computing minimal models by partial
instantiation . . . . . . . . . . . . . 157--177
Flemming Nielson and
Hanne Riis Nielson From CML to its process algebra . . . . 179--219
Guo-Qiang Zhang Quasi-prime algebraic domains . . . . . 221--264
M. W. Bunder and
J. R. Hindley Two $\beta=\lambda$-terms with no types
in common . . . . . . . . . . . . . . . 265--266
Thomas Drakengren Uniqueness of Scott's reflexive domain
in $P\omega$ . . . . . . . . . . . . . . 267--276
Wenhui Zhang Number of models and satisfiability of
sets of clauses . . . . . . . . . . . . 277--288
G. Kuoherov and
P. Lescanne and
P. Mosses Valentin Antimirov (1961--1995) . . . . 239
Gregory Kucherov and
Pierre Lescanne and
Peter Mosses Valentin Antimirov (1961--1995) . . . . 289--290
Valentin Antimirov Partial derivatives of regular
expressions and finite automaton
constructions . . . . . . . . . . . . . 291--319
Elena Barcucci and
Alberto Del Lungo and
Maurice Nivat and
Renzo Pinzani Reconstructing convex polyominoes from
horizontal and vertical projections . . 321--347
Jörg Keller Fast rehashing in PRAM emulations . . . 349--363
Steffen Lange and
Thomas Zeugmann and
Shyam Kapur Monotonic and dual monotonic language
learning . . . . . . . . . . . . . . . . 365--410
Kazuo Iwama and
Chuzo Iwamoto and
Manzur Morshed Time lower bounds do not exist for CRCW
PRAMs . . . . . . . . . . . . . . . . . 411--424
Andrzej Ehrenfeucht and
Paulien ten Pas and
Grzegorz Rozenberg A note on binary grammatical codes of
trees . . . . . . . . . . . . . . . . . 425--438
Jean Berstel and
Jean-Eric Pin Local languages and the Berry--Sethi
algorithm . . . . . . . . . . . . . . . 439--446
Lane A. Hemaspaandra and
Albrecht Hoene and
Mitsunori Ogihara Reducibility classes of $P$-selective
sets . . . . . . . . . . . . . . . . . . 447--457
Philippe Nehlig Applications quasi affines: pavages par
images réciproques. (French)
[Quasi-affine applications: tilings for
reciprocal images] . . . . . . . . . . . 1--38
Rainer Kemp Binary search trees constructed from
nondistinct keys with/without specified
probabilities . . . . . . . . . . . . . 39--70
Pál Gyenizse and
Sándor Vágvölgyi Compositions of deterministic bottom-up,
top-down, and regular look-ahead tree
transformations . . . . . . . . . . . . 71--97
Matthias Krause Geometric arguments yield better bounds
for threshold circuits and distributed
computing . . . . . . . . . . . . . . . 99--117
Nicolas Bedon Finite automata and ordinals . . . . . . 119--144
Olympia Louscou-Bozapalidou Stochastically costed tree automata:
Turakainen's theorem . . . . . . . . . . 145--158
Jean Françon Sur la topologie d'un plan arithmétique.
(French) [On the topology of an
arithmetic plan] . . . . . . . . . . . . 159--176
Michael I. Schwartzbach Static correctness of hierarchical
procedures . . . . . . . . . . . . . . . 177--201
Marco Forti and
Furio Honsell A general construction of hyperuniverses 203--215
Yoshikane Takahashi A unified constructive network model for
problem-solving . . . . . . . . . . . . 217--261
Yonghoan Kim New values in Domineering . . . . . . . 263--280
Véronique Terrier Language not recognizable in real time
by one-way cellular automata . . . . . . 281--287
André Arnold and
Ilaria Castellani An algebraic characterization of
observational equivalence . . . . . . . 289--299
Giovanni Manzini On the ordering of sparse linear systems 301--313
Roberto De Prisco and
Alfredo De Santis New lower bounds on the cost of binary
search trees . . . . . . . . . . . . . . 315--325
Anonymous Workshop on Algorithmic Complexity of
Algebraic and Geometric Models . . . . . ??
Manuel Bronstein and
Marko Petkov\vsek An introduction to pseudo-linear algebra 3--33
Olivier Devillers An introduction to randomization in
computational geometry . . . . . . . . . 35--52
Y. Elihai and
Y. Yomdin Flexible high-order discretization of
geometric data for global motion
planning . . . . . . . . . . . . . . . . 53--77
D. Grigoriev NC solving of a system of linear
ordinary differential equations in
several unknowns . . . . . . . . . . . . 79--90
Dima Grigoriev and
Marek Karpinski Computability of the additive complexity
of algebraic circuits with root
extracting . . . . . . . . . . . . . . . 91--99
Jean-Paul Laumond and
Jean-Jacques Risler Nonholonomic systems: Controllability
and complexity . . . . . . . . . . . . . 101--114
Jean Moulin Ollagnier Algorithms and methods in differential
algebra . . . . . . . . . . . . . . . . 115--127
Jean-Jacques Risler A bound for the degree of nonholonomy in
the plane . . . . . . . . . . . . . . . 129--136
Farid Ablayev Lower bounds for one-way probabilistic
communication complexity and their
application to space complexity . . . . 139--159
Dima Burago and
Michel de Rougemont and
Anatol Slissenko On the complexity of partially observed
Markov decision processes . . . . . . . 161--183
D. Grigoriev and
N. Vorobjov Complexity lower bounds for computation
trees with elementary transcendental
function gates . . . . . . . . . . . . . 185--214
Alexander V. Karzanov How to tidy up a symmetric set-system by
use of uncrossing operations . . . . . . 215--225
Andrei A. Muchnik and
Nikolai K. Vereshchagin A general method to construct oracles
realizing given relationships between
complexity classes . . . . . . . . . . . 227--258
Marek Karpinski and
Igor Shparlinski On some approximation problems
concerning sparse polynomials over
finite fields . . . . . . . . . . . . . 259--266
Leonid A. Levin Computational complexity of functions 267--271
Igor Shparlinski On finding primitive roots in finite
fields . . . . . . . . . . . . . . . . . 273--275
Oleg Verbitsky Towards the parallel repetition
conjecture . . . . . . . . . . . . . . . 277--282
Joaquim Gabarró and
Conrado Martínez and
Xavier Messeguer A design of a parallel dictionary using
skip lists . . . . . . . . . . . . . . . 1--33
Michel Koskas About the $p$-paperfolding words . . . . 35--51
Afonso Ferreira and
Miltos Grammatikakis Randomized routing on generalized
hypercubes . . . . . . . . . . . . . . . 53--64
Stéphane Fabre Dépendance de syst\`emes de numération
associés \`a des puissances d'un nombre
de Pisot. (French) [Dependence of number
systems associated with the influences
of a Pisot number] . . . . . . . . . . . 65--79
Nata\vsa Jonoska Sofic shifts with synchronizing
presentations . . . . . . . . . . . . . 81--115
Marc Demange and
Vangelis Th Paschos On an approximation measure founded on
the links between optimization and
polynomial approximation theory . . . . 117--141
Yoram Hirshfeld and
Mark Jerrum and
Faron Moller A polynomial algorithm for deciding
bisimilarity of normed context-free
processes . . . . . . . . . . . . . . . 143--159
Taishin Y. Nishida and
Arto Salomaa Slender $0$L languages . . . . . . . . . 161--176
Dany Breslauer Saving comparisons in the
Crochemore-Perrin string matching
algorithm . . . . . . . . . . . . . . . 177--192
M. Agrawal and
V. Arvind Geometric sets of low information
content . . . . . . . . . . . . . . . . 193--219
Sarah E. Mocas Separating classes in the
exponential-time hierarchy from classes
in PH . . . . . . . . . . . . . . . . . 221--231
G. Ramalingam and
Thomas Reps On the computational complexity of
dynamic graph problems . . . . . . . . . 233--277
Yoshikane Takahashi Solving optimization problems with
variable-constraint by an extended
Cohen--Grossberg model . . . . . . . . . 279--341
Uri Zwick and
Mike S. Paterson The complexity of mean payoff games on
graphs . . . . . . . . . . . . . . . . . 343--359
M. Agrawal and
V. Arvind Quasi-linear truth-table reductions to
$p$-selective sets . . . . . . . . . . . 361--370
Serge Burckel Closed iterative calculus . . . . . . . 371--378
Anonymous Contents EATCS Bulletin Number 58 . . . 379
D. Gouyou-Beauchamps and
J.-G. Penaud Preface to the Special Issue on GASCOM
'94 . . . . . . . . . . . . . . . . . . 3
Herbert S. Wilf Recents dévéloppements et probl\`emes dans
le domaine de la génération aléatoire.
(French) [Recent developments and
problems in the area of random
generation] . . . . . . . . . . . . . . 5--13
Laurent Alonso and
René Schott A parallel algorithm for the generation
of a permutation and applications . . . 15--28
Elena Barcucci and
Alberto Del Lungo and
Renzo Pinzani ``Deco'' polyominoes, permutations and
random generation . . . . . . . . . . . 29--42
Alain Denise Génération aléatoire uniforme de mots de
langages rationnels. (French)
[Generating uniformly random words of
rational languages] . . . . . . . . . . 43--63
G. Louchard Probabilistic analysis of some
(un)directed animals . . . . . . . . . . 65--79
Mohamed Mosbah Probabilistic hyperedge replacement
grammars . . . . . . . . . . . . . . . . 81--102
P. Aigrain Preface to the Special Issue on the 3rd
International Workshop on Polyominoes
and Tilings . . . . . . . . . . . . . . 103--104
J. C. Fournier Pavage des figures planes sans trous par
des dominos: Fondement graphique de
l'algorithme de Thurston,
parallelisation, unicité et décomposition.
(French) [Tiling pictures of the plane
without holes by dominoes: graphical
basis of the Thurston algorithm,
parallelisation, uniqueness and
decomposition] . . . . . . . . . . . . . 105--128
Elena Barcucci and
Alberto Del Lungo and
Renzo Pinzani and
Renzo Sprugnoli Polyominoes defined by their vertical
and horizontal projections . . . . . . . 129--136
Thomas Chaboud Domino tiling in planar graphs with
regular and bipartite dual . . . . . . . 137--142
Reinhard Bündgen Buchberger's algorithm: The term
rewriter's point of view . . . . . . . . 143--190
Andrea Asperti and
Cosimo Laneve Interaction systems II: The practice of
optimal reductions . . . . . . . . . . . 191--244
Thomas F. Gritzner and
Rudolf Berghammer A relation algebraic model of robust
correctness . . . . . . . . . . . . . . 245--270
Hakan Erdogmus and
Robert Johnston and
Michael Ferguson On the operational semantics of
nondeterminism and divergence . . . . . 271--317
Giovanni Sambin and
Silvio Valentini and
Paolo Virgili Constructive domain theory as a branch
of intuitionistic pointfree topology . . 319--341
Noriko H. Arai A proper hierarchy of propositional
sequent calculi . . . . . . . . . . . . 343--354
Mingsheng Ying When is the ideal completion of abstract
basis algebraic . . . . . . . . . . . . 355--356
Roger D. Maddux Relation-algebraic semantics . . . . . . 1--85
Bruno Courcelle The monadic second-order logic of graphs
$X$: Linear orderings . . . . . . . . . 87--143
Enrico Tronci Equational programming in
$\lambda$-calculus via SL-systems. Part
1 . . . . . . . . . . . . . . . . . . . 145--184
Enrico Tronci Equational programming in
$\lambda$-calculus via SL-systems. Part
2 . . . . . . . . . . . . . . . . . . . 185--216
Chris Tuijn and
Marc Gyssens CGOOD, a categorical graph-oriented
object data model . . . . . . . . . . . 217--239
Matthias Baaz and
Alexander Leitsch and
Richard Zach Completeness of a first-order temporal
logic with time-gaps . . . . . . . . . . 241--270
Michael Kaminski and
Chung Kei Wong The power of the ``always'' operator in
first-order temporal logic . . . . . . . 271--281
Susumu Yamasaki SLDNF resolution with non-safe rule and
fixpoint semantics for general logic
programs . . . . . . . . . . . . . . . . 283--303
Arnaud Durand and
Solomampionona Ranaivoson First-order spectra with one binary
predicate . . . . . . . . . . . . . . . 305--320
Piero A. Bonatti and
Thomas Eiter Querying disjunctive databases through
nonmonotonic logics . . . . . . . . . . 321--363
Kim Marriott and
Martin Odersky Negative Boolean constraints . . . . . . 365--380
Anonymous Master Index Volume 151--160 . . . . . . 383
Zhi-Zhong Chen Parallel constructions of maximal path
sets and applications to short
superstrings . . . . . . . . . . . . . . 1--21
F. Carrere On the Kleijn--Rozenberg $k$-adjacent
languages . . . . . . . . . . . . . . . 23--68
Salah Labhalla and
Henri Lombardi and
Roger Marlin Algorithmes de calcul de la réduction de
Hermite d'une matrice \`a coefficients
polynomiaux. (French) [Algorithms for
computing an Hermitian reduction of a
matrix with polynomial coefficients] . . 69--92
Tero Harju and
Marjo Lipponen and
Alexandru Mateescu Flatwords and Post Correspondence
Problem . . . . . . . . . . . . . . . . 93--108
Alain J. Mayer and
Larry J. Stockmeyer The complexity of PDL with interleaving 109--122
Lance Fortnow and
Martin Kummer On resource-bounded instance complexity 123--140
H. Petersen On the language of primitive words . . . 141--156
Carla Selmi Over testable languages . . . . . . . . 157--190
Olivier Carton Chain automata . . . . . . . . . . . . . 191--203
Günter Hotz and
Gisela Pitsch On parsing coupled-context-free
languages . . . . . . . . . . . . . . . 205--233
Mark Fulk and
Sanjay Jain Learning in the presence of inaccurate
information . . . . . . . . . . . . . . 235--261
Kenneth W. Regan Index sets and presentations of
complexity classes . . . . . . . . . . . 263--287
Osamu Maruyama and
Satoru Miyano Inferring a tree from walks . . . . . . 289--300
Felipe Cucker and
Michael Shub Generalized Knapsack problems and fixed
degree separations . . . . . . . . . . . 301--306
Alexander E. Andreev and
Andrea E. F. Clementi and
José D. P. Rolim Constructing the highest degree subgraph
for dense graphs is in NCAS . . . . . . 307--314
Sebastiano Vigna On the relations between distributive
computability and the BSS model . . . . 5--21
Cristopher Moore Recursion theory on the reals and
continuous-time computation . . . . . . 23--44
Vasco Brattka Recursive characterization of computable
real-valued functions and relations . . 45--77
Martín Hötzel Escardó PCF extended with real numbers . . . . . 79--115
Hratchia Pélibossian On the linearity of on-line computable
functions . . . . . . . . . . . . . . . 117--132
Nathalie Revol and
Jean-Louis Roch Parallel evaluation of arithmetic
circuits . . . . . . . . . . . . . . . . 133--150
Alexander I. Mikov Large-scale addition of machine real
numbers: Accuracy estimates . . . . . . 151--170
Victor Y. Pan Parallel computation of polynomial GCD
and some related parallel computations
over abstract fields . . . . . . . . . . 173--223
Brenda S. Baker and
Edward G. Coffman, Jr. Mutual exclusion scheduling . . . . . . 225--243
Friedhelm Meyer auf der Heide and
Christian Scheideler and
Volker Stemann Exploiting storage redundancy to speed
up randomized shared memory simulations 245--281
Ernst W. Mayr and
Ralph Werchner Divide-and-conquer algorithms on the
hypercube . . . . . . . . . . . . . . . 283--296
Tsan-sheng Hsu and
Vijaya Ramachandran Efficient massively parallel
implementation of some combinatorial
algorithms . . . . . . . . . . . . . . . 297--322
Lucian Finta and
Zhen Liu and
Ioannis Milis and
Evripidis Bampis Scheduling UET--UCT series--parallel
graphs on two processors . . . . . . . . 323--340
Soumen Chakrabarti Random allocation of jobs with weights
and precedence . . . . . . . . . . . . . 341--349
Miguel Angel García Massively parallel approximation of
irregular triangular meshes of arbitrary
topology with smooth parametric surfaces 351--369
Bruno Courcelle Basic notions of universal algebra for
language theory and graph grammars . . . 1--54
Stephen L. Bloom and
Zoltán Ésik Free shuffle algebras in language
varieties . . . . . . . . . . . . . . . 55--98
Damian Niwi\'nski and
Igor Walukiewicz Games for the $\mu$-calculus . . . . . . 99--116
Livio Colussi and
Laura Toniolo How the character comparison order
shapes the shift function of on-line
pattern matching algorithms . . . . . . 117--144
Denis Derencourt A three-word code which is not
prefix--suffix composed . . . . . . . . 145--160
E. Hausen-Tropper A framework for a theory of automated
learning . . . . . . . . . . . . . . . . 161--176
Richard Beigel and
William Gasarch and
Efim Kinber Frequency computation and bounded
queries . . . . . . . . . . . . . . . . 177--192
Siegfried Lehr and
Jeffrey Shallit and
John Tromp On the vector space of the automatic
reals . . . . . . . . . . . . . . . . . 193--210
Christos Levcopoulos and
Ola Petersson Exploiting few inversions when sorting:
Sequential and parallel algorithms . . . 211--238
Xunrang Gu and
Yuzhang Zhu Optimal heapsort algorithm . . . . . . . 239--243
Heribert Vollmer and
Klaus W. Wagner Recursion theoretic characterizations of
complexity classes of counting functions 245--258
Dongyang Long Note on group codes . . . . . . . . . . 259--267
Daniel Fredholm Computing minimum with primitive
recursion over lists . . . . . . . . . . 269--276
Robert H. Gilman A shrinking lemma for indexed languages 277--281
Tatsuie Tsukiji On a small class of Boolean sums . . . . 283--289
F. Blanchard and
A. Maass Dynamical behaviour of Coven's aperiodic
cellular automata . . . . . . . . . . . 291--302
Rémy Malgouyres There is no local characterization of
separating and thin objects in $Z^3$ . . 303--308
Djelloul Ziadi Regular expression for a language
without empty word . . . . . . . . . . . 309--315
Svante Carlsson and
Jingsen Chen and
Christer Mattsson Heaps with bits . . . . . . . . . . . . 1--12
John Case and
Sanjay Jain and
Arun Sharma Anomalous learning helps succinctness 13--28
John Harrison On almost cylindrical languages and the
decidability of the D0L and PWD0L
primitivity problems . . . . . . . . . . 29--40
Víctor F. Sirvent Relationships between the dynamical
systems associated to the Rauzy
substitutions . . . . . . . . . . . . . 41--57
C. Picouleau Worst-case analysis of fast heuristics
for packing squares into a square . . . 59--72
Martin Middendorf Two-dimensional partitioning problems 73--106
Krzysztof Diks and
Andrzej Pelc Reliable computations on faulty EREW
PRAM . . . . . . . . . . . . . . . . . . 107--122
Kai Salomaa and
Derick Wood and
Sheng Yu Structural equivalence and ET$0$L
grammars . . . . . . . . . . . . . . . . 123--140
Jack H. Lutz and
Elvira Mayordomo Cook versus Karp-Levin: Separating
completeness notions if NP is not small 141--163
Pascal Hubert Propriétés combinatoires des suites
définies par le billard dans les
triangles pavants. (French)
[Combinatorial properties of sequences
defined by a billiard in paved
triangles] . . . . . . . . . . . . . . . 165--183
James Allen Fill Limits and rates of convergence for the
distribution of search cost under the
move-to-front rule . . . . . . . . . . . 185--206
Alain Finkel and
Isabelle Tellier A polynomial algorithm for the
membership problem with categorial
grammars . . . . . . . . . . . . . . . . 207--221
Clelia De Felice An application of Hajós factorizations to
variable-length codes . . . . . . . . . 223--252
David Moews Coin-sliding and Go . . . . . . . . . . 253--276
Ioan Tomescu On the asymptotic average length of a
maximum common subsequence for words
over a finite alphabet . . . . . . . . . 277--285
Arvind Gupta and
Naomi Nishimura The complexity of subgraph isomorphism
for classes of partial $k$-trees . . . . 287--298
Costas S. Iliopoulos and
Kunsoo Park A work-time optimal algorithm for
computing all string covers . . . . . . 299--310
Anonymous Contents EATCS Bulletin Number 59 . . . 311
Michel Bidoit and
Rolf Hennicker Behavioural theories and the proof of
behavioural properties . . . . . . . . . 3--55
Michael Codish and
Grigory Mashevitzky Proving implications by algebraic
approximation . . . . . . . . . . . . . 57--74
Sergio Antoy and
Aart Middeldorp A sequential reduction strategy . . . . 75--95
Bernhard Gramlich On termination and confluence properties
of disjoint and constructor-sharing
conditional rewrite systems . . . . . . 97--131
María Alpuente and
Moreno Falaschi and
Germán Vidal A compositional semantic basis for the
analysis of equational Horn programs . . 133--169
Frank Teusink Three-valued completion for abductive
logic programs . . . . . . . . . . . . . 171--200
Dale Miller Forum: A multiple-conclusion
specification logic . . . . . . . . . . 201--232
Campbell Fraser Consistent subsequences and
supersequences . . . . . . . . . . . . . 233--246
Françoise Maurin Exact complexity bounds for ordinal
addition . . . . . . . . . . . . . . . . 247--273
Laurent Pélecq Automorphism groups of context-free
graphs . . . . . . . . . . . . . . . . . 275--293
Valérie Berthé Frequences des facteurs des suites
sturmiennes. (French) [Frequencies of
factors of Sturmian series] . . . . . . 295--309
J. Ian Munro and
Venkatesh Raman Selection from read-only memory and
sorting with minimum data movement . . . 311--323
Michelle Morcrette Sur l'équivalence de descriptions de
figures iterées. (French) [On the
equivalence of descriptions of iterative
figures] . . . . . . . . . . . . . . . . 325--354
Sulekha R. Kulkarni and
Priti Shankar Linear time parsers for classes of non
context free languages . . . . . . . . . 355--390
Michel Habib and
Lhouari Nourine Tree structure for distributive lattices
and its applications . . . . . . . . . . 391--405
Carlo Blundo and
Antonella Cresti and
Alfredo De Santis and
Ugo Vaccaro Fully dynamic secret sharing schemes . . 407--440
Vincenzo Auletta and
Domenico Parente and
Giuseppe Persiano Dynamic and static algorithms for
optimal placement of resources in a tree 441--461
Sorina Dumitrescu Nonreturning PC grammar systems can be
simulated by returning systems . . . . . 463--474
Katsunobu Imai and
Kenichi Morita Firing squad synchronization problem in
reversible cellular automata . . . . . . 475--482
V. Brimkov and
B. Codenotti and
M. Leoncini and
G. Resta Strong NP-completeness of a matrix
similarity problem . . . . . . . . . . . 483--490
Y. S. Ramakrishna and
P. M. Melliar-Smith and
L. E. Moser and
L. K. Dillon and
G. Kutty Interval logics and their decision
procedures. Part I: An interval logic 1--47
Uchang Park An algebraic formulation of the
aggregative closure query . . . . . . . 49--62
Enshao Shen and
Qijia Tian Monadic partition logics and finite
automata . . . . . . . . . . . . . . . . 63--81
R. Hoofman Comparing models of the intensional
typed $\lambda$-calculus . . . . . . . . 83--99
Sandro Etalle and
Maurizio Gabbrielli Transformations of CLP modules . . . . . 101--146
Jean-Dénis Fouks and
Jean-Claude Spehner Meta-resolution: An algorithmic
formalisation . . . . . . . . . . . . . 147--172
Stéphane Demri and
Ewa Orlowska Logical analysis of demonic
nondeterministic programs . . . . . . . 173--202
Guo-Qiang Zhang The largest Cartesian closed category of
stable domains . . . . . . . . . . . . . 203--219
Georg Gottlob and
Sherry Marcus and
Anil Nerode and
Gernot Salzer and
V. S. Subrahmanian A non-ground realization of the stable
and well-founded semantics . . . . . . . 221--262
Karl Meinke Topological methods for algebraic
specification . . . . . . . . . . . . . 263--290
Anatoli Degtyarev and
Andrei Voronkov The undecidability of simultaneous rigid
E-unification . . . . . . . . . . . . . 291--300
Peter D. Mosses and
Mogens Nielsen and
Michael I. Schwartzbach Foreword . . . . . . . . . . . . . . . . 1--1
Martin Hofmann and
Donald Sannella On behavioural abstraction and
behavioural satisfaction in higher-order
logic . . . . . . . . . . . . . . . . . 3--45
Bengt Jonsson and
Yih-Kuen Tsay Assumption/guarantee specifications in
linear-time temporal logic . . . . . . . 47--72
Dexter Kozen Rational spaces and set constraints . . 73--94
Aart Middeldorp and
Satoshi Okui and
Tetsuo Ida Lazy narrowing: Strong completeness and
eager variable elimination . . . . . . . 95--130
Mooly Sagiv and
Thomas Reps and
Susan Horwitz Precise interprocedural dataflow
analysis with applications to constant
propagation . . . . . . . . . . . . . . 131--170
Kai Salomaa Decidability of equivalence for
deterministic synchronized tree automata 171--192
David Sands Proving the correctness of
recursion-based automatic program
transformations . . . . . . . . . . . . 193--233
Davide Sangiorgi $\pi$-Calculus, internal mobility, and
agent-passing calculi . . . . . . . . . 235--274
Br\`anislav Rovan Introduction . . . . . . . . . . . . . . 1--1
Klaus Ambos-Spies and
Hans-Christian Neis and
Sebastiaan A. Terwijn Genericity and measure for exponential
time . . . . . . . . . . . . . . . . . . 3--19
Ricardo A. Baeza-Yates Bounded disorder: The effect of the
index . . . . . . . . . . . . . . . . . 21--38
Martin Dietzfelbinger and
Juraj Hromkovi\vc and
Georg Schnitger A comparison of two lower-bound methods
for communication complexity . . . . . . 39--51
Gian-Luigi Ferrari and
Ugo Montanari and
Paola Quaglia A $\pi$-calculus with explicit
substitutions . . . . . . . . . . . . . 53--103
Juhani Karhumäki and
Wojciech Plandowski On the size of independent systems of
equations in semigroups . . . . . . . . 105--119
Dimitris J. Kavvadias and
Grammati E. Pantziou and
Paul G. Spirakis and
Christos D. Zaroliagis Hammock-on-ears decomposition: A
technique for the efficient parallel
solution of shortest paths and other
problems . . . . . . . . . . . . . . . . 121--154
Kurt Sieber Full abstraction for the second order
subset of an ALGOL-like language . . . . 155--212
Anonymous International Workshop on Universal
Machines and Computations . . . . . . . ??
Maurice Margenstern Foreword . . . . . . . . . . . . . . . . 213--214
Yurii Rogozhin Small universal Turing machines . . . . 215--240
Manfred Kudlek Small deterministic Turing machines . . 241--255
Liudmila Pavlotskaya On machines, universal by extensions . . 257--266
Ivan Korec Small universal register machines . . . 267--301
Kenichi Morita Universality of a reversible two-counter
machine . . . . . . . . . . . . . . . . 303--320
Gheorghe P\uaun and
Grzegorz Rozenberg and
Arto Salomaa Computing by splicing . . . . . . . . . 321--336
Kenichi Morita and
Katsunobu Imai Self-reproduction in a reversible
cellular space . . . . . . . . . . . . . 337--366
Jacques Mazoyer On optimal solutions to the firing squad
synchronization problem . . . . . . . . 367--404
Eric Goles and
Martín Matamala Symmetric discrete universal neural
networks . . . . . . . . . . . . . . . . 405--416
Olivier Bournez and
Michel Cosnard On the computational power of dynamical
systems and hybrid systems . . . . . . . 417--459
Hava T. Siegelmann The simple dynamics of super Turing
theories . . . . . . . . . . . . . . . . 461--472
Pascal Koiran A family of universal recurrent networks 473--480
Barry Jay and
John Staples Preface . . . . . . . . . . . . . . . . 1--1
M. W. Bunder Lambda terms definable as combinators 3--21
Peter Eades and
Sue Whitesides The logic engine and the realization
problem for nearest neighbor graphs . . 23--37
C. A. Farrell and
D. H. Kieronska Formal specification of parallel SIMD
execution . . . . . . . . . . . . . . . 39--65
Jeremy Gibbons Computing downwards accumulations on
trees quickly . . . . . . . . . . . . . 67--80
Peter Nickolas and
Peter J. Robinson The Qu-Prolog unification algorithm:
Formalisation and correctness . . . . . 81--112
La Monte H. Yarroll See more through lenses than bananas
[recursive data structures] . . . . . . 113--121
Anca Muscholl On the complementation of asynchronous
cellular Buchi automata . . . . . . . . 123--145
Uriel Feige A fast randomized LOGSPACE algorithm for
graph connectivity . . . . . . . . . . . 147--160
Noa Globerman and
David Harel Complexity results for two-way and
multi-pebble automata and their logics 161--184
Jean-Eric Pin Polynomial closure of group languages
and open sets of the Hall topology . . . 185--200
Roberto Di Cosmo and
Delia Kesner Combining algebraic rewriting,
extensional lambda calculi, and
fixpoints . . . . . . . . . . . . . . . 201--220
Y. S. Ramakrishna and
P. M. Melliar-Smith and
L. E. Moser and
L. K. Dillon and
G. Kutty Interval logics and their decision
procedures. Part II: A real-time
interval logic . . . . . . . . . . . . . 1--46
J. F. Groote and
M. P. A. Sellink Confluence for process verification . . 47--81
Mariangiola Dezani-Ciancaglini and
Ugo de'Liguoro and
Adolfo Piperno Filter models for
conjunctive-disjunctive
$\lambda$-calculi . . . . . . . . . . . 83--128
Noriko H. Arai Tractability of cut-free Gentzen type
propositional calculus with permutation
inference . . . . . . . . . . . . . . . 129--144
Mila E. Majster-Cederbaum and
Christel Baier Metric completion versus ideal
completion . . . . . . . . . . . . . . . 145--171
Franco Barbanera and
Maribel Fernández Intersection type assignment systems
with higher-order algebraic rewriting 173--207
Yannis Dimopoulos and
Alberto Torres Graph theoretical structures in logic
programs and default theories . . . . . 209--244
Adel Bouhoula Using induction and rewriting to verify
and complete parameterized
specifications . . . . . . . . . . . . . 245--276
Peter Dybjer Representing inductively defined sets by
wellorderings in Martin-Löf's type theory 245--276
Vladimiro Sassone An axiomatization of the algebra of
Petri net concatenable processes . . . . 277--296
Vladimiro Sassone and
Mogens Nielsen and
Glynn Winskel Models for concurrency: Towards a
classification . . . . . . . . . . . . . 297--348
J. J. M. M. Rutten Elements of generalized ultrametric
domain theory . . . . . . . . . . . . . 349--381
Jia-Huai You and
Robert Cartwright and
Ming Li Iterative belief revision in extended
logic programming . . . . . . . . . . . 383--406
Barnaby P. Hilken Towards a proof theory of rewriting: The
simply typed $2\lambda$-calculus . . . . 407--444
Hsu-Chun Yen and
Shi-Tsuen Jian and
Ta-Pang Lao Deciding bisimulation and trace
equivalences for systems with many
identical processes . . . . . . . . . . 445--464
Anonymous Master Index Volume 161--170 . . . . . . 467
Laks V. S. Lakshmanan Preface . . . . . . . . . . . . . . . . 1--2
Giorgio Ausiello and
Roberto Giaccio On-line algorithms for satisfiability
problems with uncertainty . . . . . . . 3--24
Manolis Koubarakis The complexity of query evaluation in
indefinite temporal constraint databases 25--60
Paul Ruet and
François Fages Combining explicit negation and negation
by failure via Belnap's logic . . . . . 61--75
Bamshad Mobasher and
Don Pigozzi and
Giora Slutzki Multi-valued logic programming
semantics: An algebraic approach . . . . 77--109
A. Nerode and
J. B. Remmel and
V. S. Subrahmanian Annotated nonmonotonic rule systems . . 111--146
Liem Ngo and
Peter Haddawy Answering queries from context-sensitive
probabilistic knowledge bases . . . . . 147--177
Esteban Zimányi Query evaluation in probabilistic
relational databases . . . . . . . . . . 179--219
Jürg Kohlas Allocation of arguments and evidence
theory . . . . . . . . . . . . . . . . . 221--246
Philippe Chatalic and
Christine Froidevaux and
Camilla Schwind Graded hypothesis theories . . . . . . . 247--280
Patrick Bosc and
Didier Dubois and
Olivier Pivert and
Henri Prade Flexible queries in relational databases
--- The example of the division operator 281--302
Anonymous Contents EATCS Bulletin Number 60 . . . 303
Jeff Edmonds Fundamental study: Removing Ramsey
theory: lower bounds with smaller domain
size . . . . . . . . . . . . . . . . . . 1--41
Paul Fischer and
Klaus-Uwe Höffgen and
Hanno Lefmann PAC-learning from general examples . . . 43--65
Isabelle Fagnot Sur les facteurs des mots automatiques.
(French) [On the factors of automatic
words] . . . . . . . . . . . . . . . . . 67--89
B. Apolloni and
S. Chiaravalli PAC learning of concept classes through
the boundaries of their items . . . . . 91--120
Eric Goles and
Maurice Margenstern Universality of the chip-firing game . . 121--134
W. G. Handley Deterministic summation modulo $B_n$,
the semigroup of binary relations on $0,
1, \ldots{}, n-1$ . . . . . . . . . . . 135--174
Goos Kant and
Xin He Regular edge labeling of $4$-connected
plane graphs and its applications in
graph drawing problems . . . . . . . . . 175--193
Klaus Ambos-Spies and
Sebastiaan A. Terwijn and
Xizhong Zheng Resource bounded randomness and weakly
complete problems . . . . . . . . . . . 195--207
Andreas Brandstädt and
Feodor F. Dragan and
Falk Nicolai Homogeneously orderable graphs . . . . . 209--232
Nick D. Dendris and
Lefteris M. Kirousis and
Dimitrios M. Thilikos Fugitive-search games on graphs and
related parameters . . . . . . . . . . . 233--254
Jean-Christophe Hohl Massively parallel factorizations of
polynomials with many non-commuting
variables . . . . . . . . . . . . . . . 255--263
Shinichi Shimozono Finding optimal subgraphs by local
search . . . . . . . . . . . . . . . . . 265--271
Igor Rystsov Reset words for commutative and solvable
automata . . . . . . . . . . . . . . . . 273--279
Costas S. Iliopoulos and
Dennis Moore and
W. F. Smyth A characterization of the squares in a
Fibonacci string . . . . . . . . . . . . 281--291
Petr Savický and
Stanislav \vZák A lower bound on branching programs
reading some bits twice . . . . . . . . 293--301
Günter Rote Finding a shortest vector in a
two-dimensional lattice modulo $m$ . . . 303--308
Hendrik Jan Hoogeboom and
Anca Muscholl The code problem for traces ---
improving the boundaries . . . . . . . . 309--321
Ugo Montanari and
Francesca Rossi Preface . . . . . . . . . . . . . . . . 1--1
Laurent Michel and
Pascal Van Hentenryck Helios: A modeling language for global
optimization and its implementation in
Newton . . . . . . . . . . . . . . . . . 3--48
Nikolaj Bjòrner and
Anca Browne and
Zohar Manna Automatic generation of invariants and
intermediate assertions . . . . . . . . 49--87
Manolis Koubarakis From local to global consistency in
temporal constraint networks . . . . . . 89--112
Michael J. Maher Constrained dependencies . . . . . . . . 113--149
Stéphane Grumbach and
Jianwen Su Queries with arithmetical constraints 151--181
Farid Ajili and
Evelyne Contejean Avoiding slack variables in the solving
of linear Diophantine equations and
inequations . . . . . . . . . . . . . . 183--208
Kim Marriott and
Martin Odersky A confluent calculus for concurrent
constraint programming . . . . . . . . . 209--233
Andreas Podelski and
Gert Smolka Situated simplification . . . . . . . . 235--252
Pierre Girodias and
Eduard Cerny and
William J. Older Solving linear, min and max constraint
systems using CLP based on relational
interval arithmetic . . . . . . . . . . 253--281
Rina Dechter and
Peter van Beek Local and global relational consistency 283--308
Egidio Astesiano Preface . . . . . . . . . . . . . . . . 309--310
Maura Cerioli and
José Meseguer May I borrow your logic? (Transporting
logical structures along maps) . . . . . 311--347
Jean-Pierre Jouannaud and
Mitsuhiro Okada Abstract data type systems . . . . . . . 349--391
Rolf Hennicker and
Martin Wirsing and
Michel Bidoit Proof systems for structured
specifications with observability
operators . . . . . . . . . . . . . . . 393--443
Stefan Kahrs and
Donald Sannella and
Andrzej Tarlecki The definition of Extended ML: A gentle
introduction . . . . . . . . . . . . . . 445--484
Fernando Orejas and
Elvira Pino and
Hartmut Ehrig Institutions for logic programming . . . 485--511
Gerardo Costa and
Gianna Reggio Specification of abstract dynamic-data
types: A temporal logic approach . . . . 513--554
Igor Litovsky and
Ludwig Staiger Finite acceptance of infinite words . . 1--21
Madhav V. Marathe and
Venkatesh Radhakrishnan and
Harry B. Hunt III and
S. S. Ravi Hierarchically specified unit disk
graphs . . . . . . . . . . . . . . . . . 23--65
Felipe Bracho and
Manfred Droste and
Dietrich Kuske Representation of computations in
concurrent automata by dependence orders 67--96
Sanjeev Arora and
Ronald Fagin On winning strategies in
Ehrenfeucht--Fra\"\issé; games . . . . . 97--121
Pekka Orponen Computing with truly asynchronous
threshold logic networks . . . . . . . . 123--136
Matthias Krause and
Pavel Pudlák On the computational power of depth-$2$
circuits with threshold and modulo gates 137--156
Paola Favati and
Grazia Lotti and
Luciano Margara Additive one-dimensional cellular
automata are chaotic according to
Devaney's definition of chaos . . . . . 157--170
Marie-Line Santini-Bouchard Echanges de trois intervalles et suites
minimales. (French) [Exchanges of three
intervals and minimal sequences] . . . . 171--191
Piotr Berman and
Andrzej Lingas A nearly optimal parallel algorithm for
the Voronoi diagram of a convex polygon 193--202
Petr K\ocircurka On topological dynamics of Turing
machines . . . . . . . . . . . . . . . . 203--216
Alain Finkel and
Pierre McKenzie Verifying identical communicating
processes is undecidable . . . . . . . . 217--230
John Mullins On an effective hierarchy of
communicating processes: Separation
principle and testing . . . . . . . . . 231--246
Yõhei Yamasaki Mathematical games. The arithmetic of
reversed positional games . . . . . . . 247--249
Satoshi Kobayashi and
Takashi Yokomori Learning approximately regular languages
with reversible languages . . . . . . . 251--257
Nobuyuki Takahashi Various hierarchies of $\omega$-regular
sets . . . . . . . . . . . . . . . . . . 259--268
P. Turakainen The undecidability of some equivalence
problems concerning ngsm's and finite
substitutions . . . . . . . . . . . . . 269--274
Guo-Qiang Zhang and
Rodney E. Canfield The end of pumping? . . . . . . . . . . 275--279
Anonymous Workshop on Non-Standard Logics and
Logical Aspects of Computer Science . . ??
Hiroakira Ono Foreword . . . . . . . . . . . . . . . . 1--1
Yu. L. Ershov The bounded-complete hull of an
$\alpha$-space . . . . . . . . . . . . . 3--13
N. V. Shilov Program schemata vs. automata for
decidability of program logics . . . . . 15--27
Satoshi Kobayashi Monad as modality . . . . . . . . . . . 29--74
Masahiko Sato Intuitionistic and classical natural
deduction systems with the catch and the
throw rules . . . . . . . . . . . . . . 75--92
J. R. Kennaway and
J. W. Klop and
M. R. Sleep and
F. J. de Vries Infinitary lambda calculus . . . . . . . 93--125
Aart Middeldorp and
Hans Zantema Simple termination of rewrite systems 127--158
Vincent van Oostrom Developing developments [rewriting
system confluence] . . . . . . . . . . . 159--181
Alexei Lisitsa and
Vladimir Sazonov $\Delta$-languages for sets and LOGSPACE
computable graph transformers . . . . . 183--222
Vincent Bouchitté and
Michel Habib and
Michel Morvan Preface . . . . . . . . . . . . . . . . 223--223
Vincent Bouchitté and
Jean-Xavier Rampon On-line algorithms for orders . . . . . 225--238
Frank Bauernöppel and
Evangelos Kranakis and
Danny Krizanc and
Anil Maheshwari and
Jörg-Rüdiger Sack and
Jorge Urrutia Planar stage graphs: Characterizations
and applications . . . . . . . . . . . . 239--255
Oya Ekin and
Peter L. Hammer and
Uri N. Peled Horn functions and submodular Boolean
functions . . . . . . . . . . . . . . . 257--270
Kevin Ewacha and
Ivan Rival and
Nejib Zaguia Approximating the number of linear
extensions . . . . . . . . . . . . . . . 271--282
Stefan Felsner On-line chain partitions of orders . . . 283--292
Colin de la Higuera and
Lhouari Nourine Drawing and encoding two-dimensional
posets . . . . . . . . . . . . . . . . . 293--308
Ton Kloks and
Dieter Kratsch and
Jeremy Spinrad On treewidth and minimum fill-in of
asteroidal triple-free graphs . . . . . 309--335
Jutta Mitas and
Klaus Reuter Cover-preserving embeddings of bipartite
orders into Boolean lattices . . . . . . 337--347
Itsik Pe'er and
Ron Shamir Satisfiability problems on intervals and
unit intervals . . . . . . . . . . . . . 349--372
M. Talamo and
P. Vocca A data structure for lattice
representation . . . . . . . . . . . . . 373--392
Laurent Viennot Parallel $N$-free order recognition . . 393--406
Sue-Hwey Wu and
Scott A. Smolka and
Eugene W. Stark Composition and behaviors of
probabilistic I/O automata . . . . . . . 1--38
G. Chiola and
C. Dutheillet and
G. Franceschinis and
S. Haddad A symbolic reachability graph for
coloured Petri nets . . . . . . . . . . 39--65
Hubert Comon and
Ralf Treinen The first-order theory of lexicographic
path orderings is undecidable . . . . . 67--87
D. N. Hoover Limiting semantics of numerical programs 89--110
Miki Hermann and
Roman Galbavý Unification of infinite sets of terms
schematized by primal grammars . . . . . 111--158
Simone Martini and
Andrea Masini Experiments in linear natural deduction 159--173
Armando B. Matos Monadic logic programs and functional
complexity . . . . . . . . . . . . . . . 175--204
Chrysafis Hartonas Semantics for finite delay . . . . . . . 205--234
Benjamin Pierce and
Martin Steffen Higher-order subtyping . . . . . . . . . 235--282
Dan Suciu Bounded fixpoints for complex objects 283--328
P. Dybjer Representing inductively defined sets by
wellorderings in Martin-Löf's type theory 329--335
Giuseppe Castagna Unifying overloading and $ \lambda
$-abstraction: $\lambda^{\{\}}$ . . . . 337--345
A. Massol Minimality of the system of seven
equations for the category of finite
sets . . . . . . . . . . . . . . . . . . 347--353
Michael W. Mislove and
David A. Schmidt Foreword . . . . . . . . . . . . . . . . 1--1
S. O. Anderson and
A. J. Power A representable approach to finite
nondeterminism . . . . . . . . . . . . . 3--25
Torben Braüner A general adequacy result for a linear
functional language . . . . . . . . . . 27--58
Antonio Bucciarelli Degrees of parallelism in the continuous
type hierarchy . . . . . . . . . . . . . 59--71
J. R. B. Cockett and
David A. Spooner Constructing process categories . . . . 73--109
Bob Flagg and
Ralph Kopperman Continuity spaces: Reconciling domains
and metric spaces . . . . . . . . . . . 111--138
Doris Nolte and
Lutz Priese Abstract fairness and semantics . . . . 139--153
Guo-Qiang Zhang and
William C. Rounds Defaults in domain theory . . . . . . . 155--182
Gray T. Leavens and
Don Pigozzi The behavior--realization adjunction and
generalized homomorphic relations . . . 183--216
Z. Ésik Completeness of Park induction . . . . . 217--283
Alban Ponse and
Chris Verhoef and
Bas van Vlijmen Preface . . . . . . . . . . . . . . . . 285--286
J. L. M. Vrancken The algebra of communicating processes
with empty process . . . . . . . . . . . 287--328
R. J. van Glabbeek Notes on the methodology of CCS and CSP 329--349
Pedro R. D'Argenio and
Chris Verhoef A general conservative extension theorem
in process algebras with inequalities 351--380
J. C. M. Baeten and
J. A. Bergstra Process algebra with propositional
signals . . . . . . . . . . . . . . . . 381--405
Wan Fokkink and
Hans Zantema Termination module equations by abstract
commutation with an application to
iteration . . . . . . . . . . . . . . . 407--423
Jos van Wamel Process algebra with language matching 425--458
Lars-åke Fredlund and
Jan Friso Groote and
Henri Korver Formal verification of a leader election
protocol in process algebra . . . . . . 459--486
Marc Bezem and
Alban Ponse Two finite specifications of a queue . . 487--507
Chia-Hsiang Chang and
Robert Paige From regular expressions to DFA's using
compressed NFA's . . . . . . . . . . . . 1--36
P. Clote Nondeterministic stack register machines 37--76
G. Cattaneo and
C. Quaranta Vogliotti The ``magic'' rule spaces of neural-like
elementary cellular automata . . . . . . 77--102
M. D. Atkinson and
M. J. Livesey and
D. Tulley Permutations generated by token passing
in graphs . . . . . . . . . . . . . . . 103--118
A. Munier and
C. Hanen Using duplication for scheduling unitary
tasks on m processors with unit
communication delays . . . . . . . . . . 119--127
Gregory Kucherov and
Michaël Rusinowitch Matching a set of strings with variable
length don't cares . . . . . . . . . . . 129--154
Martin Strauss Normal numbers and sources for BPP . . . 155--169
Jean Berstel and
Aldo de Luca Sturmian words, Lyndon words and trees 171--203
Aldo de Luca Standard Sturmian morphisms . . . . . . 205--224
Peter Damaschke An optimal parallel algorithm for
digital curve segmentation . . . . . . . 225--236
A. Browne and
E. M. Clarke and
S. Jha and
D. E. Long and
W. Marrero An improved algorithm for the evaluation
of fixpoint expressions . . . . . . . . 237--255
Peter M. Higgins A proof of Simon's theorem on piecewise
testable languages . . . . . . . . . . . 257--264
Y. Kopidakis and
V. Zissimopoulos An approximation scheme for scheduling
independent jobs into subcubes of a
hypercube of fixed dimension . . . . . . 265--273
Michel Latteux and
David Simplot Recognizable picture languages and
domino tiling . . . . . . . . . . . . . 275--283
Stephen L. Bloom and
Zoltán Ésik The equational logic of fixed points . . 1--60
N. W. Keesmaat and
H. C. M. Kleijn Restrictions and representations of
vector controlled concurrent system
behaviours . . . . . . . . . . . . . . . 61--102
Henk Doornbos and
Roland Backhouse and
Jaap van der Woude A calculational approach to mathematical
induction . . . . . . . . . . . . . . . 103--135
Chantal Berline and
Klaus Grue A $\kappa$-denotational semantics for
map theory in ZFC $+$ SI . . . . . . . . 137--202
Ilaria Castellani and
Guo-Qiang Zhang Parallel product of event structures . . 203--215
Christel Baier Trees and semantics . . . . . . . . . . 217--250
Jozef Gruska and
Angelo Monti and
Margherita Napoli and
Domenico Parente Succinctness of descriptions of
SBTA-languages . . . . . . . . . . . . . 251--271
Suad Alagi\'c and
Mara Alagi\'c Order-sorted model theory for temporal
executable specifications . . . . . . . 273--299
Hsu-Chun Yen On reachability equivalence for BPP-nets 301--317
Inger Sigstam and
Viggo Stoltenberg-Hansen Representability of locally compact
regular spaces by domains and formal
spaces . . . . . . . . . . . . . . . . . 319--331
Leslie Lamport Processes are in the eye of the beholder 333--351
Yuri Gurevich and
James K. Huggins Equivalence is in the eye of the
beholder . . . . . . . . . . . . . . . . 353--380
Oscar H. Ibarra and
Nicholas Q. Tran and
Tao Yang On the parallel complexity of loops . . 381--395
Jaana Eloranta and
Martti Tienari and
Antti Valmari Essential transitions to bisimulation
equivalences . . . . . . . . . . . . . . 397--419
Jürgen Koslowski Note on free algebras over continuous
domains . . . . . . . . . . . . . . . . 421--425
Ivo Düntsch A logic for rough sets . . . . . . . . . 427--436
Marina Madonia and
Stefano Varricchio Some decisional problems on rational
relations . . . . . . . . . . . . . . . 1--15
V. Arvind and
N. V. Vinodchandran Solvable black-box group problems are
low for PP . . . . . . . . . . . . . . . 17--45
K. Hosaka and
Y. Takenaga and
T. Kaneda and
S. Yajima Size of ordered binary decision diagrams
representing threshold functions . . . . 47--60
Frédérique Bassino Nonnegative companion matrices and
star-height of N-rational series . . . . 61--80
E. Garel Séparateurs dans les mots infinis
engendrés par morphismes. (French)
[Separators in infinite words generated
by morphisms] . . . . . . . . . . . . . 81--113
Marie-France Sagot and
Alain Viari and
Henri Soldano Multiple sequence comparison --- A
peptide matching approach . . . . . . . 115--137
Hiroaki Yamamoto On the power of alternation on
reversal-bounded alternating Turing
machines with a restriction . . . . . . 139--154
Zhixiang Chen and
Steven Homer Learning counting functions with queries 155--168
Hong Shen and
Weifa Liang Efficient enumeration of all minimal
separators in a graph . . . . . . . . . 169--180
Carl Pomerance and
John Michael Robson and
Jeffrey Shallit Automaticity II: Descriptional
complexity in the unary case . . . . . . 181--201
Vitus J. Leung The undecidability of the unrestricted
modified edit distance . . . . . . . . . 203--215
D. Grigoriev Testing shift-equivalence of polynomials
by deterministic, probabilistic and
quantum machines . . . . . . . . . . . . 217--228
Martín Matamala Alternation on cellular automata . . . . 229--241
Alexander E. Andreev and
Andrea E. F. Clementi and
José D. P. Rolim Optimal bounds for the approximation of
Boolean functions and some applications 243--268
Vassilis Giakoumakis and
Jean-Marie Vanherpe On extended $P_4$-reducible and extended
$P_4$-sparse graphs . . . . . . . . . . 269--286
Bruno Codenotti and
Biswa N. Datta and
Karabi Datta and
Mauro Leoncini Parallel algorithms for certain matrix
computations . . . . . . . . . . . . . . 287--308
Marek Karpinski and
Lawrence L. Larmore and
Wojciech Rytter Correctness of constructing optimal
alphabetic trees revisited . . . . . . . 309--324
Pierre Péladeau and
Howard Straubing and
Denis Thérien Finite semigroup varieties defined by
programs . . . . . . . . . . . . . . . . 325--339
Manfred Kudlek and
Alexandru Mateescu On distributed catenation . . . . . . . 341--352
Jürgen Dassow and
Victor Mitrana Cooperation in context-free grammars . . 353--361
Víctor F. Sirvent On some dynamical subsets of the Rauzy
fractal . . . . . . . . . . . . . . . . 363--370
René David and
Karim Nour A syntactical proof of the operational
equivalence of two $\lambda$-terms . . . 371--375
Anonymous Master index volumes 171-180 . . . . . . 379
Ricardo Baeza-Yates and
Eric Goles Preface . . . . . . . . . . . . . . . . 1--2
Tetsuo Asano and
Desh Ranjan and
Thomas Roos and
Emo Welzl and
Peter Widmayer Space-filling curves and their use in
the design of geometric data structures 3--15
Véronique Bruy\`ere and
Georges Hansel Bertrand numeration systems and
recognizability . . . . . . . . . . . . 17--43
Shiva Chaudhuri and
Devdatt Dubhashi Probabilistic recurrence relations
revisited . . . . . . . . . . . . . . . 45--56
David Fernández-Baca and
Giora Slutzki Linear-time algorithms for parametric
minimum spanning tree problems on planar
graphs . . . . . . . . . . . . . . . . . 57--74
Esteban Feuerstein Paging more than one page . . . . . . . 75--90
Celina M. H. de Figueiredo and
João Meidanis and
Célia Picinin de Mello On edge-colouring indifference graphs 91--106
Giulia Galbiati and
Angelo Morzenti and
Francesco Maffioli On the approximability of some Maximum
Spanning Tree Problems . . . . . . . . . 107--118
William I. Gasarch and
Katia S. Guimarães Binary search and recursive graph
problems . . . . . . . . . . . . . . . . 119--139
Christian Herzog Pushdown automata with bounded
nondeterminism and bounded ambiguity . . 141--157
Daniel Lopresti and
Andrew Tomkins Block edit models for approximate string
matching . . . . . . . . . . . . . . . . 159--179
Helmut Prodinger On a problem of Yekutieli and Mandelbrot
about the bifurcation ratio of binary
trees . . . . . . . . . . . . . . . . . 181--194
Farn Wang A temporal logic for real-time partial
ordering with named transactions . . . . 195--225
Dingzhu Du and
Ming Li Foreword . . . . . . . . . . . . . . . . 227--227
Jay Belanger and
Jie Wang No NP problems averaging over ranking of
distributions are harder . . . . . . . . 229--245
Jianer Chen Algorithmic graph embeddings . . . . . . 247--266
Josep Díaz and
Alan Gibbons and
Grammati E. Pantziou and
Maria J. Serna and
Paul G. Spirakis and
Jacobo Toran Parallel algorithms for the minimum cut
and the minimum length tree layout
problems . . . . . . . . . . . . . . . . 267--287
Kojiro Kobayashi Transformations that preserve malignness
of universal distributions . . . . . . . 289--306
Andrzej Lingas Maximum tree-packing in time $O(n^5/2)$ 307--316
Kouichi Sakurai Practical proofs of knowledge without
relying on theoretical proofs of
membership on languages . . . . . . . . 317--335
John Tromp and
Louxin Zhang and
Ying Zhao Small weight bases for Hamming codes . . 337--345
Peng-Jun Wan and
Qifan Yang and
Dean Kelley A $(3/2) \log 3$-competitive algorithm
for the counterfeit coin problem . . . . 347--356
Xiangdong Yu and
Moti Yung Scheduling task-trees with additive
scales on parallel/distributed machines 357--378
S. O. Krumke and
M. V. Marathe and
H. Noltemeier and
V. Radhakrishnan and
S. S. Ravi and
D. J. Rosenkrantz Compact location problems . . . . . . . 379--404
Zbigniew J. Czech and
George Havas and
Bohdan S. Majewski Perfect hashing . . . . . . . . . . . . 1--143
M. D. Atkinson and
D. Tulley Bounded capacity priority queues . . . . 145--157
James Abello and
Shlomi Dolev On the computational power of
self-stabilizing systems . . . . . . . . 159--170
B. Gao and
F. K. Hwang Wide-sense nonblocking for multirate
$3$-stage Clos networks . . . . . . . . 171--182
Marco Cadoli and
Francesco M. Donini and
Marco Schaerf and
Riccardo Silvestri On compact representations of
propositional circumscription . . . . . 183--202
Ger Koole Assigning a single server to
inhomogeneous queues with switching
costs . . . . . . . . . . . . . . . . . 203--216
Daniele Mundici and
Alberto Trombetta Optimal comparison strategies in Ulam's
searching game with two errors . . . . . 217--232
Vineet Bafna and
Eugene L. Lawler and
Pavel A. Pevzner Approximation algorithms for multiple
sequence alignment . . . . . . . . . . . 233--244
Nguyen Huong Lam Hajós factorizations and completion of
codes . . . . . . . . . . . . . . . . . 245--256
Fernanda Botelho and
Max Garzon Erratum to ``Boolean neural nets are
observable'' [Theoret. Comput. Sci. 134
(1994) 51--61] . . . . . . . . . . . . . 257--257
Anonymous Contents EATCS Bulletin Number 61 . . . 259
Anonymous Contents EATCS Bulletin Number 62 . . . 263
G. Rozenberg and
A. Salomaa Contributions . . . . . . . . . . . . . 1
Grzegorz Rozenberg and
Arto Salomaa Preface . . . . . . . . . . . . . . . . 1--1
Masami Ito and
Lila Kari and
Gabriel Thierrin Insertion and deletion closure of
languages . . . . . . . . . . . . . . . 3--19
Danny Raz Length considerations in context-free
languages . . . . . . . . . . . . . . . 21--32
Lucian Ilie On computational complexity of
contextual languages . . . . . . . . . . 33--44
Aldo de Luca Sturmian words: Structure,
combinatorics, and their arithmetics . . 45--82
C. Choffrut and
T. Harju and
J. Karhumäki A note on decidability questions on
presentations of word semigroups . . . . 83--92
Oded Maler and
Ludwig Staiger On syntactic congruences for
$\omega$-languages . . . . . . . . . . . 93--112
Juha Honkala and
Werner Kuich On Lindenmayerian algebraic power series 113--142
Juha Honkala On Lindenmayerian algebraic sequences 143--154
V. S. Alagar Foreword . . . . . . . . . . . . . . . . 155--156
Anne Elisabeth Haxthausen Order-sorted algebraic specifications
with higher-order functions . . . . . . 157--185
Angelo Montanari and
Maarten de Rijke Two-sorted metric temporal logics . . . 187--214
Mads Dam On the decidability of process
equivalences for the pi--- calculus . . 215--228
Allan Cheng Petri nets, traces, and local model
checking . . . . . . . . . . . . . . . . 229--251
Pierre Collette and
Edgar Knapp A foundation for modular reasoning about
safety and progress properties of
state-based concurrent programs . . . . 253--279
Moreno Falaschi and
Maurizio Gabbrielli and
Kim Marriott and
Catuscia Palamidessi Confluence in concurrent constraint
programming . . . . . . . . . . . . . . 281--315
Antonio Brogi and
Evelina Lamma and
Paolo Mancarella and
Paola Mello A unifying view for logic programming
with non-monotonic reasoning . . . . . . 1--59
Kim Ritter Wagner Liminf convergence in
$\Omega$-categories . . . . . . . . . . 61--104
James Andrews A logical semantics for depth-first
Prolog with ground negation . . . . . . 105--143
P. Burmeister and
F. Rossello and
J. Torrens and
G. Valiente Algebraic transformation of unary
partial algebras. I. Double-pushout
approach . . . . . . . . . . . . . . . . 145--193
Jianwen Su Dynamic constraints and object migration 195--236
Thierry Lacoste $0$--$1$ laws by preservation . . . . . 237--245
Benjamin Pierce and
Martin Steffen Corrigendum to ``Higher-order
subtyping'' [Theoret. Comput. Sci.
176(1--2) (1997) 235--282] . . . . . . . 247--247
Thomas Zeugmann Foreword . . . . . . . . . . . . . . . . 1--1
John Kececioglu and
Ming Li and
John Tromp Inferring a DNA sequence from erroneous
copies . . . . . . . . . . . . . . . . . 3--13
Yasubumi Sakakibara Recent advances of grammatical inference 15--45
Hiroki Arimura and
Hiroki Ishizaka and
Takeshi Shinohara Learning unions of tree patterns using
queries . . . . . . . . . . . . . . . . 47--62
Takeshi Koshiba and
Erkki Mäkinen and
Yuji Takada Learning deterministic even linear
languages from positive examples . . . . 63--79
Léa Meyer Probabilistic language learning under
monotonicity constraints . . . . . . . . 81--128
Frank Stephan Noisy inference and oracles . . . . . . 129--157
Peter Auer Learning nested differences in the
presence of malicious noise . . . . . . 159--175
Eiji Takimoto and
Akira Miyashiro and
Akira Maruoka and
Yoshifumi Sakai Learning orthogonal $F$-Horn formulas 177--190
M. R. K. Krishna Rao A framework for incremental learning of
logic programs . . . . . . . . . . . . . 191--213
John Staples Preface . . . . . . . . . . . . . . . . 215--215
David Albrecht and
John N. Crossley and
John S. Jeavons New Curry--Howard terms for full linear
logic . . . . . . . . . . . . . . . . . 217--235
C. Barry Jay Covariant types . . . . . . . . . . . . 237--258
Xuemin Lin A fully distributed quorum consensus
method with high fault-tolerance and low
communication overhead . . . . . . . . . 259--275
Ian A. Mason A first order logic of effects . . . . . 277--318
Mehmet A. Orgun and
Weichang Du Multi-dimensional logic programming:
Theoretical foundations . . . . . . . . 319--345
Grammati E. Pantziou and
Alan Roberts and
Antonios Symvonis Many-to-many routing on trees via
matchings . . . . . . . . . . . . . . . 347--377
Millist W. Vincent A corrected 5NF definition for
relational database design . . . . . . . 379--391
Trudy Weibel An order-sorted resolution in theory and
practice . . . . . . . . . . . . . . . . 393--410
Anonymous Author index volume 185 . . . . . . . . 411
Rémy Malgouyres A definition of surfaces of $Z^3$: a new
$3$D discrete Jordan theorem . . . . . . 1--41
Gabriele Taentzer Parallel high-level replacement systems 43--81
Ernst L. Leiss Solving systems of explicit language
relations . . . . . . . . . . . . . . . 83--105
Eric Badouel and
Luca Bernardinello and
Philippe Darondeau The synthesis problem for elementary net
systems is NP-complete . . . . . . . . . 107--134
Doron Peled On projective and separable properties 135--156
Changwook Kim A hierarchy of eNCE families of graph
languages . . . . . . . . . . . . . . . 157--169
Michele Flammini and
Giorgio Gambosi On devising Boolean Routing Schemes . . 171--198
Yehuda Afek and
Shay Kutten and
Moti Yung The local detection paradigm and its
applications to self-stabilization . . . 199--230
Enno Ohlebusch and
Esko Ukkonen On the equivalence problem for E-pattern
languages . . . . . . . . . . . . . . . 231--248
Anonymous Computer Algebra. 5th Rhine Workshop
(RWCA) . . . . . . . . . . . . . . . . . ??
Jacques Calmet and
Alain Carri\`ere Foreword . . . . . . . . . . . . . . . . 1--1
Willi Geiselman and
Felix Ulmer Constructing a third-order linear
differential equation . . . . . . . . . 3--6
Evelyne Hubert Detecting degenerate behaviors in first
order algebraic differential equations 7--25
Winfried Fakler On second order homogeneous linear
differential equations with Liouvillian
solutions . . . . . . . . . . . . . . . 27--48
G. Thomas The problem of defining the singular
points of quasi-linear
differential-algebraic systems . . . . . 49--79
E. Pflügel On the latest version of DESIR-II . . . 81--86
Christian Scheen Implementation of the Painlevé test for
ordinary differential systems . . . . . 87--104
Laurent Bernardin On square-free factorization of
multivariate polynomials over a finite
field . . . . . . . . . . . . . . . . . 105--116
W. A. de Graaf An algorithm for the decomposition of
semisimple Lie algebras . . . . . . . . 117--122
Abdenacer Makhlouf Alg\`ebres associatives et calcul
formel. (French) [Associative algebras
and computer algebra] . . . . . . . . . 123--145
Christoph Zenger Indexed types . . . . . . . . . . . . . 147--165
Daniel Mall Covers and fans of polynomial ideals . . 167--178
Beatrice Amrhein and
Oliver Gloor and
Wolfgang Küchlin On the Walk . . . . . . . . . . . . . . 179--202
Jerzy Karczmarczuk Generating power of lazy semantics . . . 203--219
Jacques Calmet and
Karsten Homann Towards the Mathematics Software Bus . . 221--230
Jo\vze Korelc Automatic generation of finite-element
code by simultaneous optimization of
expressions . . . . . . . . . . . . . . 231--248
A. El Hamidi and
M. Garbey Using MAPLE for the analysis of
bifurcation phenomena in gas combustion 249--262
Alain Carri\`ere and
Louis-Rémi Oudin Applications du calcul formel \`a la
balistique. (French) [Applications of
formal calculus to ballistics] . . . . . 263--284
S. V. Nagaraj Optimal binary search trees . . . . . . 1--44
Olivier Heen Linear speed-up for cellular automata
synchronizers and applications . . . . . 45--57
Sandeep Sen Lower bounds for parallel algebraic
decision trees: parallel complexity of
convex hulls and related problems . . . 59--78
Kathleen Romanik Approximate testing and its relationship
to learning . . . . . . . . . . . . . . 79--99
Kenneth W. Regan and
Heribert Vollmer Gap-languages and log-time complexity
classes . . . . . . . . . . . . . . . . 101--116
Vince Grolmusz On the power of circuits with gates of
low $L_1$ norms . . . . . . . . . . . . 117--128
Eric Goles and
Iván Rapaport Complexity of tile rotation problems . . 129--159
Anton \vCerný On sequences resulting from iteration of
modified quadratic and palindromic
mappings . . . . . . . . . . . . . . . . 161--174
R\=usin\c\vs Freivalds and
Sanjay Jain Kolmogorov numberings and minimal
identification . . . . . . . . . . . . . 175--194
J.-P. Allouche and
F. von Haeseler and
H.-O. Peitgen and
A. Petersen and
G. Skordev Automaticity of double sequences
generated by one-dimensional linear
cellular automata . . . . . . . . . . . 195--209
Viktor Gyuris A short proof of representability of
fork algebras . . . . . . . . . . . . . 211--220
Hong Shen Optimal algorithms for generalized
searching in sorted matrices . . . . . . 221--230
Dong Yang Long and
Jian Ma and
Duanning Zhou Structure of $3$-infix--outfix maximal
codes . . . . . . . . . . . . . . . . . 231--240
Renren Liu An improved Shellsort algorithm . . . . 241--247
Damian Niwi\'nski Fixed point characterization of infinite
behavior of finite-state systems . . . . 1--69
Luc Bougé and
David Cachera and
Yann Le Guyadec and
Gil Utard and
Bernard Virot Formal validation of data-parallel
programs: a two-component assertional
proof system for a simple language . . . 71--107
Hans-Dieter Burkhard Fairness and control in multi-agent
systems . . . . . . . . . . . . . . . . 109--127
Thomas Eiter and
Georg Gottlob and
Nicola Leone Abduction from logic programs: semantics
and complexity . . . . . . . . . . . . . 129--177
Patrice Brémond-Grégoire and
Insup Lee A process algebra of communicating
shared resources with dense time and
priorities . . . . . . . . . . . . . . . 179--219
Mohamed Mezghiche $c\beta$-Machine with
$\lambda\beta$-reduction . . . . . . . . 221--228
Anne Bergeron On the rational behaviors of concurrent
timers . . . . . . . . . . . . . . . . . 229--237
Serafino Cicerone and
Francesco Parisi-Presicce On the complexity of specification
morphisms . . . . . . . . . . . . . . . 239--248
H. Kirchner Editorial . . . . . . . . . . . . . . . 1--2
Maribel Fernández and
Ian Mackie Interaction nets and term-rewriting
systems . . . . . . . . . . . . . . . . 3--39
Roope Kaivola Axiomatising extended computation tree
logic . . . . . . . . . . . . . . . . . 41--60
Björn Lisper Computing in unpredictable environments:
semantics, reduction strategies, and
program transformations . . . . . . . . 61--85
Allan Cheng and
Mogens Nielsen Open maps, behavioural equivalences, and
congruences . . . . . . . . . . . . . . 87--112
G. Gottlob and
M. Y. Vardi Foreword . . . . . . . . . . . . . . . . 113
N. Bidoit and
S. De Amo A first step towards implementing
dynamic algebraic dependences . . . . . 115--149
J. Demetrovics and
G. O. H. Katona and
D. Miklos and
O. Seleznjev and
B. Thalheim Asymptotic properties of keys and
functional dependencies in random
databases . . . . . . . . . . . . . . . 151--166
Leonid Libkin Models of approximation in databases . . 167--210
Sérgio Lifschitz and
Victor Vianu A probabilistic view of Datalog
parallelization . . . . . . . . . . . . 211--239
Victor W. Marek and
Miroslaw Truszczy\'nski Revision programming . . . . . . . . . . 241--277
Dan Suciu Domain-independent queries on databases
with external functions . . . . . . . . 279--315
Jerzy Tyszkiewicz The Kolmogorov expressive power of
Boolean query languages . . . . . . . . 317--361
R. Vingralek and
H. Hasse-Ye and
Y. Breitbart and
H.-J. Schek Unifying concurrency control and
recovery of transactions with
semantically rich operations . . . . . . 363--396
Patrice Naudin and
Claude Quitté Univariate polynomial factorization over
finite fields . . . . . . . . . . . . . 1--36
Victor Selivanov Fine hierarchy of regular
$\omega$-languages . . . . . . . . . . . 37--59
Christiane Frougny and
Jacques Sakarovitch Synchronisation deterministe des
automates \`a delai borné. (French)
[Synchronisation of deterministic
automata with bounded delay] . . . . . . 61--77
Douadi Mihoubi Characterization and closure properties
of linear $\omega$-languages . . . . . . 79--95
Rodney G. Downey and
Michael R. Fellows and
Kenneth W. Regan Parameterized circuit complexity and the
W hierarchy . . . . . . . . . . . . . . 97--115
Véronique Bruy\`ere and
Denis Derencourt and
Michel Latteux The meet operation in the lattice of
codes . . . . . . . . . . . . . . . . . 117--129
Dany Breslauer The suffix tree of a tree and minimizing
sequential transducers . . . . . . . . . 131--144
Antoni Ko\'scielski and
Leszek Pacholski Makanin's algorithm is not primitive
recursive . . . . . . . . . . . . . . . 145--156
Thomas S. Ferguson Some chip transfer games . . . . . . . . 157--171
Valtteri Niemi and
Ari Renvall Secure multiparty computations without
computers . . . . . . . . . . . . . . . 173--183
Steven M. Kautz An improved zero-one law for
algorithmically random sequences . . . . 185--192
Gerd Eriksson and
Henrik Eriksson and
Kimmo Eriksson Moving a food trolley around a corner 193--203
Martin Middendorf Shortest common superstrings and
scheduling with coordinated starting
times . . . . . . . . . . . . . . . . . 205--214
Oded Goldreich and
Bernd Meyer Computational indistinguishability:
algorithms vs. circuits . . . . . . . . 215--218
Jing Wang Finite derivation type for semi-direct
products of monoids . . . . . . . . . . 219--228
E. Angel and
V. Zissimopoulos Autocorrelation coefficient for the
graph bipartitioning problem . . . . . . 229--243
Richard Beigel and
Bill Gasarch and
Ming Li and
Louxin Zhang Addition in $\log_2 n + {\rm O}(1)$
steps on average: A simple analysis . . 245--248
Jieh Hsiang Foreword . . . . . . . . . . . . . . . . 1--1
Richard Mayr and
Tobias Nipkow Higher-order rewrite systems and their
confluence . . . . . . . . . . . . . . . 3--29
Massimo Marchiori Bubbles in modularity . . . . . . . . . 31--54
Géraud Sénizergues A polynomial algorithm testing partial
confluence of basic semi-Thue systems 55--75
Siva Anantharaman and
Gilles Richard A rewrite mechanism for logic programs
with negation . . . . . . . . . . . . . 77--106
Franz Baader and
Klaus U. Schulz Combination of constraint solvers for
free and quasi-free structures . . . . . 107--161
R. Gorrieri and
C. Hankin Foreword . . . . . . . . . . . . . . . . 163
Nadia Busi and
Roberto Gorrieri and
Gianluigi Zavattaro A process algebraic view of Linda
coordination primitives . . . . . . . . 167--199
Laurent Dami A lambda-calculus for dynamic binding 201--231
Chris Hankin and
Daniel Le Métayer and
David Sands Refining multiset transformers . . . . . 233--258
Luís Monteiro and
António Porto Entailment-based actions for
coordination . . . . . . . . . . . . . . 259--286
Manibrata Mukherji and
Dennis Kafura A process-calculus-based abstraction for
coordinating multi-agent groups . . . . 287--314
Peter Wegner Interactive foundations of computing . . 315--351
M. M. Bonsangue and
F. van Breugel and
J. J. M. M. Rutten Generalized metric spaces: completion,
topology, and power domains via the
Yoneda embedding . . . . . . . . . . . . 1--51
Abbas Edalat and
Reinhold Heckmann A computational model for metric spaces 53--73
Giorgio Ghelli and
Benjamin Pierce Bounded existentials and minimal typing 75--96
Yoshifumi Manabe and
Roberto Baldoni and
Michel Raynal and
Shigemi Aoyagi $k$-Arbiter: A safe and general scheme
for $h$-out of-$k$ mutual exclusion . . 97--112
Fabio Alessi and
Paolo Baldan A characterization of distance between
$1$-bounded compact ultrametric spaces
through a universal space . . . . . . . 113--127
Henri-Alex Esbelin and
Malika More Rudimentary relations and primitive
recursion: A toolbox . . . . . . . . . . 129--148
Kenneth A. Ross and
Divesh Srivastava and
Peter J. Stuckey and
S. Sudarshan Foundations of aggregation constraints 149--179
Thomas Drakengren A decidable canonical representation of
the compact elements in Scott's
reflexive domain in $P \omega$ . . . . . 181--195
A. Rabinovich On translations of temporal logic of
actions into monadic second-order logic 197--214
Marco Cadoli and
Luigi Palopoli Circumscribing DATALOG: expressive power
and complexity . . . . . . . . . . . . . 215--244
Anonymous Joint COMPUGRAPH/SEMAGRAPH Workshop on
Graph Rewriting and Computation
(SEGRAGRA '95) (papers in summary form
only received) . . . . . . . . . . . . . ??
Philippe Flajolet and
Brigitte Vallée Continued fraction algorithms,
functional operators, and structure
constants . . . . . . . . . . . . . . . 1--34
Henning Fernau and
Dietmar Wätjen Remarks on regulated limited ET$0$L
systems and regulated context-free
grammars . . . . . . . . . . . . . . . . 35--55
G. Dányi and
Z. Fülöp Compositions with superlinear
deterministic top-down tree
transformations . . . . . . . . . . . . 57--85
Pál Gyenizse and
Sándor Vágvölgyi Linear generalized semi-monadic rewrite
systems effectively preserve
recognizability . . . . . . . . . . . . 87--122
Peng-Jun Wan TWDM multichannel lightwave hypercube
networks . . . . . . . . . . . . . . . . 123--136
Rolf Niedermeier and
Peter Rossmanith Unambiguous computations and locally
definable acceptance types . . . . . . . 137--161
Sandy Irani and
Steve Seiden Randomized algorithms for metrical task
systems . . . . . . . . . . . . . . . . 163--182
Anatoli N. Chebotarev and
Marina K. Morokhovets Resolution-based approach to
compatibility analysis of interacting
automata . . . . . . . . . . . . . . . . 183--205
Malika Hadjiat Penelope's graph: a hard minimum cost
tension instance . . . . . . . . . . . . 207--218
Corine Ceola and
Pierre B. A. Lecomte Computability of a map and decidability
of its graph in the model of Blum, Shub
and Smale . . . . . . . . . . . . . . . 219--223
Pierre Fraigniaud On XRAM and PRAM models, and on
data-movement-intensive problems . . . . 225--237
R. Banach DPO rewriting and abstract semantics via
opfibrations . . . . . . . . . . . . . . 240
E. Barendsen and
S. Smetsers A derivation system for uniqueness
typing . . . . . . . . . . . . . . . . . 240
M. Bauderon Parallel rewriting of graphs through the
pullback approach . . . . . . . . . . . 240
E. Best and
M. Koutny Using net refinement to compute the
fixpoint of a recursive expression . . . 241
S. Brock and
G. Ostheimer A process semantics for functional
programming . . . . . . . . . . . . . . 241
D. Clark and
R. Kennaway Some properties of non-orthogonal term
graph rewriting systems . . . . . . . . 241
A. Corradini and
R. Heckel A compositional approach to structuring
and refinement of typed graph grammars 241
A. Corradini Concurrent computing: from Petri nets to
graph grammars . . . . . . . . . . . . . 241--242
B. Courcelle Logic and graphs . . . . . . . . . . . . 242
A. Drappa and
R. Melchisedech The use of graph grammar in a software
engineering education tool . . . . . . . 242
F. Drewes Semirings and tree-to-graph-to-tree
transductions . . . . . . . . . . . . . 242
H. Ehrig Introduction to COMPUGRAPH . . . . . . . 242--243
G. Engels and
A. Schurr Encapsulated hierarchical graphs, graph
types, and meta types . . . . . . . . . 243
A. Habel and
D. Plump Unification, rewriting, and narrowing on
term graphs . . . . . . . . . . . . . . 243
R. Heckel and
A. Wagner Ensuring consistency of conditional
graph rewriting --- a constructive
approach . . . . . . . . . . . . . . . . 243
P. Heimann and
G. Joeris and
C.-A. Krapp and
B. Westfechtel A programmed graph rewriting system for
software process management . . . . . . 243--244
D. Janssens Process languages for ESM systems . . . 244
T. Johnsson Graph reduction, and how to avoid it . . 244
R. Kennaway Infinitary rewriting and cyclic graphs 244
Z. Khasidashvili and
V. Van Oostrom Context-sensitive conditional expression
reductions systems . . . . . . . . . . . 244
M. Korff and
L. Ribeiro Concurrent derivations as single pushout
graph grammar processes . . . . . . . . 245
H.-J. Kreowski Specification and programming (by graph
transformation) . . . . . . . . . . . . 245
S. Kuske Implementing beta-reduction by
hypergraph rewriting . . . . . . . . . . 245
I. Litovsky and
Y. Metivier and
E. Sopena Checking global graph properties by
means of local computations: the
majority problem . . . . . . . . . . . . 245--246
M. Monserrat and
F. Rossello and
J. Torrens and
G. Valiente Hypergraph rewriting using conformisms 246
M. J. Plasmeijer CLEAN: a programming environment based
on term graph rewriting . . . . . . . . 246
Y.-M. Quemener and
T. Jeron Model-checking of infinite Kripke
structures defined by simple graph
grammars . . . . . . . . . . . . . . . . 246
G. Schied and
K. Barthelmann Linear types for higher order processes
with first class directed channels . . . 246--247
H. J. Schneider A note on outward and inward productions
in the categorical graph-grammar
approach and Delta-grammars . . . . . . 247
D. Seese Linear time computable problems and
logical descriptions . . . . . . . . . . 247
D. Shand and
S. Brock Proofs as graphs . . . . . . . . . . . . 247
R. Sleep SEMAGRAPH: the theory and practice of
term graph rewriting . . . . . . . . . . 248
G. Taentzer and
A. Schurr DIEGO, another step towards a module
concept for graph transformation systems 248
C. Wadsworth Graph reduction: a retrospective . . . . 248
Wojciech Penczek Foreword . . . . . . . . . . . . . . . . 1--1
Arie de Bruin and
Shan-Hwei Nienhuys-Cheng Linear dynamic Kahn networks are
deterministic . . . . . . . . . . . . . 3--32
Stéphane Demri A class of decidable information logics 33--60
Z. Ésik and
A. Labella Equational properties of iteration in
algebraically complete categories . . . 61--89
Patrice Séébold On the conjugation of standard morphisms 91--109
C. Stirling Decidability of bisimulation equivalence
for normed pushdown processes . . . . . 113--131
J. C. Bradfield The modal mu-calculus alternation
hierarchy is strict . . . . . . . . . . 133--153
A. M. Pitts and
J. R. X. Ross Process calculus based upon evaluation
to committed form . . . . . . . . . . . 155--182
D. Peled and
T. Wilke and
P. Wolper An algorithmic approach for checking
closure properties of temporal logic
specifications and $\omega$-regular
languages . . . . . . . . . . . . . . . 183--203
M. Boreale On the expressiveness of internal
mobility in name-passing calculi . . . . 205--226
R. Cleaveland and
G. Luttgen and
V. Natarajan A process algebra with distributed
priorities . . . . . . . . . . . . . . . 227--258
A. Philippou and
D. Walker On transformations of concurrent-object
programs . . . . . . . . . . . . . . . . 259--289
R. M. Amadio and
I. Castellani and
D. Sangiorgi On bisimulations for the asynchronous
pi-calculus . . . . . . . . . . . . . . 291--324
Luc Bougé and
Pierre Fraigniaud Editorial . . . . . . . . . . . . . . . 1--1
P. B. Gibbons and
Y. Matias and
V. Ramachandran The queue-read queue-write asynchronous
PRAM model . . . . . . . . . . . . . . . 3--29
L. Colombet and
L. Desbat Speedup and efficiency of large-size
applications on heterogeneous networks 31--44
Ajay D. Kshemkalyani A framework for viewing atomic events in
distributed computations . . . . . . . . 45--70
George Hora\ctiu Botorog and
Herbert Kuchen Efficient high-level parallel
programming . . . . . . . . . . . . . . 71--107
Alexandre Tiskin The bulk-synchronous parallel random
access machine . . . . . . . . . . . . . 109--130
Miriam Di Ianni Efficient delay routing . . . . . . . . 131--151
Miriam Di Ianni Efficient delay routing . . . . . . . . 131--151
Philip D. MacKenzie and
Vijaya Ramachandran ERCW PRAMs and optical communication . . 153--180
Friedhelm Meyer auf der Heide and
Klaus Schröder and
Frank Schwarze Routing on networks of optical crossbars 181--200
Stuart F. Oberman and
Michael J. Flynn Reducing the mean latency of
floating-point addition . . . . . . . . 201--214
Axel Podehl and
Thomas Rauber and
Gudula Rünger A shared-memory implementation of the
hierarchical radiosity method . . . . . 215--240
Jeffrey K. Hollingsworth and
Barton P. Miller Using cost to control instrumentation
overhead . . . . . . . . . . . . . . . . 241--258
Cheng-Hong Cho and
Jer-Tsang Wang Triangular grid protocol: An efficient
scheme for replica control with uniform
access quorums . . . . . . . . . . . . . 259--288
Steven T. Hackstadt and
Allen D. Malony DAQV: Distributed Array Query and
Visualization Framework . . . . . . . . 289--317
J. A. Smith and
S. K. Shrivastava Performance of fault-tolerant data and
compute intensive programs over a
network of workstations . . . . . . . . 319--345
Franco Gasperoni and
Uwe Schwiegelshohn List scheduling in the presence of
branches. A theoretical evaluation . . . 347--363
Jens Knoop Eliminating partially dead code in
explicitly parallel programs . . . . . . 365--393
Patrick Le Gouëslier d'Argence Affine scheduling on bounded convex
polyhedric domains is asymptotically
optimal . . . . . . . . . . . . . . . . 395--415
Anonymous Linear Logic '96 (papers in summary form
only received) . . . . . . . . . . . . . ??
Alexandru Mateescu and
Grzegorz Rozenberg and
Arto Salomaa Shuffle on trajectories: Syntactic
constraints . . . . . . . . . . . . . . 1--56
Koji Nakano and
Koichi Wada Integer summing algorithms on
reconfigurable meshes . . . . . . . . . 57--77
Ning Zhong Recursively enumerable subsets of $R^q$
in two computing models: Blum-Shub-Smale
machine and Turing machine . . . . . . . 79--94
Susanne Albers A competitive analysis of the list
update problem with lookahead . . . . . 95--109
Palash Sarkar and
Rana Barua Multidimensional $\sigma$-automata,
$\pi$-polynomials and generalised
$S$-matrices . . . . . . . . . . . . . . 111--138
Lance Fortnow and
R\=usin\c\vs Freivalds and
William I. Gasarch and
Martin Kummer and
Stuart A. Kurtz and
Carl H. Smith and
Frank Stephan On the relative sizes of learnable sets 139--156
Guoliang Xue An ${\rm O}(n)$ time hierarchical tree
algorithm for computing force field in
$n$-body simulations . . . . . . . . . . 157--169
Roberto De Prisco and
Angelo Monti and
Linda Pagli Testing and reconfiguration of VLSI
linear arrays . . . . . . . . . . . . . 171--188
Roberto De Prisco and
Angelo Monti and
Linda Pagli Testing and reconfiguration of VLSI
linear arrays . . . . . . . . . . . . . 171--188
Lawrence L. Larmore and
Wojciech Rytter Almost optimal sublinear time parallel
recognition algorithms for three
subclasses of context free languages . . 189--201
Ngoc-Minh Lê On determining optimal strategies in
pursuit games in the plane . . . . . . . 203--234
Ioan Tomescu On words containing all short subwords 235--240
S. Abramsky and
G. McCusker Linearity, sharing and state: a fully
abstract game semantics for idealized
Algol with active expressions . . . . . 241
G. M. Bierman Towards a classical linear
lambda-calculus . . . . . . . . . . . . 242
R. F. Blute and
P. J. Scott A noncommutative full completeness
theorem . . . . . . . . . . . . . . . . 242
V. Danos and
L. Regnier Reversible, irreversible and optimal
lambda-machines . . . . . . . . . . . . 242
D. van Dalen Intuitionism-counting its blessings . . 242
C. Fouquere and
J. Vauzeilles Linear logic for taxonomical networks
and database updates . . . . . . . . . . 243
J.-Y. Girard On denotational completeness . . . . . . 243
J.-Y. Girard Coherent Banach spaces: a continuous
denotational semantics . . . . . . . . . 244
S. Hayashi and
M. Ishikawa and
S. Kobayashi and
H. Nakano and
S. Nakazaki Two extensions of PX system . . . . . . 244
K. Honda Abstract process structures . . . . . . 244
M. Kanovitch Simulating computations in second-order
non-commutative linear logic . . . . . . 245
F. Lamarche From proof nets to games . . . . . . . . 245
P. D. Lincoln and
J. C. Mitchell and
A. Scedrov The complexity of local proof search in
linear logic . . . . . . . . . . . . . . 245
F. Metayer Some remarks on cyclic linear logic . . 245--246
R. McDowell and
D. Miller and
C. Palamidessi Encoding transition systems in sequent
calculus . . . . . . . . . . . . . . . . 246
M. Nagaymam and
M. Okada A graph-theoretic characterization
theorem for multiplicative fragment of
noncommutative linear logic . . . . . . 246
M. Okada Phase semantics for high-order
completeness, cut-elimination and
normalization proofs . . . . . . . . . . 246
V. Danos and
J.-B. Joinet and
H. Schellinx Computational isomorphisms in classical
logic . . . . . . . . . . . . . . . . . 247
V. Pratt Broadening the denotational semantics of
linear logic . . . . . . . . . . . . . . 247
C. Retore Perfect matching and series-parallel
graphs: multiplicatives proof nets as R
and B-graphs . . . . . . . . . . . . . . 247
J. S. Hodas and
J. Polakow Forum as a logic programming language 247--248
M. Pedicini Remarks on elementary linear logic . . . 248
L. Tortora de Falco Generalized standardization lemma for
the additives . . . . . . . . . . . . . 248
Friedrich Otto and
Paliath Narendran and
Daniel J. Dougherty Equational unification and word
unification, and $2$nd-order equational
unification . . . . . . . . . . . . . . 1--47
Gopalan Nadathur and
Debra Sue Wilson A notation for lambda terms. A
generalization of environments . . . . . 49--98
Viliam Geffert A communication hierarchy of parallel
computations . . . . . . . . . . . . . . 99--130
Chrysafis Hartonas A fixpoint approach to finite delay and
fairness . . . . . . . . . . . . . . . . 131--158
Michele Boreale and
Davide Sangiorgi Some congruence properties for
$\pi$-calculus bisimilarities . . . . . 159--176
Robert Goldblatt Enlargements of functional algebras for
the lambda calculus . . . . . . . . . . 177--200
Uwe Egly An answer to an open problem of Urquhart 201--209
Javier Esparza Reachability in live and safe
free-choice Petri nets is NP-complete 211--224
Flavio Corradini On the coarsest congruence within
global-clock-bounded equivalence . . . . 225--237
Naim Ça\vgman and
J. Roger Hindley Combinatory weak reduction in lambda
calculus . . . . . . . . . . . . . . . . 239--247
A. Nijholt and
G. Scollo Editorial . . . . . . . . . . . . . . . 1--3
Wojciech Buszkowski Algebraic structures in categorial
grammar . . . . . . . . . . . . . . . . 5--24
Theo M. V. Janssen Algebraic translations, correctness and
algebraic compiler construction . . . . 25--56
Eelco Visser Polymorphic syntax definition . . . . . 57--86
Klaas Sikkel Parsing schemata and correctness of
parsing algorithms . . . . . . . . . . . 87--103
Teodor Rus Algebraic processing of programming
languages . . . . . . . . . . . . . . . 105--143
Frédéric Tendeau Computing abstract decorations of parse
forests using dynamic programming and
algebraic power series . . . . . . . . . 145--166
Eric Villemonte de la Clergerie and
François Barthélemy Information flow in tabular
interpretations for generalized
push-down automata . . . . . . . . . . . 167--198
Teodor Rus and
James S. Jones PHRASE parsers from multi-axiom grammars 199--229
José Carlos Ramalho and
José João Almeida and
Pedro Henriques Algebraic specification of documents . . 231--247
Klaus Barthelmann Nondeterministic operations on finite
relational structures . . . . . . . . . 1--44
Vincent Schmitt Stable trace automata vs. full trace
automata . . . . . . . . . . . . . . . . 45--100
Lothar M. Schmitt and
Chrystopher L. Nehaniv and
Robert H. Fujii Linear analysis of genetic algorithms 101--134
Wieslaw Zielonka Infinite games on finitely coloured
graphs with applications to automata on
infinite trees . . . . . . . . . . . . . 135--183
Peter Jeavons On the algebraic structure of
combinatorial problems . . . . . . . . . 185--204
Tero Harju and
Lucian Ilie On quasi orders of words and the
confluence property . . . . . . . . . . 205--224
M. Hennessy and
J. Rathke Bisimulations for a calculus of
broadcasting systems . . . . . . . . . . 225--260
E. Rivals and
J.-P. Delahaye Optimal representation in average using
Kolmogorov complexity . . . . . . . . . 261--287
Jaco van de Pol Operational semantics of rewriting with
priorities . . . . . . . . . . . . . . . 289--312
C. Blundo and
Luiz A. Frota Mattos and
D. R. Stinson Generalized Beimel--Chor schemes for
broadcast encryption and interactive key
distribution . . . . . . . . . . . . . . 313--334
Daniele Mundici and
Nicola Olivetti Resolution and model building in the
infinite-valued calculus of Lukasiewicz 335--366
Philippe Jacquet and
Wojciech Szpankowski Analytical depoissonization and its
applications . . . . . . . . . . . . . . 1--62
E. A. Cichon and
E. Tahhan Bittar Ordinal recursive bounds for Higman's
theorem . . . . . . . . . . . . . . . . 63--84
Tak Wah Lam and
Ka Hing Lee An improved scheme for set equality
testing and updating . . . . . . . . . . 85--97
Cristopher Moore Dynamical recognizers: real-time
language recognition by analog computers 99--136
Natacha Portier Résolutions universelles pour des
probl\`emes NP-complets. (French)
[Universal resolution of NP-complete
problems] . . . . . . . . . . . . . . . 137--150
Laurent Rosaz Inventories of unavoidable languages and
the word-extension conjecture . . . . . 151--170
Gianpiero Cattaneo and
Luciano Margara Generalized sub-shifts in elementary
cellular automata: the ``strange case''
of chaotic rule $180$ . . . . . . . . . 171--187
M. Flasi\'nski Power properties of NLC graph grammars
with a polynomial membership problem . . 189--231
Koichi Wada and
Akinari Takaki and
Kimio Kawaguchi Efficient algorithms for a mixed
$k$-partition problem of graphs without
specifying bases . . . . . . . . . . . . 233--248
Paolo Ferragina and
Roberto Grossi and
Manuela Montangero On updating suffix tree labels . . . . . 249--262
Kunsoo Park Analysis of two-dimensional approximate
pattern matching algorithms . . . . . . 263--273
Kuo-Liang Chung An improved algorithm for solving the
banded cyclic string-to-string
correction problem . . . . . . . . . . . 275--279
J. Diaz and
M. Serna and
P. Spirakis On the random generation and counting of
matchings in dense graphs . . . . . . . 281--290
Marco Bernardo and
Roberto Gorrieri A tutorial on EMPA: A theory of
concurrent processes with
nondeterminism, priorities,
probabilities and time . . . . . . . . . 1--54
Christoph Brzoska Programming in metric temporal logic . . 55--125
Miguel Felder and
Angelo Gargantini and
Angelo Morzenti A theory of implementation and
refinement in timed Petri nets . . . . . 127--161
Agostino Cortesi and
Gilberto Filé and
William Winsborough The quotient of an abstract
interpretation . . . . . . . . . . . . . 163--192
Chrysafis Hartonas Duality for modal $\mu$-logics . . . . . 193--222
Franck van Breugel Terminal metric spaces of finitely
branching and image finite linear
processes . . . . . . . . . . . . . . . 223--230
G. Ramos-Jiménez and
J. López-Muñoz and
R. Morales-Bueno Comparisons of Parikh's condition to
other conditions for context-free
languages . . . . . . . . . . . . . . . 231--244
Giorgio Ausiello and
Alberto Marcjetto-Spacemela Foreword . . . . . . . . . . . . . . . . 1--1
Krzysztof Diks and
Torben Hagerup More general parallel tree contraction:
Register allocation and broadcasting in
a tree . . . . . . . . . . . . . . . . . 3--29
Stephan Hartmann and
Markus W. Schaffter and
Andreas S. Schulz Switchbox routing in VLSI design:
Closing the complexity gap . . . . . . . 31--49
P. Crescenzi and
P. Penna Strictly-upward drawings of ordered
search trees . . . . . . . . . . . . . . 51--67
Serafino Cicerone and
Daniele Frigioni and
Umberto Nanni and
Francesco Pugliese A uniform approach to semi-dynamic
problems on digraphs . . . . . . . . . . 69--90
Kay U. Drangmeister and
Sven O. Krumke and
Madhav V. Marathe and
Hartmut Noltemeier and
S. S. Ravi Modifying edges of a network to obtain
short subgraphs . . . . . . . . . . . . 91--121
Jens Gustedt Efficient Union-Find for planar graphs
and other sparse graph classes . . . . . 123--141
Tadao Takaoka Shortest path algorithms for nearly
acyclic directed graphs . . . . . . . . 143--150
Evangelos Kranakis and
Danny Krizanc and
Andrzej Pelc and
David Peleg Approximate maxima finding of continuous
functions under restricted budget . . . 151--162
Krzysztof Diks and
Andrzej Pelc System diagnosis with smallest risk of
error . . . . . . . . . . . . . . . . . 163--173
Armin Baumker and
Wolfgang Dittrich and
Friedhelm Meyer auf der Heide Truly efficient parallel algorithms:
1-optimal multisearch for an extension
of the BSP model . . . . . . . . . . . . 175--203
Shiva Chaudhuri and
Christos D. Zaroliagis Shortest paths in digraphs of small
treewidth. Part II: Optimal parallel
algorithms . . . . . . . . . . . . . . . 205--223
Devdatt Dubhashi and
David A. Grable and
Alessandro Panconesi Near-optimal, distributed edge colouring
via the nibble method . . . . . . . . . 225--251
Shimon Even and
Gene Itkis and
Sergio Rajsbaum On mixed connectivity certificates . . . 253--269
Véronique Bruy\`ere On maximal codes with bounded
synchronization delay . . . . . . . . . 11--28
Julien Cassaigne and
Juhani Karhumäki Examples of undecidable problems for
$2$-generator matrix semigroups . . . . 29--34
Christian Choffrut and
Flavio D'Alessandro Commutativity in free inverse monoids 35--54
Robert Cori and
Michel Marcus Counting non-isomorphic chord diagrams 55--73
Aldo de Luca A conjecture on continued fractions . . 75--86
Jean-Pierre Duval Périodes locales et propagation de
périodes dans un mot. (French) [Local
periods and period propagation in a
word] . . . . . . . . . . . . . . . . . 87--98
P. Goralcik and
V. Koubek On the disjunctive set problem . . . . . 99--118
Georges Hansel Syst\`emes de numération independants et
syndéticite. (French) [Systems of
independent ???? numeration] . . . . . . 119--130
Lucian Ilie and
Arto Salomaa On well quasi orders of free monoids . . 131--152
Filippo Mignosi and
Antonio Restivo and
Sergio Salemi Periodicity and the golden ratio . . . . 153--167
Robert McNaughton The finiteness of finitely presented
monoids . . . . . . . . . . . . . . . . 169--182
Gheorghe P\uaun and
Grzegorz Rozenberg Sticker systems . . . . . . . . . . . . 183--203
Jacques Sakarovitch A construction on finite automata that
has remained hidden . . . . . . . . . . 205--231
Paul E. Schupp On the structure of Hamiltonian cycles
in Cayley graphs of finite quotients of
the modular group . . . . . . . . . . . 233--248
Magnus Steinby General varieties of tree languages . . 1--43
Beate Bollig and
Martin Sauerhoff and
Detlef Sieling and
Ingo Wegener Hierarchy theorems for $k$ OBDDs and $k$
IBDDs . . . . . . . . . . . . . . . . . 45--60
Andrzej Ehrenfeucht and
Gheorghe P\uaun and
Grzegorz Rozenberg On representing recursively enumerable
languages by internal contextual
languages . . . . . . . . . . . . . . . 61--83
Chang-Wu Yu and
Gen-Huey Chen and
Tze-Heng Ma On the complexity of the $k$-chain
subgraph cover problem . . . . . . . . . 85--98
M. Golin and
S. Zaks Labelled trees and pairs of
input--output permutations in priority
queues . . . . . . . . . . . . . . . . . 99--114
Michele Flammini and
Giorgio Gambosi and
Umberto Nanni and
Richard B. Tan Multidimensional interval routing
schemes . . . . . . . . . . . . . . . . 115--133
Tadakazu Sato Ergodic characterization of linear
cellular automata over $Z_m$ . . . . . . 135--144
Dora Giammarresi and
Sabrina Mantaci and
Filippo Mignosi and
Antonio Restivo Periodicities on trees . . . . . . . . . 145--181
J. O. Durand-Lose Parallel transient time of
one-dimensional sand pile . . . . . . . 183--193
Carlos Martin-Vide and
Gheorghe P\uaun and
Arto Salomaa Characterizations of recursively
enumerable languages by means of
insertion grammars . . . . . . . . . . . 195--205
Yves Andre and
Francis Bossut On the equivalence problem for
letter-to-letter top-down tree
transducers . . . . . . . . . . . . . . 207--229
Biing-Feng Wang Simulating the CRCW PRAM on
reconfigurable networks . . . . . . . . 231--242
Marek Karpinski and
Wojciech Rytter Alphabet-independent optimal parallel
search for three-dimensional patterns 243--260
A. E. Andreev and
A. Clementi and
P. Crescenzi and
E. Dahlhaus and
S. De Agostino and
J. D. P. Rolim The parallel complexity of approximating
the high degree subgraph problem . . . . 261--282
Aviezri S. Fraenkel and
Michal Ozery Adjoining to Wythoff's game its
P-positions as moves . . . . . . . . . . 283--296
Marie-Pierre Béal and
Jean Senellart On the bound of the synchronization
delay of a local automaton . . . . . . . 297--306
Peter A. Beling and
Nimrod Megiddo Using fast matrix multiplication to find
basic solutions . . . . . . . . . . . . 307--316
Lane A. Hemaspaandra and
Zhigen Jiang and
Jörg Rothe and
Osamu Watanabe Boolean operations, joins, and the
extended low hierarchy . . . . . . . . . 317--327
Huaxiong Wang On rational series and rational
languages . . . . . . . . . . . . . . . 329--336
Wai-fong Chuan Unbordered factors of the characteristic
sequences of irrational numbers . . . . 337--344
Dominic Duggan Unification with extended patterns . . . 1--50
Sandro Etalle A semantics for modular general logic
programs . . . . . . . . . . . . . . . . 51--80
N. Bensaou and
I. Guessarian Transforming constraint logic programs 81--125
Xinxin Liu and
David Walker Partial confluence of processes and
systems of objects . . . . . . . . . . . 127--162
Patrick Dehornoy and
Abderrahim Marzouk Theorem proving by chain resolution . . 163--180
Thomas Eiter and
Nicola Leone and
Domenico Saccá Expressive power and complexity of
partial models for disjunctive deductive
databases . . . . . . . . . . . . . . . 181--218
Lutz Priese and
Harro Wimmel A uniform approach to true-concurrency
and interleaving semantics for Petri
nets . . . . . . . . . . . . . . . . . . 219--256
Susumu Yamasaki and
Yoshinori Kurose Soundness of abductive proof procedure
with respect to constraint for
non-ground abducibles . . . . . . . . . 257--281
Mark Levene and
George Loizou Axiomatisation of functional
dependencies in incomplete relations . . 283--300
Lo\"\ic Colson and
Daniel Fredholm System T, call-by-value and the minimum
problem . . . . . . . . . . . . . . . . 301--315
Ralph Loader Unary PCF is decidable . . . . . . . . . 317--329
Sachio Hirokawa Infiniteness of proof$(\alpha)$ is
polynomial-space complete . . . . . . . 331--339
Leslie Lamport Proving possibility properties . . . . . 341--352
Guy Perrier Corrigendum to Galmiche's and Perrier's
``On proof normalization in linear
logic'' [Theoret. Comput. Sci 135(1)
(1994) 67--110] . . . . . . . . . . . . 353--354
Robert McNaughton Contributions of Ronald V. Book to the
theory of string-rewriting systems . . . 13--23
Franz J. Brandenburg The ancestor width of grammars and
languages . . . . . . . . . . . . . . . 25--41
Friedrich Otto Some undecidability results concerning
the property of preserving regularity 43--72
Kai Salomaa and
Sheng Yu Synchronization expressions with
extended join operation . . . . . . . . 73--88
Herbert Baier and
Klaus W. Wagner Bounding queries in the analytic
polynomial-time hierarchy . . . . . . . 89--104
Jin-Yi Cai A relation of primal--dual lattices and
the complexity of shortest lattice
vector problem . . . . . . . . . . . . . 105--116
Ioan I. Macarie and
Mitsunori Ogihara Properties of probabilistic pushdown
automata . . . . . . . . . . . . . . . . 117--130
Ashish V. Naik and
John D. Rogers and
James S. Royer and
Alan L. Selman A hierarchy based on output multiplicity 131--157
Heribert Vollmer Relating polynomial time to constant
depth . . . . . . . . . . . . . . . . . 159--170
Xiufeng Du and
Weili Wu and
Dean F. Kelley Approximations for subset
interconnection designs . . . . . . . . 171--180
Guo-Hui Lin and
Guoliang Xue $K$-center and $K$-median problems in
graded distances . . . . . . . . . . . . 181--192
Peng-Jun Wan Conflict-Free channel set assignment for
an optical cluster interconnection
network based on rotator digraphs . . . 193--201
Jie Wang and
Yaorong Ge An optimization problem in virtual
endoscopy . . . . . . . . . . . . . . . 203--216
José L. Balcázar and
Montserrat Hermo The structure of logarithmic advice
complexity classes . . . . . . . . . . . 217--244
Amy K. Lorentz and
Jack H. Lutz Genericity and randomness over feasible
probability measures . . . . . . . . . . 245--259
Andrei A. Muchnik and
Alexei L. Semenov and
Vladimir A. Uspensky Mathematical metaphysics of randomness 263--317
An A. Muchnik On common information . . . . . . . . . 319--328
Nikolai K. Vereshchagin Randomized Boolean decision trees:
Several remarks . . . . . . . . . . . . 329--342
V. V. V'yugin Ergodic theorems for individual random
sequences . . . . . . . . . . . . . . . 343--361
V. V. V'yugin Non-stochastic infinite and finite
sequences . . . . . . . . . . . . . . . 363--382
K. Yu. Gorbunov On a complexity of the formula $(A \vee
B) \Rightarrow C$ . . . . . . . . . . . 383--386
A. N. Kolmogorov On tables of random numbers . . . . . . 387--395
Klaus Madlener and
Birgit Reinert Relating rewriting techniques on monoids
and rings: congruences on monoids and
ideals in monoid rings . . . . . . . . . 3--31
Jean-Pierre Jouannaud and
Albert Rubio Rewrite orderings for higher-order terms
in $\eta$-long $\beta$-normal form and
the recursive path ordering . . . . . . 33--58
M. R. K. Krishna Rao Modular aspects of term graph rewriting 59
M. R. K. Krishna Rao Modular aspects of term graph rewriting 59--86
Masahiko Sakai and
Yoshihito Toyama Semantics and strong sequentiality of
priority term rewriting systems . . . . 87--110
Manfred Schmidt-Schauß A decision algorithm for distributive
unification . . . . . . . . . . . . . . 111--148
Jürgen Stuber Superposition theorem proving for
abelian groups represented as integer
modules . . . . . . . . . . . . . . . . 149--177
Ralf Treinen The first-order theory of linear
one-step rewriting is undecidable . . . 179--190
Hans L. Bodlaender A partial $k$-arboretum of graphs with
bounded treewidth . . . . . . . . . . . 1--45
Eric Allender and
Jia Jiao and
Meena Mahajan and
V. Vinay Non-commutative arithmetic circuits:
depth reduction and size lower bounds 47--86
Philippe Béguin and
Antonella Cresti General information dispersal algorithms 87--105
Marc Demange and
Pascal Grisoni and
Vangelis Th. Paschos Differential approximation algorithms
for some combinatorial optimization
problems . . . . . . . . . . . . . . . . 107--122
Rodney G. Downey and
Michael R. Fellows Threshold dominating sets and an
improved characterization of $W[2]$ . . 123--140
B. Apolloni and
C. Gentile Sample size lower bounds in PAC learning
by Algorithmic Complexity Theory . . . . 141--162
Luca Aceto and
Wan Fokkink and
Anna Ingólfsdóttir On a question of A. Salomaa: The
equational theory of regular expressions
over a singleton alphabet is not
finitely based . . . . . . . . . . . . . 163--178
François Blanchard and
Petr K\ocircurka Language complexity of rotations and
Sturmian sequences . . . . . . . . . . . 179--193
F. Adele A. Communication complexity of
fault-tolerant information diffusion . . 195
Luisa Gargano and
Adele A. Rescigno Communication complexity of
fault-tolerant information diffusion . . 195--211
Erzsébet Csuhaj-Varjú and
Alica Kelemenová Team behaviour in eco-grammar systems 213--224
Marius Zimand On the size of classes with weak
membership properties . . . . . . . . . 225--235
Edoardo Amaldi and
Viggo Kann On the approximability of minimizing
nonzero variables or unsatisfied
relations in linear systems . . . . . . 237--260
Laurent Vuillon Combinatoire des motifs d'une suite
sturmienne bidimensionnelle. (French)
[Combination of motifs of a Sturmian
bidimensional sequence] . . . . . . . . 261--285
Carsten Rössner and
Jean-Pierre Seifert On the hardness of approximating
shortest integer relations among
rational numbers . . . . . . . . . . . . 287--297
Martin Beaudry Languages recognized by finite aperiodic
groupoids . . . . . . . . . . . . . . . 299--317
György Vaszil On simulating non-returning PC grammar
systems with returning systems . . . . . 319--329
Charles J. Colbourn and
Guoliang Xue A linear time algorithm for computing
the most reliable source on a
series--parallel graph with unreliable
edges . . . . . . . . . . . . . . . . . 331--345
Ewa Malesi\'nska and
Alessandro Panconesi On the hardness of allocating
frequencies for hybrid networks . . . . 347--363
Dany Breslauer On competitive on-line paging with
lookahead . . . . . . . . . . . . . . . 365--375
T. Downarowicz and
Y. Lacroix Merit factors and Morse sequences . . . 377--387
Rimli Sengupta and
H. Venkateswaran A lower bound for monotone arithmetic
circuits computing $0$--$1$ permanent 389--398
Vasco Brattka Computable invariance . . . . . . . . . 3--20
Olivier Bournez Achilles and the Tortoise climbing up
the hyper-arithmetical hierarchy . . . . 21--71
Abbas Edalat and
Philipp Sünderhauf A domain-theoretic approach to
computability on the real line . . . . . 73--98
Chun-Kuen Ho Relatively recursive reals and real
functions . . . . . . . . . . . . . . . 99--120
Martín Hötzel Escardó and
Thomas Streicher Induction and recursion on the partial
real line with applications to Real PCF 121--157
Taoufik Safer Polygonal radix representations of
complex numbers . . . . . . . . . . . . 159--171
Herve Bronnimann and
Ioannis Z. Emiris and
Victor Y. Pan and
Sylvain Pion Sign determination in residue number
systems . . . . . . . . . . . . . . . . 173--197
Joris van der Hoeven Fast evaluation of holonomic functions 199--215
Pascal Koiran and
Cristopher Moore Closed-form analytic maps in one and two
dimensions can simulate universal Turing
machines . . . . . . . . . . . . . . . . 217--223
Yasubumi Sakakibara and
Claudio Ferretti Splicing on tree-like structures . . . . 227--243
Shinichi Shimozono Alphabet indexing for approximating
features of symbols . . . . . . . . . . 245--260
Tatsuya Akutsu and
Satoru Miyano On the approximation of protein
threading . . . . . . . . . . . . . . . 261--275
Yasuo Uemura and
Aki Hasegawa and
Satoshi Kobayashi and
Takashi Yokomori Tree adjoining grammars for RNA
structure prediction . . . . . . . . . . 277--303
H. Matsuda and
T. Ishihara and
A. Hashimoto Classifying molecular sequences using a
linkage graph with their pairwise
similarities . . . . . . . . . . . . . . 305--325
Qian-Ping Gu and
Shietung Peng and
Hal Sudborough A $2$-approximation algorithm for genome
rearrangements by reversals and
transpositions . . . . . . . . . . . . . 327--339
Takahiro Ikeda and
Hiroshi Imai Enhanced $A^*$ algorithms for multiple
alignments: optimal alignments for
several sequences and $k$-opt
approximate alignments for large cases 341--374
Maciej Koutny and
Eike Best Operational and denotational semantics
for the box algebra . . . . . . . . . . 1--83
G. M. Reed and
A. W. Roscoe The timed failures --- Stability model
for CSP . . . . . . . . . . . . . . . . 85--127
Matthew Stone Representing scope in intuitionistic
deductions . . . . . . . . . . . . . . . 129--188
Yong Sun An algebraic generalization of Frege
structures --- binding algebras . . . . 189--232
A. S. Troelstra From constructivism to computer science 233--252
Rajeev Alur and
Limor Fix and
Thomas A. Henzinger Event-clock automata: a determinizable
class of timed automata . . . . . . . . 253--273
Marco Comini and
Maria Chiara Meo Compositionality properties of
SLD-derivations . . . . . . . . . . . . 275--309
Joost Engelfriet and
Tjalling Gelsema Multisets and structural congruence of
the pi-calculus with replication . . . . 311--337
Luca Aceto and
Jan Friso Groote A complete equational axiomatization for
MPA with string iteration . . . . . . . 339--374
Roel Bloo and
Herman Geuvers Explicit substitution On the edge of
strong normalization . . . . . . . . . . 375--395
Chantal Berline and
Klaus Grue A $\kappa$-denotational semantics for
map theory in ZFC$+$SI . . . . . . . . . 397--398
Marcin Benke Some complexity bounds for subtype
inequalities . . . . . . . . . . . . . . 3--27
Alessandro Berarducci and
Mariangiola Dezani-Ciancaglini Infinite $\lambda$-calculus and types 29--75
Harold Boley Functional-logic integration via minimal
reciprocal extensions . . . . . . . . . 77--99
Viviana Bono and
Michele Bugliesi Matching for the lambda calculus of
objects . . . . . . . . . . . . . . . . 101--140
Roy Dyckhoff and
Luís Pinto Permutability of proofs in
intuitionistic sequent calculi . . . . . 141--155
Martin Emms and
Hans Leiß Extending the type checker of Standard
ML by polymorphic recursion . . . . . . 157--181
Furio Honsell and
Marina Lenisa Semantical analysis of perpetual
strategies in $\lambda$-calculus . . . . 183--209
B. Intrigila and
M. Venturini Zilli Orders, reduction graphs and spectra . . 211--231
Adolfo Piperno An algebraic view of the Böhm-out
technique . . . . . . . . . . . . . . . 233--246
Helmut Schwichtenberg Termination of permutative conversions
in intuitionistic Gentzen calculi . . . 247--260
Dieter Spreen On functions preserving levels of
approximation: A refined model
construction for various lambda calculi 261--303
Michiel Hazewinkel Preface . . . . . . . . . . . . . . . . 1--3
Anonymous Subject index volumes 1--200 . . . . . . 5--436
Anonymous Reference list of indexed articles . . . 437--528
Anonymous Cumulative index volumes 1--200 . . . . 529--659
Y. Boufkhad and
O. Dubois Length of prime implicants and number of
solutions of random CNF formulae . . . . 1--30
Gilles Didier Caractérisation des $N$-écritures et
application \`a l'étude des suites de
complexité ultimement $n + c^{\rm ste}$.
(French) [Characterization of
$N$-writings and application to the
study of sequences of $n+c^{\rm th}$
ultimate complexity] . . . . . . . . . . 31--49
Yaghout Nourani and
Bjarne Andresen Exploration of NP-hard enumeration
problems by simulated annealing --- the
spectrum values of permanents . . . . . 51--68
Djelloul Ziadi and
Jean-Marc Champarnaud An optimal parallel algorithm to convert
a regular expression into its Glushkov
automaton . . . . . . . . . . . . . . . 69--87
Ryuhei Uehara and
Zhi-Zhong Chen and
Xin He Fast RNC and NC algorithms for maximal
path sets . . . . . . . . . . . . . . . 89--98
Mireille Clerbout and
Yves Roos and
Isabelle Ryl Synchronization languages . . . . . . . 99--121
Johann Hagauer and
Wilfried Imrich and
Sandi Klav\vzar Recognizing median graphs in
subquadratic time . . . . . . . . . . . 123--136
Martin Middendorf and
Welf Löwe and
Wolf Zimmermann Scheduling inverse trees under the
communication model of the LogP-machine 137--168
Valeria Mihalache Decidability problems in grammar systems 169--189
Dora Giammarresi and
Rosa Montalbano Deterministic generalized automata . . . 191--208
Oh-Heum Kwon and
Kyung-Yong Chwa Scheduling parallel tasks with
individual deadlines . . . . . . . . . . 209--223
Bruno Durand and
Anne-Cécile Fabret On the complexity of deadlock detection
in families of planar nets . . . . . . . 225--237
Martin Kutrib Pushdown cellular automata . . . . . . . 239--261
Peter Buchholz Exact performance equivalence: An
equivalence relation for stochastic
automata . . . . . . . . . . . . . . . . 263--287
Pascal Koiran Elimination of parameters in the
polynomial hierarchy . . . . . . . . . . 289--304
Thomas Andreae and
Felix Hartenstein and
Andrea Wolter A two-person game on graphs where each
player tries to encircle his opponent's
men . . . . . . . . . . . . . . . . . . 305--323
R. I. Grigorchuk and
A. Mach\`\i An example of an indexed language of
intermediate growth . . . . . . . . . . 325--327
Véronique Bruy\`ere and
Christophe Reutenauer A proof of Choffrut's theorem on
subsequential functions . . . . . . . . 329--335
Arne Andersson and
Peter Bro Miltersen and
Mikkel Thorup Fusion trees can be implemented with
AC$^0$ instructions only . . . . . . . . 337--344
Herbert Fischer and
Harley Flanders A minimal code list . . . . . . . . . . 345--348
Erzsébet Csuhaj-Varjú and
György Vaszil On the computational completeness of
context-free parallel communicating
grammar systems . . . . . . . . . . . . 349--358
Lusheng Wang and
Xiaohua Jia Fixed topology Steiner trees and
spanning forests . . . . . . . . . . . . 359--370
Philippe Flajolet Singularity analysis and asymptotics of
Bernoulli sums . . . . . . . . . . . . . 371--381
Jean-Michel Autebert Some results about centralized PC
grammar systems . . . . . . . . . . . . 383--398
Antonio Cerone and
Andrea Maggiolo-Schettini Time-based expressivity of time Petri
nets for system specification . . . . . 1--53
William Ferreira and
Matthew Hennessy A behavioural theory of first-order CML 55--107
Elena Zucca From static to dynamic abstract
data-types: an institution
transformation . . . . . . . . . . . . . 109--157
Roberto Giacobazzi and
Francesco Ranzato The reduced relative power operation on
abstract domains . . . . . . . . . . . . 159--211
Cui Zhang and
Ronald A. Olsson and
Karl N. Levitt Formal verification of a programming
logic for a distributed programming
language . . . . . . . . . . . . . . . . 213--235
Pierpaolo Degano and
Corrado Priami Non-interleaving semantics for mobile
processes . . . . . . . . . . . . . . . 237--270
Francesca Levi A compositional $\mu$-calculus proof
system for statecharts processes . . . . 271--310
P. Burmeister and
M. Monserrat and
F. Rosselló and
G. Valiente Algebraic transformation of unary
partial algebras II: Single-pushout
approach . . . . . . . . . . . . . . . . 311--362
Manfred Schmidt-Schauß Decidability of behavioural equivalence
in unary PCF . . . . . . . . . . . . . . 363--373
K. Rustan M. Leino and
Rajit Manohar Joining specification statements . . . . 375--394
Mingsheng Ying A shorter proof to uniqueness of
solutions of equations . . . . . . . . . 395--397
Thomas Worsch Parallel Turing machines with one-head
control units and cellular automata . . 3--30
G. Cattaneo and
E. Formenti and
L. Margara and
G. Mauri On the dynamical behavior of chaotic
cellular automata . . . . . . . . . . . 31--51
Jacques Mazoyer and
Véronique Terrier Signals in one-dimensional cellular
automata . . . . . . . . . . . . . . . . 53--80
Moshe Sipper and
Marco Tomassini Computation in artificially evolved,
non-uniform cellular automata . . . . . 81--98
Stefania Bandini and
Giancarlo Mauri Multilayered cellular automata . . . . . 99--113
Bastien Chopard and
Pascal O. Luthi Lattice Boltzmann computations and
applications to physics . . . . . . . . 115--130
S. Di Gregorio and
R. Serra and
M. Villani Applying cellular automata to complex
environmental problems: The simulation
of the bioremediation of contaminated
soils . . . . . . . . . . . . . . . . . 131--156
Franco A. Bignone Coupled map lattices dynamics on a
variable space for the study of
development: A general discussion on
Caenorhabditis elegans . . . . . . . . . 157--172
G. Sander Graph layout for applications in
compiler construction . . . . . . . . . 175--214
Bernhard Ganter Attribute exploration with background
knowledge . . . . . . . . . . . . . . . 215--233
Roberto Tamassia Advances in the theory and practice of
graph drawing . . . . . . . . . . . . . 235--254
J. Schmid Boolean layer cakes. Proceedings ORDAL
'96 . . . . . . . . . . . . . . . . . . 255--278
G. Grätzer Congruence lattices $101$ . . . . . . . 279--289
G. Grätzer and
E. T. Schmidt Some combinatorial aspects of congruence
lattice representations . . . . . . . . 291--300
Bernd S. W. Schröder Algorithms for the fixed point property 301--358
Peter Fishburn Preference structures and their
numerical representations . . . . . . . 359--383
H. Peter Gumm Generating algebraic laws from
imperative programs . . . . . . . . . . 385--405
Vincent Duquenne Latticial structures in data analysis 407--436
Julien Cassaigne Limit values of the recurrence quotient
of Sturmian sequences . . . . . . . . . 3--12
Aldo de Luca On the combinatorics of finite words . . 13--39
Guy Melançon Lyndon words and singular factors of
Sturmian words . . . . . . . . . . . . . 41--59
Arturo Carpi On Abelian squares and substitutions . . 61--81
M. Gabriella Castelli and
Filippo Mignosi and
Antonio Restivo Fine and Wilf's theorem for three
periods and a generalization of Sturmian
words . . . . . . . . . . . . . . . . . 83--94
Aviezri S. Fraenkel and
Jamie Simpson The exact number of squares in Fibonacci
words . . . . . . . . . . . . . . . . . 95--106
Véronique Bruy\`ere and
Dominique Perrin Maximal bifix codes . . . . . . . . . . 107--121
Juhani Karhumäki and
Wojciech Plandowski and
Wojciech Rytter Generalized factorizations of words and
their algorithmic properties . . . . . . 123--133
Jean Berstel and
Luc Boasson Partial words and a theorem of Fine and
Wilf . . . . . . . . . . . . . . . . . . 135--141
J.-P. Allouche Transcendence of formal power series
with rational coefficients . . . . . . . 143--160
Roman Kolpakov and
Gregory Kucherov and
Yuri Tarannikov On repetition-free binary words of
minimal density . . . . . . . . . . . . 161--175
Sébastien Ferenczi and
Zoltán Kása Complexity for finite factors of
infinite sequences . . . . . . . . . . . 177--195
Maxime Crochemore and
Leszek Ga\csieniec and
Wojciech Rytter Constant-space string-matching in
sublinear average time . . . . . . . . . 197--203
Costas S. Iliopoulos and
Laurent Mouchard Quasiperiodicity and string covering . . 205--216
Jacques Mazoyer and
Renzo Pinzani and
Jean-Guy Penaud Avant Propos . . . . . . . . . . . . . . 217--218
Elena Barcucci and
Alberto Del Lungo and
Elisa Pergola Random generation of trees and other
combinatorial objects . . . . . . . . . 219--232
Alain Denise and
Paul Zimmermann Uniform random generation of
decomposable structures using
floating-point arithmetic . . . . . . . 233--248
G. Louchard Asymptotic properties of some
underdiagonal walks generation
algorithms . . . . . . . . . . . . . . . 249--262
M. Mosbah and
N. Saheb Non-uniform random spanning trees on
weighted graphs . . . . . . . . . . . . 263--271
Gilles d'Andréa and
Christophe Fiorio Maximal superpositions of horizontally
convex polyominoes . . . . . . . . . . . 273--283
Eric Goles and
Ivan Rapaport Tiling allowing rotations only . . . . . 285--295
David Simplot A characterization of recognizable
picture languages by tilings by finite
sets . . . . . . . . . . . . . . . . . . 297--323
Véronique Terrier Two-dimensional cellular automata
recognizer . . . . . . . . . . . . . . . 325--346
Marianne Delorme and
Jacques Mazoyer and
Laure Tougne Discrete parabolas and circles on $2$D
cellular automata . . . . . . . . . . . 347--417
Kalvis Aps\=\itis and
Setsuo Arikawa and
R\=usin\c\vs Freivalds and
Eiju Hirowatari and
Carl H. Smith On the inductive inference of recursive
real-valued functions . . . . . . . . . 3--17
Jens Blanck Effective domain representations of
$H(X)$, the space of compact subsets . . 19--48
Paolo Boldi and
Sebastiano Vigna Equality is a jump . . . . . . . . . . . 49--64
Vasco Brattka and
Klaus Weihrauch Computability on subsets of Euclidean
space I: closed and compact subsets . . 65--93
Douglas S. Bridges Constructive mathematics: a foundation
for computable analysis . . . . . . . . 95--109
Douglas Cenzer and
Jeffrey B. Remmel Index sets in computable analysis . . . 111--150
Thomas Chadzelek and
Günter Hotz Analytic machines . . . . . . . . . . . 151--167
Abbas Edalat and
Philipp Sünderhauf Computable Banach spaces via domain
theory . . . . . . . . . . . . . . . . . 169--184
Armin Hemmerling On approximate and algebraic
computability over the real numbers . . 185--223
Peter Hertling An effective Riemann Mapping Theorem . . 225--265
Boris A. Kushner Markov's constructive analysis; a
participant's view . . . . . . . . . . . 267--285
Norbert Th. Müller Computability on random variables . . . 287--299
Erich Novak and
Henryk Woz\'niakowski On the cost of uniform and nonuniform
algorithms . . . . . . . . . . . . . . . 301--318
Marian Boykan Pour-El From axiomatics to intrinsic
characterization: some open problems in
computable analysis . . . . . . . . . . 319--329
Matthias Schröder Online computations of differentiable
functions . . . . . . . . . . . . . . . 331--345
Viggo Stoltenberg-Hansen and
John V. Tucker Concrete models of computation for
topological algebras . . . . . . . . . . 347--378
J. V. Tucker and
J. I. Zucker Computation by `While' programs on
topological partial algebras . . . . . . 379--420
Klaus Weihrauch Computability on the probability
measures on the Borel sets of the unit
interval . . . . . . . . . . . . . . . . 421--437
Klaus Weihrauch and
Xizhong Zheng Effectiveness of the global modulus of
continuity on metric spaces . . . . . . 439--450
Henryk Woz\'niakowski Why does information-based complexity
use the real number model? . . . . . . . 451--465
Mariko Yasugi and
Takakazu Mori and
Yoshiki Tsujii Effective properties of sets and
functions in metric spaces with
computability structure . . . . . . . . 467--486
Ning Zhong Computability structure of the Sobolev
spaces and its applications . . . . . . 487--510
Marcos Kawazoe Aguilera and
Wei Chen and
Sam Toueg Using the heartbeat failure detector for
quiescent reliable communication and
consensus in partitionable networks . . 3--30
Gil Neiger and
Rida A. Bazzi Using knowledge to optimally achieve
coordination in distributed systems . . 31--65
Nancy Lynch and
Nir Shavit and
Alex Shvartsman and
Dan Touitou Timing conditions for linearizability in
uniform counting networks . . . . . . . 67--91
Shay Kutten and
Boaz Patt-Shamir Stabilizing time-adaptive protocols . . 93--111
Alan Fekete and
David Gupta and
Victor Luchangco and
Nancy Lynch and
Alex Shvartsman Eventually-serializable data services 113--156
King-Shan Lui and
Shmuel Zaks Scheduling in synchronous networks and
the greedy algorithm . . . . . . . . . . 157--183
Amos Beimel and
Matthew Franklin Reliable communication over partially
authenticated networks . . . . . . . . . 185--210
Soma Chaudhuri and
Maurice Herlihy and
Mark R. Tuttle Wait-free implementations in
message-passing systems . . . . . . . . 211--245
Johannes E. Gehrke and
C. Greg Plaxton and
Rajmohan Rajaraman Rapid convergence of a local load
balancing algorithm for asynchronous
rings . . . . . . . . . . . . . . . . . 247--265
Marios Mavronicolas and
Dan Roth Linearizable read/write objects . . . . 267--319
Andris Ambainis and
Sanjay Jain and
Arun Sharma Ordinal mind change complexity of
language identification . . . . . . . . 323--343
R. Fadel and
K. V. Jakobsen and
J. Katajainen and
J. Teuhola Heaps and heapsort on secondary storage 345--362
Micheal E. Houle and
Ewan Tempero and
Gavin Turner Optimal dimension-exchange token
distribution on complete binary trees 363--376
Chuchang Liu and
Mehmet A. Orgun Verification of reactive systems using
temporal logic with clocks . . . . . . . 377--408
Ian A. Mason and
Carolyn L. Talcott Actor languages: Their syntax,
semantics, translation, and equivalence 409--467
Alan Roberts and
Antonios Symvonis On-line matching routing on trees . . . 469--488
Yan Zhang Specifying causality in action theories:
a default logic approach . . . . . . . . 489--513
Alexander E. Andreev and
Andrea E. F. Clementi and
José D. P. Rolim Worst-case hardness suffices for
derandomization: a new method for
hardness-randomness trade-offs . . . . . 3--18
Yair Bartal and
Stefano Leonardi On-line routing in all-optical networks 19--39
Frédérique Bassino and
Marie-Pierre Béal and
Dominique Perrin Enumerative sequences of leaves and
nodes in rational trees . . . . . . . . 41--60
Bruno Durand Tilings and quasiperiodicity . . . . . . 61--75
Péter L. Erd\Hos and
Michael A. Steel and
László A. Székely and
Tandy J. Warnow A few logs suffice to build (almost) all
trees: Part II . . . . . . . . . . . . . 77--118
Thomas Erlebach and
Klaus Jansen and
Christos Kaklamanis and
Milena Mihail and
Pino Persiano Optimal wavelength routing on directed
fiber trees . . . . . . . . . . . . . . 119--137
Sven O. Krumke and
Hartmut Noltemeier and
Hans-C. Wirth and
Madhav V. Marathe and
R. Ravi and
S. S. Ravi and
R. Sundaram Improving spanning trees by upgrading
nodes . . . . . . . . . . . . . . . . . 139--155
Giovanni Manzini and
Luciano Margara A complete and efficiently computable
topological classification of
$D$-dimensional linear cellular automata
over $Z_m$ . . . . . . . . . . . . . . . 157--177
Krzysztof R. Apt The essence of constraint propagation 179--210
Ahmed Bouajjani and
Peter Habermehl Symbolic reachability analysis of
FIFO-channel systems with nonregular
sets of configurations . . . . . . . . . 211--250
Olaf Burkart and
Bernhard Steffen Model checking the full modal
mu-calculus for infinite sequential
processes . . . . . . . . . . . . . . . 251--270
E. P. de Vink and
J. J. M. M. Rutten Bisimulation for probabilistic
transition systems: a coalgebraic
approach . . . . . . . . . . . . . . . . 271--293
Pietro Di Gianantonio An abstract data type for real numbers 295--326
Yuxi Fu Variations on mobile processes . . . . . 327--368
Thomas A. Henzinger and
Peter W. Kopke Discrete-time control for rectangular
hybrid automata . . . . . . . . . . . . 369--392
Kohei Honda and
Nobuko Yoshida Game-theoretic analysis of call-by-value
computation . . . . . . . . . . . . . . 393--456
Davide Sangiorgi The name discipline of uniform
receptiveness . . . . . . . . . . . . . 457--493
S. Abramsky and
S. J. Gay and
R. Nagarajan A specification structure for
deadlock-freedom of synchronous
processes . . . . . . . . . . . . . . . 1--53
Patrick Cegielski and
Denis Richard On arithmetical first-order theories
allowing encoding and decoding of lists 55--75
Gilberto Filé and
Francesco Ranzato The powerset operator on abstract
interpretations . . . . . . . . . . . . 77--111
Feng Cao and
Al Borchers Optimal transmission schedules for
lightwave networks embedded with de
Bruijn graphs . . . . . . . . . . . . . 113--131
Yuri Gurevich and
Andrei Voronkov Monadic simultaneous rigid
$E$-unification . . . . . . . . . . . . 133--152
Elena Marchiori Design of abstract domains using
first-order logic . . . . . . . . . . . 153--179
Lo\"\ic Colson On diagonal fixed points of increasing
functions . . . . . . . . . . . . . . . 181--186
Catherine Dufourd and
Alain Finkel A polynomial $\lambda$-bisimilar
normalization for reset Petri nets . . . 187--194
O. Kullmann New methods for $3$-SAT decision and
worst-case analysis . . . . . . . . . . 1--72
Xavier Droubay and
Giuseppe Pirillo Palindromes and Sturmian words . . . . . 73--85
Owen Rambow and
Giorgio Satta Independent parallelism in finite
copying parallel rewriting systems . . . 87--120
Jean-Denis Fouks Towards an algorithmic theory of
adaptation . . . . . . . . . . . . . . . 121--142
Changwook Kim and
Tae Eui Jeong HRNCE grammars --- a hypergraph
generating system with an eNCE way of
rewriting . . . . . . . . . . . . . . . 143--178
Wei-Kuan Shih and
Wen-Lian Hsu A new planarity test . . . . . . . . . . 179--191
Sui-Xiang Gao and
Xiao-Dong Hu and
Weili Wu Nontrivial monotone weakly symmetric
Boolean functions with six variables are
elusive . . . . . . . . . . . . . . . . 193--197
Matthias Baaz Note on the generalization of
calculations . . . . . . . . . . . . . . 3--11
Lev D. Beklemishev Parameter free induction and provably
total computable functions . . . . . . . 13--33
Bruno Courcelle The monadic second-order logic of graphs
XI: Hierarchical decompositions of
connected graphs . . . . . . . . . . . . 35--58
Yu. L. Ershov On $d$-Spaces . . . . . . . . . . . . . 59--72
Erich Grädel and
Martin Otto On logics with two variables . . . . . . 73--113
Philippe de Groote An algebraic correctness criterion for
intuitionistic multiplicative proof-nets 115--134
Bernhard Heinemann Temporal aspects of the modal logic of
subset spaces . . . . . . . . . . . . . 135--155
Jean-Yves Marion From multiple sequent for additive
linear logic to decision procedures for
free lattices . . . . . . . . . . . . . 157--172
Alexei Lisitsa and
Vladimir Sazonov Linear ordering on graphs, anti-founded
sets and polynomial time computability 173--213
Volker Diekert and
Yuri Matiyasevich and
Anca Muscholl Solving word equations modulo partial
commutations . . . . . . . . . . . . . . 215--235
Martin Otto Bisimulation-invariant PTIME and
higher-dimensional $\mu$-calculus . . . 237--265
G. Perrier A PSPACE-complete fragment of
second-order linear logic . . . . . . . 267--289
Gregory S. Tseytin A formalization of reasoning not derived
from standard predicate logic . . . . . 291--317
Andrei Voronkov Simultaneous rigid $E$-unification and
other decision problems related to the
Herbrand theorem . . . . . . . . . . . . 319--352
Maryse Pelletier and
Jacques Sakarovitch On the representation of finite
deterministic $2$-tape automata . . . . 1--63
Pierluigi Crescenzi and
Luca Trevisan Max NP-completeness made easy . . . . . 65--79
Zsuzsanna Róka Simulations between cellular automata on
Cayley graphs . . . . . . . . . . . . . 81--111
Andrea E. F. Clementi and
Luca Trevisan Improved non-approximability results for
minimum vertex cover with density
constraints . . . . . . . . . . . . . . 113--128
Wai-Fong Chuan Sturmian morphisms and $\alpha$-words 129--148
Ismo Hakala and
Juha Kortelainen On the system of word equations $x_0
u^i_1 x_1 u^i_2 x_2 u^i_3 x_3 = y_0
v^i_1 y_1 v^i_2 y_2 v^i_3 y_3 ( i =0, 1,
2, \ldots{})$ in a free monoid . . . . . 149--161
Pak-Ken Wong Optimal path cover problem on block
graphs . . . . . . . . . . . . . . . . . 163--169
J. M. Basart and
P. Guitart A solution for the coloured cubes
problem . . . . . . . . . . . . . . . . 171--176
Manfred Göbel The ``smallest'' ring of polynomial
invariants of a permutation group which
has no finite SAGBI bases w.r.t. any
admissible order . . . . . . . . . . . . 177--184
Jack H. Lutz and
David L. Schweizer Feasible reductions to
Kolmogorov--Loveland stochastic
sequences . . . . . . . . . . . . . . . 185--194
Leonard M. Adleman and
Jonathan DeMarrais and
Ming-Deh Huang A subexponential algorithm for discrete
logarithms over hyperelliptic curves of
large genus over GF$(q)$ . . . . . . . . 7--18
Seng Kiat Chua and
Ka Hin Leung and
San Ling Attack on RSA-type cryptosystems based
on singular cubic curves over $Z/nZ$ . . 19--27
Thomas W. Cusick The Ajtai random class of lattices . . . 29--36
Dengguo Feng Three characterizations of
correlation-immune functions over rings
$Z_N$ . . . . . . . . . . . . . . . . . 37--43
Dieter Gollmann Dual bases and bit-serial multiplication
in $F_{q^n}$ . . . . . . . . . . . . . . 45--59
Andrew Klapper and
Jinzhong Xu Algebraic feedback shift registers . . . 61--92
Harald Niederreiter and
Michael Vielhaber An algorithm for shifted continued
fraction expansions in parallel linear
time . . . . . . . . . . . . . . . . . . 93--104
Valtteri Niemi and
Ari Renvall Efficient voting with no selling of
votes . . . . . . . . . . . . . . . . . 105--116
Joseph Ó Ruanaidh and
Holger Petersen and
Alexander Herrigel and
Shelby Pereira and
Thierry Pun Cryptographic copyright protection for
digital images based on watermarking
techniques . . . . . . . . . . . . . . . 117--142
Renji Tao and
Shihua Chen On finite automaton public-key
cryptosystem . . . . . . . . . . . . . . 143--172
Vijay Varadharajan and
Khanh Quoc Nguyen and
Yi Mu On the design of efficient RSA-based
off-line electronic cash schemes . . . . 173--184
Chunru Zhang and
Kwok-Yan Lam and
Sushil Jajodia Scalable threshold closure . . . . . . . 185--206
Yuliang Zheng and
Xian-Mo Zhang and
Hideki Imai Restriction, terms and nonlinearity of
Boolean functions . . . . . . . . . . . 207--223
Samson Abramsky and
Guy McCusker Full abstraction for Idealized Algol
with passive expressions . . . . . . . . 3--42
G. M. Bierman A classical linear $\lambda$-calculus 43--78
Vincent Danos and
Laurent Regnier Reversible, irreversible and optimal
$\lambda$-machines . . . . . . . . . . . 79--97
Stefano Guerrini A general theory of sharing graphs . . . 99--151
Hongde Hu and
Andre Joyal Coherence completions of categories . . 153--184
Naoki Kobayashi and
Toshihiro Shimizu and
Akinori Yonezawa Distributed concurrent linear logic
programming . . . . . . . . . . . . . . 185--220
François Métayer Polynomial equivalence among systems
LLNC, LLNC a and LLNC 0 . . . . . . . . 221--229
David N. Turner and
Philip Wadler Operational interpretations of linear
logic . . . . . . . . . . . . . . . . . 231--248
Jean-Yves Girard On denotational completeness . . . . . . 249--273
Jean-Yves Girard Coherent Banach spaces: a continuous
denotational semantics . . . . . . . . . 275--297
Patrick D. Lincoln and
John C. Mitchell and
Andre Scedrov Optimization complexity of linear logic
proof games . . . . . . . . . . . . . . 299--331
Mitsuhiro Okada Phase semantic cut-elimination and
normalization proofs of first- and
higher-order linear logic . . . . . . . 333--396
Anonymous Editorial(s) . . . . . . . . . . . . . . 1--3
Andrew D. Gordon Bisimilarity as a theory of functional
programming . . . . . . . . . . . . . . 5--47
P. J. Freyd and
others Bireflectivity . . . . . . . . . . . . . 49--76
Philippa Gardner Closed action calculi . . . . . . . . . 77--103
Alan Jeffrey A fully abstract semantics for a
higher-order functional language with
nondeterministic computation . . . . . . 105--150
Neil D. Jones LOGSPACE and PTIME characterized by
programming languages . . . . . . . . . 151--174
J. Maraist and
M. Odersky and
D. N. Turner and
P. Wadler Call-by-name, call-by-value,
call-by-need and the linear lambda
calculus . . . . . . . . . . . . . . . . 175--210
P. W. O'Hearn and
A. J. Power and
M. Takeyama and
R. D. Tennent Syntactic control of interference
revisited . . . . . . . . . . . . . . . 211--252
Peter W. O'Hearn and
Uday S. Reddy Objects, interference, and the Yoneda
embedding . . . . . . . . . . . . . . . 253--282
Anonymous Index . . . . . . . . . . . . . . . . . 283--283
Anonymous Editorial(s) . . . . . . . . . . . . . . 1--2
A. E. Eiben and
G. Rudolph Theory of evolutionary algorithms: a
bird's eye view . . . . . . . . . . . . 3--9
J. A. Lozano and
P. Larrañaga and
M. Graña and
F. X. Albizuri Genetic algorithms: bridging the
convergence gap . . . . . . . . . . . . 11--22
Jun He and
Lishan Kang On the convergence rates of genetic
algorithms . . . . . . . . . . . . . . . 23--39
Erik van Nimwegen and
James P. Crutchfield and
Melanie Mitchell Statistical Dynamics of the Royal Road
Genetic Algorithm . . . . . . . . . . . 41--102
Michael D. Vose Random heuristic search . . . . . . . . 103--142
Walter A. Kosters and
Joost N. Kok and
Patrik Floréen Fourier Analysis of Genetic Algorithms 143--175
Walter Cedeño and
V. Rao Vemuri Analysis of speciation and niching in
the multi-niche crowding GA . . . . . . 177--197
Anonymous Index . . . . . . . . . . . . . . . . . 199--199
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
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
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
Petr K\ocircurka Erratum to: Entropy of Turing machines
with moving head . . . . . . . . . . . . 2999--3000
Aviezri S. Fraenkel and
Jamie Simpson Corrigendum to ``The exact number of
squares in Fibonacci words'' [Theoret.
Comput. Sci. \bf 218 (1) (1999) 95--106] 122