Last update:
Fri Jun 10 17:57:38 MDT 2016
Kathleen Fisher and
Furio Honsell and
John C. Mitchell A lambda calculus of objects and method
specialization . . . . . . . . . . . . . 3--37
Torben Hagerup and
Martin Maas Generalized topological sorting in
linear time . . . . . . . . . . . . . . 38--49
T. F. Melham A mechanized theory of the
$\pi$-calculus in HOL . . . . . . . . . 50--76
Hanspeter Mössenböck Extensibility in the Oberon system . . . 77--93
Pekka Orponen Computational complexity of neural
networks: a survey . . . . . . . . . . . 94--110
Hans L. Bodlaender and
Gerard Tel and
Nicola Santoro Trade-offs in non-reversing diameter . . 111--134
Olav Lysne Heuristics for completion in automatic
proofs by structural induction . . . . . 135--156
Jan Arne Telle Complexity of domination-type problems
in graphs . . . . . . . . . . . . . . . 157--171
Jean R. S. Blair and
Barry W. Peyton On finding minimum-diameter clique trees 173--201
K. Coolsaet and
V. Fack and
H. De Meyer A tabular method for verification of
data exchange algorithms on networks of
parallel processors . . . . . . . . . . 202--213
S. Jajodia and
R. Mukkamala and
K. V. S. Ramarao A view-based dynamic replication control
algorithm . . . . . . . . . . . . . . . 214--230
Ravi Janardan and
Franco P. Preparata Widest-corridor problems . . . . . . . . 231--245
Ulrich Pferschy and
Rüdiger Rudolf and
Gerhard J. Woeginger Some geometric clustering problems . . . 246--263
Klaus Jansen Integral flow with disjoint bundles . . 264--267
John W. Krussel and
Barry F. Schaudt A note on higher order Vorono\uìdiagrams 268--272
Andrzej Lingas Editor's foreword . . . . . . . . . . . 273
Madhav V. Marathe and
Harry B. Hunt, III and
S. S. Ravi The complexity of approximation
PSPACE-complete problems for
hierarchical specifications . . . . . . 275--316
Viggo Kann Polynomially bounded minimization
problems that are hard to approximate 317--331
Bogdan S. Chlebus and
Krzysztof Diks and
Andrzej Pelc Sparse networks supporting efficient
reliable broadcasting . . . . . . . . . 332--345
Klaus Havelund and
Kim Guldstrand Larsen The fork calculus . . . . . . . . . . . 346--363
Hardi Hungar and
Bernhard Steffen Local model checking for context-free
processes . . . . . . . . . . . . . . . 364--385
Sven Skyum Guest Editor's foreword . . . . . . . . 387
Peter Becker A new algorithm for the construction of
optimal $B$-trees . . . . . . . . . . . 389--401
Eric Schenk Parallel dynamic lowest common ancestors 402--432
Gautam Das and
Paul J. Heffernan and
Giri Narasimhan Finding all weakly visible chords of a
polygon in linear time . . . . . . . . . 433--457
Sven Schuierer An $O(\log \log n)$ time algorithm to
compute the kernel of a polygon . . . . 458--474
Magnús M. Halldórsson and
Jaikumar Radhakrishnan Improved approximations of independent
sets in bounded-degree graphs via
subgraph removal . . . . . . . . . . . . 475--492
Marcus Peinado Hard graphs for the randomized
Boppana-Halldórsson algorithm for
MAXCLIQUE . . . . . . . . . . . . . . . 493--515
Esko Ukkonen Editor's foreword . . . . . . . . . . . 1
Mordecai Golin and
Rajeev Raman and
Christian Schwarz and
Michiel Smid Simple randomized algorithms for closest
pair problems . . . . . . . . . . . . . 3--27
V. Kamakoti and
Kamala Krithivasan and
C. Pandu Rangan An efficient randomized algorithm for
the closest pair problem on colored
point sets . . . . . . . . . . . . . . . 28--40
Jan Kratochvíl and
Paul D. Manuel and
Mirka Miller Generalized domination in chordal graphs 41--50
Ville Leppänen and
Martti Penttonen Work-optimal simulation of PRAM models
on meshes . . . . . . . . . . . . . . . 51--69
Michael Vassilakopoulos and
Yannis Manolopoulos and
Brigitte Kröll Efficiency analysis of overlapped
quadtrees . . . . . . . . . . . . . . . 70--84
B. Jonsson and
Joachim Parrow Guest Editors' foreword . . . . . . . . 87
Olaf Burkart and
Bernhard Steffen Composition, decomposition and model
checking of pushdown processes . . . . . 89--125
Pietro Di Gianantonio and
Furio Honsell and
Gordon Plotkin Uncountable limits and the lambda
calculus . . . . . . . . . . . . . . . . 126--145
Paris C. Kanellakis and
Dimitrios Michailidis and
Alex Allister Shvartsman Controlling memory access concurrency in
efficient fault-tolerant parallel
algorithms . . . . . . . . . . . . . . . 146--180
Nax P. Mendler and
Prakash Panangaden and
P. J. Scott and
R. A. G. Seely A logical view of concurrent constraint
programming . . . . . . . . . . . . . . 181--220
Mogens Nielsen and
Christian Clausen Games and logics for a noninterleaving
bisimulation . . . . . . . . . . . . . . 221--249
Roberto Segala and
Nancy Lynch Probabilistic simulations for
probabilistic processes . . . . . . . . 250--273
Chris Verhoef A congruence theorem for structured
operational semantics with predicates
and negative premises . . . . . . . . . 274--302
Campbell B. Fraser and
Robert W. Irving Approximation Algorithms for the
Shortest Common Supersequence . . . . . 303--325
Kuo Liang Chung and
Yu Wei Chen Mapping Pyramids into $3$-D Meshes . . . 326--337
Jens Chr. Godskesen and
Kim G. Larsen Synthesizing Distinguishing Formulae for
Real Time Systems . . . . . . . . . . . 338--357
Micha\l Walicki and
Manfred Broy Structured Specifications and
Implementation of Nondeterministic Data
Types . . . . . . . . . . . . . . . . . 358--395
Kuo-Liang -L. Chung Fast Median-Finding on Mesh-Connected
Computers with Segmented Buses . . . . . 397--406
Joachim Parrow Interaction Diagrams . . . . . . . . . . 407--443
Claus Rick A New Flexible Algorithm for the Longest
Common Subsequence Problem . . . . . . . 444--461
Hans L. Bodlaender and
Teofilo F. Gonzalez and
Ton Kloks Complexity Aspects of Two-Dimensional
Data Compression . . . . . . . . . . . . 462--495
Jens Clausen and
Jakob Krarup A Family of Bipartite Cardinality
Matching Problems Solvable in $O(n^2)$
Time . . . . . . . . . . . . . . . . . . 496--501
Yung H. Tsin and
Cao-An Wang Geodesic Voronoi Diagrams in the
Presence of Rectilinear Barriers . . . . 1--26
Jyrki Katajainen and
Tomi Pasanen and
Jukka Teuhola Practical In-Place Mergesort . . . . . . 27--40
Helmut Seidl Least and greatest solutions of
equations over $\scr N$ . . . . . . . . 41--62
Selim G. Akl and
Ivan Stojmenovic Generating $t$-ary Trees in Parallel . . 63--71
Amitava Datta and
Anil Maheshwari and
Jörg-Rüdiger -R. Sack Optimal Parallel Algorithms for Direct
Dominance Problems . . . . . . . . . . . 72--88
C.-Z. Lin and
C.-C. Tseng and
Y.-L. Chen and
T.-W. Kuo A Systematic Approach to Synthesize Data
Alignment Directives for Distributed
Memory Machines . . . . . . . . . . . . 89--119
Lauri Malmi A New Method for Updating and
Rebalancing Tree-Type Main Memory
Dictionaries . . . . . . . . . . . . . . 111--130
Henrik Linnestad Fatal Steps of Knuth--Bendix Completion 131--143
Flemming Nielson and
Hanne Riis Nielson Operational Semantics of Termination
Types . . . . . . . . . . . . . . . . . 144--187
Krzysztof Diks and
Andrzej Pelc Fault-Tolerant Linear Broadcasting . . . 188--201
Cynthia A. Brown and
Larry Finkelstein and
Paul Walton Purdom, Jr. Backtrack Searching in the Presence of
Symmetry . . . . . . . . . . . . . . . . 203--219
Peter Eades and
Mark Keil and
Paul D. Manuel and
Mirka Miller Two Minimum Dominating Sets with Minimum
Intersection in Chordal Graphs . . . . . 220--237
Gerth Stòlting Brodal Partially Persistent Data Structures of
Bounded Degree with Constant Update Time 238--255
Sridhar Natarajan and
Alan P. Sprague Disjoint Paths in Circular Arc Graphs 256--270
J.-C. Chen Proportion Split Sort . . . . . . . . . 271--279
C.-H. Ang and
H. Samet Approximate Average Storage Utilization
of Bucket Methods with Arbitrary Fanout 280--291
R. Karlsson and
Andrzej Lingas Guest Editors' Foreword . . . . . . . . 293--294
T. W. Lam and
W. K. Sung and
H. F. Ting Computing unrooted maximum subtrees in
sub-quartic time . . . . . . . . . . . . 295--322
Thore Husfeldt and
Theis Rauhe and
Sòren Skyum Lower Bounds for Dynamic Transitive
Closure, Planar Point Location, and
Parentheses Matching . . . . . . . . . . 323--336
Gerth Stòlting Brodal and
Shiva Chaudhuri and
Jaikumar Radhakrishnan The Randomized Complexity of Maintaining
the Minimum . . . . . . . . . . . . . . 337--351
David Fernández-Baca and
Giora Slutzki and
David Eppstein Using Sparsification for Parametric
Minimum Spanning Tree Problems . . . . . 352--366
M. V. Marathe and
R. Ravi and
R. Sundaram Service-Constrained Network Design
Problems . . . . . . . . . . . . . . . . 367--387
Takao Asano and
Takao Ono and
Tomio Hirata Approximation Algorithms for the Maximum
Satisfiability Problem . . . . . . . . . 388--404
Hoong Chuin Lau and
Osamu Watanabe Randomized Approximations of the
Constraint Satisfaction Problem . . . . 405--424
Noga Alon and
Pierre Kelsen and
Sanjeev Mahajan and
Hariharan Ramesh Coloring $2$-colorable hypergraphs with
a sublinear number of colors . . . . . . 425--439
K. Koskimies Editor's Foreword . . . . . . . . . . . 1--2
J. Paakki and
J. Koskinen and
A. Salminen From Relational Program Dependencies to
Hypertextual Access Structures . . . . . 3--36
Sofoklis G. Efremidis and
Khalid A. Mughal and
John H. Reppy and
Lars Sòraas AML: Attribute Grammars in ML . . . . . 37--65
Jan Bosch Delegating Compiler Objects: Modularity
and Reusability in Language Engineering 66--92
Goerel Hedin Attribute Extensions -- a Technique for
Enforcing Programming Conventions . . . 93--122
Dag I. K. Sjòberg and
Ray Welland and
Malcolm P. Atkinson and
Paul Philbrow and
Cathy Waite and
Stewart Macneill The Persistent Workshop --- a
Programming Environment for Napier88 . . 123--149
Giorgio Gambosi and
Alberto Postiglione and
Maurizio Talamo On-Line Maintenance of an Approximate
Bin-Packing Solution . . . . . . . . . . 151--166
Thomas Roos New Upper Bounds on Voronoi Diagrams of
Moving Points . . . . . . . . . . . . . 167--171
Marek Karpinski and
Wojciech Rytter and
Ayumi Shinohara An Efficient Pattern-Matching Algorithm
for Strings with Short Descriptions . . 172--186
Emmanuel Roche Compact Factorization of Finite-State
Transducers and Finite-State Automata 187--216
Mehryar Mohri String-Matching with Automata . . . . . 217--231
Lars Lundberg and
Håkan Lennerstad Bounding the Gain of Changing the Number
of Memory Modules in Shared Memory
Multiprocessors . . . . . . . . . . . . 233--258
Jens Palsberg and
Trevor Jim Type Inference with Simple Selftypes is
NP-complete . . . . . . . . . . . . . . 259--286
Tibor Gyimóthy and
Tamás Horváth Learning Semantic Functions of Attribute
Grammars . . . . . . . . . . . . . . . . 287--302
Atsuko Yamaguchi and
Koji Nakano and
Satoru Miyano An Approximation Algorithm for the
Minimum Common Supertree Problem . . . . 303--316
Amos Israeli and
Evangelos Kranakis and
Danny Krizanc and
Nicola Santoro Time-Message Trade-Offs for the Weak
Unison Problem . . . . . . . . . . . . . 317--329
Asish Mukhopadhyay and
Alok Agrawal and
Ravi Mohan Hosabettu On the Ordinary Line Problem in
Computational Geometry . . . . . . . . . 330--341
Madhumangal Pal and
G. P. Bhattacharjee An Optimal Parallel Algorithm for
All-Pairs Shortest Paths on Unweighted
Interval Graphs . . . . . . . . . . . . 342--356
Owen Kaser Optimal Height Reduction Problems for
Tree-Structured Hierarchies . . . . . . 357--379
Hakan Erdogmus Architecture-Driven Verification of
Concurrent Systems . . . . . . . . . . . 380--413
Drago Krznaric and
Christos Levcopoulos Computing a Threaded Quadtree from the
Delaunay Triangulation in linear time 1--18
Ole-Johan Dahl and
Olaf Owe and
Tore J. Bastiansen Subtyping and Constructive Specification 19--49
Bjòrn Kristoffersen and
Ole-Johan Dahl On Introducing Higher Order Functions in
ABEL . . . . . . . . . . . . . . . . . . 50--69
Ricardo A. Baeza-Yates and
Héctor Soza-Pollman Analysis of Linear Hashing Revisited . . 70--85
Stefan Dobrev and
Peter Ru\vzi\vcka On the Communication Complexity of
Strong Time-Optimal Distributed
Algorithms . . . . . . . . . . . . . . . 87--104
Peter Hòyer and
Kim S. Larsen Parametric Permutation Routing via
Matchings . . . . . . . . . . . . . . . 105--114
Joseph L. Ganley and
Jeffrey S. Salowe The Power-$p$ Steiner Tree Problem . . . 115--127
Pinar Heggernes and
Jan Arne Telle Partitioning Graphs into Generalized
Dominating Sets . . . . . . . . . . . . 128--142
Mika Johnsson and
Gábor Magyar and
Olli Nevalainen On the Euclidean $3$-Matching Problem 143--171
Jan Kratochvíl and
Andrzej Proskurowski and
Jan Arne Telle On the Complexity of Graph Covering
Problems . . . . . . . . . . . . . . . . 173
Teofilo F. Gonzalez Bounded Fan-Out Multimessage
Multicasting . . . . . . . . . . . . . . 196
Christian Mossin Higher-Order Value Flow Graphs . . . . . 214
Jukka Paakki and
Antti-Pekka Tuovinen Source-to-Source Translation of Visual
Languages . . . . . . . . . . . . . . . 235
Chris Hankin Guest Editor's Foreword . . . . . . . . 265
Martín Abadi and
Andrew D. Gordon A Bisimulation Method for Cryptographic
Protocols . . . . . . . . . . . . . . . 267
Christian Fecht and
Helmut Seidl Propagating Differences: an Efficient
New Fixpoint Algorithm for Distributive
Constraint Systems . . . . . . . . . . . 304
K. Rustan M. Leino Recursive Object Types in a Logic of
Object-Oriented Programs . . . . . . . . 330
John L. Ross and
Mooly Sagiv Building a Bridge between Pointer
Aliases and Program Dependences . . . . 361
Khalid A. Mughal and
Andreas L. Opdahl Guest Editors' Foreword: Programming and
Software Development Environment
Research in the Nordic Countries . . . . 1
Henrik Bærbak Christensen The Ragnarok Software Development
Environment . . . . . . . . . . . . . . 4
Kåre Kjelstròm and
Peter Petersen A CASE Tool for COM Development . . . . 22
Elizabeth Bjarnason and
Görel Hedin and
Klas Nilsson Interactive Language Development for
Embedded Systems . . . . . . . . . . . . 36
Henrik Ròn An Overview of a Dynamic Programming
Environment Based on Extensibility . . . 55
Erik Ernst Dynamic Inheritance in a Statically
Typed Language . . . . . . . . . . . . . 72
Maarit Harsu Translation of Conditional Compilation 93
Kurt Nòrmark and
Lars Iversen and
Per Madsen Animation and Presentation Tools for
Object-Oriented Design . . . . . . . . . 110
Lars Bendix and
Ulf Asklund Summary of the Subworkshop on Change
Management . . . . . . . . . . . . . . . 129
Jens Lagergren and
Peter Bro Miltersen Guest Editors' Foreword . . . . . . . . 135
Nora H. Sleumer Output-Sensitive Cell Enumeration in
Hyperplane Arrangements . . . . . . . . 137
Steven S. Seiden Randomized Online Multi-Threaded Paging 148
Venkatesh Raman and
Sarnath Ramnath Improved Upper Bounds for Time-Space
Trade-offs for Selection . . . . . . . . 162
Piotr Berman and
Chris Coulston Speed is More Powerful than Clairvoyance 181
Sandeep Sen and
Neelima Gupta Distribution-Sensitive Algorithms . . . 194
Kaisa Sere Guest Editor's Foreword . . . . . . . . 213
Paolo Ciancarini and
Andrea Omicini and
Franco Zambonelli Coordination Technologies for Internet
Agents . . . . . . . . . . . . . . . . . 215
Magne Haveraaen and
Helmer André Friis and
Tor Arne Johansen Formal Software Engineering for
Computational Modelling . . . . . . . . 241
Kim G. Larsen and
Justin Pearson and
Carsten Weise and
Wang Yi Clock Difference Diagrams . . . . . . . 271
Carl Johan Lillieroth and
Satnam Singh Formal Verification of FPGA Cores . . . 299
Elena A. Troubitsyna Reliability Assessment through
Probabilistic Refinement . . . . . . . . 320
Tarmo Uustalu and
Varmo Vene Mendler-Style Inductive Types,
Categorically . . . . . . . . . . . . . 343
Min-Shiang Hwang A Dynamic Key Generation Scheme for
Access Control in a Hierarchy . . . . . 363
Sofi\`ene Tahar and
Paul Curzon Comparing HOL and MDG: a Case Study on
the Verification of an ATM Switch Fabric 372
Jesper Larsen and
Ib Pedersen Experiments with the Auction Algorithm
for the Shortest Path Problem . . . . . 403
Maria Andreou and
Stavros D. Nikolopoulos NC Coloring Algorithms for Permutation
Graphs . . . . . . . . . . . . . . . . . 422
Drago Krznaric and
Christos Levcopoulos and
Bengt J. Nilsson Minimum Spanning Trees in $d$ Dimensions 446
Olivier Devillers and
Asish Mukhopadhyay Finding an Ordinary Conic and an
Ordinary Hyperplane . . . . . . . . . . 462
Joachim Gudmundsson and
Christos Levcopoulos A Fast Approximation Algorithm for TSP
with Neighborhoods . . . . . . . . . . . 469
Juhani Karhumäki and
Wojciech Plandowski and
Wojciech Rytter Pattern-Matching Problems for
Two-Dimensional Images Described by
Finite Automata . . . . . . . . . . . . 1
Hans L. Bodlaender and
Klaus Jansen On the Complexity of the Maximum Cut
Problem . . . . . . . . . . . . . . . . 14
Joachim Gudmundsson and
Christos Levcopoulos A Parallel Approximation Algorithm for
Minimum Weight Triangulation . . . . . . 32
Michele Zito Linear Time Maximum Induced Matching
Algorithm for Trees . . . . . . . . . . 58
Andreas L. Opdahl and
Dag I. K. Sjòberg Guest Editors' Foreword: Programming and
Software Development Environment
Research in the Nordic Countries . . . . 65
Eva Magnusson and
Görel Hedin Program Visualization Using Reference
Attributed Grammars . . . . . . . . . . 67
Kurt Nòrmark Elucidative Programming . . . . . . . . 87
Thomas Vestdam Documentation Threads --- Presentation
of Fragmented Documentation . . . . . . 106
Maarit Harsu Identifying Object-Oriented Features
from Procedural Software . . . . . . . . 126
Lars Bendix and
Ulf Asklund and
Jonas Persson Summary of the Subworkshop on Change
Management for Open Source Software . . 143
Mágnus M. Halldórsson Guest Editor's Foreword . . . . . . . . 149
Rasmus Pagh A Trade-Off for Worst-Case Efficient
Dictionaries . . . . . . . . . . . . . . 151
Anne Berry and
Jean-Paul Bordat and
Pinar Heggernes Recognizing Weakly Triangulated Graphs
by Edge Separability . . . . . . . . . . 164
Piotr Berman A $d/2$ Approximation for Maximum Weight
Independent Set in $d$-Claw Free Graphs 178
Srinivas Doddi and
Madhav V. Marathe and
S. S. Ravi and
David S. Taylor and
Peter Widmayer Approximation Algorithms for Clustering
to Minimize the Sum of Diameters . . . . 185
Vincenzo Liberatore Scheduling Jobs before Shut-Down . . . . 204
Pankaj K. Agarwal and
Leonidas J. Guibas and
Sariel Har-Peled and
Alexander Rabinovitch and
Micha Sharir Penetration Depth of Two Convex
Polytopes in $3$D . . . . . . . . . . . 227
Tetsuo Asano and
Tomomi Matsui and
Takeshi Tokuyama Optimal Roundings of Sequences and
Matrices . . . . . . . . . . . . . . . . 241
Gert Smolka Guest Editor's Foreword . . . . . . . . 257
Martin Hofmann A Type System for Bounded Space and
Functional In-Place Update . . . . . . . 258
Laurent Mauborgne An Incremental Unique Representation for
Regular Trees . . . . . . . . . . . . . 290
François Pottier A Versatile Constraint-Based Type
Inference System . . . . . . . . . . . . 312
Claudio V. Russo First-Class Structures for Standard ML 348
Helmut Seidl and
Bernhard Steffen Constraint-Based Inter-Procedural
Analysis of Parallel Programs . . . . . 375
Kaisa Sere and
Wang Li Guest Editors' Foreword . . . . . . . . 1
Ralph-Johan Back and
Luigia Petre and
Ivan Porres Continuous Action Systems as a Model for
Hybrid Systems . . . . . . . . . . . . . 2
Ana Bove Simple General Recursion in Type Theory 22
Thomas Hune and
Kim G. Larsen and
Paul Pettersson Guided Synthesis of Control Programs
Using UPPAAL . . . . . . . . . . . . . . 43
Bengt Jonsson and
Tiziana Margaria and
Gustaf Naeser and
Jan Nyström and
Bernhard Steffen Incremental Requirement Specification
for Evolving Systems . . . . . . . . . . 65
R. F. Lutje Spelberg and
W. J. Toetenel Parametric Real-Time Model Checking
Using Splitting Trees . . . . . . . . . 88
Simon Mòrk Distributed Implementation of a
Process-Algebra Based Programming
Language for Embedded Systems . . . . . 121
Mauno Rönkkö and
Xuandong Li Linear Hybrid Action Systems . . . . . . 159
Thomas Ottmann and
Sven Schuierer and
Subbiah Soundaralakshmi Enumerating Extreme Points in Higher
Dimensions . . . . . . . . . . . . . . . 179
Kaisa Sere and
Marina Waldén Structuring and Verifying Distributed
Algorithms . . . . . . . . . . . . . . . 193
Joachim Gudmundsson and
Christos Levcopoulos and
Giri Narasimhan Approximating a Minimum Manhattan
Network . . . . . . . . . . . . . . . . 216
Magne Haveraaen and
Olaf Owe Guest Editors' Foreword . . . . . . . . 277
Walter Dosch and
Sönke Magnussen Computer Aided Fusion for Algebraic
Program Derivation . . . . . . . . . . . 279
Yngve Lamo and
Michal Walicki Specification of Parameterized Programs
--- Persistency Revisited . . . . . . . 298
Viktor Petersson and
Sergei Vorobyov A Randomized Subexponential Algorithm
for Parity Games . . . . . . . . . . . . 324
Harald Fecher A Real-Time Process Algebra with Open
Intervals and Maximal Progress . . . . . 346
Tarmo Uustalu and
Varmo Vene and
Alberto Pardo Recursion Schemes from Comonads . . . . 366
Jose Emilio Labra Gayo and
Juan Manuel Cueva Lovelle and
Maria Cándida Luengo Díez and
Agustín Cernuda del Río Modular Development of Interpreters from
Semantic Building Blocks . . . . . . . . 391--407
Béla Bollobás and
Gautam Das and
Dimitrios Gunopulos and
Heikki Mannila Time-Series Similarity Problems and
Well-Separated Geometric Sets . . . . . 409--423
Patric R. J. Östergård A New Algorithm for the Maximum-Weight
Clique Problem . . . . . . . . . . . . . 424--436
Bernd Grobauer and
Julia L. Lawall Partial Evaluation of Pattern Matching
in Strings, revisited . . . . . . . . . 437--462
Joan Boyar and
Lene M. Favrholdt and
Kim S. Larsen and
Morten N. Nielsen The Competitive Ratio for On-Line Dual
Bin Packing with Restricted Input
Sequences . . . . . . . . . . . . . . . 463--472
Jochen Burghardt Maintaining Partial Sums in Logarithmic
Time . . . . . . . . . . . . . . . . . . 473--474
M. Goldberg and
M. Torgersen How to Circumvent Church Numerals . . . 1
G. Narasimhan and
M. Smid Approximation Algorithms for the
Bottleneck Stretch Factor Problem . . . 13
M. Hammar and
B. J. Nilsson and
S. Schuierer Improved Exploration of Rectilinear
Polygons . . . . . . . . . . . . . . . . 32
M. Crochemore and
C. Iliopoulos and
C. Makris and
W. Rytter and
A. Tsakalidis and
K. Tsichlas Approximate String Matching with Gaps 54
K. N. Klipsch and
D. S. Wise Note: Blood from Dahm's Turnip . . . . . 66
L. Aceto and
P. Panangaden Guest Editors' Foreword . . . . . . . . 69
R. M. Amadio and
C. Meyssonnier On Decidability of the Control
Reachability Problem in the Asynchronous
pi-Calculus . . . . . . . . . . . . . . 70
J. C. Bradfield and
S. B. Fröschle Independence-Friendly Modal Logic and
True Concurrency . . . . . . . . . . . . 102
A. Labroue and
Ph. Schnoebelen An Automata-Theoretic Approach to the
Reachability Analysis of RPPS Systems 118
M. Nielsen and
C. Palamidessi and
F. D. Valencia Temporal Concurrent Constraint
Programming: Denotation, Logic and
Applications . . . . . . . . . . . . . . 145
K. Òsterbye Guest Editor's Foreword . . . . . . . . 189
E. Ernst Safe Dynamic Multiple Inheritance . . . 191
T. Vestdam Elucidative Program Tutorials . . . . . 209
E. Arisholm and
D. I. K. Sjòberg and
G. J. Carelius and
Y. Lindsjòrn A Web-Based Support Environment for
Software Engineering Experiments . . . . 231
I. Hammouda and
K. Koskimies A Pattern-Based J2EE Application
Development Environment . . . . . . . . 248
L. Bendix and
G. Hedin Summary of the Subworkshop on Extreme
Programming . . . . . . . . . . . . . . 261
M. Haveraaen and
M. R. Hansen Guest Editors' Foreword . . . . . . . . 267
T. Amnell and
E. Fersman and
P. Pettersson and
H. Sun and
W. Yi Code Synthesis for Timed Automata . . . 269
J. Hoenicke and
E.-R. Olderog CSP-OZ-DC: A Combination of
Specification Techniques for Processes,
Data and Time . . . . . . . . . . . . . 301
F. Nielson and
H. Seidl and
H. Riis Nielson A Succinct Solver for ALFP . . . . . . . 335
E. G. Wagner Algebraic Specifications: some old
history and new thoughts . . . . . . . . 373
H. Wehrheim Relating State-based and
Behaviour-oriented Subtyping . . . . . . 405
Anonymous Author Index Volume 9 (2002) . . . . . . 436
J. Holub Guest Editor's Foreword . . . . . . . . 1--1
K. Baba and
A. Shinohara and
M. Takeda and
S. Inenaga and
S. Arikawa A Note on Randomized Algorithm for
String Matching with Mismatches . . . . 2
L. Cinque and
S. De Agostino and
F. Liberati A Work-Optimal Parallel Implementation
of Lossless Image Compression by Block
Matching . . . . . . . . . . . . . . . . 13
F. Franek and
W. F. Smyth and
X. Xiao A Note on Crochemore's Repetitions
Algorithm --- A Fast Space-Efficient
Approach . . . . . . . . . . . . . . . . 21
H. Hyyrö A Bit-Vector Algorithm for Computing
Levenshtein and Damerau Edit Distances 29
C. S. Iliopoulos and
M. Mohamed and
L. Mouchard and
K. G. Perdikuri and
W. F. Smyth and
A. K. Tsakalidis String Regularities with Don't Cares . . 40
S. Inenaga Bidirectional Construction of Suffix
Trees . . . . . . . . . . . . . . . . . 52
U. Nestmann and
P. Panangaden Guest Editors' Foreword . . . . . . . . 69
M. Carbone and
S. Maffeis On the Expressive Power of Polyadic
Synchronisation in pi-calculus . . . . . 70
J. Ouaknine and
J. Worrell Timed CSP = Closed Timed
epsilon-automata . . . . . . . . . . . . 99
M. Fernández and
L. Khalil Interaction Nets with McCarthy's \tt
amb: Properties and Applications . . . . 134
V. Sassone and
P. Sobocinski Deriving Bisimulation Congruences using
$2$-categories . . . . . . . . . . . . . 163
K. Lemström and
J. Tarhio Transposition Invariant Pattern Matching
for Multi-Track Strings . . . . . . . . 185
J. Fiala and
P. Heggernes and
P. Kristiansen and
J. A. Telle Generalized $H$-coloring and
$H$-covering of Trees . . . . . . . . . 206
M. Segal Placing an Obnoxious Facility in
Geometric Networks . . . . . . . . . . . 225
J. Katajainen and
F. Vitale Navigation Piles with Applications to
Sorting, Priority Queues, and Priority
Deques . . . . . . . . . . . . . . . . . 238
M. Haveraaen and
J. Vain Guest Editors' Foreword . . . . . . . . 263
M. Benke and
P. Dybjer and
P. Jansson Universes for Generic Programs and
Proofs in Dependent Type Theory . . . . 265
N. Ghani and
C. Lüth Rewriting Via Coinserters . . . . . . . 290
E. B. Johnsen and
C. Lüth Abstracting Refinements for
Transformation . . . . . . . . . . . . . 313
H. Pilegaard and
M. R. Hansen and
R. Sharp An Approach to Analyzing Availability
Properties of Security Protocols . . . . 337
Anonymous Author Index Volume 10 (2003) . . . . . 374
M. Gairing and
R. M. Geist and
S. T. Hedetniemi and
P. Kristiansen A Self-stabilizing Algorithm for Maximal
$2$-packing . . . . . . . . . . . . . . 1
T. Sivertsen Undefinedness vs. Underspecification in
HALDEN ASL . . . . . . . . . . . . . . . 12
Z. Tronícek Episode Directed Acyclic Subsequence
Graph . . . . . . . . . . . . . . . . . 35
A. Berlea and
H. Seidl Binary Queries for Document Trees . . . 41
K. Sere and
M. Waldén Guest Editors' Foreword . . . . . . . . 73
P. Boström and
M. Waldén Implementation of Control Systems Using
B Action Systems: A Case Study . . . . . 75
O. Celiku and
A. McIver Cost-Based Analysis of Probabilistic
Programs Mechanised in HOL . . . . . . . 102
E. Fersman and
W. Yi A Generic Approach to Schedulability
Analysis of Real-Time Tasks . . . . . . 129
T. Latvala and
H. Tauriainen Improved On-the-fly Verification with
Testers . . . . . . . . . . . . . . . . 148
R. Ruksenas A Rigourous Environment for Development
of Concurrent Systems . . . . . . . . . 165
G. Schneider Computing Invariance Kernels of
Polygonal Hybrid Systems . . . . . . . . 194
J. Lilius and
K. Òsterbye Guest Editors' Foreword: Programming and
Software Development Environment
Research in the Nordic Countries . . . . 211
A. Nilsson and
A. Ive and
T. Ekman and
G. Hedin Implementing Java Compilers Using ReRAGs 213
P. Selonen and
M. Siikarla and
K. Koskimies and
T. Mikkonen Towards the Unification of Patterns and
Profiles in UML . . . . . . . . . . . . 235
M. Staron and
L. Kuzniarz and
L. Wallin Case Study on a Process of Industrial
MDA Realization -- Determinants of
Effectiveness . . . . . . . . . . . . . 254
H. Störrle Structured Nodes in UML 2.0 Activities 279
T. Vestdam and
K. Nòrmark Maintaining Program Understanding --
Issues, Tools, and Future Directions . . 303
E. Sutinen and
J. Tarhio Approximate String Matching with Ordered
$q$-Grams . . . . . . . . . . . . . . . 321
S. Bereg and
M. Segal Dynamic Algorithms for Approximating
Interdistances . . . . . . . . . . . . . 344
G. Navarro Approximate Regular Expression Searching
with Arbitrary Integer Weights . . . . . 356
H. L. Bodlaender and
J. A. Telle Space-Efficient Construction Variants of
Dynamic Programming . . . . . . . . . . 374
Anonymous Author Index Volume 11 (2004) . . . . . 386
Danny Krizanc and
Pat Morin and
Michiel Smid Range Mode and Range Median Queries on
Lists and Trees . . . . . . . . . . . . 1--17
Wan Fokkink and
Jaap-Henk Hoepman and
Jun Pang A Note on $K$-State Self-stabilization
in a Ring with $K = N$ . . . . . . . . . 18--26
Amr Elmasry Deterministic Jumplists . . . . . . . . 27--39
Veli Mäkinen and
Gonzalo Navarro Succinct Suffix Arrays based on
Run-Length Encoding . . . . . . . . . . 40--66
Paul Pettersson and
Wang Yi Guest Editors' Foreword . . . . . . . . 67
Juhan Ernits Memory Arbiter Synthesis and
Verification for a Radar Memory
Interface Card . . . . . . . . . . . . . 68--88
Lars Kristiansen and
Paul J. Voda Programming Languages Capturing
Complexity Classes . . . . . . . . . . . 89--115
Marcel Kyas and
Frank S. de Boer and
Willem-Paul de Roever A Compositional Trace Logic for
Behavioural Interface Specifications . . 116--132
Härmel Nestra Transfinite Corecursion . . . . . . . . 133--156
Ragnhild Kobro Runde and
Òystein Haugen and
Ketil Stòlen Refining UML Interactions with
Underspecification and Nondeterminism 157--188
Todd L. Veldhuizen Language Embeddings that Preserve
Staging and Safety . . . . . . . . . . . 189--198
Johan Lilius and
Ricardo J. Machado and
Dragos Truscan and
João M. Fernandes and
Ivan Porres Guest Editors' Foreword . . . . . . . . 198--199
Issam Al-Azzoni and
Douglas G. Down and
Ridha Khedri Modeling and Verification of
Cryptographic Protocols Using Coloured
Petri Nets and Design/CPN . . . . . . . 200--228
João Paulo Barros and
Jens Bæk Jòrgensen A Case Study on Coloured Petri Nets in
Object-Oriented Analysis and Design . . 229--250
Jonathan Billington and
Guy Edward Gallasch and
Laure Petrucci Verification of the Class of
Stop-and-Wait Protocols Modelled by
Coloured Petri Nets . . . . . . . . . . 251--274
Erez Petrank and
Dror Rawitz The Hardness of Cache Conscious Data
Placement . . . . . . . . . . . . . . . 275--307
Elena Prieto and
Christian Sloper Reducing to Independent Set Structure --
the Case of $k$-Internal Spanning Tree 308--318
Kai Koskimies and
Ludwik Ku\'zniarz Guest Editors' Foreword . . . . . . . . 319--320
Marcus Alanen and
Torbjörn Lundkvist and
Ivan Porres Comparison of Modeling Frameworks for
Software Engineering . . . . . . . . . . 321--342
\Lukasz Dobrza\'nski and
Ludwik Ku\'zniarz Practical Refactoring of Executable UML
Models . . . . . . . . . . . . . . . . . 343--360
Johan Lilius and
Tomas Lillqvist and
Torbjörn Lundkvist and
Ian Oliver and
Ivan Porres and
Kim Sandström and
Glen Sveholm and
Asim Pervez Zaka An Architecture Exploration Environment
for System on Chip Design . . . . . . . 361--378
Sven Wenzel Automatic Detection of Incomplete
Instances of Structural Patterns in UML
Class Diagrams . . . . . . . . . . . . . 361--378
Neil D. Jones Guest Editor's Foreword . . . . . . . . 1
Maksym Bortin and
Einar Broch Johnsen and
Christoph Lüth Structured Formal Development in
Isabelle . . . . . . . . . . . . . . . . 2--21
Ingo Brückner and
Björn Metzler and
Heike Wehrheim Optimizing Slicing of Formal
Specifications by Deductive Verification 22--45
Tristan Crolard and
Samuel Lacas and
Pierre Valarcher On the Expressive Power of the Loop
Language . . . . . . . . . . . . . . . . 46--57
Troels C. Damgaard and
Lars Birkedal Axiomatizing Binding Bigraphs . . . . . 58--77
Monica Nesi and
Giustina Nocera Deriving the Type Flaw Attacks in the
Otway--Rees Protocol by Rewriting . . . 78--97
Christoffer Rosenkilde Nielsen and
Hanne Riis Nielson Static Analysis for Blinding . . . . . . 98--116
Kristian Stòvring Higher-Order Beta Matching with
Solutions in Long Beta-Eta Normal Form 117--126
Leonidas Tsiopoulos and
Marina Waldén Formal Development of NoC Systems in B 127--145
Andreas Prinz and
Merete Skjelten Tveit Guest Editor's Foreword . . . . . . . . 147--148
Pauli Byckling and
Petri Gerdt and
Ludwik Kuzniarz and
Jorma Sajaniemi Increasing Comprehensibility of Object
Models: Making the Roles of Attributes
Explicit in UML Diagrams . . . . . . . . 149--161
Johannes Koskinen and
Anna Ruokonen and
Tarja Systä A Pattern-Based Approach to Generate
Code from API Usage Scenarios . . . . . 162--179
Mika Siikarla and
Jari Peltonen and
Johannes Koskinen Towards Unambiguous Model Fragments . . 180--195
André L. Santos and
Kai Koskimies and
Antónia Lopes A Model-Driven Approach to Variability
Management in Product-Line Engineering 196--213
Assefaw Hadish Gebremedhin and
Mohamed Essa\"\idi and
Isabelle Guérin Lassous and
Jens Gustedt and
Jan Arne Telle PRO: A Model for the Design and Analysis
of Efficient and Scalable Parallel
Algorithms . . . . . . . . . . . . . . . 215--239
Alexandru Berlea Online Evaluation of Regular Tree
Queries . . . . . . . . . . . . . . . . 240--265
Rajiv Kumar Poddar and
Purandar Bhaduri Verification of Giotto based Embedded
Control Systems . . . . . . . . . . . . 266--293
Prosenjit Gupta Range-Aggregate Query Problems Involving
Geometric Aggregation Operations . . . . 294--308
K. Subramani and
John Argentieri Chain Programming over Difference
Constraints . . . . . . . . . . . . . . 309--327
Daniel Lemire Streaming Maximum-Minimum Filter Using
No More than Three Comparisons per
Element . . . . . . . . . . . . . . . . 328--339
Michel Schellekens and
Rachit Agarwal and
Emanuel Popovici and
Ka Lok Man A Simplified Derivation of Timing
Complexity Lower Bounds for Sorting by
Comparisons . . . . . . . . . . . . . . 340--346
Parosh Aziz Abdulla and
Johann Deneux and
Pritha Mahata and
Aletta Nylén Using Forward Reachability Analysis for
Verification of Timed Petri Nets . . . . 1--42
Vitus S. W. Lam A Formalism for Reasoning about UML
Activity Diagrams . . . . . . . . . . . 43--64
Ka Lok Man Formal Specification and Analysis of
Hardware Systems in Timed Chi . . . . . 65--86
Pinar Heggernes and
Dieter Kratsch Linear-time certifying recognition
algorithms and forbidden induced
subgraphs . . . . . . . . . . . . . . . 87--108
Anat Bremler-Barr and
Leah Epstein Path layout on tree networks: Bounds in
different label switching models . . . . 109--125
Meena Mahajan and
Raghavan Rama and
S. Vijayakumar Block Sorting: A Characterization and
some Heuristics . . . . . . . . . . . . 126--150
Mark Cieliebak and
Stephan Eidenbenz and
Aris T. Pagourtzis and
Konrad Schlude On the Complexity of Variations of Equal
Sum Subsets . . . . . . . . . . . . . . 151--172
Qiwen Xu and
Naijun Zhan Formalising Scheduling Theories in
Duration Calculus . . . . . . . . . . . 173--201
Evangelos Kranakis and
Danny Krizanc and
Sunil Shende Tracking Mobile Users in Cellular
Networks using Timing Information . . . 202--215
Y. Boichut and
P.-C. Héam and
O. Kouchnarenko Approximation-based Tree Regular
Model-Checking . . . . . . . . . . . . . 216--241
Ebba Hvannberg Guest Editor's Foreword . . . . . . . . 243--244
Cyril Carrez and
Lotte Johansen and
Pawel Cieslak and
Stefan Hänsgen Service Engineering with the SIMS Design
and Validation Tools . . . . . . . . . . 245--263
Samuel Lahtinen and
Kai Koskimies A Model-Based Approach to Reflective
Command Interfaces . . . . . . . . . . . 264--281
Kenneth Lind and
Rogardt Heldal Estimation of Real-Time Software
Component Size . . . . . . . . . . . . . 282--300
Parastoo Mohagheghi and
Vegard Dehlen and
Tor Neple A Metamodel and Supporting Process and
Tool for Specifying Quality Models in
Model-Based Software Development . . . . 301--320
Mikko Raatikainen and
Varvana Myllärniemi and
Tomi Männistö Featback: Method for Enhancing
Management of Agile Development . . . . 321--337
Outi Räihä and
Kai Koskimies and
Erkki Mäkinen and
Tarja Systä Pattern-Based Genetic Model Refinements
in MDA . . . . . . . . . . . . . . . . . 338--355
Jari Peltonen Guest Editor's Foreword . . . . . . . . 1--2
Maarit Harsu and
Tibor Bakota and
István Siket and
Kai Koskimies and
Tarja Systä Code Clones: Good, Bad, or Ugly? . . . . 3--17
Zoltán Herczeg and
Gábor Lóki and
Tamás Szirbucz and
Ákos Kiss Validating JavaScript Guidelines across
Multiple Web Browsers . . . . . . . . . 18--31
Markku Sakkinen and
Philippe Lahire and
Ciprian-Bogdan Chiril\ua Towards Fully-Fledged Reverse
Inheritance in Eiffel . . . . . . . . . 32--52
Mikko Tiusanen and
Antti Valmari Good to Know about the Efficiency of
State Space Methods . . . . . . . . . . 53--74