Last update:
Wed Jul 9 22:04:47 MDT 2008
V. Mihalache and
Gheorghe P\uaun and
Grzegorz Rozenberg and
Arto Salomaa Generating strings by replication: a
simple case . . . . . . . . . . . . . . ??
Douglas R. Smith Structure and Design of Global Search
Algorithms . . . . . . . . . . . . . . . ??
Edward G. Coffman and
Brian Randell Performance Predictions for Extended
Paged Memories . . . . . . . . . . . . . 1--13
Donald E. Knuth Optimum Binary Search Trees . . . . . . 14--25
Wladyslaw M. Turski A Model for Data Structures and Its
Applications. I . . . . . . . . . . . . 26--34
Niklaus Wirth The Programming Language Pascal . . . . 35--63
Volker Claus Ein Vollständigkeitssatz für Programme und
Schaltkreise. (German) [A Completeness
Condition for Programs and Circuits] . . 64--78
Donald E. Knuth Top-Down Syntax Analysis . . . . . . . . 79--110
Hans Langmaack Application of Regular Canonical Systems
to Grammars Translatable from Left to
Right . . . . . . . . . . . . . . . . . 111--114
Edsger W. Dijkstra Hierarchical Ordering of Sequential
Processes . . . . . . . . . . . . . . . 115--138
A. Schönhage Schnelle Berechnung von
Kettenbruchentwicklungen. (German) [Fast
Calculation of Expansions of Continued
Fractions] . . . . . . . . . . . . . . . 139--144
F. K. Hwang and
Shen Lin Optimal Merging of 2 Elements with $n$
Elements . . . . . . . . . . . . . . . . 145--158
Dominique Perrin and
J.-F. Perrot Congruences et Automorphismes des
Automates Finis. (French) [Congruences
and Automorphisms of Finite Automata] 159--172
Rudolf Bayer and
Edward M. McCreight Organization and Maintenance of Large
Ordered Indexes . . . . . . . . . . . . 173--189
Per Brinch Hansen A Comparison of Two Synchronizing
Concepts . . . . . . . . . . . . . . . . 190--199
Edward G. Coffman and
R. L. Graham Optimal Scheduling for Two-Processor
Systems . . . . . . . . . . . . . . . . 200--213
M. Clint and
C. A. R. Hoare Program Proving: Jumps and Functions . . 214--224
Gerd Kaufholz Der programmierbare endliche Automat.
(German) [The Programmable Finite
Automaton] . . . . . . . . . . . . . . . 225--241
Grzegorz Rozenberg Direction Controlled Programmed Grammars 242--252
Hermann Walter Inhibitionsfelder. (German) [Inhibition
fields] . . . . . . . . . . . . . . . . 253--269
C. Anthony R. Hoare Proof of correctness of data
representations . . . . . . . . . . . . 271--281
Wladyslaw M. Turski A Model for Data Structures and its
Applications. (Part II) . . . . . . . . 282--289
Rudolf Bayer Symmetric Binary B-Trees: Data Structure
and Maintenance Algorithms . . . . . . . 290--306
T. C. Hu and
K. C. Tan Least Upper Bound on the Cost of Optimum
Binary Search Trees . . . . . . . . . . 307--310
A. C. McKellar and
C. K. Wong Bounds on Algorithms for String
Generation . . . . . . . . . . . . . . . 311--319
Volker Strassen Berechnung und Programm. I. (German)
[Calculation and Programs. I] . . . . . 320--335
Juris Hartmanis On Non-Determinancy in Simple Computing
Devices . . . . . . . . . . . . . . . . 336--344
Claus-Peter Schnorr and
H. Stimm Endliche Automaten und Zufallsfolgen.
(German) [Finite Automata and Random
Sequnces] . . . . . . . . . . . . . . . 345--359
G. Schott Automatic Analysis of Inflectional
Morphemes in German Nouns . . . . . . . 360--374
P. J. Courtois and
F. Heymans and
David Lorge Parnas Comments on \em A Comparison of Two
Synchronizing Concepts by Per Brinch
Hansen . . . . . . . . . . . . . . . . . 375--376
Sòren Lauesen Job Scheduling Guaranteeing Reasonable
Turn-Around Times . . . . . . . . . . . 1--11
T. Anderson and
J. Eve and
James J. Horning Efficient \em LR($1$) Parsers . . . . . 12--39
Arto K. Salomaa On Sentential Forms of Context-Free
Grammars . . . . . . . . . . . . . . . . 40--49
M. Clint Program Proving: Co-routines . . . . . . 50--63
Volker Strassen Berechnung und Programm. II. (German)
[Calculation and Programs. II] . . . . . 64--79
H.-J. Stoß Rangierkomplexität von Permutationen.
(German) [The Switching Complexity of
Permutations] . . . . . . . . . . . . . 80--96
David Gries Describing an Algorithm by Hopcroft . . 97--109
Hans Langmaack On Correct Procedure Parameter
Transmission in Higher Programming
Languages . . . . . . . . . . . . . . . 110--142
H. J. Genrich and
Kurt Lautenbach Synchronisationsgraphen. (German)
[Synchronization Graphs] . . . . . . . . 143--161
Karel Culík and
Michael A. Arbib Sequential and Jumping Machines and
their Relation to Computers . . . . . . 162--171
Hans-Dieter Ehrich Minimale und $m$-minimale
Variablenmengen für partielle Boole'sche
Funktionen. (German) [Minimal and
$m$-Minimal Sets of Variables for
Partial Boolean Functions] . . . . . . . 172--179
Luc Boasson and
Maurice Nivat Sur diverses familles de langages fermées
par transductions rationelle. (French)
[On Diverse Families of Languages Closed
by Rational Transductions] . . . . . . . 180--188
Per Brinch Hansen A Reply to Comments on \em A Comparison
of Two Synchronizing Concepts . . . . . 189--190
Jeffrey D. Ullman Fast Algorithms for the Elimination of
Common Subexpressions . . . . . . . . . 191--213
Grzegorz Rozenberg and
Aristid Lindenmayer Developmental Systems with Locally
Catenative Formulas . . . . . . . . . . 214--248
Walter J. Savitch A Note on Multihead Automata and
Context-Sensitive Languages . . . . . . 249--252
Peter Kandzia Zur Theorie der Partiell-linearen
Realisierungen endlicher Automaten.
(German) [On the Theory of Partial
Linear Realizations of Finite Automata] 253--282
Volker Claus Die mittlere Additionsdauer eines
Paralleladdierwerks. (German) [The
Median Addition Time of a Parallel
Adder] . . . . . . . . . . . . . . . . . 283--291
Jay Earley Relational Level Data Structures for
Programming Languages . . . . . . . . . 293--309
Hans Langmaack On Procedures as Open Subroutines. I . . 311--333
C. A. R. Hoare and
Niklaus Wirth An Axiomatic Definition of the
Programming Language Pascal . . . . . . 335--355
W. Menzel An Extension of the Theory of Learning
Systems . . . . . . . . . . . . . . . . 357--381
Luc Boasson and
J. P. Crestin and
Maurice Nivat Familles de langages translatables et
fermées par crochet. (French) [Families
of Translatable Bracket-Closed
Languages] . . . . . . . . . . . . . . . 383--393
Erol Gelenbe and
Paolo Tiberio and
J. C. A. Boekhorst Page Size in Demand Paging Systems . . . 1--23
Maurice Schlumberger and
Jean Vuillemin Optimal Disk Merge Patterns . . . . . . 25--35
A. Nahapetian Node Flows in Graphs with Conservative
Flow . . . . . . . . . . . . . . . . . . 37--41
B. L. Fox Reducing the Number of Multiplikations
in Iterative Processes . . . . . . . . . 43--45
A. Nico Habermann Critical Comments on the Programming
Language Pascal . . . . . . . . . . . . 47--57
Armin B. Cremers Normal Forms for Context-Sensitive
Grammars . . . . . . . . . . . . . . . . 59--73
Lutz Eichner Lineare Realisierbarkeit endlicher
Automaten über endlichen Körpern. (German)
[Linearly Realizable Finite Automata
over Finite Fields] . . . . . . . . . . 75--100
Terry Betteridge An Analytic Storage Allocation Model . . 101--122
Ellis Horowitz A Unified View of the Complexity of
Evaluation and Interpolation . . . . . . 123--133
C. A. R. Hoare and
Peter E. Lauer Consistent and Complementary Formal
Theories of the Semantics of Programming
Languages . . . . . . . . . . . . . . . 135--153
P. F. Schuler Weakly Context-Sensitive Languages as
Model for Programming Languages . . . . 155--170
Gerd Kaufholz Über die Vernetzungsstruktur von
Maschinen. (German) [On the Network
Structure of Machines] . . . . . . . . . 171--186
David B. Benson An Abstract Machine Theory for Formal
Language Parsers . . . . . . . . . . . . 187--202
David J. Kuck and
Yoichi Muraoka Bounds on the Parallel Evaluation of
Arithmetic Expressions Using
Associativity and Commutativity . . . . 203--216
Wolfgang J. Paul and
H.-J. Stoß Zur Komplexität von Sortierproblemen.
(German) [On the Complexity of the
Sorting Problem] . . . . . . . . . . . . 217--225
Hans Langmaack On Procedures as Open Subroutines. II 227--241
Zohar Manna and
Amir Pnueli Axiomatic Approach to Total Correctness
of Programs . . . . . . . . . . . . . . 243--263
Andrzej Ehrenfeucht and
Grzegorz Rozenberg Nonterminals Versus Homomorphisms in
Defining Languages for Some Classes of
Rewriting Systems . . . . . . . . . . . 265--283
Martti Penttonen On Derivation Languages Corresponding to
Context-Free Grammars . . . . . . . . . 285--291
Jean Berstel Sur une Conjecture de S. Greibach . . . 293--295
C. A. R. Hoare and
N. Wirth Addenda and Corrigenda to \em An
Axiomatic Definition of the Programming
Language Pascal . . . . . . . . . . . . 296--296
C. C. Gotlieb and
Frank Wm. Tompa Choosing a Storage Schema . . . . . . . 297--319
Erol Gelenbe and
Jaques Lenfant and
Dominique Potier Analyse d'un algorithme de gestion
simultanée Mémoire centrale---Disque de
pagination. (French) [Analysis of a
Simultaneous Management Algorithm for
Central Memory and Paging Disk] . . . . 321--345
M. R. Garey and
R. L. Graham Performance Bounds on the Splitting
Algorithm for Binary Testing . . . . . . 347--355
Mogens Nielsen and
Grzegorz Rozenberg and
Arto Salomaa and
Sven Skyum Nonterminals, Homomorphisms and Codings
in Different Variations of OL-Systems.
II. Nondeterministic Systems . . . . . . 357--364
K. Ecker and
H. Ratschek Eigenschaften der von linearen Automaten
erkennbaren Worte. (German)
[Characteristics of Words Recognized by
Linear Automata] . . . . . . . . . . . . 365--383
Lutz Eichner Total lineare Realisierbarkeit endlicher
Automaten. (German) [Total Linear
Realizability of Finite Automata] . . . 385--397
Raphael A. Finkel and
Jon Louis Bentley Quad Trees: A Data Structure for
Retrieval on Composite Keys . . . . . . 1--9
A. Brandwajn A Model of a Time Sharing Virtual Memory
System Solved Using Equivalence and
Decomposition Methods . . . . . . . . . 11--47
Guy Fayolle and
Erol Gelenbe and
Jacques Labetoulle and
D. Bastin The Stability Problem of Broadcast
Packet Switching Computer Networks . . . 49--53
Günter Hotz Sequentielle Analyse kontextfreier
Sprachen. (German) [Sequential Analysis
of Context-Free Grammars] . . . . . . . 55--75
Nabil A. Khabbaz Multipass Precedence Analysis . . . . . 77--85
Mogens Nielsen and
Grzegorz Rozenberg and
Arto Salomaa and
Sven Skyum Nonterminals, Homomorphisms and Codings
in Different Variations of OL-Systems.
I. Deterministic Systems . . . . . . . . 87--106
Yuri Breitbart and
Allen Reiter Algorithms for Fast Evaluation of
Boolean Expressions . . . . . . . . . . 107--116
Glen Newton Proving Properties of Interacting
Processes . . . . . . . . . . . . . . . 117--126
Jay M. Spitzen and
Ben Wegbreit The Verification and Synthesis of Data
Structures . . . . . . . . . . . . . . . 127--144
Shigeru Igarashi and
Ralph L. London and
David C. Luckham Automatic program verification. I. A
logical basis and its implementation . . 145--182
Jay Earley Ambiguity and Precedence in Syntax
Description . . . . . . . . . . . . . . 183--192
Oscar H. Ibarra and
Chul E. Kim On $3$-Head Versus $2$-Head Finite
Automata . . . . . . . . . . . . . . . . 193--200
Hans-Dieter Ehrich Grundlagen einer Theorie der
Datenstrukturen und Zugriffssysteme.
Teil I: Datenstrukturen und Schemata.
(German) [Foundation of a Theory of Data
Structures and Access Systems. Part I.
Data Structures and Schemata] . . . . . 201--211
James F. Gimpel Nonlinear Pattern Theory . . . . . . . . 213--229
Olivier Lecarme and
Pierre Desjardins More Comments on the Programming
Language Pascal . . . . . . . . . . . . 231--243
Paul M. Zislis Semantic Decomposition of Computer
Programs: An Aid to Program Testing . . 243--269
J.-P. Lévy Automatic Correction of Syntax-Errors in
Programming Languages . . . . . . . . . 271--292
Leonidas J. Guibas A Principle of Independence for Binary
Tree Searching . . . . . . . . . . . . . 293--298
Hans-Dieter Ehrich Grundlagen einer Theorie der
Datenstrukturen und Zugriffssysteme.
Teil II: Zugriffssysteme. (German)
[Foundation of a Theory of Data
Structures and Access Systems. Part II.
Access Systems] . . . . . . . . . . . . 299--310
Yuri Breitbart and
Allen Reiter A Branch-and-Bound Algorithm to Obtain
an Optimal Evaluation Tree for Monotonic
Boolean Functions . . . . . . . . . . . 311--319
Wolfgang J. Paul Boolesche Minimalpolynome und
Überdeckungsprobleme. (German) [Boolean
Minimal Polynomials and Coverage
Problems] . . . . . . . . . . . . . . . 321--336
Barry K. Rosen Deriving Graphs from Graphs by Applying
a Production . . . . . . . . . . . . . . 337--357
P. F. Schuler WCS-Analysis of the Context-Sensitive 359--371
Mogens Nielsen EOL systems with control devices . . . . 373--386
Adriaan van Wijngaarden and
B. J. Mailloux and
J. E. L. Peck and
C. H. A. Koster and
M. Sintzoff and
C. H. Lindsey and
L. G. L. T. Meertens and
R. G. Fisker Revised Report on the Algorithmic
Language ALGOL 68 . . . . . . . . . . . 1--236
J. Nehmer Dispatcher Primitives for the
Construction of Operating System Kernels 237--255
Wolfgang K. Giloi and
J. Encarnação and
S. Savitt Interactive Graphics on Intelligent
Terminals in a Time-Sharing Environment 257--271
John R. Rice Parallel Algorithms for Adaptive
Quadrature II Metalgorithm Correctness 273--285
Kurt Mehlhorn Nearly Optimal Binary Search Trees . . . 287--295
P. E. Lauer and
Roy H. Campbell Formal Semantics of a Class of
High-Level Primitives for Coordinating
Concurrent Processes . . . . . . . . . . 297--332
Shmuel M. Katz and
Zohar Manna A Closer Look at Termination . . . . . . 333--352
Peter Deussen A Decidability Criterion for van
Wijngaarden Grammars . . . . . . . . . . 353--375
Seymour Ginsburg and
Edwin H. Spanier Substitution of Grammar Forms . . . . . 377--386
P. F. Schuler A Note on Degrees of Context-Sensitivity 387--394
E. G. Coffman, Jr. and
Ravi Sethi Algorithms Minimizing Mean Flow Time:
Schedule Length Properties . . . . . . . 1--14
Erich J. Neuhold and
T. Weller Specification and Proving of Command
Programs . . . . . . . . . . . . . . . . 15--40
John L. Darlington and
Rod M. Burstall A System which Automatically Improves
Programs . . . . . . . . . . . . . . . . 41--60
A. P. Ershov Axiomatics for Memory Allocation . . . . 61--75
Zvi Galil Hierarchies of Complete Problems . . . . 77--88
Ronald V. Book and
Ashok K. Chandra Inherently Nonplanar Automata . . . . . 89--94
Burkhard Monien Transformational Methods and their
Application to Complexity Problems . . . 95--108
E. R. Anderson and
F. C. Belz and
E. K. Blum SEMANOL(73). A Metalanguage for
Programming the Semantics of Programming
Languages . . . . . . . . . . . . . . . 109--131
Michael Karr On affine relationships among variables
of a program . . . . . . . . . . . . . . 133--151
Robert T. Moenck Another Polynomial Homomorphism . . . . 153--169
Robert Endre Tarjan Edge-Disjoint Spanning Trees and
Depth-First Search . . . . . . . . . . . 171--185
W. R. Franta The Mathematical Analysis of the
Computer System Modeled as a Two Stage
Cyclic Queue . . . . . . . . . . . . . . 187--209
Gary J. Nutt Some Resource Allocation Policies in a
Multi Associative Processor . . . . . . 211--225
Hans Albrecht Schmid On the Efficient Implementation of
Conditional Critical Regions and the
Construction of Monitors . . . . . . . . 227--249
P.-J. Courtois and
H. Vantilborgh A Decomposable Model of Program Paging
Behaviour . . . . . . . . . . . . . . . 251--275
Roland C. Backhouse An Alternative Approach to the
Improvement of \em LR($k$) Parsers . . . 277--296
Hans Jürgen Schneider and
Hartmut Ehrig Grammars on Partial Graphs . . . . . . . 297--316
E. A. Ashcroft and
M. Clint and
C. A. R. Hoare Remarks on \em Program Proving: Jumps
and Functions by M. Clint and C. A. R.
Hoare . . . . . . . . . . . . . . . . . 317--318
Susan Speer Owicki and
David Gries An Axiomatic Proof Technique for
Parallel Programs I . . . . . . . . . . 319--340
Jacques Cohen and
Martin Roth On the Implementation of Strassen's Fast
Multiplication Algorithm . . . . . . . . 341--355
Edsger W. Dijkstra On a Gauntlet Thrown by David Gries . . 357--359
Kenichi Taniguchi and
Tadeo Kasami An $O(n)$ Algorithm for Computing the
Set of Available Expressions of
$D$-Charts . . . . . . . . . . . . . . . 361--364
A. Brandwajn A Model of a Virtual Memory System . . . 365--386
R. M. Wharton Resolution of Ambiguity in Parsing . . . 387--395
Hermann A. Maurer and
D. Wood On Grammar Forms with Terminal Context 397--402
Werner Heise Optimal Codes, $n$-Arcs and Laguerre
Geometry . . . . . . . . . . . . . . . . 403--406
Andrzej Ehrenfeucht and
Grzegorz Rozenberg On Proving that Certain Languages are
not ETOL . . . . . . . . . . . . . . . . 407--415
R. Zuczek A New Approach to Parallel Computing . . 1--13
Leslie Lamport The Synchronization of Independent
Processes . . . . . . . . . . . . . . . 15--34
Erol Gelenbe and
Richard R. Muntz Probabilistic Models of Computer
Systems---Part I (Exact Results) . . . . 35--60
Ole Lehrmann Madsen and
Bent Bruun Kristensen \em LR-Parsing of Extended Context Free
Grammars . . . . . . . . . . . . . . . . 61--73
H. K.-G. Walter Grammarforms and Grammarhomomorphisms 75--93
Claus-Peter Schnorr The Network Complexity and the Turing
Machine Complexity of Finite Functions 95--107
Donald P. Gaver and
George Humfeld Multitype Multiprogramming Models . . . 111--121
Erol Gelenbe and
Guy Pujolle The Behaviour of a Single-Queue in a
General Queueing Network . . . . . . . . 123--136
Thomas Giammo Validation of a Computer Performance
Model of the Exponential Queuing Network
Family . . . . . . . . . . . . . . . . . 137--152
Carl E. Landwehr An Endogenous Priority Model for Load
Control in Combined Batch-Interactive
Computer Systems . . . . . . . . . . . . 153--166
Jeffrey P. Buzen Fundamental Operational Laws of Computer
System Performance . . . . . . . . . . . 167--182
Jacques Labetoulle and
Guy Pujolle A Study of Queueing Networks with
Deterministic Service and Application to
Computer Networks . . . . . . . . . . . 183--195
Peter J. Denning and
Kevin C. Kahn and
Jacques Leroudier and
Dominique Potier and
Rajan Suri Optimal Multiprogramming . . . . . . . . 197--216
Jeffrey R. Spirn Multi-Queue Scheduling of Two Tasks . . 217--226
Peter D. Welch On the Self Contained Modelling of DB/DC
Systems . . . . . . . . . . . . . . . . 227--247
David Pager A Practical General Method for
Constructing \em LR($k$) Parsers . . . . 249--268
Werner Kern Speicheroptimale Formelübersetzung.
(German) [Storage Optimal Formula
Translation] . . . . . . . . . . . . . . 269--287
Arnold L. Rosenberg and
Larry J. Stockmeyer Storage Schemes for Boundedly Extendible
Arrays . . . . . . . . . . . . . . . . . 289--303
John B. Kam and
Jeffrey D. Ullman Monotone Data Flow Analysis Frameworks 305--317
Robert E. Shostak On the Role of Unification in Mechanical
Theorem Proving . . . . . . . . . . . . 319--323
P. E. Lauer and
Roy H. Campbell Addenda and Corrigenda: \em Formal
Semantics of a Class of High-Level
Primitives for Coordinating Concurrent
Processes . . . . . . . . . . . . . . . 325--325
Robert Sedgewick The Analysis of Quicksort Programs . . . 327--355
Tomasz Kowaltowski Axiomatic Approach to Side Effects and
General Jumps . . . . . . . . . . . . . 357--360
Donal T. MacVeigh, S. J. Effect of Data Representation on Cost of
Sparse Matrix Operations . . . . . . . . 361--394
A. A. Schönhage Schnelle Multiplikation von Polynomen
über Körpern der Charakteristik $2$.
(German) [Fast Multiplication of
Polynomials over Fields of
Characteristic $2$] . . . . . . . . . . 395--398
J.-F. Perrot Mono\"\ides syntactiques des langages
algébriques. (French) [Syntactic Monoids
of Algebraic Languages] . . . . . . . . 399--413
David A. Watt The Parsing Problem for Affix-Grammars 1--20
David C. Luckham and
Norihisa Suzuki Proof of Termination within a Weak Logic
of Programs . . . . . . . . . . . . . . 21--36
Mila E. Majster Extended Directed Graphs, a Formalism
for Structured Data and Data Structures 37--59
Isi Mitrani and
J. H. Hine Complete Parameterized Families of Job
Scheduling Strategies . . . . . . . . . 61--73
Hermann A. Maurer and
Arto Salomaa and
Derick Wood EOL Forms . . . . . . . . . . . . . . . 75--96
Robert D. Tennent Language Design Methods Based on
Semantic Principles . . . . . . . . . . 97--112
Bruce Russell On an Equivalence between Continuation
and Stack Semantics . . . . . . . . . . 113--123
Nissim Francez and
Boris Klebansky and
Amir Pnueli Backtracking in Recursive Computations 125--144
George W. Ernst Rules of Inference for Procedure Calls 145--152
Bo Munch-Andersen and
Torben U. Zahle Scheduling According to Job Priority
with Prevention of Deadlock and
Permanent Blocking . . . . . . . . . . . 153--175
Joel I. Seiferas Iterative Arrays with Direct Central
Control . . . . . . . . . . . . . . . . 177--192
Peter Deussen and
Kurt Mehlhorn Van Wijngaarden Grammars and Space
Complexity Class EXSPACE . . . . . . . . 193--199
Tilak Agerwala Some Extended Semaphore Primitives . . . 201--220
James E. Donahue Locations Considered Unnecessary . . . . 221--242
Fred Kröger LAR: A Logic of Algorithmic Reasoning 243--266
Yoshihide Igarashi General Properties of Derivational
Complexity . . . . . . . . . . . . . . . 267--283
Peter R. J. Asveld and
Joost Engelfriet Iterated Deterministic Substitution . . 285--302
J. Eve and
R. Kurki-Suonio On computing the transitive closure of a
relation . . . . . . . . . . . . . . . . 303--314
Robert D. Tennent On a New Approach to Representation
Independent Data Classes . . . . . . . . 315--324
N. Ramsperger Concurrent Access to Data . . . . . . . 325--334
Reidar Conradi Some Comments on \em Concurrent Readers
and Writers . . . . . . . . . . . . . . 335--340
Hisao Kameda and
Calvin C. Gotlieb A Feedback-Coupled Resource Allocation
Policy for Multiprogrammed Computer
Systems . . . . . . . . . . . . . . . . 341--357
Michel Parent and
Dominique Potier A Note on the Influence of Program
Loading on the Page Fault Rate . . . . . 359--370
Burkhard Monien The LBA-Problem and the Deterministic
Tape Complexity of Two-Way One-Counter
Languages over a One-Letter Alphabet . . 371--382
Burkhard Monien Corrigenda: \em Transformational Methods
and Their Application to Complexity
Problems . . . . . . . . . . . . . . . . 383--384
Rudolf Bayer and
Mario Schkolnick Concurrency of Operations on B-Trees . . 1--21
D. T. Lee and
C. K. Wong Worst-Case Analysis for Region and
Partial Region Searches in
Multidimensional Binary Search Trees and
Balanced Quad Trees . . . . . . . . . . 23--29
David Pager Eliminating Unit Productions from \em LR
Parsers . . . . . . . . . . . . . . . . 31--59
Stefan Sokolowski Axioms for Total Correctness . . . . . . 61--71
Jan Paredaens and
R. Vyncke A Class of Measures on Formal Languages 73--86
Jürgen Avenhaus and
Klaus Madlener Subrekursive Komplexität bei Gruppen: I.
Gruppen mit vorgeschriebener Komplexität.
(German) [Subrecursive Complexity on
Groups. I. Groups of Given Complexity] 87--104
Wilfried J. Hansen and
Hendrik Boom The Report on the Standard Hardware
Representation for ALGOL 68 . . . . . . 105--119
Claus H. Correll Proving Programs Correct through
Refinement . . . . . . . . . . . . . . . 121--132
Nissim Francez and
Amir Pnueli A Proof Method for Cyclic Programs . . . 133--157
Andrew Chi-Chih Yao On Random $2$-$3$ Trees . . . . . . . . 159--170
Ronald V. Book On the Complexity of Formal Grammars . . 171--181
Jürgen Avenhaus and
Klaus Madlener Subrekursive Komplexität bei Gruppen: II.
Der Einbettungssatz von Higman für
entscheidbare Gruppen. (German)
[Subrecursive Complexity on Groups. II.
Higman's Embedding Theorem for Decidable
Groups] . . . . . . . . . . . . . . . . 183--193
Terrence W. Pratt Program Analysis and Optimization
through Kernel-Control Decomposition . . 195--216
Christoph M. Hoffmann Design and Correctness of a Compiler for
a Non-Procedural Language . . . . . . . 217--241
Armin B. Cremers and
Thomas N. Hibbard Orthogonality of Information Structures 243--261
Edward G. Coffman, Jr. and
Joseph Y.-T. Leung and
D. W. Ting Bin Packing: Maximizing the Number of
Pieces Packed . . . . . . . . . . . . . 263--271
Arnold L. Rosenberg Data Encodings and Their Costs . . . . . 273--292
Armin B. Cremers and
Thomas N. Hibbard Functional Behavior in Data Spaces . . . 293--307
Manfred Stadel Die Zeitkomplexität des
Normalisierungsproblems bei
kontextsensitiven Grammatiken. (German)
[The Time Complexity of the
Normalization Problem of
Context-Sensitive Grammars] . . . . . . 309--329
Anthony E. Krzesinski and
Peter Teunissen A Multiclass Network Model of a Demand
Paging Computer System . . . . . . . . . 331--343
H. Hule and
Hermann A. Maurer and
Thomas Ottmann Good OL Forms . . . . . . . . . . . . . 345--353
Henry S. Warren, Jr. Static Main Storage Packing Problems . . 355--376
Peter Deussen A Unified Approach to the Generation and
the Acception of Formal Languages . . . 377--390
Ralph L. London and
John V. Guttag and
James J. Horning and
Butler W. Lampson and
J. G. Mitchell and
Gerald J. Popek Proof Rules for the Programming Language
Euclid . . . . . . . . . . . . . . . . . 1--26
John V. Guttag and
James J. Horning The algebraic specification of abstract
data types . . . . . . . . . . . . . . . 27--52
William E. Howden Algebraic Program Testing . . . . . . . 53--66
Teuvo Laurinolli Bounded Quantification and Relations
Recognizable by Finite Automata . . . . 67--78
Karel Culik II The Ultimate Equivalence Problem for DOL
Systems . . . . . . . . . . . . . . . . 79--84
Carlo Montangero and
Giuliano Pacini and
Maria Simi and
Franco Turini Information Management in Context Trees 85--94
Jane W. S. Liu and
C. L. Liu Performance Analysis of Multiprocessor
Systems Containing Functionally
Dedicated Processors . . . . . . . . . . 95--104
B. Bartsch and
G. Bolch A Conservation Law for G/G/m Queueing
Systems . . . . . . . . . . . . . . . . 105--109
Wolfgang J. Paul and
Robert Endre Tarjan Time-Space Trade-Offs in a Pebble Game 111--115
Mordechai Ben-Ari Ianov Pushdown Schemes Are Contained in
Boolean Recursive Schemes . . . . . . . 117--125
V. K. Sabel\cprimefel\cprimed Äquivalente Transformationen für
Flußdiagramme. (German) [Equivalence
Transformations of Program Schemes] . . 127--155
Peter J. L. Wallis The Design of a Portable Programming
Language . . . . . . . . . . . . . . . . 157--167
Detlef Wotschke and
Celia Wrathall A Note on Classes of Complements and the
LBA Problem . . . . . . . . . . . . . . 169--173
Reinhold Franck A Class of Linearly Parsable Graph
Grammars . . . . . . . . . . . . . . . . 175--201
Carlton J. Maxson Linear Regular Sets . . . . . . . . . . 203--208
J. Lewi and
Karel De Vlaminck and
J. Huens and
M. Huybrechts The \em ELL($1$) Parser Generator and
the Error Recovery Mechanism . . . . . . 209--228
Eric C. R. Hehner On Removing the Machine from the
Language . . . . . . . . . . . . . . . . 229--243
Wayne A. Babich and
Mehdi Jazayeri The Method of Attributes for Data Flow
Analysis: Part I. Exhaustive Analysis 245--264
Wayne A. Babich and
Mehdi Jazayeri The Method of Attributes for Data Flow
Analysis: Part II. Demand Analysis . . . 265--272
D. M. Choy and
C. K. Wong Optimal $\alpha-\beta$ trees with
capacity constraint . . . . . . . . . . 273--296
Joachim Biskup On the Complementation Rule for
Multivalued Dependencies in Database
Relations . . . . . . . . . . . . . . . 297--305
Augusto Celentano Incremental \em LR Parsers . . . . . . . 307--321
Robert Meersman and
Grzegorz Rozenberg Two-Level Meta-Controlled Substitution
Grammars . . . . . . . . . . . . . . . . 323--339
Lutz Eichner The Semigroups of Linearly Realizable
Finite Automata I . . . . . . . . . . . 341--367
Lutz Eichner The Semigroups of Linearly Realizable
Finite Automata II . . . . . . . . . . . 369--390
John Darlington A Synthesis of Several Sorting
Algorithms . . . . . . . . . . . . . . . 1--30
Gérard P. Huet and
Bernard Lang Proving And Applying Program
Transformations Expressed With
second-Order Patterns . . . . . . . . . 31--55
Abraham Silberschatz and
Brian Johnson Remarks on \em Some Comments on
Concurrent Readers and Writers by Reidar
Conradi . . . . . . . . . . . . . . . . 57--60
Leonard M. Adleman and
Kellogg S. Booth and
Franco P. Preparata and
Walter L. Ruzzo Improved Time and Space Bounds for
Boolean Matrix Multiplication . . . . . 61--70
William F. McColl Complexity hierarchies for Boolean
functions . . . . . . . . . . . . . . . 71--77
Seymour Ginsburg and
Derick Wood Precedence Relations in Grammar Forms 79--88
S. A. Greibach Hierarchy Theorems for Two-Way Finite
State Transducers . . . . . . . . . . . 89--101
C. Adams and
Erol Gelenbe and
J. Vicard An Experimentally Validated Model of the
Paging Drum . . . . . . . . . . . . . . 103--117
Cliff B. Jones Constructing a Theory of a Data
Structure as an Aid to Program
Development . . . . . . . . . . . . . . 119--137
Michael A. Arbib and
Suad Alagi\'c Proof Rules for Gotos . . . . . . . . . 139--148
Wolfgang Merzenich A Binary Operation on Trees and an
Initial Algebra Characterization for
Finite Tree Types . . . . . . . . . . . 149--168
Stephan Heilbrunner On the Definition of \em ELR($k$) and
\em ELL($k$) Grammars . . . . . . . . . 169--176
Wilf R. LaLonde Constructing \em LR Parsers for Regular
Right Part Grammars . . . . . . . . . . 177--193
D. Coleman and
J. W. Hughes The Clean Termination of Pascal Programs 195--210
Rodney W. Topor The Correctness of the Schorr-Waite List
Marking Algorithm . . . . . . . . . . . 211--221
David Gries The Schorr--Waite Graph Marking
Algorithm . . . . . . . . . . . . . . . 223--232
Michel Latteux Intersections de langages algébriques
bornés. (French) [Intersections of
Bounded Algebraic Languages] . . . . . . 233--240
Jean-Michel Autebert Opérations de Cylindre et applications
séquentielles gauches inverses. (French)
[Cylinder operations and sequential
left-inverse applications] . . . . . . . 241--258
Peter R. J. Asveld and
Joost Engelfriet Extended Linear Macro Grammars,
Iteration Grammars, and Register
Programs . . . . . . . . . . . . . . . . 259--285
Eric C. R. Hehner do considered od: A contribution to the
programming calculus . . . . . . . . . . 287--304
P. Bouchet Procédures de reprise dans les syst\`emes
de gestion de base de données réparties.
(French) [Recovery Techniques for
Distributed Database Management Systems] 305--340
Karl Unterauer Dynamic Weighted Binary Search Trees . . 341--362
R. Kemp The Average Number of Registers Needed
to Evaluate a Binary Tree Optimally . . 363--372
Jan van Leeuwen A Useful Lemma for Context-Free
Programmed Grammars . . . . . . . . . . 373--386
Axel van Lamsweerde and
Michel Sintzoff Formal Derivation of Strongly Correct
Concurrent Programs . . . . . . . . . . 1--31
Helmut Alt Lower Bounds on Space Complexity for
Contextfree Recognition . . . . . . . . 33--61
Yasuichi Horibe and
Tibor O. H. Nemetz On the Max-Entropy Rule for a Binary
Search Tree . . . . . . . . . . . . . . 63--72
Jòrgen Steensgaard-Madsen Pascal---Clarifications and Recommended
Extensions . . . . . . . . . . . . . . . 73--94
Warren Burton Generalized Recursive Data Structures 95--108
P. E. Lauer and
P. R. Torrigiani and
M. W. Shields COSY --- A system specification language
based on paths and processes . . . . . . 109--158
Donald L. Iglehart and
Gerald S. Shedler Regenerative Simulation of Response
Times in Networks of Queues with
Multiple Job Types . . . . . . . . . . . 159--175
Ronald V. Book On Languages Accepted by Space-Bounded
Oracle Machines . . . . . . . . . . . . 177--185
C. J. M. Turnbull and
E. S. Lee Generalized Deterministic Left To Right
Parsing . . . . . . . . . . . . . . . . 187--207
Reinhard Wilhelm Computation and Use of Data Flow
Information in Optimizing Compilers . . 209--225
Beate Commentz-Walter Size-depth trade-off in monotone Boolean
formulae . . . . . . . . . . . . . . . . 227--243
J. W. Cohen The Multiple Phase Service Network with
Generalized Processor Sharing . . . . . 245--284
Erol Gelenbe Probabilistic models of computer
systems. II. Diffusion approximations,
waiting times and batch arrivals . . . . 285--303
Teruo Hikita On a Class of Recursive Procedures and
Equivalent Iterative Ones . . . . . . . 305--320
N. Mikou and
S. Tucci Analyse et optimisation d'une procédure
de reprise dans un syst\`eme de gestion
de données centralisées. (French)
[Analysis and Optimization of a Recovery
Technique in a Management System of
Centralized Data] . . . . . . . . . . . 321--338
Eljas Soisalon-Soininen and
Esko Ukkonen A Method for Transforming Grammars into
\em LL($k$) Form . . . . . . . . . . . . 339--369
Kurt Mehlhorn Some Remarks on Boolean Sums . . . . . . 371--375
Hirokazu Nishimura Sequential Method in Propositional
Dynamic Logic . . . . . . . . . . . . . 377--400
Edsger W. Dijkstra Some Beautiful Arguments Using
Mathematical Induction . . . . . . . . . 1--8
Christoph M. Hoffmann Semantic Properties of Lucid's Compute
Clause and its Compilation . . . . . . . 9--20
Philip Heidelberger Variance Reduction Techniques for the
Simulation of Markov Process . . . . . . 21--37
Gaston H. Gonnet and
Lawrence D. Rogers and
J. Alan George An Algorithmic and Complexity Analysis
of Interpolation Search . . . . . . . . 39--52
Zvi Galil Applications of Efficient Mergeable
Heaps for Optimization Problems on Trees 53--58
Stefan Reisch Gobang ist PSPACE-vollständig. (German)
[Gobang is PSPACE-Complete] . . . . . . 59--66
Jörg H. Siekmann and
Graham Wrightson Paramodulated Connection Graphs . . . . 67--86
Hermann A. Maurer and
Arto K. Salomaa and
Derick Wood On Generators and Generative Capacity of
EOL Forms . . . . . . . . . . . . . . . 87--107
Ingo Wegener A new Lower Bound on the Monotone
Network Complexity of Boolean Sums . . . 109--114
Johannes Röhrich Methods for the Automatic Construction
of Error Correcting Parsers . . . . . . 115--139
Charles N. Fischer and
Donn R. Milton and
Sam B. Quiring Efficient \em LL($1$) Error Correction
and Recovery Using Only Insertions . . . 141--154
Jon Louis Bentley and
Hermann A. Maurer Efficient Worst-Case Data Structures for
Range Searching . . . . . . . . . . . . 155--168
Edmund Melson Clarke Proving Correctness of Coroutines
Without History Variables . . . . . . . 169--188
Christophe Reutenauer An Ogden-Like Iteration Lemma for
Rational Power Series . . . . . . . . . 189--197
Chandra M. R. Kintala and
Detlef Wotschke Amounts of Nondeterminism in Finite
Automata . . . . . . . . . . . . . . . . 199--204
Frank Wm. Tompa A Practical Example of the Specification
of Abstract Data Types . . . . . . . . . 205--224
David R. Barstow and
John Darlington Remarks on \em A Synthesis of Several
Sorting Algorithms by John Darlington 225--227
Uwe Kastens Ordered Attributed Grammars . . . . . . 229--256
Grzegorz Rozenberg and
D. Wood Context-Free Grammars With Selective
Rewriting . . . . . . . . . . . . . . . 257--268
Hans Kleine Büning and
Lutz Priese Universal Asynchronous Iterative Arrays
of Mealy Automata . . . . . . . . . . . 269--285
H. A. Rollik Automaten in planaren Graphen. (German)
[Automata in Planar Graphs] . . . . . . 287--298
William R. Franta and
Mark Benedict Bilodeau Analysis of a Prioritized CSMA Protocol
Based on Staggered Delays . . . . . . . 299--324
A. T. Berztiss Depth-First $K$-Trees and Critical Path
Analysis . . . . . . . . . . . . . . . . 325--346
Michel Latteux Sur les générateurs algébriques et
linéaires. (French) [Algebraic and Linear
Generators] . . . . . . . . . . . . . . 347--363
Hermann A. Maurer and
Maurice Nivat Rational Bijection of Rational Sets . . 365--378
Susumu Morito and
Harvey M. Salkin Using the Blankinship Algorithm to Find
the General Solution of a Linear
Diophantine Equation . . . . . . . . . . 379--382
Bernhard Mescheder On the Number of Active-Operations
Needed to Compute the Discrete Fourier
Transform . . . . . . . . . . . . . . . 383--408
Bruce Russell Correctness of the Compiling Process
Based on Axiomatic Semantics . . . . . . 1--20
Leslie Lamport The ``Hoare Logic'' of Concurrent
Programs . . . . . . . . . . . . . . . . 21--37
Brigitte Plateau Evaluation des Performances d'un
Algorithme de Contrôle de la Cohérence
d'une Base de Données Répartie. (French)
[Performance Evaluation of a Concurrency
Control Algorithm for a Distributed
Database] . . . . . . . . . . . . . . . 39--62
Carla Schlatter Ellis Concurrent Search and Insertion in
$2$-$3$ Trees . . . . . . . . . . . . . 63--86
Reiner Philipp and
Ernst-Jürgen Prauß Über Separatoren in planaren Graphen.
(German) [Separators in Planar Graphs] 87--106
Allan G. Bromley Memory Fragmentation in Buddy Methods
for Dynamic Storage Allocation . . . . . 107--117
Vijay K. Vaishnavi and
Hans-Peter Kriegel and
D. Wood Optimum Multiway Search Trees . . . . . 119--133
Reiji Nakajima and
Michio Honda and
Hayao Nakahara Hierarchical Program Specification and
Verification --- a Many-sorted Logical
Approach . . . . . . . . . . . . . . . . 135--155
Eljas Soisalon-Soininen On the Space Optimizing Effect of
Eliminating Single Productions from $LR$
Parsers . . . . . . . . . . . . . . . . 157--174
Lutz Michael Wegner On Parsing Two-Level Grammars . . . . . 175--193
Marco A. Casanova and
Philip A. Bernstein General Purpose Schedulers for Database
Systems . . . . . . . . . . . . . . . . 195--220
Zvi Galil An $O(V^{5/3} E^{2/3})$ Algorithm for
the Maximal Flow Problem . . . . . . . . 221--242
Wolfgang J. Paul and
Ernst J. Prauß and
Rüdiger Reischuk On Alternation . . . . . . . . . . . . . 243--255
Beate Commentz-Walter and
Jürgen Sattler Size-depth Tradeoff in Non-monotone
Boolean Formulae . . . . . . . . . . . . 257--269
Anton Nijholt A Survey of Normal Form Covers for
Context Free Grammars . . . . . . . . . 271--294
R. Kemp A Note on the Density of Inherently
Ambiguous Context-free Languages . . . . 295--298
Paul Walton Purdom, Jr. and
Cynthia A. Brown Semantic Routines and \em LR($k$)
Parsers . . . . . . . . . . . . . . . . 299--315
Karl-Rudolf R. Moll Left Context Precedence Grammars . . . . 317--335
Mitchell Wand First-Order Identities as a Defining
Language . . . . . . . . . . . . . . . . 337--357
Hirokazu Nishimura Descriptively Complete Process Logic . . 359--369
Fred Kröger Infinite Proof Rules for Loops . . . . . 371--389
Wolfgang J. Paul and
Rüdiger Reischuk On Alternation II. A Graph Theoretic
Approach to Determinism Versus
Nondeterminism . . . . . . . . . . . . . 391--403
Friedrich L. Bauer and
Andrei P. Ershov and
M. Paul and
Alan J. Perlis Klaus Samelson . . . . . . . . . . . . . 1--2
William E. Wright Binary Search Trees in Secondary Memory 3--17
Onno J. Boxma and
Alan G. Konheim Approximate Analysis of Exponential
Queueing Systems with Blocking . . . . . 19--66
François Baccelli Analysis of a Service Facility with
Periodic Checkpointing . . . . . . . . . 67--81
Daniel M. Berry Remarks on R. D. Tennent's \em Language
Design Methods Based on Semantic
Principles: Algol 68, A Language
Designed Using Semantic Principles . . . 83--98
Paul Walton Purdom, Jr. and
Cynthia A. Brown and
Edward L. Robertson Backtracking with Multi-Level Dynamic
Search Rearrangement . . . . . . . . . . 99--113
Paul Walton Purdom, Jr. and
Cynthia A. Brown Parsing Extended \em LR($k$) Grammars 115--127
Werner Kuich The Characterization of Parallel
Ultralinear Grammars by Rational Power
Series . . . . . . . . . . . . . . . . . 129--139
L. Kou and
George Markowsky and
Leonard Berman A Fast Algorithm for Steiner Trees . . . 141--145
Ingo Wegener An Improved Complexity Hierarchy on the
Depth of Boolean Functions . . . . . . . 147--152
F. Rodriguez Indépendance Forte de Certaines
Opérations. (French) [Strong Independence
of Certain Operations] . . . . . . . . . 153--166
Stefan Reisch Hex ist PSPACE-vollständig. (German) [Hex
is PSPACE-Complete] . . . . . . . . . . 167--191
Daniel J. Moore and
Bruce Russell Axiomatic Data Type Specifications: A
First Order Theory of Linear Lists . . . 193--207
Toshiro Araki and
Nobuki Tokura Flow Languages Equal Recursively
Enumerable Languages . . . . . . . . . . 209--217
Krzysztof R. Apt Recursive Assertions and Parallel
Programs . . . . . . . . . . . . . . . . 219--232
R. J. R. Back Proving Total Correctness of
Nondeterministic Programs in Infinitary
Logic . . . . . . . . . . . . . . . . . 233--249
Hans Daduna and
R. Schassberger A Discrete-Time Round-Robin Queue with
Bernoulli Input and General Arithmetic
Service Time Distributions . . . . . . . 251--263
R. Kemp \em LR($0$) Grammars Generated by \em
LR($0$) Parsers . . . . . . . . . . . . 265--280
Gary Marc Levin and
David Gries A Proof Technique for Communicating
Sequential Processes . . . . . . . . . . 281--302
Stal O. Anderaa and
Egon Börger The Equivalence of Horn and Network
Complexity for Boolean Functions . . . . 303--307
Ernst W. Mayr Persistence of Vector Replacement
Systems is Decidable . . . . . . . . . . 309--318
Kellogg S. Booth and
Richard J. Lipton Computing Extremal and Approximate
Distances in Graphs Having Unit Cost
Edges . . . . . . . . . . . . . . . . . 319--328
Witold Lipski, Jr. and
Franco P. Preparata Efficient Algorithms for Finding Maximum
Matchings in Convex Bipartite Graphs and
Related Problems . . . . . . . . . . . . 329--346
Donald L. Iglehart and
Gerald S. Shedler Regenerative Simulation of Response
Times in Networks of Queues: Statistical
Efficiency . . . . . . . . . . . . . . . 347--363
Robert Cartwright and
Derek C. Oppen The Logic of Aliasing . . . . . . . . . 365--384
Arie de Bruin Goto Statements: Semantics and Deduction
Systems . . . . . . . . . . . . . . . . 385--424
Harald Würges A Specification Technique Based on
Predicate Transformers . . . . . . . . . 425--445
Takehiro Tokuda Eliminating Unit Reductions from \em
LR($k$) Parsers Using Minimum Contexts 447--470
Marco A. Casanova and
Philip A. Bernstein Erratum: \em General Purpose Schedulers
for Database System . . . . . . . . . . 471--471
Zvi M. Kedem and
Abraham Silberschatz A Characterization of Database Graphs
Admitting a Simple Locking Protocol . . 1--13
M. Clint On the Use of History Variables . . . . 15--30
Richard G. Hamlet Reliability Theory of Program Testing 31--43
Manfred Stadel Behandlung verschiedener
INTEGER-Darstellungen durch optimierende
Compiler. (German) [Treatment of Various
INTEGER-Representation by Optimizing
Compiler] . . . . . . . . . . . . . . . 45--56
R. Schassberger On the Response Time Distribution in a
Discrete Round-Robin Queue . . . . . . . 57--62
Dirk Janssens and
Grzegorz Rozenberg A Characterization of Context-Free
String Languages by Directed Node Label
Controlled Graph Grammars . . . . . . . 63--85
Paul Pritchard Another Look at the ``Longest Ascending
Subsequence'' Problem . . . . . . . . . 87--91
Eike Best and
Brian Randell A Formal Model of Atomicity in
Asynchronous Systems . . . . . . . . . . 93--124
Thomas J. Ostrand and
Marvin C. Paull and
Elaine J. Weyuker Parsing Regular Grammars with Finite
Lookahead . . . . . . . . . . . . . . . 125--138
Volker Claus The $(n, k)$-Bounded Emptiness-Problem
for Probabilistic Acceptors and Related
Problems . . . . . . . . . . . . . . . . 139--160
Ernst-Rüdiger Olderog Sound and Complete Hoare-like Calculi
Based on Copy Rules . . . . . . . . . . 161--197
Andrzej Blikle The Clean Termination of Iterative
Programs . . . . . . . . . . . . . . . . 199--217
Alain J. Martin An Axiomatic Definition of
Synchronization Primitives . . . . . . . 219--235
Trevor I. Fenner and
George Loizou An Analysis of two Related Loop-free
Algorithms for Generating Integer
Partitions . . . . . . . . . . . . . . . 237--252
Jayashree Ramanathan and
Ken Kennedy Pathlistings Applied to Data Flow
Analysis . . . . . . . . . . . . . . . . 253--273
Joost Engelfriet and
Gilberto Fil\`e The Formal Power of One-Visit Attribute
Grammars . . . . . . . . . . . . . . . . 275--302
Leslie M. Goldschlager $\varepsilon$-productions in
context-free grammars . . . . . . . . . 303--308
John L. Hennessy and
Richard B. Kieburtz The Formal Definition of a Real-Time
Language . . . . . . . . . . . . . . . . 309--345
Thomas Klingler and
Stefan Reisch A Gap Between the Actual Complexity of
Permutations and Their Entropy Defined
by Stoß . . . . . . . . . . . . . . . . . 347--362
George Markowsky Best Huffman Trees . . . . . . . . . . . 363--370
Zohar Manna and
Richard J. Waldinger Problematic Features of Programming
Languages: A Situational-Calculus
Approach . . . . . . . . . . . . . . . . 371--426
Henk Alblas A Characterization of Attribute
Evaluation in Passes . . . . . . . . . . 427--464
Thomas Lengauer Black-White Pebbles and Graph Separation 465--475
T. Gergely and
L. Úry A Theory of Interactive Programming . . 1--20
A. Arnold Synchronized Behaviours of Processes and
Rational Relations . . . . . . . . . . . 21--29
C. L. Liu and
Jane W. S. Liu and
Arthur L. Liestman Scheduling with Slack Time . . . . . . . 31--41
John E. Shore Information Theoretic Approximations for
M/G/1 und G/G/1 Queuing Systems . . . . 43--61
Satoru Miyano A Hierarchy Theorem for Multihead
Stack-Counter Automata . . . . . . . . . 63--67
Grzegorz Rozenberg and
R. Verraedt Completeness of EOL Forms is Decidable 69--87
Thiet-Dung Huynh Remarks on the Complexity of an
Invariant of Context-Free Grammars . . . 89--99
Michel Martinez Program Behavior Prediction and
Prepaging . . . . . . . . . . . . . . . 101--120
Michael O. Rabin The Choice Coordination Problem . . . . 121--134
Joep L. W. Kessels Arbitration Without Common Modifiable
Variables . . . . . . . . . . . . . . . 135--141
Sridhar Vasudevan Inner Loops in Flowgraphs and Code
Optimization . . . . . . . . . . . . . . 143--155
Scott Huddleston and
Kurt Mehlhorn A New Data Structure for Representing
Sorted Lists . . . . . . . . . . . . . . 157--184
Kari-Jouko Räihä and
Mikko Saarinen Testing Attribute Grammars for
Circularity . . . . . . . . . . . . . . 185--192
Jean-Michel Autebert and
Joffroy Beauquier and
Luc Boasson Formes de langages et de grammaires.
(French) [Grammar and language forms] 193--213
Alon Itai and
Michael Rodeh Representation of Graphs . . . . . . . . 215--219
Hagen Huwig Ein Modell des $P=NP$-Problems mit einer
positiven Lösung. (German) [A Model of
the ${P}={NP}$ Problem with a Positive
Solution] . . . . . . . . . . . . . . . 221--243
Ernst-Erich Doberkat Deleting the Root of a Heap . . . . . . 245--265
Mark H. Overmars and
Jan van Leeuwen Dynamic Multi-Dimensional Data
Structures Based on Quad- and $K$-$D$
Trees . . . . . . . . . . . . . . . . . 267--285
François Baccelli and
Thierry Fleury On Parsing Arithmetic Expressions in a
Multiprocessing Environment . . . . . . 287--310
A. Staphylopatis Performance Considerations in the
Parallel Execution of Numerical
Algorithms on two Processors . . . . . . 311--325
Lawrence Snyder Recognition and Selection of Idioms for
Code Optimization . . . . . . . . . . . 327--348
A. Demers and
C. Keleman and
Bernd Reusch On Some Decidable Properties of Finite
State Translations . . . . . . . . . . . 349--364
Flaviu Cristian Robust Data Types . . . . . . . . . . . 365--397
Clement H. C. Leung and
Q. H. Choo The Effect of Fixed-Length Record
Implementation on File System Response 399--409
Joseph JáJá and
Janos Simon Space Efficient Algorithms for Some
Graph Theoretical Problems . . . . . . . 411--423
Norbert Blum On the Power of Chain Rules in Context
Free Grammars . . . . . . . . . . . . . 425--433
Eljas Soisalon-Soininen and
Derick Wood On a Covering Relation for Context-Free
Grammars . . . . . . . . . . . . . . . . 435--449
Peter R. J. Asveld and
J. V. Tucker Complexity theory and the operational
structure of algebraic programming
systems . . . . . . . . . . . . . . . . 451--476
Paul Pritchard Explaining the Wheel Sieve . . . . . . . 477--485
Robert B. K. Dewar and
Susan M. Merritt and
Micha Sharir Some Modified Algorithms for Dijkstra's
Longest Upsequence Problem . . . . . . . 1--15
Raúl J. Ramírez and
Frank Wm. Tompa and
J. Ian Munro Optimum Reorganization Points for
Arbitrary Database Costs . . . . . . . . 17--30
Timothy A. Budd and
Dana Angluin Two Notions of Correctness and Their
Relation to Testing . . . . . . . . . . 31--45
Manfred Broy and
Martin Wirsing Partial Abstract Types . . . . . . . . . 47--64
Jeannine Leguy Langages saturés et cones décroissants
Langages et cones bifid\`eles. (French)
[Saturated Languages and Decreasing
Cones. Bifaithful Languages and
Bifaithful Cones] . . . . . . . . . . . 65--78
Hans Langmaack On Termination Problems for Finitely
Interpreted ALGOL-like Programs . . . . 79--108
Christiane Frougny and
Jacques Sakarovitch and
Erich Valkema On the Hotz Group of a Context-Free
Grammar . . . . . . . . . . . . . . . . 109--115
Wolfgang Reisig Deterministic Buffer Synchronization of
Sequential Processes . . . . . . . . . . 117--134
Lynn Robert Carter Further Analysis of Code Generation for
a Single Register Machine . . . . . . . 135--147
George W. Ernst and
Jainendra K. Navlakha and
William F. Ogden Verification of Programs with
Procedure-Type Parameters . . . . . . . 149--169
Narao Nakatsu and
Yahiko Kambayashi and
Shuzo Yajima A longest common subsequence algorithm
suitable for similar text strings . . . 171--179
Alberto Pettorossi and
Rod M. Burstall Deriving Very Efficient Algorithms for
Evaluating Linear Recurrence Relations
Using the Program Transformation
Technique . . . . . . . . . . . . . . . 181--206
Donna J. Brown and
Brenda S. Baker and
Howard P. Katseff Lower Bounds for On-Line Two-Dimensional
Packing Algorithms . . . . . . . . . . . 207--225
Jean-Marie M. Nicolas Logic For Improving Integrity Checking
in Relational Data Bases . . . . . . . . 227--253
Brian Allen On the Costs of Optimal and Near-Optimal
Binary Search Trees . . . . . . . . . . 255--263
Flemming Nielson A Denotational Framework for Data Flow
Analysis . . . . . . . . . . . . . . . . 265--287
S. O. Anderson and
R. C. Backhouse An Alternative Implementation of an
Insertion-Only Recovery Technique . . . 289--298
Karl Winklmann On the complexity of some problems
concerning the use of procedures. I . . 299--318
Ashok K. Agrawala and
Satish K. Tripathi On an Exponential Server with General
Cyclic Arrivals . . . . . . . . . . . . 319--334
Karel Culik II and
J. Gruska and
Arto Salomaa Systolic Automata for VLSI on Balanced
Trees . . . . . . . . . . . . . . . . . 335--344
Jan van Leeuwen and
Mark H. Overmars Stratified Balanced Search Trees . . . . 345--359
Ole Eriksen and
Jòrgen Staunstrup Concurrent Algorithms for Root Searching 361--376
Kenneth J. Supowit and
Edward M. Reingold The Complexity of Drawing Trees Nicely 377--392
Giora Slutzki Finite State Relational Programs . . . . 393--409
Karl Winklmann On the complexity of some problems
concerning the use of procedures. II . . 411--430
Jean-Pierre Banâtre and
Patrice Frison and
Patrice Quinton A Network for the Detection of Words in
Continuous Speech . . . . . . . . . . . 431--448
Philippe Nain Partage de tâches entre [deux]
processeurs homog\`enes. (French) [Task
Scheduling Between Two Homogeneous
Processors] . . . . . . . . . . . . . . 449--466
H. T. Kung and
Christos H. Papadimitriou An Optimality Theory of Concurrency
Control for Databases . . . . . . . . . 1--11
Takao Tsuda and
Takashi Sato Transposition of Large Tabular Data
Structures with Applications to Physical
Database Organization. Part I.
Transposition of Tabular Data Structures 13--33
Klaus Küspert Storage Utilization in $B^*$-Trees with
a Generalized Overflow Technique . . . . 35--55
Richard N. Taylor Complexity of Analyzing the
Synchronization Structure of Concurrent
Programs . . . . . . . . . . . . . . . . 57--84
Kazuo Iwama The Universe Problem for Unrestricted
Flow Languages . . . . . . . . . . . . . 85--96
Jan A. Bergstra and
J. Terlouw Standard Model Semantics for DSL. A Data
Type Specification Language . . . . . . 97--113
Gilberto Filé Interpretation and Reduction of
Attribute Grammars . . . . . . . . . . . 115--150
Günther E. Pfaff The Construction of Operator Interfaces
Based on Logical Input Devices . . . . . 151--166
Takao Tsuda and
Akira Urano and
Takashi Sato Transposition of Large Tabular Data
Structures with Applications to Physical
Database Organization. Part II.
Applications to Physical Database
Organization . . . . . . . . . . . . . . 167--182
Ute Schürfeld New Lower Bounds on the Formula Size of
Boolean Functions . . . . . . . . . . . 183--194
J.-P. P. Queille and
Joseph Sifakis Fairness and Related Properties in
Transition Systems: a Temporal Logic to
deal with Fairness . . . . . . . . . . . 195--220
John P. Kearns and
Mary Lou Soffa The Implementation of Retention in a
Coroutine Environment . . . . . . . . . 221--233
Gregor Engels and
Udo Pletat and
Hans-Dieter Ehrich An Operational Semantics for
Specifications of Abstract Data Types
with Error Handling . . . . . . . . . . 235--253
Hanne Riis Nielson Computation Sequences: A Way to
Characterize Classes of Attribute
Grammars . . . . . . . . . . . . . . . . 255--268
Friedhelm Meyer auf der Heide Efficiency of Universal Parallel
Computers . . . . . . . . . . . . . . . 269--296
Alfred Schmitt On the Number of Relational Operators
Necessary to Compute Certain Functions
of Real Variables . . . . . . . . . . . 297--304
Moshe Y. Vardi Inferring Multivalued Dependencies From
Functional and Join Dependencies . . . . 305--324
Ichiro Suzuki and
Tadao Kasami Three Measures for Synchronic Dependence
in Petri Nets . . . . . . . . . . . . . 325--338
M. A. El-Affendi and
Demetres D. Kouvatsos A Maximum Entropy Analysis of the M/G/1
and G/M/1 Queueing Systems at
Equilibrium . . . . . . . . . . . . . . 339--355
Keijo Ruohonen On Some Variants of Post's
Correspondence Problem . . . . . . . . . 357--367
Rakesh Agrawal and
Keith D. Detro An Efficient Incremental \em LR Parser
for Grammars With Epsilon Productions 369--376
Juraj Hromkovi\vc One-Way Multihead Deterministic Finite
Automata . . . . . . . . . . . . . . . . 377--384
Peter Klein and
Friedhelm Meyer auf der Heide A Lower Time Bound for the Knapsack
Problem on Random Access Machines . . . 385--395
R. Sommerhalder and
S. C. van Westrhenen Parallel Language Recognition in
Constant Time by Cellular Automata . . . 397--407
Martin Wirsing and
Peter Pepper and
Helmut Partsch and
Walter Dosch and
Manfred Broy On hierarchies of abstract data types 1--33
Jifeng He General Predicate Transformer and the
Semantics of a Programming Language With
Go To Statement . . . . . . . . . . . . 35--57
Werner Damm and
Bernhard Josko A Sound and Relatively $^*$Complete
Hoare-Logic for a Language With Higher
Type Procedures . . . . . . . . . . . . 59--101
Ashok K. Chandra and
Lawrence T. Kou and
George Markowsky and
Shmuel Zaks On sets of Boolean $n$-vectors with all
$k$-projections surjective . . . . . . . 103--111
Hisao Kameda A Note on Multi-queue Scheduling of Two
Tasks . . . . . . . . . . . . . . . . . 113--120
Herman Akdag Performances of an Algorithm
Constructing a Nearly Optimal Binary
Tree . . . . . . . . . . . . . . . . . . 121--132
W. Bucher Two-Symbol DOS Systems Generating
Regular Languages . . . . . . . . . . . 133--142
Heikki Mannila and
Kari-Jouko Räihä On the Relationship of Minimum and
Optimum Covers for a Set of Functional
Dependencies . . . . . . . . . . . . . . 143--158
Mario Coppo On the Semantics of Polymorphism . . . . 159--170
Nathan Goodman and
Oded Shmueli NP-complete Problems Simplified on Tree
Schemas . . . . . . . . . . . . . . . . 171--178
Jean-Jacques Pansiot Hiérarchie et fermeture de certaines
classes de tag-syst\`emes. (French)
[Hierarchy and Closure Properties of
Certain Classes of Tag-Systems] . . . . 179--196
Christian Ronse A Three-Stage Construction for
Multiconnection Networks . . . . . . . . 197--206
Mordechai Ben-Ari and
Amir Pnueli and
Zohar Manna The Temporal Logic of Branching Time . . 207--226
Hans-Ulrich U. Simon Pattern Matching in Trees and Nets . . . 227--248
G. Marque-Pucheu Rational Set of Trees and The Algebraic
Semantics of Logic Programming . . . . . 249--260
Joseph A. Bannister and
Kishor S. Trivedi Task Allocation in Fault-Tolerant
Distributed Systems . . . . . . . . . . 261--281
Werner Pohlmann \em LR Parsing for Affix Grammars . . . 283--300
Alain J. Martin A General Proof Rule for Procedures in
Predicate Transformer Semantics . . . . 301--313
Ali Mili A Relational Approach to the Design of
Deterministic Programs . . . . . . . . . 315--328
Nissim Francez Product Properties and Their Direct
Verification . . . . . . . . . . . . . . 329--344
Philippe Flajolet On the Performance Evaluation of
Extendible Hashing and Trie Searching 345--369
Aviezri S. Fraenkel and
Moshe Mor and
Y. Perl Is Text Compression by Prefixes and
Suffixes Practical? . . . . . . . . . . 371--389
H. C. M. Kleijn and
Grzegorz Rozenberg On the Generative Power of Regular
Pattern Grammars . . . . . . . . . . . . 391--411
Rudolf Bayer and
Peter Schlichtiger Data Management Support for Database
Management . . . . . . . . . . . . . . . 1--28
N. P. Chapman \em LALR($1,1$) Parser Generation for
Regular Right Part Grammars . . . . . . 29--45
Jayme Luiz Szwarcfiter Optimal Multiway Search Trees for
Variable Size Keys . . . . . . . . . . . 47--60
Matthew Hennessy Axiomatising Finite Delay Operators . . 61--88
Eike Best and
Klaus Voss Free Choice Systems Have Home States . . 89--100
Athanasios K. Tsakalidis Maintaining Order in a Generalized
Linked List . . . . . . . . . . . . . . 101--112
Shou Hsuan Stephen Huang and
C. K. Wong Generalized Binary Split Trees . . . . . 113--123
Boris D. Lubachevsky An Approach to Automating the
Verification of Compact Parallel
Coordination Programs: Part 1 . . . . . 125--169
Norbert Blum and
Martin Seysen Characterization of all Optimal Networks
for a Simultaneous Computation of AND
and NOR . . . . . . . . . . . . . . . . 171--181
Will D. Gillett On Binary Tree Encodements . . . . . . . 183--192
Oscar H. Ibarra and
Sam M. Kim A Characterization of Systolic Binary
Tree Automata and Applications . . . . . 193--207
Jean-Michel Autebert and
Joffroy Beauquier and
Luc Boasson and
Françoise Gire Bicentres de langages algébriques.
(French) [Bicenters of Context-Free
Languages] . . . . . . . . . . . . . . . 209--227
Luc Devroye A Probabilistic Analysis of the Height
of Tries and of the Complexity of
Triesort . . . . . . . . . . . . . . . . 229--237
R. S. Bird Using Circular Programs to Eliminate
Multiple Traversals of Data . . . . . . 239--250
H. Barringer and
J. H. Cheng and
Cliff B. Jones A Logic Covering Undefinedness in
Program Proofs . . . . . . . . . . . . . 251--269
Ralf Hartmut Güting Optimal Divide-and-Conquer to Compute
Measure and Contour for a Set of
Iso-Rectangles . . . . . . . . . . . . . 271--291
Jan A. Bergstra and
J. V. Tucker The Axiomatic Semantics of Programs
Based on Hoare's Logic . . . . . . . . . 293--320
Donald L. Iglehart and
Gerald S. Shedler Simulation Output Analysis for Local
Area Computer Networks . . . . . . . . . 321--338
Kurt Mehlhorn and
Uzi Vishkin Randomized and Deterministic Simulations
of PRAMs by Parallel Machines with
Restricted Granularity of Parallel
Memories . . . . . . . . . . . . . . . . 339--374
Pierre Deransart and
Martin Jourdan and
Bernard Lorho Speeding up Circularity Tests for
Attribute Grammars . . . . . . . . . . . 375--391
Christian Choffrut and
Karel Culik II On Real-Time Cellular Automata and
Trellis Automata . . . . . . . . . . . . 393--407
Edward G. Coffman, Jr. and
Michael A. Langston A Performance Guarantee for the Greedy
Set-Partitioning Algorithm . . . . . . . 409--415
Gerardo Costa and
Colin Stirling A Fair Calculus of Communicating Systems 417--441
D. T. Sannella A Set--Theoretic Semantics for CLEAR . . 443--472
Mikhail A. Bulyonkov Polyvariant Mixed Computation for
Analyzer Programs . . . . . . . . . . . 473--484
Clement H. C. Leung and
Q. H. Choo The Paging Drum Queue: A Uniform
Perspective and Further Results . . . . 485--500
Stefan Hertel and
Martti Mäntylä and
Kurt Mehlhorn and
Jürg Nievergelt Space Sweep Solves Intersection of
Convex Polyhedra . . . . . . . . . . . . 501--519
Günther Bauer and
Friedrich Otto Finite Complete Rewriting Systems and
the Complexity of the Word Problem . . . 521--540
William E. Wright Some average performance measures for
the $B$-tree . . . . . . . . . . . . . . 541--557
A. J. Fisher Practical \em LL($1$)-Based Parsing of
van Wijngaarden Grammars . . . . . . . . 559--584
Marina C. Chen and
Martin Rem Deadlock-Freedom in Resource Contentions 585--598
Daniel M. Berry A Denotational Semantics for
Shared-Memory Parallelism and
Nondeterminism . . . . . . . . . . . . . 599--627
Jacques Lenfant and
Serge Tahé Permuting data with the Omega network 629--641
Rüdiger Valk and
Matthias Jantzen The Residue of Vector Sets with
Applications to Decidability Problems in
Petri Nets . . . . . . . . . . . . . . . 643--674
Michael Bechtold and
Guy Pujolle and
Otto Spaniol Throughput of a Satellite Channel
Communication . . . . . . . . . . . . . 1--14
Jeffrey H. Kingston Analysis of Tree Algorithms for the
Simulation Event List . . . . . . . . . 15--33
Fred B. Schneider and
Richard Conway and
Dale Skeen Thrifty Execution of Task Pipelines . . 35--45
Ali Mili and
Jules Desharnais and
Jean-Raymond Gagné Strongest Invariant Functions: Their Use
in the Systematic Analysis of While
Statements . . . . . . . . . . . . . . . 47--66
Dean Jacobs and
David Gries General Correctness: A Unification of
Partial and Total Correctness . . . . . 67--83
Thomas Ottmann and
Michael Schrapp and
Derick Wood Purely Top-Down Updating Algorithms for
Stratified Search Trees . . . . . . . . 85--100
Donald W. Loveland Performance Bounds for Binary Testing
with Arbitrary Weights . . . . . . . . . 101--114
Burkhard Monien and
Ewald Speckenmeyer Ramsey Numbers and an Approximation
Algorithm for the Vertex Cover Problem 115--123
Carlo Meghini and
Costantino Thanos Querying Fragmented Relations in a
Distributed Database . . . . . . . . . . 125--138
John Bruno On Scheduling Tasks with Exponential
Service Times and In-Tree Precedence
Constraints . . . . . . . . . . . . . . 139--148
R. J. Cunningham and
A. J. J. Dick Rewrite Systems on a Lattice of Types 149--169
Jörg-Rüdiger Sack and
Thomas Strothotte An Algorithm for Merging Heaps . . . . . 171--186
Norishige Chiba and
Kazunori Onoguchi and
Takao Nishizeki Drawing Plane Graphs Nicely . . . . . . 187--201
Tsutomu Kamimura An Effectively Given Initial Semigroup 203--227
Paul E. S. Dunne A $2.5n$ Lower Bound on the Monotone
Network Complexity of $T_3^n$ . . . . . 229--240
Bogdan Rembowski A Priority Queue With Interruptions of
Service Permitted After a Time Quantum 241--251
Balakrishnan Krishnamurthy Short Proofs for Tricky Formulas . . . . 253--275
Jakob Gonczarowski Decidable Properties of Monadic
Recursive Schemas With a Depth Parameter 277--310
Piotr Rudnicki and
W\lodzimierz Drabent Proving Properties of Pascal Programs in
MIZAR 2 . . . . . . . . . . . . . . . . 311--331
John L. Bruno and
Peter J. Downey Probabilistic Bounds for Dual
Bin-Packing . . . . . . . . . . . . . . 333--345
A. J. Kfoury and
Pawe\l Urzyczyn Necessary and Sufficient Conditions for
the Universality of Programming
Formalisms . . . . . . . . . . . . . . . 347--377
Moon-Jung Chung and
W. Michael Evangelist and
Ivan Hal Sudborough Complete Problems for Space Bounded
Subclasses of NP . . . . . . . . . . . . 379--395
Michael Sonnenschein Global Storage Cells for Attributes in
an Attribute Grammar . . . . . . . . . . 397--420
Dung T. Huynh Complexity of the Word Problem for
Commutative Semigroups of Fixed
Dimension . . . . . . . . . . . . . . . 421--432
Meurig Beynon Replaceability and Computational
Equivalence for Monotone Boolean
Functions . . . . . . . . . . . . . . . 433--449
Errol L. Lloyd and
Michael C. Loui On the Worst Case Performance of Buddy
Systems . . . . . . . . . . . . . . . . 451--473
Masahiro Miyakawa Optimum Decision Trees---An Optimal
Variable Theorem and its Related
Applications . . . . . . . . . . . . . . 475--498
Stephan Heilbrunner Truly Prefix-Correct Chain-Free \em
LR($1$) Parsers . . . . . . . . . . . . 499--536
Bernhard Möller On the Algebraic Specification of
Infinite Objects---Ordered and
Continuous Models of Algebraic Types . . 537--578
Michel Latteux and
B. Leguy and
B. Ratoandromanana The Family of One-Counter Languages is
Closed Under Quotient . . . . . . . . . 579--588
Juraj Hromkovi\vc Fooling a Two-Way Nondeterministic
Multihead Automaton with Reversal Number
Restriction . . . . . . . . . . . . . . 589--594
Paul Caspi and
Nicolas Halbwachs A Functional Model for Describing and
Reasoning About Time Behaviour of
Computing Systems . . . . . . . . . . . 595--627
Tobias Nipkow Non-deterministic data types: models and
implementations . . . . . . . . . . . . 629--661
Bernd Reusch and
W. Merzenich Minimal Coverings for Incompletely
Specified Sequential Machines . . . . . 663--678
Volker Diekert Investigations on Hotz Groups for
Arbitrary Grammars . . . . . . . . . . . 679--698
Piotr Rudnicki and
W\lodzimierz Drabent Proving Properties of Pascal Programs in
MIZAR 2 . . . . . . . . . . . . . . . . 699--707
Edsger W. Dijkstra and
A. J. M. van Gasteren A Simple Fixpoint Argument Without the
Restriction to Continuity . . . . . . . 1--7
Ernst-Rüdiger R. Olderog and
C. A. R. Hoare Specification-Oriented Semantics for
Communicating Processes . . . . . . . . 9--66
L. Duponcheel and
M. Duponcheel Acceptable Functional Programming
Systems . . . . . . . . . . . . . . . . 67--98
Friedrich Otto On Deciding Whether a Monoid is a Free
Monoid or is a Group . . . . . . . . . . 99--110
Hosam M. Mahmoud On the Average Internal Path Length of
$m$-ary Search Trees . . . . . . . . . . 111--117
S. A. Bengelloun An Incremental Primal Sieve . . . . . . 119--125
Reinhold Heckmann An Efficient \em ELL($1$)-Parser
Generator . . . . . . . . . . . . . . . 127--148
Ikuo Nakata and
Masataka Sassa Generation of Efficient \em LALR Parsers
for Regular Right Part Grammars . . . . 149--162
M. Becker and
Kurt Mehlhorn Algorithms for Routing in Planar Graphs 163--176
Catherine Rosenberg Files d'attente exponentielles ayant des
param\`etres non-stationnaires dans le
temps. (French) [Exponential Queueing
Systems with Non-Stationary [Time]
Parameters] . . . . . . . . . . . . . . 177--192
N. Soundararajan Total Correctness of CSP Programs . . . 193--215
Michael S. Paterson and
Ingo Wegener Nearly Optimal Hierarchies for Network
and Formula Size . . . . . . . . . . . . 217--221
Y. F. Wu and
Peter Widmayer and
C. K. Wong A Faster Approximation Algorithm for the
Steiner Problem in Graphs . . . . . . . 223--229
Johann A. Makowsky and
Moshe Y. Vardi On the Expressive Power of Data
Dependencies . . . . . . . . . . . . . . 231--244
W. Bucher A Regularity Test for Dual Bordered OS
Systems . . . . . . . . . . . . . . . . 245--253
Maria Calzarossa and
M. Italiani and
Giuseppe Serazzi A Workload Model Representative of
Static and Dynamic Characteristics . . . 255--266
Markku Tamminen and
W. K. Luk and
Paolo Sipala and
L. S. Woo and
C. K. Wong Constructing Maximal Slicings From
Geometry . . . . . . . . . . . . . . . . 267--288
Grzegorz Rozenberg and
Emo Welzl Graph Theoretic Closure Properties of
the Family of Boundary NLC Graph
Languages . . . . . . . . . . . . . . . 289--309
Mirko K\vrivánek and
Jaroslav Morávek NP-Hard Problems in Hierarchical-Tree
Clustering . . . . . . . . . . . . . . . 311--323
Klaus W. Wagner The Complexity of Combinatorial Problems
with Succinct Input Representation . . . 325--356
A. Bijlsma and
J. G. Wiltink and
P. A. Matthews Equivalence of the Gries and Martin
Proof Rules for Procedure Calls . . . . 357--360
Piotr Wyrostek Precedence Technique is not Worse than
\em SLR($1$) . . . . . . . . . . . . . . 361--392
Rodney Farrow and
Daniel M. Yellin A Comparison of Storage Optimizations in
Automatically-Generated Attribute
Evaluators . . . . . . . . . . . . . . . 393--427
Maciej Koutny The Merlin-Randell Problem of Train
Journeys . . . . . . . . . . . . . . . . 429--463
Victor F. Nicola A Single Server Queue with Mixed Types
of Interruptions . . . . . . . . . . . . 465--486
Eric C. R. Hehner and
Lorene E. Gupta and
Andrew J. Malton Predicative Methodology . . . . . . . . 487--505
Susanne Graf and
Joseph Sifakis A Logic for the Specification and Proof
of Regular Controllable Processes of CCS 507--527
C. C. Lee and
D. T. Lee and
C. K. Wong Generating Binary Trees of Bounded
Height . . . . . . . . . . . . . . . . . 529--544
Demetres D. Kouvatsos Maximum Entropy and the G/G/1/N Queue 545--565
Johannes Reichardt Deterministic Grammars and Grammar
Morphisms . . . . . . . . . . . . . . . 567--583
Yael Maon On the Equivalence of Some Transductions
Involving Letter to Letter Morphisms on
Regular Languages . . . . . . . . . . . 585--596
Karel Culik II and
Juhani Karhumäki Synchronizable Deterministic Pushdown
Automata and the Decidability of their
Equivalence . . . . . . . . . . . . . . 597--605
Valdis Berzins On Merging Software Extensions . . . . . 607--619
Robert Geist and
Mark Smotherman and
Kishor S. Trivedi and
Joanne Bechta Dugan The Reliability of Life-Critical
Computer Systems . . . . . . . . . . . . 621--642
Erol Gelenbe and
David Finkel and
Satish K. Tripathi Availability of a Distributed Computer
System with Failures . . . . . . . . . . 643--655
J. Cantor and
A. Ephremides and
D. Horton Information Theoretic Analysis for a
General Queueing System at Equilibrium
with Application to Queues in Tandem . . 657--678
José L. Balcázar and
Ronald V. Book Sets with Small Generalized Kolmogorov
Complexity . . . . . . . . . . . . . . . 679--688
Siegfried Bublitz Decomposition of Graphs and Monotone
Formula Size of Homogeneous Functions 689--696
Costas S. Iliopoulos Monte Carlo Circuits for the Abelian
Permutation Group Intersection Problem 697--705
Patrick Cousot and
Radhia Cousot ${\rm Sometime}={\rm always}+{\rm
recursion}\equiv{\rm always}$ on the
equivalence of the intermittent and
invariant assertions methods for proving
inevitability properties of programs . . 1--31
Ryszard Janicki A Formal Semantics for Concurrent
Systems with a Priority Relation . . . . 33--55
Masato Takeichi Partial Parameterization Eliminates
Multiple Traversals of Data Structures 57--77
Oded Goldreich and
Liuba Shrira Electing a Leader in a Ring with Link
Failures . . . . . . . . . . . . . . . . 79--91
Clement H. C. Leung Analysis of Space Allocation in a
Generally Fragmented Linear Store . . . 93--104
K. Vidyasankar Generalized Theory of Serializability 105--119
Manfred Kunde Lower Bounds for Sorting on
Mesh-Connected Architectures . . . . . . 121--130
G. Loizou and
P. Thanisch Losslessness and Project-Join
Constructibility in Relational Databases 131--144
Thomas P. Murtagh Redundant Proofs of Non-Interference in
Levin-Gries CSP Program Proofs . . . . . 145--156
Stephan Heilbrunner and
Steffen Hölldobler The Undecidability of the Unification
and Matching Problem for Canonical
Theories . . . . . . . . . . . . . . . . 157--171
Wojciech Szpankowski An Analysis of a Contention Resolution
Algorithm: Another Approach . . . . . . 173--190
Lawrence A. Harris \em SLR($1$) and \em LALR($1$) Parsing
for Unrestricted Grammars . . . . . . . 191--209
Rocco De Nicola Extensional Equivalences for Transition
Systems . . . . . . . . . . . . . . . . 211--237
Ali Mili and
Jules Desharnais and
Fatma Mili Relational Heuristics for the Design of
Deterministic Programs . . . . . . . . . 239--276
Luc Devroye Branching Processes in the Analysis of
the Heights of Trees . . . . . . . . . . 277--298
Henk Alblas One-pass Transformations of Attributed
Program Trees . . . . . . . . . . . . . 299--352
S. Kiran Kumar and
C. Pandu Rangan A Linear Space Algorithm for the LCS
Problem . . . . . . . . . . . . . . . . 353--362
Bernd Becker An Easily Testable Optimal-Time
VLSI-Multiplier . . . . . . . . . . . . 363--380
Albert Hoogewijs Partial-Predicate Logic in Computer
Science . . . . . . . . . . . . . . . . 381--393
Deepak Kapur and
Paliath Narendran and
Hant\`ao Zhang On sufficient completeness and related
properties of term rewriting systems . . 395--415
Joseph G. Peters and
Larry Rudolph Parallel Approximation Schemes for
Subset Sum and Knapsack Problems . . . . 417--432
Ursula Schmidt Long Unavoidable Patterns . . . . . . . 433--445
Paul E. S. Dunne A Result on $k$-Valent Graphs and Its
Application to a Graph Embedding Problem 447--459
M. Kempf and
Rudolf Bayer and
Ulrich Güntzer Time Optimal Left to Right Construction
of Position Trees . . . . . . . . . . . 461--474
Edward A. Bender and
Cheryl E. Praeger and
Nicholas C. Wormald Optimal Worst Case Trees . . . . . . . . 475--489
J. W. de Bakker and
J.-J. Ch. Meyer Order and Metric in the Stream Semantics
of Elemental Concurrency . . . . . . . . 491--511
J. B\la\.zewicz and
W. Kubiak and
H. Röck and
J. Szwarcfiter Minimizing Mean Flow-Time with Parallel
Processors and Resource Constraints . . 513--524
Andrzej Duda and
Tadeusz Czachórski Performance Evaluation of Fork and Join
Synchronization Primitives . . . . . . . 525--553
Shyamal K. Chowdhury and
Pradip K. Srimani Worst Case Performance of Weighted Buddy
Systems . . . . . . . . . . . . . . . . 555--564
Bernard Chazelle Some Techniques for Geometric Searching
with Implicit Set Representations . . . 565--582
Walter Cunto and
Jose Luis Gascon Improving Time and Space Efficiency in
Generalized Binary Search Trees . . . . 583--594
Chua-Huang Huang and
Christian Lengauer The Derivation of Systolic
Implementations of Programs . . . . . . 595--632
Uwe Kastens Lifetime Analysis for Attributes . . . . 633--651
Marek J. Lao Combinator-Based Compilation of
Recursive Functions with Different
Parameter Passing Modes . . . . . . . . 653--678
Susan Horwitz and
Alan J. Demers and
Tim Teitelbaum An Efficient General Iterative Algorithm
for Dataflow Analysis . . . . . . . . . 679--694
Samuel Kamin The Expressive Theory of Stacks . . . . 695--709
Eric C. R. Hehner and
Andrew J. Malton Termination Conventions and Comparative
Semantics . . . . . . . . . . . . . . . 1--14
Alain Finkel and
Annie Choquet FIFO nets without order deadlock . . . . 15--36
Athanasios K. Tsakalidis The Nearest Common Ancestor in a Dynamic
Tree . . . . . . . . . . . . . . . . . . 37--54
Victor Vianu Database Survivability Under Dynamic
Constraints . . . . . . . . . . . . . . 55--84
Mahadevan Ganapathi and
Charles N. Fischer Integrating Code Generation and Peephole
Optimization . . . . . . . . . . . . . . 85--109
Friedrich L. Bauer and
Martin Wirsing Crypt-equivalent algebraic
specifications . . . . . . . . . . . . . 111--153
Thomas W. Reps Incremental Evaluation for Attribute
Grammars with Unrestricted Movement
Between Tree Modifications . . . . . . . 155--178
Luc Bougé On the Existence of Symmetric Algorithms
to Find Leaders in Networks of
Communicating Sequential Processes . . . 179--201
Andrzej Ehrenfeucht and
Hendrik Jan Hoogeboom and
Grzegorz Rozenberg Recording the Use of Memory in
Right-Boundary Grammars and Push-Down
Automata . . . . . . . . . . . . . . . . 203--231
Donald T. Sannella and
Andrzej Tarlecki Toward formal development of programs
from algebraic specifications:
implementations revisited . . . . . . . 233--281
Ming-Hua Zhang A Second Order Theory of Data Types . . 283--303
A. E. K. Sobel and
N. Soundararajan A Proof System for Distributed Processes 305--332
John H. Reif and
Scott A. Smolka The Complexity of Reachability in
Distributed Communicating Processes . . 333--354
Robert Giegerich Composition and Evaluation of Attribute
Coupled Grammars . . . . . . . . . . . . 355--423
Ulf R. Schmerl Resolution on Formula Trees . . . . . . 425--438
Andrzej Biela Program-Substitution and Admissibility
of Rules in Algorithmic Logic . . . . . 439--473
Edward P. F. Chan and
Héctor J. Hernández On Generating Database Schemes Bounded
or Constant-time-maintainable by
Extensibility . . . . . . . . . . . . . 475--496
William P. R. Mitchell Inductive Completion with Retracts . . . 497--514
Pavel Pudlák and
Vojt\vech Rödl and
Petr Savick\'y Graph Complexity . . . . . . . . . . . . 515--535
Joost Engelfriet and
George Leih and
Grzegorz Rozenberg Apex Graph Grammars and Attribute
Grammars . . . . . . . . . . . . . . . . 537--571
Paliath Narendran and
Friedrich Otto Elements of Finite Order for Finite
Weight-Reducing and Confluent Thue
Systems . . . . . . . . . . . . . . . . 573--591
R. J. R. Back A Calculus of Refinements for Program
Derivations . . . . . . . . . . . . . . 593--624
José Fiadeiro and
Amílcar Sernadas Specification and Verification of
Database Dynamics . . . . . . . . . . . 625--661
Sheldon Shen Cooperative Distributed Dynamic Load
Balancing . . . . . . . . . . . . . . . 663--676
Satish K. Tripathi and
David Finkel and
Erol Gelenbe Load Sharing in Distributed Systems with
Failures . . . . . . . . . . . . . . . . 677--689
Giorgio Levi and
Catuscia Palamidessi Contributions to the Semantics of Logic
Perpetual Processes . . . . . . . . . . 691--711
Anonymous Author index for Volumes 1--25
(1971--1988) . . . . . . . . . . . . . . 715--735
Johannes G. G. van de Vorst The formal development of a parallel
program performing $LU$-decomposition 1--17
Dean Jacobs and
Martin S. Feather Corrections to \em A Synthesis of
Several Sorting Algorithms by J.
Darlington . . . . . . . . . . . . . . . 19--23
Elisa Bertino and
Daniela Musto Correctness of Semantic Integrity
Checking in Database Management Systems 25--57
Pierpaolo Degano and
Rocco De Nicola and
Ugo Montanari A Distributed Operational Semantics for
CCS Based on Condition/Event Systems . . 59--91
Klaus Sutner and
Wolfgang Maass Motion Planning Among Time Dependent
Obstacles . . . . . . . . . . . . . . . 93--122
Luc Devroye Applications of the Theory of Records in
the Study of Random Trees . . . . . . . 123--130
Joost Engelfriet and
Heiko Vogler High Level Tree Transducers and Iterated
Pushdown Tree Transducers . . . . . . . 131--192
Walter Cunto and
Patricio V. Poblete Transforming Unbalanced Multiway Trees
into a Practical External Data Structure 193--211
Peter Lipps and
Ulrich Möncke and
Matthias Olk and
Reinhard Wilhelm Attribute (re)evaluation in OPTRAN . . . 213--239
Demetres D. Kouvatsos and
John Almond Maximum Entropy Two-Station Cyclic
Queues with Multiple General Servers . . 241--267
Christos Levcopoulos and
Mark H. Overmars A Balanced Search Tree with $O(1)$
Worst-case Update Time . . . . . . . . . 269--277
Róbert Szelepcsényi The Method of Forced Enumeration for
Nondeterministic Automata . . . . . . . 279--284
Eric C. R. Hehner and
Lorene E. Gupta and
Andrew J. Malton Erratum: ``Predicative methodology''
[Acta Inform. \bf 23 (1986), no. 5,
487--505; MR 87k:68090] . . . . . . . . 285--285
Joseph M. Morris Laws of Data Refinement . . . . . . . . 287--308
Wim H. Hesselink Predicate-Transformer Semantics of
General Recursion . . . . . . . . . . . 309--332
Walter Vogler Failures Semantics and Deadlocking of
Modular Petri Nets . . . . . . . . . . . 333--348
Ricardo A. Baeza-Yates Modeling Splits in File Structures . . . 349--362
Johannes Köbler and
Uwe Schöning and
Jacobo Torán On Counting and Approximation . . . . . 363--379
Edward G. Belaga Through the mincing machine with a
Boolean layer cake. Nonstandard
computations over Boolean circuits in
the lower-bounds-to-circuit-size
complexity proving . . . . . . . . . . . 381--407
A. Bijlsma and
P. A. Matthews and
J. G. Wiltink A Sharp Proof Rule for Procedures in
$wp$ Semantics . . . . . . . . . . . . . 409--419
Bin Zhang and
Meichun Hsu Unsafe Operations in B-Trees . . . . . . 421--438
Ricardo A. Baeza-Yates Expected Behaviour of $B^+$-trees under
Random Insertions . . . . . . . . . . . 439--471
Bing-Chao Huang and
Michael A. Langston Stable Duplicate-Key Extraction with
Optimal Time and Space Bounds . . . . . 473--484
Paul Helman A Family of NP-Complete Data Aggregation
Problems . . . . . . . . . . . . . . . . 485--499
Demetres D. Kouvatsos and
John Almond Erratum: ``Maximum entropy two-station
cyclic queues with multiple general
servers'' . . . . . . . . . . . . . . . 501--501
Laurent Pierre and
Sylviane R. Schwer Rational Index of Vector Addition
Systems Languages . . . . . . . . . . . 503--525
Helmut Seidl On the Finite Degree of Ambiguity of
Finite Tree Automata . . . . . . . . . . 527--542
Yennun Huang and
Pankaj Jalote Analytic Models for the Primary Site
Approach to Fault-Tolerance . . . . . . 543--557
Ian F. Akyildiz and
Horst von Brand Computational Algorithms for Networks of
Queues with Rejection Blocking . . . . . 559--576
K. V. S. Ramarao Complexity of Distributed Commit
Protocols . . . . . . . . . . . . . . . 577--595
Witold Litwin and
Yehoshua Sagiv and
K. Vidyasankar Concurrency and Trie Hashing . . . . . . 597--614
Mark A. Roth and
Henry F. Korth and
Abraham Silberschatz Null Values in Nested Relational
Databases . . . . . . . . . . . . . . . 615--642
Yijie Han and
Yoshihide Igarashi Time Lower Bounds for Parallel Sorting
on a Mesh-Connected Processor Array . . 643--655
Annegret Habel and
Hans-Jörg Kreowski and
Walter Vogler Metatheorems for Decision Problems on
Hyperedge Replacement Graph Languages 657--677
Igal Adiri and
John Bruno and
Esther Frostig and
A. H. G. Rinnooy Kan Single Machine Flow-Time Scheduling With
a Single Breakdown . . . . . . . . . . . 679--696
J. Csirik An On-Line Algorithm for Variable-Sized
Bin Packing . . . . . . . . . . . . . . 697--709
R. Kemp The Expected Additive Weight of Trees 711--740
Arunabha Sen Supercube: An Optimally Fault Tolerant
Network Architecture . . . . . . . . . . 741--748
Jean-Michel Autebert and
Joaquim Gabarró Iterated GSM's and Co-CFL . . . . . . . 749--769
Hans-Ulrich Simon Continuous Reductions Among
Combinatorial Optimization Problems . . 771--785
Demetres D. Kouvatsos and
John Almond Erratum: ``Maximum entropy two-station
cyclic queues with multiple general
servers'' . . . . . . . . . . . . . . . 787--787
Henk Alblas Iteration of Transformation Passes over
Attributed Program Trees . . . . . . . . 1--40
Carl E. Langenhop and
William E. Wright A Model of the Dynamic Behavior of
B-Trees . . . . . . . . . . . . . . . . 41--59
Peter Ru\vzi\vcka and
Igor Prívara An Almost Linear Robinson Unification
Algorithm . . . . . . . . . . . . . . . 61--71
K. K. Lau A Note on Synthesis and Classification
of Sorting Algorithms . . . . . . . . . 73--80
Jakob Gonczarowski and
Manfred K. Warmuth Scattered Versus Context-Sensitive
Rewriting . . . . . . . . . . . . . . . 81--95
Chua-Huang Huang and
Christian Lengauer An Incremental Mechanical Development of
Systolic Solutions to the Algebraic Path
Problem . . . . . . . . . . . . . . . . 97--124
Dirk Taubner and
Walter Vogler Step Failures Semantics and a Complete
Proof System . . . . . . . . . . . . . . 125--156
Vernon Rego Some Efficient Computational Algorithms
Related to Phase Models . . . . . . . . 157--177
Karel Culik II and
Juhani Karhumäki HDTOL Matching of Computations of
Multitape Automata . . . . . . . . . . . 179--191
Friedrich L. Bauer In memoriam: Andrei Petrovich Ershov, 19
April 1931--8 December 1988 . . . . . . 193--194
Betty Salzberg Merging Sorted Runs Using Large Main
Memory . . . . . . . . . . . . . . . . . 195--215
Gunther Schmidt and
Rudolf Berghammer and
Hans Zierer Describing Semantic Domains with Sprouts 217--245
Demetres D. Kouvatsos and
Nasreddine Tabet-Aouel A Maximum Entropy Priority Approximation
for a Stable G/G/1 Queue . . . . . . . . 247--286
Joseph M. Morris Temporal Predicate Transformers and Fair
Termination . . . . . . . . . . . . . . 287--313
Andrzej Ehrenfeucht and
Grzegorz Rozenberg Partial (Set) $2$-Structures. Part I:
Basic Notions and the Representation
Problem . . . . . . . . . . . . . . . . 315--342
Andrzej Ehrenfeucht and
Grzegorz Rozenberg Partial (Set) $2$-Structures. Part II:
State Spaces of Concurrent Systems . . . 343--368
Lawrence T. Kou On Efficient Implementation of an
Approximation Algorithm for the Steiner
Tree Problem . . . . . . . . . . . . . . 369--380
J.-J. Ch. Meyer and
Ernst-Rüdiger Olderog Hiding in Stream Semantics of Uniform
Concurrency . . . . . . . . . . . . . . 381--397
Clemens Lautemann The Complexity of Graph Languages
Generated by Hyperedge Replacement . . . 399--421
Mark H. Overmars and
Michiel H. M. Smid and
Mark T. de Berg and
Marc J. van Kreveld Maintaining Range Trees in Secondary
Memory. Part I: Partitions . . . . . . . 423--452
Michiel H. M. Smid and
Mark H. Overmars Maintaining Range Trees in Secondary
Memory. Part II: Lower Bounds . . . . . 453--480
Carroll Morgan and
P. H. B. Gardiner Data Refinement by Calculation . . . . . 481--503
Harald Sòndergaard and
Peter Sestoft Referential Transparency, Definiteness
and Unfoldability . . . . . . . . . . . 505--517
Erol Gelenbe and
Marisela Hernández Optimum Checkpoints with Age Dependent
Failures . . . . . . . . . . . . . . . . 519--531
Dirk Taubner Representing CCS Programs by Finite
Predicate/Transition Nets . . . . . . . 533--565
Joost Engelfriet and
Willem de Jong Attribute Storage Optimization by Stacks 567--581
R. J. R. Back and
J. von Wright Duality in Specification Languages: A
Lattice--theoretical Approach . . . . . 583--625
Lin Yu and
Daniel J. Rosenkrantz Minimizing Time-Space Cost for Database
Version Control . . . . . . . . . . . . 627--663
A. Michael Berman and
Marvin C. Paull and
Barbara G. Ryder Proving Relative Lower Bounds for
Incremental Algorithms . . . . . . . . . 665--683
Wladyslaw M. Turski On Specification of Multiprocessor
Computing . . . . . . . . . . . . . . . 685--696
Mohamed G. Gouda and
Rodney R. Howell and
Louis E. Rosier The Instability of Self-Stabilization 697--724
Rance Cleaveland Tableau-Based Model Checking in the
Propositional $\mu$-calculus . . . . . . 725--747
Andreas Weber On the Valuedness of Finite Transducers 749--780
Alexander Meduna Context Free Derivations on Word Monoids 781--786
Donald E. Knuth Nested Satisfiability . . . . . . . . . 1--6
K. Lodaya and
R. K. Shyamasundar Proof Theory for Exception Handling in a
Tasking Environment . . . . . . . . . . 7--41
Hessam Khoshnevisan Efficient Memo-Table Management
Strategies . . . . . . . . . . . . . . . 43--81
Andrzej Ehrenfeucht and
Grzegorz Rozenberg A characterization of set representable
labeled partial $2$-structures through
decompositions . . . . . . . . . . . . . 83--94
Jeremy Dick and
John Kalmus and
Ursula Martin Automating the Knuth Bendix Ordering . . 95--119
Thomas J. Marlowe and
Barbara G. Ryder Properties of Data Flow Frameworks. A
Unified Model . . . . . . . . . . . . . 121--163
Arne Andersson and
Christian Icking and
Rolf Klein and
Thomas Ottmann Binary Search Trees of Almost Optimal
Height . . . . . . . . . . . . . . . . . 165--178
Michel Latteux and
Paavo Turakainen On Characterizations of Recursively
Enumerable Languages . . . . . . . . . . 179--186
Rolf Hennicker Observational Implementation of
Algebraic Specifications . . . . . . . . 187--230
Eike Best and
Raymond Devillers and
Astrid Kiehn and
Lucia Pomello Concurrent Bisimulations in Petri Nets 231--264
Panagiotis J. Tomaras and
Demetres D. Kouvatsos MRE Hierarchical Decomposition of
General Queueing Network Models . . . . 265--295
James H. Anderson and
Mohamed G. Gouda A New Explanation of the Glitch
Phenomenon . . . . . . . . . . . . . . . 297--309
Deepak Kapur and
Paliath Narendran and
Daniel J. Rosenkrantz and
Hantao Zhang Sufficient--completeness,
ground--reducibility and their
complexity . . . . . . . . . . . . . . . 311--350
Symeon Bozapalidis Effective Construction of the Syntactic
Algebra of a Recognizable Series on
Trees . . . . . . . . . . . . . . . . . 351--363
Klaus Hülsmann and
Gunter Saake Theoretical Foundations of Handling
Large Substitution Sets in Temporal
Integrity Monitoring . . . . . . . . . . 365--407
A. Nico Habermann Alan J. Perlis (1922--1990) . . . . . . 409--410
Gregor Snelting The calculus of context relations . . . 411--445
Carol Critchlow and
Prakash Panangaden The Expressive Power of Delay Operators
in SCCS . . . . . . . . . . . . . . . . 447--452
Daniel P. Bovet and
Pierluigi Crescenzi Minimum-Delay Schedules in Layered
Networks . . . . . . . . . . . . . . . . 453--461
Reiner Kolla and
Bernd Serf The Virtual Feedback Problem in
Hierarchical Representations of
Combinational Circuits . . . . . . . . . 463--476
Friedrich Otto and
Louxin Zhang Decision Problems for Finite Special
String-Rewriting Systems that are
Confluent on Some Congruence Class . . . 477--510
Jan van den Bos and
Chris Laffra PROCOL: A Concurrent Object-Oriented
Language with Protocols Delegation and
Constraints . . . . . . . . . . . . . . 511--538
Uwe Kastens and
W. M. Waite An Abstract Data Type for Name Analysis 539--558
Peter G. Harrison On the Expansion of Non-Linear Functions 559--574
Joost Engelfriet Branching Processes of Petri Nets . . . 575--591
Ulrich Faigle and
W. Kern Some Order Dimension Bounds for
Communication Complexity Problems . . . 593--601
Mark Levene and
George Loizou Correction to \em Null Values in Nested
Relational Databases by Mark A. Roth, H.
F. Korth, and A. Silberschatz . . . . . 603--605
Mark A. Roth and
Henry F. Korth and
Abraham Silberschatz Addendum to \em Null values in nested
relational databases . . . . . . . . . . 607--610
Werner Pohlmann A Fixed Point Approach to Parallel
Discrete Event Simulation . . . . . . . 611--629
Xiaolei Qian The Expressive Power of the
Bounded-Iteration Construct . . . . . . 631--656
José M. Bernabéu-Aubán and
Mustaque Ahamad and
Mostafa H. Ammar Resource Finding in Store-and-Forward
Networks . . . . . . . . . . . . . . . . 657--680
Hsu-Chun Yen Priority Systems with many Identical
Processes . . . . . . . . . . . . . . . 681--692
David G. Cantor and
Erich Kaltofen On Fast Multiplication of Polynomials
over Arbitrary Algebras . . . . . . . . 693--701
Thomas P. Whaley Postorder Trees and Eulerian Numbers . . 703--712
Susan Horwitz and
Thomas W. Reps Efficient Comparison of Program Slices 713--732
Paul Pritchard Opportunistic Algorithms for Eliminating
Supersets . . . . . . . . . . . . . . . 733--754
Donald W. Gillies and
Jane W.-S. Liu Greed in Resource Scheduling . . . . . . 755--775
Paolo Atzeni and
Edward P. F. Chan Independent Database Schemes under
Functional and Inclusion Dependencies 777--799
Attahiru Sule Alfa and
Mingyuan Chen Approximating queue lengths in \em
M(t)/G/1 queue using the maximum entropy
principle . . . . . . . . . . . . . . . 801--815
Sanguthevar Rajasekaran and
Sandeep Sen On Parallel Integer Sorting . . . . . . 1--15
Mark B. Josephs Receptive Process Theory . . . . . . . . 17--31
Ian J. Hayes Multi-relations in Z: A cross between
multi-sets and binary relations . . . . 33--62
Didier Y. Hinz A Run-Time Load Balancing Strategy for
Highly Parallel Systems . . . . . . . . 63--94
Peter Roth Every binary pattern of length six is
avoidable on the two-letter alphabet . . 95--107
Charles N. Fischer and
Jon Mauney A Simple, Fast, and Effective \em
LL($1$) Error Repair Algorithm . . . . . 109--120
J. Xu On-Line Multiversion Database
Concurrency Control . . . . . . . . . . 121--160
Joost Engelfriet and
Linda Heyker Context-Free Hypergraph Grammars Have
the Same Term-Generating Power as
Attribute Grammars . . . . . . . . . . . 161--210
Peter G. Harrison and
Hessam Khoshnevisan On the synthesis of function inverses 211--239
Patrick E. O'Neil The SB-tree. An index-sequential
structure for high-performance
sequential access . . . . . . . . . . . 241--265
Svante Carlsson and
Jingsen Chen On Partitions and Presortedness of
Sequences . . . . . . . . . . . . . . . 267--280
M. W. Du and
S. C. Chang A Model and a Fast Algorithm for
Multiple Errors Spelling Correction . . 281--302
Jos C. M. Baeten and
Frits W. Vaandrager An Algebra for Process Creation . . . . 303--334
M. Aris Ouksel and
Otto Mayer A robust and efficient spatial data
structure. The nested
interpolation-based grid file . . . . . 335--373
Chung-Yee Lee and
Surya Danusaputro Liman Single Machine Flow-Time Scheduling with
Scheduled Maintenance . . . . . . . . . 375--382
Klaus Hinrichs and
Jürg Nievergelt and
Peter Schorn An All-Round Sweep Algorithm for
$2$-Dimensional Nearest-Neighbor
Problems . . . . . . . . . . . . . . . . 383--394
Dana S. Richards and
Jeffrey S. Salowe Stacks, Queues, and Deques with
Order-Statistic Operations . . . . . . . 395--414
Dong-wan Tcha and
Bum-Il Lee and
Young-duck Lee Processors Selection and Traffic
Splitting in a Parallel Processors
System . . . . . . . . . . . . . . . . . 415--423
Anna Slobodová Communication for Alternating Machines 425--441
Ricardo A. Baeza-Yates and
Walter Cunto Unbalanced Multiway Trees Improved by
Partial Expansions . . . . . . . . . . . 443--460
Anthony J. Fisher A ``Yo-Yo'' Parsing Algorithm for a
Large Class of van Wijngaarden Grammars 461--481
Aldo de Luca and
Stefano Varricchio On Finitely Recognizable Semigroups . . 483--498
Wuxu Peng and
S. Purushothaman Analysis of a Class of Communicating
Finite State Machines . . . . . . . . . 499--522
Nicolas Halbwachs and
Fabienne Lagnier and
Christophe Ratel An Experience in Proving Regular
Networks of Processes by Modular Model
Checking . . . . . . . . . . . . . . . . 523--543
Tero Harju and
H. C. M. Kleijn and
Michel Latteux Deterministic Sequential Functions . . . 545--554
Mogens Nielsen and
Grzegorz Rozenberg and
P. S. Thiagarajan Elementary Transition Systems and
Refinement . . . . . . . . . . . . . . . 555--578
Vernon Rego Naive Asymptotics for Hitting Time
Bounds in Markov Chains . . . . . . . . 579--594
Oliver Schoett Two Impossibility Theorems on Behaviour
Specification of Abstract Data Types . . 595--621
E. Fachini and
Andrea Maggiolo-Schettini and
Davide Sangiorgi Classes of Systolic $Y$-Tree Automata
and a Comparison with Systolic Trellis
Automata . . . . . . . . . . . . . . . . 623--643
Leo Marcus and
Telis Menas Expressibility of output equals input.
Negative and positive results . . . . . 645--662
Andreas Weber On the Lengths of Values in a Finite
Transducer . . . . . . . . . . . . . . . 663--687
Donald Sannella and
Stefan Soko\lowski and
Andrzej Tarlecki Toward Formal Development of Programs
from Algebraic Specifications:
Parameterisation Revisited . . . . . . . 689--736
S. Arun-Kumar and
M. Hennessy An Efficiency Preorder for Processes . . 737--760
E. Fachini and
Angelo Monti and
Margherita Napoli and
Domenico Parente Languages Accepted by Systolic $Y$-Tree
Automata: Structural Characterizations 761--778
Adrian Atanasiu A Class of Coders Based on GSM . . . . . 779--791
Bent Thomsen Plain CHOCS: A Second Generation
Calculus for Higher Order Processes . . 1--59
Iain A. Stewart Logical and Schematic Characterization
of Complexity Classes . . . . . . . . . 61--87
Antoine Petit Recognizable Trace Languages,
Distributed Automata and the
Distribution Problem . . . . . . . . . . 89--101
Kim Marriott Frameworks for Abstract Interpretation 103--129
Anna Hac Performance and Reliability Improvement
by Using Asynchronous Algorithms in Disk
Buffer Cache Memory . . . . . . . . . . 131--146
Marisa Navarro and
Fernando Orejas and
Jean-Luc Rémy Contextual Rewriting as a Sound and
Complete Proof Method for Conditional
LOG-Specifications . . . . . . . . . . . 147--180
Xavier Nicollin and
Joseph Sifakis and
Sergio Yovine From ATP to Timed Graphs and Hybrid
Systems . . . . . . . . . . . . . . . . 181--202
Paul S. Amerins and
Ricardo A. Baeza-Yates and
Derick Wood On Efficient Entreeings . . . . . . . . 203--213
Yuzheng Ding and
Mark Allen Weiss The relaxed min-max heap. A mergeable
double-ended priority queue . . . . . . 215--231
Patricio V. Poblete The Analysis of Heuristics for Search
Trees . . . . . . . . . . . . . . . . . 233--248
James H. Anderson A Fine-Grained Solution to the Mutual
Exclusion Problem . . . . . . . . . . . 249--265
Shigeki Iwata and
Takumi Kasai and
Etsuro Moriya Relations among Simultaneous Complexity
Classes of Nondeterministic and
Alternating Turing Machines . . . . . . 267--278
Karel Culik II and
Simant Dube $L$-Systems and Mutually Recursive
Function Systems . . . . . . . . . . . . 279--302
Thomas Lehmann and
Jacques Loeckx OBSCURE: A Specification Language for
Abstract Data Types . . . . . . . . . . 303--350
Gheorghe P\uaun On the Synchronization in Parallel
Communicating Grammar Systems . . . . . 351--367
Daniel M. Yellin Speeding up Dynamic Transitive Closure
for Bounded Degree Graphs . . . . . . . 369--384
Julien Cassaigne Unavoidable Binary Patterns . . . . . . 385--395
Jan Kratochvíl and
Mirko K\vrivánek Satisfiability of Co-Nested Formulas . . 397--403
David Spuler The Optimal Binary Search Tree for
Andersson's Search Algorithm . . . . . . 405--407
Edward G. Coffman, Jr. and
Leopold Flatto and
A. Ya. Kre\uìnin Scheduling Saves in Fault-Tolerant
Computations . . . . . . . . . . . . . . 409--423
Walid G. Aref and
Hanan Samet Decomposing a Window into Maximal
Quadtree Blocks . . . . . . . . . . . . 425--439
Alexandru Mateescu and
Arto Salomaa On Simplest Possible Solutions for Post
Correspondence Problems . . . . . . . . 441--457
Luc Devroye On the Expected Height of
Fringe-Balanced Trees . . . . . . . . . 459--466
K. Narayan Kumar and
Paritosh K. Pandya Infinitary Parallelism without Unbounded
Nondeterminism in CSP . . . . . . . . . 467--487
Jan Van den Bussche On Minimizing the $\forall$-$\neg$
Degree of a Connective-Free Formula . . 489--502
Ambuj K. Singh Program Refinement in Fair Transition
Systems . . . . . . . . . . . . . . . . 503--535
Eddy Bevers and
Johan Lewi Proving Termination of (Conditional)
Rewrite Systems. A Semantic Approach . . 537--568
Zhenyu Qian An Algebraic Semantics of Higher-Order
Types with Subtypes . . . . . . . . . . 569--607
Zohar Manna and
Amir Pnueli Models for Reactivity . . . . . . . . . 609--678
Alexander Tuzhilin Querying Datalog Programs with Temporal
Logic . . . . . . . . . . . . . . . . . 679--700
C. A. R. Hoare and
Jifeng He and
A. C. A. Sampaio Normal Form Approach to Compiler Design 701--739
Héctor J. Hernández Extended Nested Relations . . . . . . . 741--771
John Buckle A Characterisation of Meet and Join
Respecting Pre-Orders and Congruences on
Finite Lattices . . . . . . . . . . . . 773--785
Dana Scott A. Nico Habermann 1932--1993 . . . . . . 1--3
J. F. Costa and
Amílcar Sernadas and
Cristina Sernadas Object inheritance beyond subtyping . . 5--26
Jianwen Su Dependency Preservation in Semantic
Databases . . . . . . . . . . . . . . . 27--54
Nicoletta De Francesco and
Paola Inverardi Proving Finiteness of CCS Processes by
Non-Standard Semantics . . . . . . . . . 55--80
Christel Baier and
Mila E. Majster-Cederbaum The Connection between an Event
Structure Semantics and an Operational
Semantics for TCSP . . . . . . . . . . . 81--104
J. von Wright The Lattice of Data Refinement . . . . . 105--135
Catherine Mongenet and
Philippe Clauss and
Guy-René Perrin Geometrical Tools to Map Systems of
Affine Recurrence Equations on Regular
Arrays . . . . . . . . . . . . . . . . . 137--160
Andrzej Ehrenfeucht and
Paulien ten Pas and
Grzegorz Rozenberg Context-free Text Grammars . . . . . . . 161--206
Vincenzo Grassi Dependability Evaluation of Hierarchical
Systems . . . . . . . . . . . . . . . . 207--233
Symeon Bozapalidis and
George Rahonis On two Families of Forests . . . . . . . 235--260
Myung-Joon Lee and
Kwang-Moo Choe Boundedly \em LR($k$)-conflictable
Grammars . . . . . . . . . . . . . . . . 261--283
Hongzhong Wu On $n$-Column $0$, $1$-Matrices with all
$k$-Projections Surjective . . . . . . . 285--299
Jyrki Katajainen and
Tomi Pasanen Sorting Multisets Stably in Minimum
Space . . . . . . . . . . . . . . . . . 301--313
Oscar H. Ibarra and
Nicholas Q. Trân On Communication-Bounded Synchronized
Alternating Finite Automata . . . . . . 315--327
Karl Meinke A Recursive Second Order Initial Algebra
Specification of Primitive Recursion . . 329--340
Joost Engelfriet and
Linda Heyker and
George Leih Context-Free Graph Languages of Bounded
Degree are Generated by Apex Graph
Grammars . . . . . . . . . . . . . . . . 341--378
Volker Diekert and
Anca Muscholl Deterministic Asynchronous Automata for
Infinite Traces . . . . . . . . . . . . 379--397
Cliff B. Jones and
C. A. (Kees) Middelburg A Typed Logic of Partial Functions
Reconstructed Classically . . . . . . . 399--430
Armin Kühnemann and
Heiko Vogler Synthesized and Inherited Functions. A
new Computational Model for
Syntax-Directed Semantics . . . . . . . 431--477
Graham Farr On Problems with Short Certificates . . 479--502
Gerhard J. Woeginger Heuristics for Parallel Machine
Scheduling with Delivery Times . . . . . 503--512
Richard Hull and
Jianwen Su Domain Independence and the Relational
Calculus . . . . . . . . . . . . . . . . 513--524
Gheorghe P\uaun and
Grzegorz Rozenberg Prescribed Teams of Grammars . . . . . . 525--537
Aldo de Luca and
Stefano Varricchio Well Quasi-Orders and Regular Languages 539--557
G. I. Falin and
M. Mart\`\in D\`\iaz and
J. R. Artalejo Information theoretic approximations for
the M/G/1 retrial queue . . . . . . . . 559--571
Riccardo Torlone Update Operations in Deductive Databases
with Functional Dependencies . . . . . . 573--600
Uwe Kastens and
William M. Waite Modularity and Reusability in Attribute
Grammars . . . . . . . . . . . . . . . . 601--627
Astrid R. Rühl On Bounds of Response Time Performance
Achievable by Multiclass Single-Server
Queues . . . . . . . . . . . . . . . . . 629--650
Gilles Bernot and
Michel Bidoit and
Teodor Knapik Behavioural Approaches to Algebraic
Specifications: A Comparative Study . . 651--671
Philippe Flajolet and
Mordecai Golin Mellin Transforms and Asymptotics: The
Mergesort Recurrence . . . . . . . . . . 673--696
Astrid Kiehn Comparing Locality and Causality Based
Equivalences . . . . . . . . . . . . . . 697--718
Dirk Hauschildt and
Matthias Jantzen Petri Net Algorithms in the Theory of
Matrix Grammars . . . . . . . . . . . . 719--728
David Spuler Optimal Search Trees Using Two-Way Key
Comparisons . . . . . . . . . . . . . . 729--740
Christian Ferdinand and
Helmut Seidl and
Reinhard Wilhelm Tree Automata for Code Selection . . . . 741--760
Karel Culik II and
Jarkko Kari On the Power of $L$-Systems in Image
Generation . . . . . . . . . . . . . . . 761--773
Peter Kirschenhofer and
Helmut Prodinger The Path Length of Random Skip Lists . . 775--792
Joachim Biskup and
Pratul Dublish and
Yehoshua Sagiv Optimization of a Subclass of
Conjunctive Queries . . . . . . . . . . 1--26
W\lodzimierz Drabent What is Failure? An Approach to
Constructive Negation . . . . . . . . . 27--59
I. P. de Guzmán and
M. Ojeda and
A. Valverde A Formal Identification between Tuples
and Lists with an Application to
List-Arithmetic Categories . . . . . . . 61--78
Ramachandran Vaidyanathan and
Carlos R. P. Hartmann and
Pramod K. Varshney Parallel integer sorting using small
operations (*) . . . . . . . . . . . . . 79--92
Wei-Ngan Chin and
Masami Hagiya A Transformation Method for
Dynamic-Sized Tabulation . . . . . . . . 93--115
Janet A. Walz and
Gregory F. Johnson Inductive Attribute Grammars: A Basis
for Incremental Program Execution . . . 117--144
W.-J. Hsu and
C. V. Page Parallel Tree Contraction and Prefix
Computations on a Large Family of
Interconnection Topologies . . . . . . . 145--153
Lefteris M. Kirousis and
Andreas G. Veneris Efficient Algorithms for Checking the
Atomicity of a Run of Read and Write
Operations . . . . . . . . . . . . . . . 155--170
Thomas Eiter Generating Boolean $\mu$-Expressions . . 171--187
Ludmila Cherkasova and
Rodney R. Howell and
Louis E. Rosier Bounded Self-Stabilizing Petri Nets . . 189--207
Baudouin Le Charlier and
Pascal Van Hentenryck Reexecution in Abstract Interpretation
of Prolog . . . . . . . . . . . . . . . 209--253
Adam L. Buchsbaum and
Rajamani Sundar and
Robert Endre Tarjan Lazy Structure Sharing for Query
Optimization . . . . . . . . . . . . . . 255--270
Vasudha Krishnaswamy and
John Bruno On the complexity of concurrency control
using semantic information (*) . . . . . 271--284
Alexander Meduna Syntactic Complexity of Scattered
Context Grammars . . . . . . . . . . . . 285--298
Ekkart Kindler Invariants, composition, and
substitution (*) . . . . . . . . . . . . 299--312
Raymond R. Devillers $S$-invariant analysis of general
recursive Petri boxes . . . . . . . . . 313--345
Cinzia Bernardeschi and
Nicoletta De Francesco and
Gigliola Vaglini A Petri Nets Semantics for Data Flow
Networks . . . . . . . . . . . . . . . . 347--374
M. Hennessy and
X. Liu A Modal Logic for Message Passing
Processes . . . . . . . . . . . . . . . 375--393
Etsuji Tomita and
Kazushi Seino The Extended Equivalence Problem for a
Class of Non-Real-Time Deterministic
Pushdown Automata . . . . . . . . . . . 395--413
X. J. Chen and
Carlo Montangero Compositional Refinements in Multiple
Blackboard Systems . . . . . . . . . . . 415--458
Wuu Yang On the Look-Ahead Problem in Lexical
Analysis . . . . . . . . . . . . . . . . 459--476
Jean Néraud Detecting Morphic Images of a Word on
the Rank of a Pattern . . . . . . . . . 477--489
H. Jürgensen and
Ludwig Staiger Local Hausdorff Dimension . . . . . . . 491--507
Matthew Hennessy Concurrent Testing of Processes . . . . 509--543
Ugo Montanari and
Francesca Rossi Contextual Nets . . . . . . . . . . . . 545--596
Sumit Sur and
Pradip K. Srimani IEH Graphs. A Novel Generalization of
Hypercube Graphs . . . . . . . . . . . . 597--609
W. Wesley Peterson Variance of storage requirements for
B$+$-trees . . . . . . . . . . . . . . . 611--625
Robert Gold A Compositional Dataflow Semantics for
Petri Nets . . . . . . . . . . . . . . . 627--645
Eric Badouel and
Philippe Darondeau Trace Nets and Process Automata . . . . 647--679
Karel Culik II and
Peter Raj\vcáni Iterative Weighted Finite Transductions 681--703
Gary T. Leavens and
William E. Weihl Specification and Verification of
Object-Oriented Programs Using Supertype
Abstraction . . . . . . . . . . . . . . 705--778
Chong Kye Rhee and
Y. Daniel Liang Finding a Maximum Matching in a
Permutation Graph . . . . . . . . . . . 779--792
Anonymous Acknowledgement to Referees . . . . . . 793
Gadi Taubenfeld and
Shlomo Moran Possibility and Impossibility Results in
a Shared Memory Environment . . . . . . 1--20
Dominic Duggan and
Gordon V. Cormack and
John Ophel Kinded Type Inference for Parametric
Overloading . . . . . . . . . . . . . . 21--68
Davide Sangiorgi A Theory of Bisimulation for the
$\pi$-Calculus . . . . . . . . . . . . . 69--97
Aki Matsumoto and
D. S. Han and
Takao Tsuda Alias analysis of pointers in Pascal and
Fortran 90: Dependence analysis between
pointer references . . . . . . . . . . . 99--130
John Lee and
Alan Fekete Multi-Granularity Locking for Nested
Transactions: A Proof Using a
Possibilities Mapping . . . . . . . . . 131--152
A. Cau and
P. Collette Parallel Composition of
Assumption-Commitment Specifications: A
Unifying Approach for Shared Variable
and Distributed Message Passing
Concurrency . . . . . . . . . . . . . . 153--176
S. Haldar and
K. Vidyasankar Simple Extensions of $1$-writer Atomic
Variable Constructions to Multiwriter
Ones . . . . . . . . . . . . . . . . . . 177--202
Alexander Tuzhilin and
Zvi M. Kedem Modeling Data-Intensive Reactive Systems
with Relational Transition Systems . . . 203--231
Wim H. Hesselink Bounded Delay for a Free Address . . . . 233--254
Akhil Kumar and
Kavindra Malik Optimizing the Costs of Hierarchical
Quorum Consensus . . . . . . . . . . . . 255--275
Gunnar Stålmarck Short Resolution Proofs for a Sequence
of Tricky Formulas . . . . . . . . . . . 277--280
Géraud Sénizergues On the Rational Subsets of the Free
Group . . . . . . . . . . . . . . . . . 281--296
Jörg Desel and
Wolfgang Reisig The Synthesis Problem of Petri Nets . . 297--315
Luca Aceto and
David Murphy Timing and Causality in Process Algebra 317--350
Patrick E. O'Neil and
Edward Cheng and
Dieter Gawlick and
Elizabeth J. O'Neil The Log-Structured Merge-Tree (LSM-Tree) 351--385
J. Díaz and
M. J. Serna and
Jacobo Torán Parallel Approximation Schemes for
problems on planar graphs . . . . . . . 387--408
Petr Jan\vcar and
Franti\vsek Mráz and
Martin Plátek Forgetting Automata and Context-Free
Languages . . . . . . . . . . . . . . . 409--420
N. A. Harman and
J. V. Tucker Algebraic models of microprocessors:
Architecture and organisation . . . . . 421--456
Alexander Meduna Syntactic Complexity of Context-Free
Grammars Over Word Monoids . . . . . . . 457--462
Egon Wanke Undecidability of Restricted Uniform
Recurrence Equations . . . . . . . . . . 463--475
R\uazvan Diaconescu Category-Based Modularisation for
Equational Logic Programming . . . . . . 477--510
Mikkel Thorup Disambiguating Grammars by Exclusion of
Sub-Parse Trees . . . . . . . . . . . . 511--522
Andrea Maggiolo-Schettini and
Józef Winkowski A Kernel Language for Programmed
Rewriting of (Hyper)graphs . . . . . . . 523--546
Otto Nurmi and
Eljas Soisalon-Soininen Chromatic Binary Search Trees: A
Structure for Concurrent Rebalancing . . 547--557
Vladimir Deineko and
Rüdiger Rudolf and
Gerhard J. Woeginger On the recognition of permuted Supnick
and incomplete Monge matrices . . . . . 559--569
Andrzej Ehrenfeucht and
Gheorghe P\uaun and
Grzegorz Rozenberg The Linear Landscape of External
Contextual Languages . . . . . . . . . . 571--593
M. R. K. Krishna Rao Relating Confluence,
Innermost-Confluence and
Outermost-Confluence Properties of Term
Rewriting Systems . . . . . . . . . . . 595--606
Sanjeev Saxena Parallel Integer Sorting and Simulation
Amongst CRCW Models . . . . . . . . . . 607--619
Foued Ameur and
Paul Fischer and
Klaus-Uwe Höffgen and
Friedhelm Meyer auf der Heide Trial and Error: A new approach to
space-bounded learning . . . . . . . . . 621--630
Eberhard Bertsch An Observation on Suffix Redundancy in
\em LL($1$) Error Repair . . . . . . . . 631--639
Pierpaolo Degano and
José Meseguer and
Ugo Montanari Axiomatizing the Algebra of Net
Computations and Processes . . . . . . . 641--667
Falko Bause On the Analysis of Petri Nets with
Static Priorities . . . . . . . . . . . 669--685
Robert H. Sloan and
Ugo A. Buy Reduction Rules for Time Petri Nets . . 687--706
Robin Milner Calculi for Interaction . . . . . . . . 707--737
Thomas W. Reps On the Sequential Nature of
Interprocedural Program-Analysis
Problems . . . . . . . . . . . . . . . . 739--757
Andrzej Biela and
Jakub Borowczyk RETRPROV, A System that Looks for Axioms 759--780
Stephan Heilbrunner A Direct Complement Construction for \em
LR($1$) Grammars . . . . . . . . . . . . 781--797
Ke Wang and
Weining Zhang and
Siu-Cheung Chau Weakly Independent Database Schemes . . 1--22
N. W. Keesmaat and
H. C. M. Kleijn Net-Based Control Versus Rational
Control. The Relation Between ITNC
Vector Languages and Rational Relations 23--57
Zoltán Fülöp and
Sándor Vágvölgyi Minimal Equational Representations of
Recognizable Tree Languages . . . . . . 59--84
Javier Esparza Decidability of Model Checking for
Infinite-State Concurrent Systems . . . 85--107
Thomas Eiter and
Heikki Mannila Distance Measures for Point Sets and
their Computation . . . . . . . . . . . 109--133
Mark Levene and
George Loizou The Additivity Problem for Functional
Dependencies in Incomplete Relations . . 135--149
Karel Culik II and
Jarkko Kari Computational Fractal Geometry with WFA 151--166
Levent V. Orman Relational Database Constraints as
Counterexamples . . . . . . . . . . . . 167--189
Teodor Rus and
Sriram V. Pemmaraju Using Graph Coloring in an Algebraic
Compiler . . . . . . . . . . . . . . . . 191--209
Alexander Shapiro A Generalized Distribution Model for
Random Recursive Trees . . . . . . . . . 211--216
Ismo Hakala and
Juha Kortelainen On the System of word equations $x^i_1
x^i_2 \cdots x^i_m = y^i_1 y^i_2 \cdots
y^i_n$ ($i=1, 2, \ldots$) in a Free
Monoid . . . . . . . . . . . . . . . . . 217--230
Hristo N. Djidjev and
Shankar M. Venkatesan Reduced Constants for Simple Cycle Graph
Separation . . . . . . . . . . . . . . . 231--243
Petr Savický and
Ingo Wegener Efficient Algorithms for the
Transformation Between Different Types
of Binary Decision Diagrams . . . . . . 245--256
Victor Mitrana On the Interdependence Between Shuffle
and Crossing-Over Operations . . . . . . 257--266
Arnd Rußmann Dynamic \em LL($k$) Parsing . . . . . . 267--289
Flavio Corradini and
Rocco De Nicola Locality Based Semantics for Process
Algebras . . . . . . . . . . . . . . . . 291--324
Koichi Yamazaki A Hierarchy of the Class of Apex NLC
Graph Languages by Bounds on the Number
of Nonterminal Nodes in Productions . . 325--335
Y. Daniel Liang and
Maw-Shang Chang Minimum Feedback Vertex Sets in
Cocomparability Graphs and Convex
Bipartite Graphs . . . . . . . . . . . . 337--346
Karel Culik II and
Simant Dube Implementing Daubechies Wavelet
Transform with Weighted Finite Automata 347--366
Ryszard Janicki and
Maciej Koutny Fundamentals of Modelling Concurrency
Using Discrete Relational Structures . . 367--388
Kenichi Morita and
Noritaka Nishihara and
Yasunori Yamamoto and
Zhiguo Zhang A Hierarchy of Uniquely Parsable Grammar
Classes and Deterministic Acceptors . . 389--410
Georg Trogemann and
Matthias Gente Performance Analysis of Parallel
Programs Based on Directed Acyclic
Graphs . . . . . . . . . . . . . . . . . 411--428
Kemal Efe and
Nancy Eleser An Optimal Emulator and VLSI Layout for
Complete Binary Trees . . . . . . . . . 429--447
Roberto Barbuti and
Nicoletta Di Francesco and
Antonella Santone Algebraic computational models of
OR-parallel execution of Prolog . . . . 449--489
Robert Stephens A Survey of Stream Processing . . . . . 491--541
Sampath Rangarajan and
Yennun Huang and
Satish K. Tripathi On the scalability and mean-time to
failure of $k$ resilient protocols . . . 543--556
Nieves R. Brisaboa and
Héctor J. Hernández Testing Bag-Containment of Conjunctive
Queries . . . . . . . . . . . . . . . . 557--578
Chi-Chung Hui and
Samuel T. Chanson Minimal Communication Cost Software
Construction in the Internet Environment 579--595
Albert Nymeyer and
Joost-Pieter Katoen Code Generation Based on Formal BURS
Theory and Heuristic Search . . . . . . 597--635
János Aczél and
Wolfgang Ertel A New Formula for Speedup and its
Characterization . . . . . . . . . . . . 637--652
C. Samuel Hsieh A Fine-Grained Data-Flow Analysis
Framework . . . . . . . . . . . . . . . 653--665
Vijay K. Garg and
Alexander I. Tomlinson Using the Causal Domain to Specify and
verify Distributed Programs . . . . . . 667--686
Apostolos Burnetas and
Daniel Solow and
Rishi Agarwal An Analysis and Implementation of an
Efficient In-Place Bucket Sort . . . . . 687--700
Christel Baier and
Mila E. Majster-Cederbaum Metric Semantics from Partial Order
Semantics . . . . . . . . . . . . . . . 701--735
Arnd Poetzsch-Heffter Prototyping Realistic Programming
Languages Based On Formal Specifications 737--772
Joost Engelfriet and
Jan Joris Vereijken Context-Free Graph Grammars and
Concatenation of Graphs . . . . . . . . 773--803
Flavio Corradini and
Roberto Gorrieri and
Marco Roccetti Performance Preorder and Competitive
Equivalence . . . . . . . . . . . . . . 805--835
Henning Fernau Unconditional Transfer in Regulated
Rewriting . . . . . . . . . . . . . . . 837--857
Lane A. Hemaspaandra and
Jörg Rothe and
Gerd Wechsung Easy Sets and Hard Certificate Schemes 859--879
John Bruno and
Edward G. Coffman, Jr. Optimal Fault-Tolerant Computing on
Multiprocessor Systems . . . . . . . . . 881--904
Dominique Laurent and
V. Phan Luong and
Nicolas Spyratos The Use of Deleted Tuples in Database,
Querying and Updating . . . . . . . . . 905--925
A. H. M. ter Hofstede and
E. Lippe and
Th. P. van der Weide Applications of a categorical framework
for conceptual data modeling . . . . . . 927--963
Anonymous Acknowledgement to Referees . . . . . . 965
Vincent D. Blondel Structured numbers: Properties of a
hierarchy of operations on binary trees 1--15
Rainer Kemp Generating words lexicographically: An
average-case analysis . . . . . . . . . 17--89
Beverly A. Sanders Data refinement of mixed specifications.
A generalization of UNITY . . . . . . . 91--129
Ralph J. R. Back and
Qiwen Xu Refinement of Fair Action Systems . . . 131--165
\cStefan Andrei and
Cristian Masalagiu About the Collatz Conjecture . . . . . . 167--179
Elvira Locuratolo and
Fausto Rabitti Conceptual classes and system classes in
object databases . . . . . . . . . . . . 181--210
Wenceslas Fernandez de la Vega and
Vangelis Th. Paschos and
Andreas N. Stafylopatis Average-case complexity for the
execution of recursive definitions on
relational databases . . . . . . . . . . 211--243
Edward Y. C. Cheng and
Michael Kaminski Context-free languages over infinite
alphabets . . . . . . . . . . . . . . . 245--267
Derrick G. Kourie and
G. Deon Oosthuizen Lattices in machine learning: Complexity
issues . . . . . . . . . . . . . . . . . 269--292
Alexander Rabinovich Modularity and expressibility for nets
of relations . . . . . . . . . . . . . . 293--327
Thomas Buchholz and
Martin Kutrib On time computability of functions in
one-way cellular automata . . . . . . . 329--352
Michele Boreale and
Davide Sangiorgi A fully abstract semantics for causality
in the $\pi$-calculus . . . . . . . . . 353--400
Lila Kari and
Gheorghe P\uaun and
Grzegorz Rozenberg and
Arto Salomaa and
Sheng Yu DNA computing, sticker systems, and
universality . . . . . . . . . . . . . . 401--420
Reuven Bar Yehuda and
Sergio Fogel Partitioning a sequence into few
monotone subsequences . . . . . . . . . 421--440
Roberto Baldoni and
Jean-Michel Helary and
Michel Raynal Consistent records in asynchronous
computations . . . . . . . . . . . . . . 441--455
Mooly Sagiv and
Nissim Francez and
Michael Rodeh and
Reinhard Wilhelm A logic-based approach to program flow
analysis . . . . . . . . . . . . . . . . 457--504
Zoltán Ésik and
Michael Bertol Nonfinite axiomatizability of the
equational theory of shuffle . . . . . . 505--539
D. Laurent and
V. Phan Luong and
N. Spyratos Erratum: ``The use of deleted tuples in
database querying and updating'' . . . . 541--541
Jop F. Sibeyn List ranking on meshes . . . . . . . . . 543--566
Volker Diekert and
Paul Gastin Approximating traces . . . . . . . . . . 567--593
Hing Leung On finite automata with limited
nondeterminism . . . . . . . . . . . . . 595--624
Juha Honkala Decision problems concerning thinness
and slenderness of formal languages . . 625--636
Jan Van den Bussche and
Luca Cabibbo Converting untyped formulas to typed
ones . . . . . . . . . . . . . . . . . . 637--643
Dani\`ele Beauquier and
Anatol Slissenko Polytime Model Checking for Timed
Probabilistic Computation Tree Logic . . 645--664
Salvatore Caporaso and
Michele Zito On a relation between uniform coding and
problems of the form ${\rm DTIMEF}(\scr
F)=? {\rm DSPACEF}(\scr F)$ . . . . . . 665--672
Hsu-Chun Yen Priority conflict-free Petri nets . . . 673--688
H. J. Shyr and
S. S. Yu Bi-catenation and shuffle product of
languages . . . . . . . . . . . . . . . 689--707
Chen-Ming Fan and
H. J. Shyr and
S. S. Yu $d$-words and $d$-languages . . . . . . 709--727
Amílcar Sernadas and
Cristina Sernadas and
Carlos Caleiro Denotational semantics of object
specification . . . . . . . . . . . . . 729--773
Alistair Moffat and
Ola Petersson and
Nicholas C. Wormald A tree-based Mergesort . . . . . . . . . 775--793
Eric Sanlaville and
Günter Schmidt Machine scheduling with availability
constraints . . . . . . . . . . . . . . 795--811
Eike Best and
Wojciech Fra\kczak and
Richard P. Hopkins and
Hanna Klaudel and
Elisabeth Pelz $M$-nets: An algebra of high-level Petri
nets, with an application to the
semantics of concurrent programming
languages . . . . . . . . . . . . . . . 813--857
Kim S. Larsen Amortized constant relaxed rebalancing
using standard rotations . . . . . . . . 859--874
Christoph Wedler and
Christian Lengauer On linear list recursion in parallel . . 875--909
Hsien-Kuei Hwang Asymptotic expansions of the mergesort
recurrences . . . . . . . . . . . . . . 911--919
Ralph-Johan Back and
Michael Butler Fusion and simultaneous execution in the
refinement calculus . . . . . . . . . . 921--949
Michel Bidoit and
Rolf Hennicker Modular correctness proofs of
behavioural implementations . . . . . . 951--1005
Lex Bijlsma and
Rob Nederpelt Dijkstra-Scholten predicate calculus:
concepts and misconceptions . . . . . . 1007--1036
Nicoletta De Francesco and
Antonella Santone A transformation system for concurrent
processes . . . . . . . . . . . . . . . 1037--1073
Joost Engelfriet and
Tjalling Gelsema Axioms for generalized graphs,
illustrated by a Cantor-Bernstein
proposition . . . . . . . . . . . . . . 1075--1096
Michael Schenke and
Ernst-Rüdiger Olderog Transformational design of real-time
systems. Part I: From requirements to
program specifications . . . . . . . . . 1--65
Michael Schenke and
Ernst-Rüdiger Olderog Transformational design of real-time
systems. Part II: From program
specifications to programs . . . . . . . 67--96
Klaus-Dieter Schewe and
Bernhard Thalheim Towards a theory of consistency
enforcement . . . . . . . . . . . . . . 97--141
William C. K. Yen and
C. Y. Tang An optimal algorithm for solving the
searchlight guarding problem on weighted
two-terminal series-parallel graphs . . 143--172
Millist W. Vincent Semantic foundations of 4NF in
relational database design . . . . . . . 173--213
Yijie Han and
Yoshihide Igarashi Parallel PROFIT/COST algorithms through
fast derandomization . . . . . . . . . . 215--232
Ivana \vCerná and
Mojmír K\vretínský and
Antonín Ku\vcera Comparing expressibility of normed BPA
and normed BPP processes . . . . . . . . 233--256
Guido Proietti An optimal algorithm for decomposing a
window into maximal quadtree blocks . . 257--266
Roni Khardon and
Heikki Mannila and
Dan Roth Reasoning with examples: propositional
formulae and database dependencies . . . 267--286
Amos Fiat and
Gerhard J. Woeginger On-line scheduling on a single machine:
minimizing the total completion time . . 287--293
R. J. R. Back and
J. von Wright Reasoning algebraically about loops . . 295--334
Pierpaolo Degano and
Corrado Priami and
Lone Leth and
Bent Thomsen Causality for debugging mobile agents 335--374
Beata Konikowska and
Marcin Bialasik Reasoning with first order
nondeterministic specifications . . . . 375--403
Hong Shen Finding the $k$ most vital edges with
respect to minimum spanning tree . . . . 405--424
Lars Lundberg and
Håkan Lennerstad Optimal bounds on the gain of permitting
dynamic allocation of communication
channels in distributed computing . . . 425--446
Shlomi Dolev and
Mohamed G. Gouda and
Marco Schneider Memory requirements for silent
stabilization . . . . . . . . . . . . . 447--462
Ferri Abolhassan and
Jörg Keller and
Wolfgang J. Paul On the cost-effectiveness of PRAMs . . . 463--487
Jesús N. Ravelo Two graph algorithms derived . . . . . . 489--510
Anthony J. Bonner and
Giansalvatore Mecca Querying sequence databases with
transducers . . . . . . . . . . . . . . 511--544
Karsten Schmidt How to calculate symmetries of Petri
nets . . . . . . . . . . . . . . . . . . 545--590
Hans-Dieter Ehrich and
Carlos Caleiro Specifying communication in distributed
information systems . . . . . . . . . . 591--616
Gary T. Leavens and
Don Pigozzi A complete algebraic characterization of
behavioral subtyping . . . . . . . . . . 617--663
Lucian Ilie and
Arto Salomaa On the expressiveness of subset-sum
representations . . . . . . . . . . . . 665--672
T. C. E. Cheng and
Q. Ding Single machine scheduling with deadlines
and increasing rates of processing times 673--692
Yoshiki Kinoshita and
John Power Data refinement and algebraic structure 693--719
Gunnar Forst and
Anders Thorup Minimal Huffman trees . . . . . . . . . 721--734
Hosam Mahmoud and
Philippe Flajolet and
Philippe Jacquet and
Mireille Régnier Analytic variations on bucket selection
and sorting . . . . . . . . . . . . . . 735--760
Sergei Gorlatch and
Christian Lengauer Abstraction and performance in the
design of parallel programs: an overview
of the SAT approach . . . . . . . . . . 761--803
Juha Honkala On slender 0L languages over the binary
alphabet . . . . . . . . . . . . . . . . 805--815
Benedetto Intrigila and
Stefano Varricchio On the generalization of Higman and
Kruskal's theorems to regular languages
and rational trees . . . . . . . . . . . 817--835
Yonit Kesten and
Zohar Manna and
Amir Pnueli Verification of clocked and hybrid
systems . . . . . . . . . . . . . . . . 837--912
Erzsébet Csuhaj-Varjú and
Victor Mitrana Evolutionary systems: a language
generating device inspired by evolving
communities of cells . . . . . . . . . . 913--926
Frank Tip and
Peter F. Sweeney Class hierarchy specialization . . . . . 927--982
Arturo Carpi and
Aldo de Luca Special factors, periodicity, and an
application to Sturmian words . . . . . 983--1006
Aart Middeldorp and
Hitoshi Ohsaki Type introduction for equational
rewriting . . . . . . . . . . . . . . . 1007--1029
Anonymous Acknowledgement to Referees . . . . . . 1031--1032
Youichi Kobuchi and
Takashi Saito and
Hidenobu Nunome Semantics analysis through elementary
meanings . . . . . . . . . . . . . . . . 1--19
Desh Ranjan and
Enrico Pontelli and
Gopal Gupta Data structures for order-sensitive
predicates in parallel nondeterministic
systems . . . . . . . . . . . . . . . . 21--43
Béatrice Bérard and
Claudine Picaronny Accepting Zeno words: a way toward timed
refinements . . . . . . . . . . . . . . 45--81
Amir M. Ben-Amram and
Neil D. Jones Computational complexity via programming
languages: constant factors do matter 83--120
Danny Dubé and
Marc Feeley Efficiently building a parse tree from a
regular expression . . . . . . . . . . . 121--144
Stefan Andrei and
Manfred Kudlek and
Radu Stefan Niculescu Some results on the Collatz problem . . 145--160
Soma Chaudhuri and
Martha J. Kosa and
Jennifer L. Welch One-write algorithms for multivalued
regular and atomic registers . . . . . . 161--192
Boting Yang and
Paul Gillard The class Steiner minimal tree problem:
a lower bound and test problem
generation . . . . . . . . . . . . . . . 193--211
Hendrik Jan Hoogeboom and
Nik\`e van Vugt Fair sticker languages . . . . . . . . . 213--225
Manfred Broy Editorial: Letter from the Editor . . . 227--228
Rob van Glabbeek and
Ursula Goltz Refinement of actions and equivalence
notions for concurrent systems . . . . . 229--327
A. K. McIver and
C. Morgan Demonic, angelic and unbounded
probabilistic choices in sequential
programs . . . . . . . . . . . . . . . . 329--354
Philippe Chanzy and
Luc Devroye and
Carlos Zamora-Cura Analysis of range search for random
$k$-$d$ trees . . . . . . . . . . . . . 355--383
Ian J. Hayes and
Mark Utting A sequential real-time refinement
calculus . . . . . . . . . . . . . . . . 385--448
Ferucio Laurentiu Tiplea and
Erkki Mäkinen and
Corina Apachite Synchronized extension systems . . . . . 449--465
Flavio Corradini and
Marco Pistore `Closed Interval Process Algebra' versus
`Interval Process Algebra' . . . . . . . 467--509
Henning Fernau Parallel communicating grammar systems
with terminal transmission . . . . . . . 511--540
Joseph M. Morris and
Alexander Bunkenburg A theory of bunches . . . . . . . . . . 541--561
Luc Moreau and
Jean Duprat A construction of distributed reference
counting . . . . . . . . . . . . . . . . 563--595
Arturo Carpi and
Aldo de Luca Periodic-like words, periodicity, and
boxes . . . . . . . . . . . . . . . . . 597--618
Changwook Kim Efficient recognition algorithms for
boundary and linear eNCE graph languages 619--632
John Aycock and
Nigel Horspool and
Jan Janousek and
Borivoj Melichar Even faster generalized LR parsing . . . 633--651
Laurent Alonso and
René Schott On the tree inclusion problem . . . . . 653--670
Shin-ichi Morimoto and
Masataka Sassa Yet another generation of LALR parsers
for regular right part grammars . . . . 671--697
Sergio Greco and
Domenico Sacc\`a and
Carlo Zaniolo Extending stratified datalog to capture
complexity classes ranging from ${\cal
P}$ to ${\cal QH}$ . . . . . . . . . . . 699--725
Rob van Stee and
Han La Poutré Running a job on a collection of partly
available machines, with on-line
restarts . . . . . . . . . . . . . . . . 727--742
Kim S. Larsen and
Thomas Ottmann and
Eljas Soisalon-Soininen Relaxed balance for search trees with
local rebalancing . . . . . . . . . . . 743--763
Jan Ramon and
Maurice Bruynooghe A polynomial time computable metric
between point sets . . . . . . . . . . . 765--780
Eike Best and
Raymond Devillers and
Maciej Koutny Recursion and Petri nets . . . . . . . . 781--829
E. Astesiano and
G. Reggio Labelled transition logic: an outline 831--879
Ram Chakka and
Peter G. Harrison A Markov modulated multi-server queue
with negative customers --- The MM
CPP/GE/c/L G-queue . . . . . . . . . . . 881--919
Robert M. Colomb and
C. N. G. Dampney and
Michael Johnson Category-theoretic fibration as an
abstraction mechanism in information
systems . . . . . . . . . . . . . . . . 1--44
K. Meinke and
L. J. Steggles Correctness of dataflow and systolic
algorithms using algebras of streams . . 45--88
Salvatore La Torre and
Margherita Napoli Timed tree automata with an application
to temporal logic . . . . . . . . . . . 89--116
Masami Ito and
Carlos Martín-Vide and
Victor Mitrana Group weighted finite transducers . . . 117--129
Jürgen Dassow and
Gheorghe Paun and
Gabriel Thierrin and
Sheng Yu Tree-systems of morphisms . . . . . . . 131--153
Arend Rensink and
Heike Wehrheim Process algebra with action dependencies 155--234
Erkki Mäkinen and
Tarja Systä Minimally adequate teacher synthesizes
statechart diagrams . . . . . . . . . . 235--259
Michael Drmota The variance of the height of digital
search trees . . . . . . . . . . . . . . 261--276
Huimin Lin and
Wang Yi Axiomatising timed automata . . . . . . 277--305
Dan A. Simovici and
Dana Cristofor and
Laurentiu Cristofor Impurity measures in databases . . . . . 307--324
Jixue Liu and
Millist Vincent Containment and disjointedness in
partitioned normal form relations . . . 325--342
Wim H. Hesselink An assertional criterion for atomicity 343--366
Dominic Duggan Object type constructors . . . . . . . . 367--408
Arturo Carpi and
Aldo de Luca and
Stefano Varricchio Words, univalent factors, and boxes . . 409--436
P. J. M. Frederiks and
T. P. van der Weide Deriving and paraphrasing information
grammars using object-oriented analysis
models . . . . . . . . . . . . . . . . . 437--488
Miguel R. Penabad and
Nieves R. Brisaboa and
Héctor J. Hernández and
others A general procedure to check conjunctive
query containment . . . . . . . . . . . 489--529
Antonella Santone Automatic verification of concurrent
systems using a formula-based
compositional approach . . . . . . . . . 531--564
Kim S. Larsen Relaxed red-black trees with group
updates . . . . . . . . . . . . . . . . 565--586
Venkatesan T. Chakaravarthy and
Susan Horwitz On the non-approximability of points-to
analysis . . . . . . . . . . . . . . . . 587--598
P. Cordero and
M. Enciso and
I. P. de Guzmán Bases for closed sets of implicants and
implicates in temporal logic . . . . . . 599--619
Chris Giannella and
Dirk Van Gucht Adding a path connectedness operator to
FO $+$ poly (linear) . . . . . . . . . . 621--648
Jean Berstel and
Luc Boasson Formal properties of XML grammars and
languages . . . . . . . . . . . . . . . 649--671
E. G. Coffman, Jr. and
Peter J. Downey and
Peter Winkler Packing rectangles in a strip . . . . . 673--693
Paolo Bottoni and
Carlos Martín-Vide and
Gheorghe P\uaun and
others Membrane systems with
promoters/inhibitors . . . . . . . . . . 695--720
Mutyam Madhu and
Kamala Krithivasan Generalized normal form for rewriting P
systems . . . . . . . . . . . . . . . . 721--734
Flavio Corradini and
Walter Vogler and
Lars Jenner Comparing the worst-case efficiency of
asynchronous systems with PAFAS . . . . 735--792
Vincent Vajnovszki Gray visiting Motzkins . . . . . . . . . 793--811
Hosam M. Mahmoud The size of random bucket trees via urn
models . . . . . . . . . . . . . . . . . 813--838
Iiro Honkala and
Antoine Lobstein On the complexity of the identification
problem in Hamming spaces . . . . . . . 839--845
Chuzo Iwamoto and
Katsuyuki Tateishi and
Kenichi Morita and
others A quadratic speedup theorem for
iterative arrays . . . . . . . . . . . . 847--858
Anonymous Acknowledgement to Referees . . . . . . 859--860
Stéphane Coulondre A top-down proof procedure for
generalized data dependencies . . . . . 1--29
Giuseppe Della Penna and
Benedetto Intrigila and
Enrico Tronci and
others Synchronized regular expressions . . . . 31--70
Alfredo Burrieza and
Inma P. de Guzmán A functional approach for temporal
$\times$ modal logics . . . . . . . . . 71--96
Leah Epstein Bin stretching revisited . . . . . . . . 97--117
Ján Gawo and
Martin Nehéz Stochastic cooperative distributed
grammar systems and random graphs . . . 119--140
Friedrich L. Bauer and
Manfred Broy Edsger W. Dijkstra --- Acta Informatica
and Marktoberdorf . . . . . . . . . . . 141--142
B. Kiepuszewski and
A. H. M. ter Hofstede and
W. M. P. van der Aalst Fundamentals of control flow in
workflows . . . . . . . . . . . . . . . 143--209
Wim H. Hesselink Preference rankings in the face of
uncertainty . . . . . . . . . . . . . . 211--231
Axel Wabenhorst Stepwise development of fair distributed
systems . . . . . . . . . . . . . . . . 233--271
W. Reisig On Gurevich's theorem on sequential
algorithms . . . . . . . . . . . . . . . 273--305
A. Meduna Coincidental extension of scattered
context languages . . . . . . . . . . . 307--314
M. Ying Reasoning about probabilistic sequential
programs in a probabilistic logic . . . 315--389
Joachim Biskup and
Torsten Polle Adding inclusion dependencies to an
object-oriented data model with
uniqueness constraints . . . . . . . . . 391--449
James D. Currie and
Erica Moodie A word on $7$ letters which is
non-repetitive up to $\bmod 5$ . . . . . 451--468
Ji\vrí Srba Strong bisimilarity of simple process
algebras: complexity lower bounds . . . 469--499
Wan Fokkink and
Thuy Duong Vu Structural operational semantics and
bounded nondeterminism . . . . . . . . . 501--516
Juan Castellanos and
Carlos Martín-Vide and
Victor Mitrana and
others Networks of evolutionary processors . . 517--529
Mila Majster-Cederbaum and
Jinzhao Wu Towards action refinement for true
concurrent real time . . . . . . . . . . 531--577
Pedro V. Silva A note on pure and $p$-pure languages 579--595
E. G. Coffman and
J. Sethuraman and
V. G. Timkovsky Ideal preemptive schedules on two
processors . . . . . . . . . . . . . . . 597--612
Joost Engelfriet and
Sebastian Maneth A comparison of pebble tree transducers
with macro tree transducers . . . . . . 613--698
Alexander Meduna Erratum: Coincidental extension of
scattered context languages . . . . . . 699--699
Anonymous Acknowledgement to Referees . . . . . . 701--701
Anonymous Message from the Publisher: Publication
in the Online First Directory . . . . . 1--1
Joan Boyar and
Lene M. Favrholdt and
Kim S. Larsen and
others Extending the accommodating function . . 3--35
Ernst-Erich Doberkat Pipelines: Modelling a software
architecture through relations . . . . . 37--79
Anonymous Message from the Publisher . . . . . . . ??
Amir M. Ben-Amram and
Omer Berkman and
Holger Petersen Element distinctness on one-tape Turing
machines: a complete solution . . . . . 81--94
Victor Khomenko and
Maciej Koutny and
Walter Vogler Canonical prefixes of Petri net
unfoldings . . . . . . . . . . . . . . . 95--118
Lila Kari and
Stavros Konstantinidis and
Elena Losseva and
others Sticky-free and overhang-free DNA
languages . . . . . . . . . . . . . . . 119--157
N. Lesley and
A. Fekete Providing view synchrony for group
communication services . . . . . . . . . 159--210
Li Layuan and
Li Chunlin A distributed QoS-Aware multicast
routing protocol . . . . . . . . . . . . 211--233
Andrea Walther Program reversals for evolutions with
non-uniform step costs . . . . . . . . . 235--263
Michel Charpentier and
K. Mani Chandy Specification transformers: a predicate
transformer approach to composition . . 265--301
Wen-Chiung Lee and
Chin-Chia Wu and
Hua-Jung Sung A bi-criterion single-machine scheduling
problem with learning considerations . . 303--315
Roberto Barbuti and
Luca Tesei Timed automata with urgent transitions 317--347
Stefan Andrei and
Wei-Ngan Chin and
Salvador Valerio Cavadini Self-embedded context-free grammars with
regular counterparts . . . . . . . . . . 349--365
Yong He and
Yiwei Jiang Optimal algorithms for semi-online
preemptive scheduling problems on two
uniform machines . . . . . . . . . . . . 367--383
Joost Engelfriet and
Tjalling Gelsema A new natural structural congruence in
the pi-calculus with replication . . . . 385--430
Nicolas Markey Past is for free: on the complexity of
verifying linear temporal properties
with past . . . . . . . . . . . . . . . 431--458
Elizabeth Scott and
Adrian Johnstone Reducing non-determinism in right nulled
GLR parsers . . . . . . . . . . . . . . 459--489
Michael Domaratzki Trajectory-based codes . . . . . . . . . 491--527
Stéphane Grumbach and
Maurizio Rafanelli and
Leonardo Tininini On the equivalence and rewriting of
aggregate queries . . . . . . . . . . . 529--584
Silvia Bacchelli and
Elena Barcucci and
Elisabetta Grazzini and
Elisa Pergola Exhaustive generation of combinatorial
objects by ECO . . . . . . . . . . . . . 585--602
Thorsten Akkerman and
Christoph Buchheim and
Michael Jünger and
Daniel Teske On the complexity of drawing trees
nicely: corrigendum . . . . . . . . . . 603--607
Shlomi Dolev and
Elad Schiller Self-stabilizing group communication in
directed networks . . . . . . . . . . . 609--636
Steven Delvaux and
Leon Horsten On best transitive approximations to
simple graphs . . . . . . . . . . . . . 637--655
Leah Epstein and
Tamir Tassa Approximation schemes for the Min-Max
Starting Time Problem . . . . . . . . . 657--674
Anonymous Acknowledgement to Referees . . . . . . 675--675
Hosam M. Mahmoud Random sprouts as Internet models, and
Pólya processes . . . . . . . . . . . . . 1--18
Erratum An axiomatization of graphs . . . . . . 19--61
Hosam M. Mahmoud The size of random bucket trees via urn
models . . . . . . . . . . . . . . . . . 63--63
SungSuk Kim and
Sun Ok Yang and
SangKeun Lee Maintaining mobile transactional
consistency in hybrid broadcast
environments . . . . . . . . . . . . . . 65--81
Alexander Grigoriev and
Gerhard J. Woeginger Project scheduling with irregular costs:
complexity, approximability, and
algorithms . . . . . . . . . . . . . . . 83--97
Hosam Mahmoud and
Tatsuie Tsukiji Limit laws for terminal nodes in random
circuits with restricted fan-out: a
family of graphs generalizing binary
search trees . . . . . . . . . . . . . . 99--110
Artiom Alhazov and
Linqiang Pan and
Gheorghe P\uaun Trading polarizations for labels in $P$
systems with active membranes . . . . . 111--144
Pierluigi Frisco and
Hendrik Jan Hoogeboom $P$ systems with symport/antiport
simulating counter automata . . . . . . 145--170
Zheng-Zhu Li and
Y. S. Tsai Three-element codes with one
$d$-primitive word . . . . . . . . . . . 171--180
Dominic Duggan Type-based hot swapping of running
modules . . . . . . . . . . . . . . . . 181--220
Michael G. Lamoureux and
Bradford G. Nickerson A deterministic skip list for
$k$-dimensional range search . . . . . . 221--255
Erzsébet Csuhaj-Varjú and
Carlos Martín-Vide and
Victor Mitrana Hybrid networks of evolutionary
processors are computationally complete 257--272
Gerth Stòlting Brodal and
Erik D. Demaine and
J. Ian Munro Fast allocation and deallocation with an
improved buddy system . . . . . . . . . 273--291
Christophe Morvan and
Chloé Rispal Families of automata characterizing
context-sensitive languages . . . . . . 293--314
Yiwei Jiang and
Yong He Preemptive online algorithms for
scheduling with machine cost . . . . . . 315--340
Kamilla Klonowska and
Håkan Lennerstad and
Lars Lundberg and
Charlie Svahnberg Optimal recovery schemes in fault
tolerant distributed computing . . . . . 341--365
Stijn Vansummeren On the complexity of deciding typability
in the relational algebra . . . . . . . 367--381
Yifeng Chen and
J. W. Sanders The weakest specifunction . . . . . . . 383--414
Antonín Kucera and
Jan Strejcek The stuttering principle revisited . . . 415--434
Paolo Zuliani Compiling quantum programs . . . . . . . 435--474
Ingo Schmitt and
Gunter Saake A comprehensive database schema
integration method based on the theory
of formal concepts . . . . . . . . . . . 475--524
Mingsheng Ying $\pi$-calculus with noisy channels . . . 525--593
Leah Epstein and
Rob van Stee Online square and cube packing . . . . . 595--606
Anonymous Acknowledgement to Referees . . . . . . 607--607
Iwona Cie\'slik On-line coloring and cliques covering
for $K_{s,t}$-free graphs . . . . . . . 1--20
Markus Büttner Enhanced prefetching and caching
strategies for single- and multi-disk
systems . . . . . . . . . . . . . . . . 21--42
Floris Geerts and
Lieven Smits and
Jan Van den Bussche $N$-dimensional versus
$(N-1)$-dimensional connectivity testing
of first-order queries to semi-algebraic
sets . . . . . . . . . . . . . . . . . . 43--56
Lars Jacobsen and
Kim Skak Larsen Exponentially decreasing number of
operations in balanced trees . . . . . . 57--78
Rocco De Nicola and
Davide Sangiorgi Types in concurrency . . . . . . . . . . 79--81
Martin Berger and
Kohei Honda and
Nobuko Yoshida Genericity and the $\pi$-calculus . . . 83--141
Lorenzo Bettini and
Betti Venneri and
Viviana Bono MOMI: a calculus for mobile mixins . . . 143--190
Simon Gay and
Malcolm Hole Subtyping for session types in the pi
calculus . . . . . . . . . . . . . . . . 191--225
Matthew Hennessy and
Julian Rathke and
Nobuko Yoshida $D$ . . . . . . . . . . . . . . . . . . 227--290
Naoki Kobayashi Type-based information flow analysis for
the $\pi$-calculus . . . . . . . . . . . 291--347
Barbara König A general framework for types in graph
rewriting . . . . . . . . . . . . . . . 349--388
Mila Majster-Cederbaum and
Jinzhao Wu and
Houguang Yue Refinement of actions for real-time
concurrent systems with causal ambiguity 389--418
Andrzej Ehrenfeucht and
Tero Harju and
Grzegorz Rozenberg Embedding linear orders in grids . . . . 419--428
Francesca Levi A typed encoding of boxed into safe
ambients . . . . . . . . . . . . . . . . 429--500
Leah Epstein and
Tamir Tassa Vector assignment schemes for asymmetric
settings . . . . . . . . . . . . . . . . 501--514
Alberto Trombetta and
Danilo Montesi Equivalences and optimizations in an
expressive XSLT subset . . . . . . . . . 515--539
Alexander Meduna Deep pushdown automata . . . . . . . . . 541--552
Symeon Bozapalidis and
Antonios Kalampakas Recognizability of graph and pattern
languages . . . . . . . . . . . . . . . 553--581
Wim H. Hesselink Splitting forward simulations to cope
with liveness . . . . . . . . . . . . . 583--602
Srecko Brlek and
Elisa Pergola and
Olivier Roques Non uniform random generation of
generalized Motzkin paths . . . . . . . 603--616
Nikolaj Tatti Safe projections of binary data sets . . 617--638
Ferucio Laurentiu Tiplea and
Constantin Enea Abstractions of data types . . . . . . . 639--671
Klaus Indermark and
Thomas Noll Algebraic Correctness Proofs for
Compiling Recursive Function Definitions
with Strictness Information . . . . . . 1--43
Juergen Dingel Compositional Analysis of C/C++ Programs
with VeriSoft . . . . . . . . . . . . . 45--71
F. Corradini and
M. R. Di Berardini and
W. Vogler Fairness of Actions in System
Computations . . . . . . . . . . . . . . 73--130
Linqiang Pan and
Artiom Alhazov Solving HPP and SAT by $P$ Systems with
Active Membranes and Separation Rules 131--145
Amrinder Arora and
Fanchun Jin and
Gokhan Sahin and
Hosam Mahmoud and
Hyeong-Ah Choi Throughput analysis in wireless networks
with multiple users and multiple
channels . . . . . . . . . . . . . . . . 147--164
Tero Harju and
Dirk Nowotka Periods in Extensions of Words . . . . . 165--171
Zheng-Zhu Li and
H. J. Shyr and
Y. S. Tsai Classifications of Dense Languages . . . 173--194
Wim H. Hesselink Refinement verification of the lazy
caching algorithm . . . . . . . . . . . 195--222
Henning Bordihn and
Markus Holzer Programmed grammars and their relation
to the LBA problem . . . . . . . . . . . 223--242
Rafik Aguech and
Nabil Lasmar and
Hosam Mahmoud Distances in random digital search trees 243--264
Arnaud Carayol and
Antoine Meyer Linearly bounded infinite graphs . . . . 265--292
José María Amigó Representing the integers with powers of
$2$ and $3$ . . . . . . . . . . . . . . 293--306
Victor Khomenko and
Alex Kondratyev and
Maciej Koutny and
Walter Vogler Merged processes: a new condensed
representation of Petri net behaviour 307--330
Artiom Alhazov and
Carlos Martín-Vide and
Yurii Rogozhin On the number of nodes in universal
networks of evolutionary processors . . 331--339
José R. Paramá and
Nieves R. Brisaboa and
Miguel R. Penabad and
Ángeles S. Places A semantic approach to optimize linear
datalog programs . . . . . . . . . . . . 341--370
Wim Janssen and
Alexandr Korlyukov and
Jan Van den Bussche On the tree-transformation power of XSLT 371--393
Stavros Konstantinidis and
Nicolae Santean and
Sheng Yu Representation and uniformization of
algebraic transductions . . . . . . . . 395--417
Juha Honkala A new bound for the D0L sequence
equivalence problem . . . . . . . . . . 419--429
Andrew M. Gravell Verification conditions are code . . . . 431--447
Ernst-Rüdiger Olderog and
Anders P. Ravn Editorial: Hybrid Systems . . . . . . . 449--450
Eugene Asarin and
Thao Dang and
Antoine Girard Hybridization methods for the analysis
of nonlinear systems . . . . . . . . . . 451--476
Paulo Tabuada Symbolic models for control systems . . 477--500
Rafael Wisniewski and
Martin Raussen Geometric analysis of nondeterminacy in
dynamical systems . . . . . . . . . . . 501--519
James D. Currie and
Terry I. Visentin On Abelian $2$-avoidable binary patterns 521--533
Yuxi Fu Fair ambients . . . . . . . . . . . . . 535--594
Anonymous Acknowledgement to referees . . . . . . 595--595
Ladislav Vagner and
Borivoj Melichar Parallel LL parsing . . . . . . . . . . 1--21
Tian-Shyr Dai and
Yuh-Dauh Lyuu An exact subexponential-time lattice
algorithm for Asian options . . . . . . 23--39
John Derrick and
Heike Wehrheim On using data abstractions for model
checking refinements . . . . . . . . . . 41--71
Ladislav Vagner and
Borivoj Melichar Parallel LL parsing . . . . . . . . . . 73--73
Jan A. Bergstra and
Inge Bethke and
Alban Ponse Decision problems for pushdown threads 75--90
Stefan Kahrs Infinitary rewriting: meta-theory and
convergence . . . . . . . . . . . . . . 91--121
Wim H. Hesselink A criterion for atomicity revisited . . 123--151
Lila Kari and
Kalpana Mahalingam and
Gabriel Thierrin The syntactic monoid of hairpin-free
languages . . . . . . . . . . . . . . . 153--166
Alexander Okhotin Recursive descent parsing for Boolean
grammars . . . . . . . . . . . . . . . . 167--189
Vesa Halava and
Mika Hirvensalo Improved matrix pair undecidability
results . . . . . . . . . . . . . . . . 191--205
Millist W. Vincent and
Jixue Liu and
Mukesh Mohania On the equivalence between FDs in XML
and FDs in relations . . . . . . . . . . 207--247
Gilles Geeraerts and
Jean-François Raskin and
Laurent Van Begin Well-structured languages . . . . . . . 249--288
Foto Afrati and
Rada Chirkova and
Manolis Gergatsoulis and
Vassia Pavlaki View selection for real conjunctive
queries . . . . . . . . . . . . . . . . 289--321
Joseph M. Morris and
Malcolm Tyrrell Dual unbounded nondeterminacy,
recursion, and fixpoints . . . . . . . . 323--344
Chuzo Iwamoto and
Naoki Hatayama and
Yoshiaki Nakashiba and
Kenichi Morita and
Katsunobu Imai Translational lemmas for
DLOGTIME-uniform circuits, alternating
TMs, and PRAMs . . . . . . . . . . . . . 345--359
Antonio Bernini and
Elisabetta Grazzini and
Elisa Pergola and
Renzo Pinzani A general exhaustive generation
algorithm for Gray structures . . . . . 361--376
Rachele Fuzzati and
Massimo Merro and
Uwe Nestmann Distributed Consensus, revisited . . . . 377--425
Elizabeth Scott and
Adrian Johnstone and
Rob Economopoulos BRNGLR: a cubic Tomita-style GLR parsing
algorithm . . . . . . . . . . . . . . . 427--461
Serge Haddad and
Denis Poitrenaud Recursive Petri nets . . . . . . . . . . 463--508
Naomi Nishimura and
Prabhakar Ragde and
Stefan Szeider Solving #SAT using vertex covers . . . . 509--523
J. A. Bergstra and
C. A. Middelburg Synchronous cooperation for explicit
multi-threading . . . . . . . . . . . . 525--569
Yiwei Jiang and
Yong He Optimal semi-online algorithms for
preemptive scheduling problems with
inexact partial information . . . . . . 571--590
Toon Calders The complexity of satisfying constraints
on databases of transactions . . . . . . 591--624
Anonymous Acknowledgement to Referees . . . . . . 625--625
Symeon Bozapalidis Picture deformation . . . . . . . . . . 1--31
Amr Elmasry and
Michael L. Fredman Adaptive sorting: an information
theoretic perspective . . . . . . . . . 33--42
Zhenhua Duan and
Cong Tian and
Li Zhang A decision procedure for propositional
projection temporal logic with infinite
models . . . . . . . . . . . . . . . . . 43--78
Iwona Cie\'slik On-line graph coloring of
$\mathbb{P}_5$-free graphs . . . . . . . 79--91
Matteo Magnani and
Danilo Montesi Management of interval probabilistic
data . . . . . . . . . . . . . . . . . . 93--130
Tomás Brázdil and
Antonín Kucera and
Oldrich Strazovský Deciding probabilistic bisimilarity over
infinite-state probabilistic systems . . 131--154
Leah Epstein and
Asaf Levin and
Rob van Stee Two-dimensional packing with conflicts 155--175
Martin Kutrib and
Andreas Malcher and
Detlef Wotschke The Boolean closure of linear
context-free languages . . . . . . . . . 177--191
Amr Elmasry and
Claus Jensen and
Jyrki Katajainen Two-tier relaxed heaps . . . . . . . . . 193--210
Rudolf Berghammer Applying relation algebra and RelView to
solve problems on orders and lattices 211--236
N. Broutin and
L. Devroye and
E. McLeish Weighted height of random trees . . . . 237--277
Ryszard Janicki Relational structures model of
concurrency . . . . . . . . . . . . . . 279--320
Larissa Meinicke and
Ian J. Hayes Algebraic reasoning for probabilistic
action systems and while-loops . . . . . 321--382
Robert Brijder and
Hendrik Jan Hoogeboom The fibers and range of reduction graphs
in ciliates . . . . . . . . . . . . . . 383--402