Last update:
Fri Nov 22 09:47:20 MST 2024
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 \bf 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 \em 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
Symeon Bozapalidis and
Antonios Kalampakas An axiomatization of graphs . . . . . . 19--61
Hosam M. Mahmoud Erratum: \em 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 SAFE$D$PI: a language for controlling
mobile code . . . . . . . . . . . . . . 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
Benny Godlin and
Ofer Strichman Inference rules for proving the
equivalence of recursive procedures . . 403--439
Joseph M. Morris and
Malcolm Tyrrell Modelling higher-order dual
nondeterminacy . . . . . . . . . . . . . 441--465
Chen-Ming Fan and
C. C. Huang and
H. J. Shyr Regular autodense languages . . . . . . 467--477
Ferruccio Damiani and
Elena Giachino and
Paola Giannini and
Sophia Drossopoulou A type safe state abstraction for
coordination in Java-like languages . . 479--536
Hanna Klaudel and
Franck Pommereau M-nets: a survey . . . . . . . . . . . . 537--564
Sebastian Link Charting the completeness frontier of
inference systems for multivalued
dependencies . . . . . . . . . . . . . . 565--591
Alexander Meduna and
Ji\vrí Techet Scattered context grammars that erase
nonterminals in a generalized
$k$-limited way . . . . . . . . . . . . 593--608
Laura Bozzelli and
Mojmír K\vretínsky and
Vojt\vech \vRehák and
Jan Strej\vcek On decidability of LTL model checking
for process rewrite systems . . . . . . 1--28
Vince Várány Semi-synchronous transductions . . . . . 29--42
Rza Bashirov and
Fabrice Kordon and
Hüseyin Lort Exploiting colored Petri nets to decide
on permutation admissibility . . . . . . 43--55
Amir M. Ben-Amram A complexity tradeoff in
ranking-function termination proofs . . 57--72
Alex A. Aravind and
Wim H. Hesselink A queue based mutual exclusion algorithm 73--86
Roland Meyer A theory of structural stationarity in
the $\pi$-Calculus . . . . . . . . . . . 87--137
Joost Engelfriet The time complexity of typechecking
tree-walking tree transducers . . . . . 139--154
K. Subramani and
Hong-Jian Lai and
Xiaofeng Gu Random walks for selected boolean
implication and equivalence problems . . 155--168
Zden\vek Sawa and
Petr Jan\vcar Hardness of equivalence checking for
composed finite-state systems . . . . . 169--191
Cezar Câmpeanu and
Nicolae Santean On the closure of pattern expressions
languages under intersection with
regular languages . . . . . . . . . . . 193--207
Flavio Corradini and
Maria Rita Di Berardini and
Walter Vogler Liveness of a mutex algorithm in a fair
process algebra . . . . . . . . . . . . 209--235
Eike Best and
Philippe Darondeau A decomposition theorem for finite
persistent transition systems . . . . . 237--254
Achim D. Brucker and
Burkhart Wolff Semantics, calculi, and analysis for
object-oriented specifications . . . . . 255--284
Kamilla Klonowska and
Lars Lundberg and
Håkan Lennerstad The maximum gain of increasing the
number of preemptions in multiprocessor
scheduling . . . . . . . . . . . . . . . 285--295
José Enrique Armendáriz-Iñigo and
José Ramón González de Mendívil and
José Ramón Garitagoitia and
Francesc D. Muñoz-Esco Correctness proof of a database
replication protocol under the
perspective of the I/O automaton model 297--330
Davide Bresolin and
Angelo Montanari and
Gabriele Puppis A theory of ultimately periodic
languages and automata with an
application to time granularity . . . . 331--360
Gabriel Ciobanu and
Sergiu Rudeanu Final and sequential behaviours of
M-automata . . . . . . . . . . . . . . . 361--374
J. A. Bergstra and
C. A. Middelburg Machine structure oriented control code
logic . . . . . . . . . . . . . . . . . 375--401
Paolo Zuliani Reasoning about faulty quantum programs 403--432
Victor Khomenko and
Mark Schaefer and
Walter Vogler and
Ralf Wollowski STG decomposition strategies in
combination with unfolding . . . . . . . 433--474
Md. Sumon Shahriar and
Jixue Liu Preserving key in XML data
transformation . . . . . . . . . . . . . 475--507
Argimiro Arratia Quesada and
Iain A. Stewart On the power of deep pushdown stacks . . 509--531
Jan Janou\vsek and
Bo\vrivoj Melichar On regular tree languages and
deterministic pushdown automata . . . . 533--547
John Aycock and
Angelo Borsotti Early action in an Earley parser . . . . 549--559
Joost Engelfriet and
Eric Lilin and
Andreas Maletti Extended multi bottom-up tree
transducers: Composition and
decomposition . . . . . . . . . . . . . 561--590
Arturo Carpi and
Flavio D'Alessandro Strongly transitive automata and the
\vCerný conjecture . . . . . . . . . . . 591--607
Peter Habermehl and
Radu Iosif and
Tom Vojnar Automata-based verification of programs
with tree updates . . . . . . . . . . . 1--31
Mohammad Mahdi Jaghoori and
Marjan Sirjani and
Mohammad Reza Mousavi and
Ehsan Khamespanah and
Ali Movaghar Symmetry and partial order reduction
techniques in model checking Rebeca . . 33--66
Tien Van Do M/M/1 retrial queue with working
vacations . . . . . . . . . . . . . . . 67--75
Rudolf Berghammer and
Michael Winter Embedding mappings and splittings with
applications . . . . . . . . . . . . . . 77--110
Massimo Merro On the observational theory of the
CPS-calculus . . . . . . . . . . . . . . 111--132
Remco Loos and
Florin Manea and
Victor Mitrana Small universal accepting hybrid
networks of evolutionary processors . . 133--146
Luca Aceto and
Wan Fokkink and
Anna Ingolfsdottir and
MohammadReza Mousavi Lifting non-finite axiomatizability
results to extensions of process
algebras . . . . . . . . . . . . . . . . 147--177
Ik-Soon Kim and
Kwangkeun Yi LR error repair using the A* algorithm 179--207
Chen-Ming Fan and
C. C. Huang and
H. J. Shyr and
Kuo-Hsiang Chen A note on autodense related languages 209--219
Mingsheng Ying and
Yuan Feng Quantum loop programs . . . . . . . . . 221--250
Christian Dax and
Felix Klaedtke and
Martin Lange On regular temporal logics with past . . 251--277
Ruggero Lanotte and
Andrea Maggiolo-Schettini and
Angelo Troina Reachability results for timed automata
with unbounded data structures . . . . . 279--311
Shlomi Dolev and
Nir Tzachar Randomization adaptive
self-stabilization . . . . . . . . . . . 313--323
Dorit S. Hochbaum and
Asaf Levin How to allocate review tasks for robust
ranking . . . . . . . . . . . . . . . . 325--345
C. C. Huang A note on pure codes . . . . . . . . . . 347--357
Joan Boyar and
Martin R. Ehmsen and
Jens S. Kohrt and
Kim S. Larsen A theoretical comparison of LRU and
LRU-K . . . . . . . . . . . . . . . . . 359--374
Leah Epstein Equilibria for two parallel links: the
strong price of anarchy versus the price
of anarchy . . . . . . . . . . . . . . . 375--389
Martin Kutrib and
Hartmut Messerschmidt and
Friedrich Otto On stateless deterministic restarting
automata . . . . . . . . . . . . . . . . 391--412
Chen-Ming Fan and
C. C. Huang A note on prefix primitive words . . . . 413--423
Zheng-Zhu Li and
Y. S. Tsai Some properties of the disjunctive
languages contained in Q . . . . . . . . 1--18
Juha Honkala A characterization of rational D0L power
series . . . . . . . . . . . . . . . . . 19--24
F. Blanchet-Sadri and
Robert Merca\cs and
Sean Simmons and
Eric Weissenstein Avoidable binary patterns in partial
words . . . . . . . . . . . . . . . . . 25--41
Victor Mitrana and
Cristina T\^\irn\uauc\ua New bounds for the query complexity of
an algorithm that learns DFAs with
correction and equivalence queries . . . 43--50
Md. Enamul Kabir and
Hua Wang and
Elisa Bertino Efficient systematic clustering method
for $k$-anonymization . . . . . . . . . 51--66
Alex A. Aravind and
Wim H. Hesselink Nonatomic dual bakery algorithm with
bounded tokens . . . . . . . . . . . . . 67--96
Ana Cavalcanti and
Marie-Claude Gaudel Testing for refinement in Circus . . . . 97--147
Alexander Meduna and
Petr Zemek One-sided random context grammars . . . 149--163
Frank Drewes and
Johanna Högberg and
Andreas Maletti MAT learners for tree series: an
abstract data type and two realizations 165--189
Daniel Seidel and
Janis Voigtländer Refined typing to localize the impact of
forced strictness on free theorems . . . 191--211
Artem Polyvyanyy and
Matthias Weidlich and
Mathias Weske Connectivity of workflow nets: the
foundations of stepwise verification . . 213--242
Tien Van Do and
Ram Chakka and
Nam H. Do and
László Pap A Markovian queue with varying number of
servers and applications to the
performance comparison of HSDPA user
equipment . . . . . . . . . . . . . . . 243--269
Daowen Qiu and
Lvzhou Li and
Xiangfu Zou and
Paulo Mateus and
Jozef Gruska Multi-letter quantum finite automata:
decidability of the equivalence and
minimization of states . . . . . . . . . 271--290
Markus N. Rabe and
Sven Schewe Finite optimal control for time-bounded
reachability in CTMDPs and
continuous-time Markov games . . . . . . 291--315
Sándor Vágvölgyi CHAP and rewrite components . . . . . . 317--361
Juan Perna and
Jim Woodcock and
Augusto Sampaio and
Juliano Iyoda Correct hardware synthesis: an algebraic
approach . . . . . . . . . . . . . . . . 363--396
Pál Dömösi and
György Maróti On $\alpha_2$-$\nu_2$-products of
automata . . . . . . . . . . . . . . . . 397--408
Bogdan Aman and
Gabriel Ciobanu Solving a weak NP-complete problem in
polynomial time by using mutual mobile
membrane systems . . . . . . . . . . . . 409--415
Amit Chakrabarti and
Venkatesan Guruswami and
Andrew Wirth and
Anthony Wirth The query complexity of estimating
weighted averages . . . . . . . . . . . 417--426
Edward G. Coffman and
Dariusz Dereniowski and
Wieslaw Kubiak An efficient algorithm for finding ideal
schedules . . . . . . . . . . . . . . . 1--14
Yunhe Wang and
Li Jiao Using transition set sequences to
partition behaviors of Petri nets . . . 15--28
Symeon Bozapalidis and
Zoltán Fülöp and
George Rahonis Equational weighted tree transformations 29--52
F. Blanchet-Sadri and
Robert Mercas and
Sean Simmons and
Eric Weissenstein Erratum to: ``Avoidable binary patterns
in partial words'' . . . . . . . . . . . 53--54
Alexander Meduna and
Petr Zemek Nonterminal complexity of one-sided
random context grammars . . . . . . . . 55--68
Christian Stahl and
Walter Vogler A trace-based service semantics
guaranteeing deadlock freedom . . . . . 69--103
A. Lorencs The identity problem of finitely
generated bi-ideals . . . . . . . . . . 105--115
Pierre Lescanne and
Matthieu Perrinel `Backward' coinduction, Nash equilibrium
and the rationality of escalation . . . 117--137
J. A. Bergstra and
C. A. Middelburg Instruction sequence processing
operators . . . . . . . . . . . . . . . 139--172
Junhu Wang and
Jeffrey Xu Yu and
Chaoyi Pang and
Chengfei Liu Least common container of tree pattern
queries and its applications . . . . . . 173--202
Christel Baier and
Tomás Brázdil and
Marcus Größer and
Antonín Kucera Stochastic game logic . . . . . . . . . 203--224
Christian Choffrut and
Andreas Malcher and
Carlo Mereghetti and
Beatrice Palano First-order logics: some
characterizations and closure properties 225--248
Laura Bozzelli and
Axel Legay and
Sophie Pinchinat On timed alternating simulation for
concurrent timed games . . . . . . . . . 249--279
Chen-Ming Fan and
Cheng-Chih Huang and
Christine Chifen Tseng and
Jen-Tse Wang Prefix-primitive annihilators of
languages under some operations . . . . 281--293
Bastian Katz and
Ignaz Rutter and
Gerhard Woeginger An algorithmic study of switch graphs 295--312
Antonella Santone and
Gigliola Vaglini Abstract reduction in directed model
checking CCS processes . . . . . . . . . 313--341
Walter Guttmann Algebras for iteration and infinite
computations . . . . . . . . . . . . . . 343--359
Zhiyi Tan and
Long Wan and
Qi Zhang and
Wei Ren Inefficiency of equilibria for the
machine covering game on uniform
machines . . . . . . . . . . . . . . . . 361--379
Petr A. Golovach and
Bernard Lidický and
Barnaby Martin and
Daniël Paulusma Finding vertex-surjective graph
homomorphisms . . . . . . . . . . . . . 381--394
Cristian Ioan Vasile and
Ana Brândusa Pavel and
Ioan Dumitrache and
Gheorghe Paun On the power of enzymatic numerical P
systems . . . . . . . . . . . . . . . . 395--412
Pascal Caron and
Jean-Marc Champarnaud and
Ludovic Mignot Multi-tilde-bar expressions and their
automata . . . . . . . . . . . . . . . . 413--436
Cao Chunhua and
Yang Di and
Liu Yin Disjunctive languages related to
$p$-primitive words . . . . . . . . . . 437--444
Xian Xu Distinguishing and relating higher-order
and first-order processes by
expressiveness . . . . . . . . . . . . . 445--484
Michael Brand Does indirect addressing matter? . . . . 485--491
Fernando Arroyo and
Juan Castellanos and
Jürgen Dassow and
Victor Mitrana \ldots Accepting splicing systems with
permitting and forbidding words . . . . 1--14
Jetty Kleijn and
Maciej Koutny and
Marta Pietkiewicz-Koutny \ldots Step semantics of boolean nets . . . . . 15--39
Jürgen Dassow and
Florin Manea and
Bianca Truthe Networks of evolutionary processors: the
power of subregular filters . . . . . . 41--75
Lorenzo Bettini and
Ferruccio Damiani and
Ina Schaefer Compositional type checking of
delta-oriented software product lines 77--122
Stefan Kahrs Infinitary rewriting: closure operators,
equivalences and models . . . . . . . . 123--156
Stefano Bilotta and
Elisabetta Grazzini and
Elisa Pergola and
Renzo Pinzani Avoiding cross-bifix-free binary words 157--173
Tamar Aizikowitz and
Michael Kaminski Conjunctive grammars and alternating
pushdown automata . . . . . . . . . . . 175--197
Wim H. Hesselink Verifying a simplification of mutual
exclusion by Lycklama--Hadzilacos . . . 199--228
Benedek Nagy and
Friedrich Otto Deterministic pushdown-CD-systems of
stateless deterministic $ R(1)
$-automata . . . . . . . . . . . . . . . 229--255
Dongfeng Chen and
Rada Chirkova and
Fereidoon Sadri and
Tiia J. Salo Query optimization in information
integration . . . . . . . . . . . . . . 257--287
Amr Elmasry and
Arash Farzan and
John Iacono On the hierarchy of
distribution-sensitive properties for
data structures . . . . . . . . . . . . 289--295
Wim H. Hesselink A distributed resource allocation
algorithm for many processes . . . . . . 297--329
Vesa Halava and
Tero Harju New proof for the undecidability of the
circular PCP . . . . . . . . . . . . . . 331--341
Marie G. Christ and
Lene M. Favrholdt and
Kim S. Larsen Online multi-coloring on the path
revisited . . . . . . . . . . . . . . . 343--357
Jeongbong Seo and
Sungwoo Park Judgmental subtyping systems with
intersection types and modal types . . . 359--380
Clelia De Felice A note on the factorization conjecture 381--402
Fernando Rosa-Velardo Petri nets with name creation for
transient secure association . . . . . . 403--436
Yangjia Li and
Nengkun Yu and
Mingsheng Ying Termination of nondeterministic quantum
programs . . . . . . . . . . . . . . . . 1--24
Laura Bozzelli and
César Sánchez Visibly rational expressions . . . . . . 25--49
Suo Ping Li and
Yong Qiang Zhou and
Yong Zhou Delay and energy efficiency analysis of
multicast cooperative ARQ over wireless
networks . . . . . . . . . . . . . . . . 51--60
Eleni Mandrali and
George Rahonis On weighted first-order logics with
discounting . . . . . . . . . . . . . . 61--106
Francesco Ranzato An efficient simulation algorithm on
Kripke structures . . . . . . . . . . . 107--125
Doron Peled and
Sven Schewe Editorial: special issue on synthesis 127--128
Krishnendu Chatterjee and
Mickael Randour and
Jean-François Raskin Strategy synthesis for multi-dimensional
quantitative objectives . . . . . . . . 129--163
Peter Bulychev and
Alexandre David and
Kim G. Larsen and
Guangyuan Li Efficient controller synthesis for a
fragment of $ {\rm MTL}_{0, \infty } $ 165--192
Roderick Bloem and
Krishnendu Chatterjee and
Karin Greimel Synthesizing robust systems . . . . . . 193--220
Wladimir Fridman and
Bernd Puchala Distributed synthesis for regular and
contextfree specifications . . . . . . . 221--260
Uli Fahrenberg and
Axel Legay General quantitative specification
theories with modal transition systems 261--295
Zoltán Fülöp and
Heiko Vogler Forward and backward application of
symbolic tree transducers . . . . . . . 297--325
Alexander Meduna and
Petr Zemek Controlled finite automata . . . . . . . 327--337
Cao Chunhua and
Yang Shuang and
Yang Di Some kinds of primitive and
non-primitive words . . . . . . . . . . 339--346
Miquel Bertran and
Francesc Babot and
August Climent Formal communication elimination and
sequentialization equivalence proofs for
distributed system models . . . . . . . 347--418
Walter Cazzola and
Edoardo Vacchi On the incremental growth and shrinkage
of LR goto-graphs . . . . . . . . . . . 419--447
Manuel Sorge and
Hannes Moser and
Rolf Niedermeier and
Mathias Weller Exploiting a hypergraph model for
finding Golomb rulers . . . . . . . . . 449--471
Rémy Belmonte and
Petr A. Golovach and
Pim van 't Hof and
Daniël Paulusma Parameterized complexity of three edge
contraction problems with degree
constraints . . . . . . . . . . . . . . 473--497
Walter Vogler and
Christian Stahl and
Richard Müller Trace- and failure-based semantics for
responsiveness . . . . . . . . . . . . . 499--552
Martin Kutrib and
Andreas Malcher and
Matthias Wendlandt Head and state hierarchies for unary
multi-head finite automata . . . . . . . 553--569
Ernst-Rüdiger Olderog Letter from the Managing Editor . . . . 1--2
Rob J. van Glabbeek and
Ursula Goltz and
Ernst-Rüdiger Olderog Special issue on ``Combining
Compositionality and Concurrency'': part
1 . . . . . . . . . . . . . . . . . . . 3--4
Roberto Bruni and
Ugo Montanari and
Matteo Sammartino Revisiting causality, coalgebraically 5--33
Eike Best and
Raymond Devillers Synthesis and reengineering of
persistent systems . . . . . . . . . . . 35--60
Marco Bernardo and
Rocco De Nicola and
Michele Loreti Revisiting bisimilarity and its modal
logic for nondeterministic and
probabilistic processes . . . . . . . . 61--106
Gerald Lüttgen and
Flavio Corradini Special issue on ``Comprehending
asynchrony in specification and
analysis'' dedicated to Walter Vogler on
the occasion of his 60th birthday . . . 107--108
Han-Hing Dang and
Bernhard Möller Modal algebra and Petri nets . . . . . . 109--132
Eike Best and
Raymond Devillers State space axioms for $T$-systems . . . 133--152
Jörg Desel and
Görkem Kilinç Observable liveness of Petri nets . . . 153--174
Rob J. van Glabbeek and
Peter Höfner CCS: It's not fair! . . . . . . . . . . 175--205
Antti Valmari On constructibility and
unconstructibility of LTS operators from
other LTS operators . . . . . . . . . . 207--234
Rolf Hennicker and
Alexander Knapp Moving from interface theories to
assembly theories . . . . . . . . . . . 235--268
Nikola Benes and
Jan Kretínský and
Kim G. Larsen and
Mikael H. Mòller and
Salomon Sickert and
Jirí Srba Refinement checking on parametric modal
transition systems . . . . . . . . . . . 269--297
Manfred Broy A life dedicated to informatics: an
obituary for Prof. Friedrich L. Bauer 299--301
Rob J. van Glabbeek and
Ursula Goltz and
Ernst-Rüdiger Olderog Special issue on ``Combining
Compositionality and Concurrency'': part
2 . . . . . . . . . . . . . . . . . . . 303--304
Gerald Lüttgen and
Walter Vogler and
Sascha Fendrich Richer interface automata with
optimistic and pessimistic compatibility 305--336
Hubert Garavel and
Frédéric Lang and
Radu Mateescu Compositional verification of
asynchronous concurrent systems using
CADP . . . . . . . . . . . . . . . . . . 337--392
Joaquín Aguado and
Michael Mendler and
Reinhard von Hanxleden and
Insa Fuhrmann Denotational fixed-point semantics for
constructive scheduling of synchronous
concurrency . . . . . . . . . . . . . . 393--442
Joachim Klein and
Christel Baier and
Sascha Klüppelholz Compositional construction of most
general controllers . . . . . . . . . . 443--482
Chen-Ming Fan and
Jen-Tse Wang and
Cheng-Chih Huang Some properties of involution binary
relations . . . . . . . . . . . . . . . 483--495
Frank Drewes and
Berthold Hoffmann Contextual hyperedge replacement . . . . 497--524
Alejandro Sánchez and
César Sánchez Parametrized invariance for infinite
state processes . . . . . . . . . . . . 525--557
Joost Engelfriet Two-way pebble transducers for partial
functions and their composition . . . . 559--571
A. Bernini and
S. Bilotta and
R. Pinzani and
A. Sabri and
V. Vajnovszki Gray code orders for $q$-ary words
avoiding a given factor . . . . . . . . 573--592
Friedrich Otto and
Frantisek Mráz Deterministic ordered restarting
automata for picture languages . . . . . 593--623
Suoping Li and
Yongqiang Zhou and
Duo Peng and
Zufang Dou and
Yong Zhou Analysis of dual-hop and multiple relays
cooperative truncated ARQ with relay
selection in WSNs . . . . . . . . . . . 1--22
Chunhua Cao and
Haiyan Liu and
Di Yang Characterizations of $k$-comma codes and
$k$-comma intercodes . . . . . . . . . . 23--33
Ryszard Janicki and
Jetty Kleijn and
Maciej Koutny and
\Lukasz Mikulski Step traces . . . . . . . . . . . . . . 35--65
Yo-Sub Han and
Sang-Ki Ko and
Kai Salomaa State complexity of deletion and bipolar
deletion . . . . . . . . . . . . . . . . 67--85
Cesar Sanchez and
K. Brent Venable and
Esteban Zimanyi Special issue on temporal representation
and reasoning (TIME'13) . . . . . . . . 87--88
Luke Hunsberger Efficient execution of dynamically
controllable simple temporal networks
with uncertainty . . . . . . . . . . . . 89--147
Jean-François Condotta and
Souhila Kaci and
Yakoub Salhi Optimization in temporal qualitative
constraint networks . . . . . . . . . . 149--170
Marcello M. Bersani and
Matteo Rossi and
Pierluigi San Pietro A tool for deciding the satisfiability
of continuous-time metric temporal logic 171--206
Luca Aceto and
Dario Della Monica and
Valentin Goranko and
Anna Ingólfsdóttir and
Angelo Montanari and
Guido Sciavicco A complete classification of the
expressiveness of interval logics of
Allen's relations: the general and the
dense cases . . . . . . . . . . . . . . 207--246
Viktor Schuppan Extracting unsatisfiable cores for LTL
via temporal resolution . . . . . . . . 247--299
Mark Reynolds Metric temporal logic revisited . . . . 301--324
Bernd Finkbeiner and
Cesar Sanchez Special issue on Rich Models, EU-COST
Action IC0901 Rich-Model Toolkit . . . . 325--326
Hila Peleg and
Sharon Shoham and
Eran Yahav and
Hongseok Yang Symbolic automata for representing big
code . . . . . . . . . . . . . . . . . . 327--356
Parosh Aziz Abdulla and
Lukás Holík and
Bengt Jonsson and
Ondrej Lengál and
Cong Quy Trinh and
Tomás Vojnar Verification of heap manipulating
programs with ordered data by extended
forest automata . . . . . . . . . . . . 357--385
Jérôme Leroux and
Philipp Rümmer and
Pavle Suboti\'c Guiding Craig interpolation with
domain-specific abstractions . . . . . . 387--424
Christian von Essen and
Barbara Jobstmann and
David Parker and
Rahul Varshneya Synthesizing efficient systems in
probabilistic environments . . . . . . . 425--457
Xiaoning Peng and
Zhijun Xiao Optimal covers in the relational
database model . . . . . . . . . . . . . 459--468
Egon Börger and
Klaus-Dieter Schewe Concurrent abstract state machines . . . 469--492
Anthony W. Lin and
Sanming Zhou A linear-time algorithm for the orbit
problem over cyclic groups . . . . . . . 493--508
Holger Bock Axelsen and
Robert Glück On reversible Turing machines and their
function universality . . . . . . . . . 509--543
Davide Bresolin and
Guido Sciavicco Special issue: selected papers from the
21st International Symposium on Temporal
Representations and Reasoning
(TIME-2014) . . . . . . . . . . . . . . 545--546
Carlo Combi and
Pietro Sala Mining approximate interval-based
temporal dependencies . . . . . . . . . 547--585
Alberto Molinari and
Angelo Montanari and
Aniello Murano and
Giuseppe Perelli and
Adriano Peron Checking interval properties of
computations . . . . . . . . . . . . . . 587--619
Angelo Montanari and
Marco Pazzaglia and
Pietro Sala Metric propositional neighborhood logic
with an equivalence relation . . . . . . 621--648
Marta Cialdea Mayer and
Andrea Orlandini and
Alessandro Umbrico Planning and execution with flexible
timelines: a formal account . . . . . . 649--680
Alessandro Cimatti and
Luke Hunsberger and
Andrea Micheli and
Roberto Posenato and
Marco Roveri Dynamic controllability via Timed Game
Automata . . . . . . . . . . . . . . . . 681--722
Mikael Nilsson and
Jonas Kvarnström and
Patrick Doherty Efficient processing of simple temporal
networks with uncertainty: algorithms
for dynamic controllability verification 723--752
Luca Aceto and
David de Frutos Escrig Special issue: Selected papers from the
26th International Conference on
Concurrency Theory (CONCUR 2015) . . . . 1--2
Paul Hunter and
Guillermo A. Pérez and
Jean-François Raskin Reactive synthesis without regret . . . 3--39
Romain Brenguier and
Jean-François Raskin and
Ocan Sankur Assume-admissible synthesis . . . . . . 41--83
Thomas Brihaye and
Gilles Geeraerts and
Axel Haddad and
Benjamin Monmege Pseudopolynomial iterative algorithm to
solve total-payoff games and min-cost
reachability games . . . . . . . . . . . 85--125
Filippo Bonchi and
Daniela Petri\csan and
Damien Pous and
Jurriaan Rot A general account of coinduction up-to 127--190
Javier Esparza and
Pierre Ganty and
Jérôme Leroux and
Rupak Majumdar Verification of population protocols . . 191--215
Sadegh Esmaeil Zadeh Soudjani and
Alessandro Abate and
Rupak Majumdar Dynamic Bayesian networks for formal
verification of structured stochastic
processes . . . . . . . . . . . . . . . 217--242
Marco Carbone and
Fabrizio Montesi and
Carsten Schürmann and
Nobuko Yoshida Multiparty session types as coherence
proofs . . . . . . . . . . . . . . . . . 243--269
Dimitrios Kouzapas and
Jorge A. Pérez and
Nobuko Yoshida Characteristic bisimulation for
higher-order session processes . . . . . 271--341
Mohammad Mahdi Jaghoori and
Frank de Boer and
Delphine Longuet and
Tom Chothia and
Marjan Sirjani Compositional schedulability analysis of
real-time actor-based systems . . . . . 343--378
Lila Kari and
Manasi S. Kulkarni Disjunctivity and other properties of
sets of pseudo-bordered words . . . . . 379--398
Pierpaolo Degano and
Gian-Luigi Ferrari and
Gianluca Mezzetti Regular and context-free nominal traces 399--433
Bogdan Aman and
Gabriel Ciobanu Efficiently solving the Bin Packing
problem through bio-inspired mobility 435--445
A. Marin and
S. Rossi On the relations between Markov chain
lumpability and reversibility . . . . . 447--485
Kingshuk Chatterjee and
Kumar Sankar Ray Reversible Watson--Crick automata . . . 487--499
Achour Mostéfaoui and
Michel Raynal Signature-free asynchronous Byzantine
systems: from multivalued to binary
consensus with $ t < n / 3 $, $ O(n^2) $
messages, and constant time . . . . . . 501--520
Ke Gu and
Weijia Jia and
Guojun Wang and
Sheng Wen Efficient and secure attribute-based
signature for monotone predicates . . . 521--541
Krishnendu Chatterjee and
Rüdiger Ehlers Special issue: Synthesis and SYNT 2014 543--544
Aaron Bohy and
Véronique Bruy\`ere and
Jean-François Raskin and
Nathalie Bertrand Symblicit algorithms for mean-payoff and
shortest path in monotonic Markov
decision processes . . . . . . . . . . . 545--587
Milan Ceska and
Frits Dannenberg and
Nicola Paoletti and
Marta Kwiatkowska and
Lubos Brim Precise parameter synthesis for
stochastic biochemical systems . . . . . 589--623
Chung-Hao Huang and
Sven Schewe and
Farn Wang Model-checking iterated games . . . . . 625--654
Takashi Tomita and
Atsushi Ueno and
Masaya Shimakawa and
Shigeki Hagihara and
Naoki Yonezaki Safraless LTL synthesis considering
maximal realizability . . . . . . . . . 655--692
Susmit Jha and
Sanjit A. Seshia A theory of formal synthesis via
inductive learning . . . . . . . . . . . 693--726
Christel Baier and
Cesare Tinelli Special issue of the 21st International
Conference on Tools and Algorithms for
the Construction and Analysis of Systems
(TACAS 2015) . . . . . . . . . . . . . . 727--728
Dmitry Chistikov and
Rayna Dimitrova and
Rupak Majumdar Approximate counting in SMT and value
estimation for probabilistic programs 729--764
Mirco Giacobbe and
Calin C. Guet and
Ashutosh Gupta and
Thomas A. Henzinger and
Tiago Paixão and
Tatjana Petrov Model checking the evolution of gene
regulatory networks . . . . . . . . . . 765--787
Parosh Aziz Abdulla and
Stavros Aronis and
Mohamed Faouzi Atig and
Bengt Jonsson and
Carl Leonardsson and
Konstantinos Sagonas Stateless model checking for TSO and PSO 789--818
Édouard Bonnet and
Vangelis Th. Paschos Sparsification and subexponential
approximation . . . . . . . . . . . . . 1--15
Henrik Björklund and
Wim Martens and
Thomas Schwentick Conjunctive query containment over trees
using schema information . . . . . . . . 17--56
Lene M. Favrholdt and
Jesper W. Mikkelsen Online edge coloring of paths and trees
with a fixed number of colors . . . . . 57--80
Juha Honkala A new bound for the D0L language
equivalence problem . . . . . . . . . . 81--88
Javier Esparza and
Enrico Tronci Preface for the special issue GandALF
2015 . . . . . . . . . . . . . . . . . . 89--90
Patricia Bouyer and
Nicolas Markey and
Mickael Randour and
Kim G. Larsen and
Simon Laursen Average-energy games . . . . . . . . . . 91--127
Martin Zimmermann Parameterized linear temporal logics
meet costs: still not costlier than LTL 129--152
Rayna Dimitrova and
Rupak Majumdar Reachability analysis of
reversal-bounded automata on
series--parallel graphs . . . . . . . . 153--189
Hazem Torfah and
Martin Zimmermann The complexity of counting models of
linear-time temporal logic . . . . . . . 191--212
Hadassa Daltrophe and
Shlomi Dolev and
Zvi Lotker Big data interpolation using functional
representation . . . . . . . . . . . . . 213--225
Roberto Barbuti and
Roberta Gori and
Francesca Levi and
Paolo Milazzo Generalized contexts for reaction
systems: definition and study of dynamic
causalities . . . . . . . . . . . . . . 227--267
Ferruccio Damiani and
Luca Padovani and
Ina Schaefer and
Christoph Seidl A core calculus for dynamic
delta-oriented programming . . . . . . . 269--307
David Basin and
Felix Klaedtke and
Eugen Zalinescu Algorithms for monitoring real-time
properties . . . . . . . . . . . . . . . 309--338
Raymond Devillers Factorisation of transition systems . . 339--362
Elie Fares and
Jean-Paul Bodeveix and
Mamoun Filali Event algebra for transition systems
composition application to timed
automata . . . . . . . . . . . . . . . . 363--400
Sjoerd Cranen and
Jeroen J. A. Keiren and
Tim A. C. Willemse Parity game reductions . . . . . . . . . 401--444
Cao Chunhua and
Lu Qing and
Yang Di A first step in characterizing
three-element codes . . . . . . . . . . 445--457
Frank de Boer and
Nikolaj Bjorner Preface for the special issue ``FM15'' 459--460
Lijun Zhang and
Pengfei Yang and
Lei Song and
Holger Hermanns and
Christian Eisentraut and
David N. Jansen and
Jens Chr. Godskesen Probabilistic bisimulation for realistic
schedulers . . . . . . . . . . . . . . . 461--488
Sòren Debois and
Thomas T. Hildebrandt and
Tijs Slaats Replication, refinement & reachability:
complexity in dynamic condition-response
graphs . . . . . . . . . . . . . . . . . 489--520
Gianluca Amato and
Simone Di Nardo Di Maio and
Maria Chiara Meo and
Francesca Scozzari Descending chains and narrowing on
template abstract domains . . . . . . . 521--545
Angelo Borsotti and
Luca Breveglieri and
Stefano Crespi Reghizzi and
Angelo Morzenti Fast deterministic parsers for
transition networks . . . . . . . . . . 547--574
Eike Best and
Raymond Devillers and
Uli Schlachter Bounded choice-free Petri net synthesis:
algorithmic issues . . . . . . . . . . . 575--611
Hongbo Zhang An analysis of the $ M^X $ /M/1 queue
with multiple working vacations by
GI/M/1 type Markov process . . . . . . . 613--624
Bernd Finkbeiner and
Geguang Pu and
Lijun Zhang Preface for the special issue for ATVA
2015 . . . . . . . . . . . . . . . . . . 625--626
Paul Hunter and
Guillermo A. Pérez and
Jean-François Raskin Looking at mean payoff through foggy
windows . . . . . . . . . . . . . . . . 627--647
Chao Wang and
Yi Lv and
Peng Wu TSO-to-TSO linearizability is
undecidable . . . . . . . . . . . . . . 649--668
Dietmar Berwanger and
Anup Basil Mathew and
Marie van den Bogaard Hierarchical information and the
synthesis of distributed strategies . . 669--701
Rachel Faran and
Orna Kupferman Spanning the spectrum from safety to
liveness . . . . . . . . . . . . . . . . 703--732
Masoud Ebrahimi and
Gholamreza Sotudeh and
Ali Movaghar Symbolic checking of Fuzzy CTL on Fuzzy
Program Graph . . . . . . . . . . . . . 1--33
Henning Fernau and
Lakshmanan Kuppusamy and
Indhumathi Raman On path-controlled insertion-deletion
systems . . . . . . . . . . . . . . . . 35--59
Paolo Baldan and
Fabio Gadducci Petri nets are dioids: a new algebraic
foundation for non-deterministic net
theory . . . . . . . . . . . . . . . . . 61--92
Jörg Desel and
Javier Esparza and
Philipp Hoffmann Negotiation as concurrency primitive . . 93--159
Rosa Abbasi and
Fatemeh Ghassemi and
Ramtin Khosravi Verification of asynchronous systems
with an unspecified component . . . . . 161--203
Tomás Fiedor and
Lukás Holík and
Ondrej Lengál and
Tomás Vojnar Nested antichains for WS1S . . . . . . . 205--228
Wolfgang Reisig Associative composition of components
with double-sided interfaces . . . . . . 229--253
Benjamin Lucien Kaminski and
Joost-Pieter Katoen and
Christoph Matheja On the hardness of analyzing
probabilistic programs . . . . . . . . . 255--285
Sascha Fendrich and
Gerald Lüttgen A generalised theory of Interface
Automata, component compatibility and
error . . . . . . . . . . . . . . . . . 287--319
Soumyadip Bandyopadhyay and
Dipankar Sarkar and
Chittaranjan Mandal Equivalence checking of Petri net models
of programs using static and dynamic
cut-points . . . . . . . . . . . . . . . 321--383
David Monniaux On the decidability of the existence of
polyhedral invariants in transition
systems . . . . . . . . . . . . . . . . 385--389
Amr Elmasry and
Mostafa Kahla and
Fady Ahdy and
Mahmoud Hashem Red-black trees with constant update
time . . . . . . . . . . . . . . . . . . 391--404
Pietro Cenciarelli and
Daniele Gorla and
Ivano Salvo Depletable channels: dynamics,
behaviour, and efficiency in network
design . . . . . . . . . . . . . . . . . 405--431
Sathyanarayanan Srinivasan and
Ramesh Kandukoori A Paxos based algorithm to minimize the
overhead of process recovery in
consensus . . . . . . . . . . . . . . . 433--446
Zoltán Fülöp and
Heiko Vogler Weighted iterated linear control . . . . 447--469
Huiyan Chen and
Chenchen Zhang Identity-based signatures in standard
model . . . . . . . . . . . . . . . . . 471--486
Andreas Krebs and
Arne Meier and
Martin Mundhenk The model checking fingerprints of CTL
operators . . . . . . . . . . . . . . . 487--519
Adrian Atanasiu and
Ghajendran Poovanandran and
Wen Chean Teh Parikh matrices for powers of words . . 521--535
Petr Jancar and
David Purser Structural liveness of Petri nets is
ExpSpace-hard and decidable . . . . . . 537--552
Ilaria Castellani and
Mariangiola Dezani-Ciancaglini and
Paola Giannini Reversible sessions with flexible
choices . . . . . . . . . . . . . . . . 553--583
Jurriaan Rot Distributive laws for monotone
specifications . . . . . . . . . . . . . 585--617
Paul Bonsma and
Daniël Paulusma Using contracted solution graphs for
solving reconfiguration problems . . . . 619--648
Roderick Bloem and
Paulo Tabuada Preface for the SYNT . . . . . . . . . . 1--1
Michael Luttenberger and
Philipp J. Meyer and
Salomon Sickert Practical synthesis of reactive systems
from LTL specifications via parity games 3--36
Elizabeth Firman and
Shahar Maoz and
Jan Oliver Ringert Performance heuristics for GR(1)
synthesis and related algorithms . . . . 37--79
Swen Jacobs and
Mouhammad Sakr A symbolic algorithm for lazy synthesis
of eager strategies . . . . . . . . . . 81--106
Rayna Dimitrova and
Mahsa Ghasemi and
Ufuk Topcu Reactive synthesis with maximum
realizability of linear temporal logic
specifications . . . . . . . . . . . . . 107--135
Bernd Finkbeiner and
Christopher Hahn and
Philip Lukert and
Marvin Stenger Synthesis from hyperproperties . . . . . 137--163
Hila Peleg and
Shachar Itzhaky and
Sharon Shoham and
Eran Yahav Programming by predicates: a formal
model for interactive synthesis . . . . 165--193
Daniel Neider and
Alexander Weinert and
Martin Zimmermann Synthesizing optimally resilient
controllers . . . . . . . . . . . . . . 195--221
Alessandro Abate and
Iury Bessa and
Lucas Cordeiro and
Cristina David Automated formal synthesis of provably
safe digital controllers for continuous
plants . . . . . . . . . . . . . . . . . 223--244
Antoine Girard and
Gregor Gössler Safety synthesis for incrementally
stable switched systems using
discretization-free multi-resolution
abstractions . . . . . . . . . . . . . . 245--269
Nahal Mirzaie and
Fathiyeh Faghih and
Swen Jacobs and
Borzoo Bonakdarpour Parameterized synthesis of
self-stabilizing protocols in symmetric
networks . . . . . . . . . . . . . . . . 271--304
Peter Höfner and
Carroll Morgan and
Vaughan Pratt Preface . . . . . . . . . . . . . . . . 305--311
Ursula Goltz and
Jens-W. Schicke-Uffmann Synchronous and asynchronous
communication(s) between three parties 313--320
Vaughan Pratt My time with Rob . . . . . . . . . . . . 321--322
Ansgar Fehnker Out for coffee: with Rob . . . . . . . . 323--327
Maciej Gazda and
Wan Fokkink and
Vittorio Massaro Congruence from the operator's point of
view . . . . . . . . . . . . . . . . . . 329--351
Antti Valmari All congruences below
stability-preserving fair testing or
CFFD . . . . . . . . . . . . . . . . . . 353--383
Jan A. Bergstra and
Alban Ponse Arithmetical datatypes with true
fractions . . . . . . . . . . . . . . . 385--402
David Mestel and
A. W. Roscoe Translating between models of
concurrency . . . . . . . . . . . . . . 403--438
Benjamin Bisping and
Uwe Nestmann and
Kirstin Peters Coupled similarity: the first 32 years 439--463
Christel Baier and
Pedro R. D'Argenio and
Holger Hermanns On the probabilistic bisimulation
spectrum with silent moves . . . . . . . 465--512
Walter Vogler and
Gerald Lüttgen A linear-time branching-time perspective
on interface automata . . . . . . . . . 513--550
Mark Bouwman and
Bas Luttik and
Tim Willemse Off-the-shelf automated analysis of
liveness properties for just paths . . . 551--590
Manuel Gieseking and
Ernst-Rüdiger Olderog and
Nick Würdemann Solving high-level Petri games . . . . . 591--626
Xudong Qin and
Simon Bliudze and
Eric Madelaine and
Zechen Hou and
Yuxin Deng SMT-based generation of symbolic
automata . . . . . . . . . . . . . . . . 627--656
Chenyi Zhang Minimal consistent DFA from sample
strings . . . . . . . . . . . . . . . . 657--670
Marc Jasper and
Maximilian Schlüter and
Bernhard Steffen Characteristic invariants in
Hennessy--Milner logic . . . . . . . . . 671--687
Mathias Claus Jensen and
Kim Guldstrand Larsen A complete axiomatization of weighted
branching bisimulation . . . . . . . . . 689--725
Jörg Endrullis and
Jan Willem Klop and
Rena Bakhshi Transducer degrees: atoms, infima and
suprema . . . . . . . . . . . . . . . . 727--758
Kirstin Peters and
Simone Tini Preface to special issue: EXPRESS/SOS
2016 + 2017 . . . . . . . . . . . . . . 759--760
Eduard Baranov and
Simon Bliudze Expressiveness of component-based
frameworks: a study of the
expressiveness of BIP . . . . . . . . . 761--800
Hans Hüttel Using session types for reasoning about
boundedness in the $ \pi $-calculus . . 801--827
Eduard Baranov and
Simon Bliudze Correction to: Expressiveness of
component-based frameworks: a study of
the expressiveness of BIP . . . . . . . 829--829
Ivan Lanese and
Doriana Medi\'c and
Claudio Antares Mezzina Static versus dynamic reversibility in
CCS . . . . . . . . . . . . . . . . . . 1--34
Steven Engels and
Tony Tan and
Jan Van den Bussche Subsequence versus substring constraints
in sequence pattern languages . . . . . 35--56
Arnab Bhattacharyya and
Ashutosh Gupta and
Mukund Thattai A formal methods approach to predicting
new features of the eukaryotic vesicle
traffic system . . . . . . . . . . . . . 57--93
Joost Engelfriet and
Kazuhiro Inaba and
Sebastian Maneth Linear-bounded composition of
tree-walking tree transducers: linear
size increase and complexity . . . . . . 95--152
Benedek Nagy and
Shaghayegh Parchami On deterministic sensing $ 5 '
\rightarrow 3 ' $ Watson--Crick finite
automata: a full hierarchy in 2detLIN 153--175
Johanna Björklund and
Loek Cleophas Aggregation-based minimization of finite
state automata . . . . . . . . . . . . . 177--194
Angelo Borsotti and
Luca Breveglieri and
Angelo Morzenti A deterministic parsing algorithm for
ambiguous regular expressions . . . . . 195--229
Debayan Ganguly and
Kingshuk Chatterjee and
Kumar Sankar Ray Watson--Crick quantum finite automata 231--240
Henning Fernau and
Andreas Malcher and
Giovanni Pighizzini Preface to Martin Kutrib Festschrift . . 241--242
Ahmad Ostovar and
Suna Bensch and
Thomas Hellström Natural language guided object retrieval
in images . . . . . . . . . . . . . . . 243--261
Henning Bordihn and
György Vaszil Reversible parallel communicating finite
automata systems . . . . . . . . . . . . 263--279
Jürgen Dassow Operational complexity and right linear
grammars . . . . . . . . . . . . . . . . 281--299
Henning Bordihn and
Markus Holzer On the number of active states in finite
automata . . . . . . . . . . . . . . . . 301--318
Supreeti Kamilya and
Jarkko Kari Nilpotency and periodic points in
non-uniform cellular automata . . . . . 319--333
Sebastian Jakobi and
Katja Meckel and
Beatrice Palano The descriptional power of queue
automata of constant length . . . . . . 335--356
Stavros Konstantinidis and
António Machiavelo and
Rogério Reis On the size of partial derivatives and
the word membership problem . . . . . . 357--375
Kenichi Morita An instruction set for reversible Turing
machines . . . . . . . . . . . . . . . . 377--396
Friedrich Otto and
Matthias Wendlandt Reversibility for stateless ordered
RRWW-automata . . . . . . . . . . . . . 397--425
Hiroshi Umeo and
Naoki Kamikawa and
Gen Fujita A new class of the smallest FSSP partial
solutions for 1D rings of length $ n =
2^k - 1 $ . . . . . . . . . . . . . . . 427--450
Thomas Worsch A faster algorithm for the Birthday Song
Singers Synchronization Problem (FSSP)
in one-dimensional CA with multiple
speeds . . . . . . . . . . . . . . . . . 451--462
Viliam Geffert and
Christos A. Kapoutsis and
Mohammad Zakzok Complement for two-way alternating
automata . . . . . . . . . . . . . . . . 463--495
Mingshuai Chen and
Martin Fränzle and
Naijun Zhan Indecision and delays are the parents of
failure-taming them algorithmically by
synthesizing delay-resilient control . . 497--528
Roberto Gorrieri Team bisimilarity, and its associated
modal logic, for BPP nets . . . . . . . 529--569
Litan Kumar Das and
Kumar Sankar Ray Bitopological duality for algebras of
Fitting's logic and natural duality
extension . . . . . . . . . . . . . . . 571--584
Julian Gutierrez and
Aniello Murano and
Michael Wooldridge Equilibria for games with combined
qualitative and quantitative objectives 585--610
Rabia Mazhar and
Muddassar Azam Sindhu DKL: an efficient algorithm for learning
deterministic Kripke structures . . . . 611--651
Ming Xu and
Cheng-Chao Huang and
Yuan Feng Measuring the constrained reachability
in quantum Markov chains . . . . . . . . 653--674
Manuel Gieseking and
Ernst-Rüdiger Olderog and
Nick Würdemann Correction to: Solving high-level Petri
games . . . . . . . . . . . . . . . . . 675--676
Walter Vogler and
Gerald Lüttgen Correction to: A linear-time
branching-time perspective on interface
automata . . . . . . . . . . . . . . . . 677--677
Tamás Tóth and
István Majzik Configurable verification of timed
automata with discrete variables . . . . 1--35
Mauricio Cano and
Hugo A. López and
Camilo Rueda Session-based concurrency, declaratively 1--87
James Baxter and
Pedro Ribeiro and
Ana Cavalcanti Sound reasoning in tock-CSP . . . . . . 125--162
Martin Kutrib and
Andreas Malcher and
Christian Schneider Finite automata with undirected state
graphs . . . . . . . . . . . . . . . . . 163--181
Mert Ergurtuna and
Beyazit Yalcinkaya and
Ebru Aydin Gol An automated system repair framework
with signal temporal logic . . . . . . . 183--209
Andrea Marin and
Carla Piazza and
Sabina Rossi Proportional lumpability and
proportional bisimilarity . . . . . . . 211--244
Amr Elmasry and
Jyrki Katajainen Regular numeral systems for data
structures . . . . . . . . . . . . . . . 245--281
James Baxter and
Pedro Ribeiro and
Ana Cavalcanti Correction to: Sound reasoning in \em
tock-CSP . . . . . . . . . . . . . . . . 283--283
Henning Fernau and
Markus Holzer and
Petra Wolf Preface to Klaus-Jörn Lange Festschrift 285--287
Eric Allender and
Archit Chauhan and
Samir Datta Depth-first search in directed planar
graphs, revisited . . . . . . . . . . . 289--319
Michaël Cadilhac and
Charles Paperman The regular languages of wire linear
AC$^0$ . . . . . . . . . . . . . . . . . 321--336
Jürgen Dassow and
Ismaël Jecker Operational complexity and pumping
lemmas . . . . . . . . . . . . . . . . . 337--355
Volker Diekert and
Henning Fernau and
Petra Wolf Properties of graphs specified by a
regular language . . . . . . . . . . . . 357--385
Thomas Erlebach and
Jakob T. Spooner Exploration of $k$-edge-deficient
temporal graphs . . . . . . . . . . . . 387--407
Kaoru Fujioka and
Fumiya Okubo and
Takashi Yokomori $ \mathcal {L} $-reduction computation
revisited . . . . . . . . . . . . . . . 409--426
Hans-Joachim Böckenhauer and
Elisabet Burjons and
Peter Rossmanith Reoptimization of parameterized problems 427--450
Sanjay Jain and
Birzhan Moldagaliyev and
Tien Dat Tran Lamplighter groups and automata . . . . 451--478
Hanan Shabana and
M. V. Volkov Careful synchronization of partial
deterministic finite automata . . . . . 479--504
Petra Wolf On the decidability of finding a
positive ILP-instance in a regular set
of ILP-instances . . . . . . . . . . . . 505--519
Ayleen Schinko and
Walter Vogler and
Gerald Lüttgen Interface Automata for Shared Memory . . 521--556
Radim Kocman and
Zbynek Krivka and
Benedek Nagy A jumping $ 5 ' \rightarrow 3 ' $
Watson--Crick finite automata model . . 557--584
Jan Kretínský and
Tobias Meggendorfer and
Maximilian Weininger Index appearance record with preorders 585--618
Viliam Geffert and
Christos A. Kapoutsis and
Mohammad Zakzok Improved complement for two-way
alternating automata . . . . . . . . . . 619--669
Paul Hunter and
Guillermo A. Pérez and
Jean-François Raskin Correction to: Reactive synthesis
without regret . . . . . . . . . . . . . 671--671
Marcin Michalak Hierarchical heuristics for
Boolean-reasoning-based binary bicluster
induction . . . . . . . . . . . . . . . 673--685
Marek Chrobak and
Mordecai Golin and
J. Ian Munro and
Neal E. Young On Huang and Wong's algorithm for
generalized binary split trees . . . . . 687--708
Philip Bille and
Inge Li Gòrtz From regular expression matching to
parsing . . . . . . . . . . . . . . . . 709--724
Soumyadip Bandyopadhyay and
Dipankar Sarkar and
Chittaranjan Mandal and
Holger Giese Translation validation of coloured Petri
net models of programs on integers . . . 725--759
Haiyan Guo and
Bo Zhou Minimum status of trees with a given
degree sequence . . . . . . . . . . . . 1--10
Rob van Glabbeek Reactive bisimulation semantics for a
process algebra with timeouts . . . . . 11--57
Shlomi Dolev and
Yin Li Secret-shared RAM indefinite private and
secure RAM execution of perfectly
unrevealed programs . . . . . . . . . . 59--78
Dietrich Kuske and
Christian Schwarz Alternating complexity of counting
first-order logic for the subword order 79--100
Asaf Levin and
Tal Shusterman Weighted throughput in a single machine
preemptive scheduling with continuous
controllable processing times . . . . . 101--122
Giovanni Pighizzini and
Luca Prigioniero Pushdown automata and constant height:
decidability and bounds . . . . . . . . 123--144
Mahboubeh Samadi and
Fatemeh Ghassemi and
Ramtin Khosravi Decentralized runtime verification of
message sequences in message-based
systems . . . . . . . . . . . . . . . . 145--178
Ivano Lodato and
Snehal M. Shekatkar and
Tian An Wong On partial information retrieval: the
unconstrained 100 prisoner problem . . . 179--208
Besma Khaireddine and
Aleksandr Zakharchenko and
Matias Martinez and
Ali Mili Toward a theory of program repair . . . 209--255
Jingnan Xie and
Harry B. Hunt III On the undecidability and descriptional
complexity of synchronized regular
expressions . . . . . . . . . . . . . . 257--278
Niklas Kochdumper and
Matthias Althoff Constrained polynomial zonotopes . . . . 279--316
Pál Dömösi and
Géza Horváth and
Norbert Tihanyi Simple chain automaton random number
generator for IoT devices . . . . . . . 317--329
Henning Fernau Editorial 2023: changes and invariants 331--333
Farnaz Sheikhi and
Behnam Zeraatkar and
Sama Hanaie Dot to dot, simple or sophisticated: a
survey on shape reconstruction
algorithms . . . . . . . . . . . . . . . 335--359
Richard Lassaigne and
Michel de Rougemont Testing membership for timed automata 361--384
Luca Aceto and
Ian Cassar and
Adrian Francalanza and
Anna Ingólfsdóttir On first-order runtime enforcement of
branching-time properties . . . . . . . 385--451
Chunhua Cao and
Jiao Xu and
Lei Liao and
Di Yang and
Guichuan Jia and
Qian Du The second step in characterizing a
three-word code . . . . . . . . . . . . 453--465
Tonatiuh Tapia-Flores and
Ernesto López-Mellado Discovering workflow nets of concurrent
iterative processes . . . . . . . . . . 1--21
Hao Wu and
Yu-Fang Chen and
Zhilin Wu and
Bican Xia and
Naijun Zhan A decision procedure for string
constraints with string/integer
conversion and flat regular constraints 23--52
Shuyang Gao and
Leen Hatem and
Hosam Mahmoud Balancing $m$-ary search trees with
compressions on the fringe . . . . . . . 53--66
Haiyan Liu and
Rongdong Cui and
Tianjie Zhang $n$-PS-codes, 2-infix-outfix codes and
some related classes of codes . . . . . 67--81
Shlomi Dolev and
Sayaka Kamei and
Yoshiaki Katayama and
Fukuhito Ooshita and
Koichi Wada Neighborhood mutual remainder:
self-stabilizing distributed
implementation and applications . . . . 83--100
Giannis Alonistiotis and
Antonis Antonopoulos and
Nikolaos Melissinos and
Aris Pagourtzis and
Stavros Petsalakis and
Manolis Vasilakis Approximating subset sum ratio via
partition computations . . . . . . . . . 101--113
Cahit Dede New families of Laplacian
borderenergetic graphs . . . . . . . . . 115--129
Hao Li and
Daowen Qiu and
Le Luo and
Paulo Mateus Exact distributed quantum algorithm for
generalized Simon's problem . . . . . . 131--159
Attila Bagossy and
Péter Battyányi An encoding of the $ \lambda $-calculus
in the String MultiSet Rewriting
calculus . . . . . . . . . . . . . . . . 161--181
Gang Yang and
Jiannan Zhou and
Changxiang He and
Yaping Mao Distance-edge-monitoring sets of
networks . . . . . . . . . . . . . . . . 183--198
Kamaledin Ghiasi-Shirazi and
Taraneh Ghandi and
Ali Taghizadeh and
Ali Rahimi-Baigi Revisiting 2-3 red--black trees with a
pedagogically sound yet efficient
deletion algorithm: parity-seeking . . . 199--229
Shiping Chen and
Xinyu Ge Reachability analysis of linear systems 231--260
Wided Ghardallou and
Hessamaldin Mohammadi and
Richard C. Linger and
Mark Pleszkoch and
JiMeng Loh and
Ali Mili Invariant relations for affine loops . . 261--314
Wenfeng Lai and
Adiesha Liyanage and
Binhai Zhu and
Peng Zou The longest letter-duplicated
subsequence and related problems . . . . 315--329
Henning Fernau Editorial 2024: moving forwards in the
electronic age . . . . . . . . . . . . . 331--332
Burkay Sucu and
Ebru Aydin Gol Cycle encoding-based parameter synthesis
for timed automata safety . . . . . . . 333--356
R. Mahendra Kumar and
N. Sadagopan A closer look at Hamiltonicity and
domination through the lens of diameter
and convexity . . . . . . . . . . . . . 357--382
Pamela Fleischmann and
Lukas Haschke and
Tim Löck and
Dirk Nowotka Word-representable graphs from a word's
perspective . . . . . . . . . . . . . . 383--400
Koustav De and
Harshil Mittal and
Palash Dey and
Neeldhara Misra Parameterized aspects of distinct Kemeny
rank aggregation . . . . . . . . . . . . 401--414
Davaajav Jargalsaikhan and
Diptarama Hendrian and
Yohei Ueki and
Ryo Yoshinaka and
Ayumi Shinohara Serial and parallel algorithms for
order-preserving pattern matching based
on the duel-and-sweep paradigm . . . . . 415--444
Shunsuke Inenaga Linear-size suffix tries and linear-size
CDAWGs simplified and improved . . . . . 445--468
Lucas P. Ramos and
Felipe A. Louza and
Guilherme P. Telles Comparative genomics with succinct
colored de Bruijn graphs . . . . . . . . ??