NORDIC JOURNAL OF COMPUTING VOLUME 1 NUMBER 1 SPRING 1994 INVITED PAPERS: K. Fisher, F. Honsell and J. C. Mitchell A Lambda Calculus of Objects and Method Specialization 3 T. Hagerup and M. Maas Generalized Topological Sorting in Linear Time 38 T. F. Melham A Mechanized Theory of the Pi-calculus in HOL 50 H. MÃ¶ssenbÃ¶ck Extensibility in the Oberon System 77 SURVEY: P. Orponen Neural Networks and Complexity Theory 94 REGULAR PAPERS: H. L. Bodlaender, G. Tel and N. Santoro Trade-Offs in Non-Reversing Diameter 111 O. Lysne Heuristics for Completion in Automatic Proofs by Structural Induction 135 J. A. Telle Complexity of Domination-Type Problems in Graphs 157 VOLUME 1 NUMBER 2 SUMMER 1994 REGULAR PAPERS: J.R.S. Blair and B. W. Peyton On Finding Minimum-Diameter Clique Trees 173 K. Coolsaet, V. Fack and H. De Meyer A Tabular Method for Verification of Data Exchange Algorithms on Networks of Parallel Processors 202 S. Jajodia, R. Mukkamala and K.V.S. Ramarao A View-based Dynamic Replication Control Algorithm 214 R. Janardan and F. P. Preparata Widest-Corridor Problems 231 U. Pferschy, R. Rudolf and G. J. Woeginger Some Geometric Clustering Problems 246 NOTES: K. Jansen Integral Flow with Disjoint Bundles 264 J. W. Krussel and B. F. Schaudt A Note on Higher Order Voronoi Diagrams 268 VOLUME 1 NUMBER 3 FALL 1994 SELECTED PAPERS OF THE 20TH INTERNATIONAL COLLOQUIUM ON AUTOMATA, LANGUAGES AND PROGRAMMING (ICALP93), JULY 5-9, 1993: A. Lingas Editor's Foreword 273 M. V. Marathe, H. B. Hunt III, S. S. Ravi The Complexity of Approximation PSPACE-Complete Problems for Hierarchical Specifications 275 V. Kann Polynomially Bounded Minimization Problems that are Hard to Approximate 317 B. S. Chlebus, K. Diks, A. Pelc Sparse Networks Supporting Efficient Reliable Broadcasting 332 K. Havelund and K. G. Larsen The Fork Calculus 346 H. Hungar and B. Steffen Local Model-Checking for Context-Free Processes 364 VOLUME 1 NUMBER 4 WINTER 1994 SELECTED PAPERS OF THE 4TH SCANDINAVIAN WORKSHOP ON ALGORITHM THEORY (SWAT94), JULY 6-8, 1994: S. Skyum Guest Editor's Foreword 387 P. Becker A New Algorithm for the Construction of Optimal B-Trees 389 E. Schenk Parallel Dynamic Lowest Common Ancestors 402 G. Das, P. J. Heffernan and G. Narasimhan Finding All Weakly-Visible Chords of a Polygon in Linear Time 433 S. Schuierer An O(log log n) Time Algorithm to Compute the Kernel of a Polygon 458 M. M. HalldÃ³rsson and J. Radhakrishnan Improved Approximations of Independent Sets in Bounded- Degree Graphs via Subgraph Removal 475 M. Peinado Hard Graphs for the Randomized Boppana-HalldÃ‚?Ã³rsson Algorithm for MAXCLIQUE 493 Author Index Volume 1 (1994) 517 NORDIC JOURNAL OF COMPUTING VOLUME 2 NUMBER 1 SPRING 1995 E. Ukkonen Editor's Foreword 1 M. Golin, R. Raman, C. Schwartz, and M. Smid Simple Randomized Algorithms for Closest Pair Problems 3 V. Kamakoti, K. Krithivasan and C. Pandu Rangan An Efficient Randomized Algorithm for the Closest Pair Problem on Colored Point Sets 28 J. KratochvÃl, P. D. Manuel and M. Miller Generalized Domination in Chordal Graphs 41 V. LeppÃ¤nen and M. Penttonen Work-Optimal Simulation of PRAM Models on Meshes 51 M. Vassilakopoulos, Y. Manolopoulos and B. KrÃ¶ll Efficiency Analysis of Overlapped Quadtrees 70 VOLUME 2 NUMBER 2 SUMMER 1995 SELECTED PAPERS OF THE 5TH INTERNATIONAL CONFERENCE ON CONCUR '94: CONCURRENCY THEORY, AUGUST 22-25, 1994: B. Jonsson and J. Parrow Guest Editors Foreword 87 O. Burkart and B. Steffen Composition, Decomposition and Model Checking of Pushdown Processes 89 P. Di Gianantonio, F. Honsell and G. Plotkin Uncountable Limits and the Lambda Calculus 126 P. C. Kanellakis, D. Michailidis and A. A. Shvartsman Controlling Memory Access Concurrency in Efficient Fault-Tolerant Parallel Algorithms 146 N. P. Mendler, P. Panangaden, P. J. Scott and R.A.G. Seely A Logical View of Concurrent Constraint Programming 181 M. Nielsen and C. Clausen Games and Logics for a Noninterleaving Bisimulation 221 R. Segala and N. Lynch Probabilistic Simulations for Probabilistic Processes 250 C. Verhoef A Congruence Theorem for Structured Operational Semantics with Predicates and Negative Premises 274 VOLUME 2 NUMBER 3 FALL 1995 C. B. Fraser and R. W. Irving Approximation Algorithms for the Shortest Common Supersequence 303 K-L. Chung and Y-W. Chen Mapping Pyramids into 3-D Meshes 326 J. C. Godskesen and K. G. Larsen Synthesizing Distinguishing Formulae for Real Time Systems 338 M. Walicki and M. Broy Structured Specifications and Implementation of Nondeterministic Data Types 358 VOLUME 2 NUMBER 4 WINTER 1995 K.-L. Chung Fast Median-Finding on Mesh-Connected Computers with Segmented Buses 397 J. Parrow Interaction Diagrams 407 C. Rick A New Flexible Algorithm for the Longest Common Subsequence Problem 444 H.L. Bodlaender, T.F. Gonzalez and T. Kloks Complexity Aspects of Two-Dimensional Data Compression 462 NOTE: J. Clausen and J. Krarup A Family of Bipartite Cardinality Matching Problems Solvable in O(n^2) Time 496 Author Index Volume 2 (1995) 503 VOLUME 3 NUMBER 1 SPRING 1996 Y. H. Tsin and C.-A. Wang Geodesic Voronoi Diagrams in the Presence of Rectilinear Barriers 1 J. Katajainen, T. Pasanen and J. Teuhola Practical In-Place Mergesort 27 H. Seidl Least and Greatest Solutions of Equations over N 41 S. G. Akl and I. Stojmenovic Generating t-ary Trees in Parallel 63 A. Datta, A. Maheshwari and J.-R. Sack Optimal Parallel Algorithms for Direct Dominance Problems 72 VOLUME 3 NUMBER 2 SUMMER 1996 C.-Z. Lin, C.-C. Tseng, Y.-L. Chen and T.-W. Kuo A Systematic Approach to Synthesize Data Alignment Directives for Distributed Memory Machines 89 L. Malmi A New Method for Updating and Rebalancing Tree-Type Main Memory Dictionaries 111 H. Linnestad Fatal Steps of Knuth-Bendix Completion 131 F. Nielson and H. R. Nielson Operational Semantics of Termination Types 144 K. Diks and A. Pelc Fault-Tolerant Linear Broadcasting 188 VOLUME 3 NUMBER 3 FALL 1996 C. A. Brown, L. Finkelstein and P. W. Purdom Jr. Backtrack Searching in the Presence of Symmetry 203 P. Eades, M. Keil, P. D. Manuel and M. Miller Two Minimum Dominating Sets with Minimum Intersection in Chordal Graphs 220 G. S. Brodal Partially Persistent Data Structures of Bounded Degree with Constant Update Time 238 S. Natarajan and A. P. Sprague Disjoint Paths in Circular Arc Graphs 256 J.-C. Chen Proportion Split Sort 271 C.-H. Ang and H. Samet Approximate Average Storage Utilization of Bucket Methods with Arbitrary Fanout 280 VOLUME 3 NUMBER 4 WINTER 1996 SELECTED PAPERS OF THE 5TH SCANDINAVIAN WORKSHOP ON ALGORITHM THEORY (SWAT'96), JULY 3-5, 1996: R. Karlsson and A. Lingas Guest Editors' Foreword 293 T. W. Lam, W. K. Sung and H. F. Ting Computing Unrooted Maximum Subtrees in Sub-quartic Time 295 T. Husfeldt, T. Rauhe and S. Skyum Lower Bounds for Dynamic Transitive Closure, Planar Point Location, and Parantheses Matching 323 G. S. Brodal, S. Chaudhuri and J. Radhakrishnan The Randomized Complexity of Maintaining the Minimum 337 D. FernÃ¡ndez-Baca, G. Slutzki and D. Eppstein Using Sparsification for Parametric Minimum Spanning Tree Problems 352 M. V. Marathe, R. Ravi and R. Sundaram Service-Constrained Network Design Problems 367 T. Asano, T. Ono and T. Hirata Approximation Algorithms for the Maximum Satisfiability Problem 405 H. C. Lau and O. Watanabe Randomized Approximation of the Constraint Satisfaction Problem 425 N. Alon, P. Kelsen, S. Mahajan and H. Ramesh Coloring 2-colorable Hypergraphs with a Sublinear Number of Colors 425 Author Index Volume 3 (1996) 440 VOLUME 4 NUMBER 1 SPRING 1997 THEME ISSUE ON PROGRAMMING ENVIRONMENTS K. Koskimies Editor's Foreword 1 J. Paakki, J. Koskinen and A. Salminen From Relational Program Dependencies to Hypertextual Access Structures 3 S. G. Efremidis, K. A. Mughal, J. H. Reppy and L. SÃ¸raas AML: Attribute Grammars in ML 37 J. Bosch Delegating Compiler Objects: Modularity and Reusability in Language Engineering 66 G. Hedin Attribute Extensions - a Technique for Enforcing Programming Conventions 93 D. I. K. SjÃ¸berg, R. Welland, M. P. Atkinson, P. Philbrow, C. Waite and S. Macneill The Persistent Workshop - a Programming Environment for Napier88 123 VOLUME 4 NUMBER 2 SUMMER 1997 G. Gambosi, A. Postiglione and M. Talamo On-Line Maintenance of an Approximate Bin-Packing Solution 151 T. Roos New Upper Bounds on Voronoi Diagrams of Moving Points 167 M. Karpinski, W. Rytter and A. Shinohara An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions 172 E. Roche Compact Factorization of Finite-State Transducers and Finite-State Automata 187 M. Mohri String-Matching with Automata 217 VOLUME 4 NUMBER 3 FALL 1997 L. Lundberg and H. Lennerstad Bounding the Gain of Changing the Number of Memory Modules in Shared Memory Multiprocessors 233 J. Palsberg and T. Jim Type Inference with Simple Selftypes is NP-complete 259 T. GyimÃ³thy and T. HorÃ¡th Learning Semantic Functions of Attribute Grammars 287 A. Yamaguchi, K. Nakano and S. Miyano An Approximation Algorithm for the Minimum Common Supertree Problem 303 VOLUME 4 NUMBER 4 WINTER 1997 A. Israeli, E. Kranakis, D. Krizanc and N. Santoro Time-Message Trade-Offs for the Weak Unison Problem 317 A. Mukhopadhyay, A. Agrawal and R. M. Hosabettu On the Ordinary Line Problem in Computational Geometry 330 M. Pal and G. P. Bhattacharjee An Optimal Parallel Algorithm for All-Pairs Shortest Paths on Unweighted Interval Graphs 342 O. Kaser Optimal Height Reduction Problems for Tree-Structured Hierarchies 357 H. Erdogmus Architecture-Driven Verification of Concurrent Systems 380 Author Index Volume 4 (1997) 414 VOLUME 5 NUMBER 1 SPRING 1998 D. Krznaric and C. Levcopoulos Computing a Threaded Quadtree from the Delaunay Triangulation in Linear Time 1 O.-J. Dahl, O. Owe and T. J. Bastiansen Subtyping and Constructive Specification 19 B. Kristoffersen and O.-J. Dahl On Introducing Higher Order Functions in ABEL 50 R. A. Baeza-Yates and H. Soza-Pollman Analysis of Linear Hashing Revisited 70 VOLUME 5 NUMBER 2 SUMMER 1998 S. Dobrev and P. Ruzicka On the Communication Complexity of Strong Time-Optimal Distributed Algorithms 87 P. HÃ¸yer and K. S. Larsen Parametric Permutation Routing via Matchings 105 J. L. Ganley and J. S. Salowe The Power-p Steiner Tree Problem 115 P. Heggernes and J. A. Telle Partitioning Graphs Into Generalized Dominating Sets 128 M. Johnsson, G. Magyar and O. Nevalainen On the Euclidean 3-Matching Problem 143 VOLUME 5 NUMBER 3 FALL 1998 J. KratochvÃl, A. Proskurowski and J. A. Telle Complexity of Graph Covering Problems 173 T. F. Gonzalez Bounded Fan-Out Multimessage Multicasting 196 C. Mossin Higher-Order Value Flow Graphs 214 J. Paakki and A.-P. Tuovinen Source-to-Source Translation of Visual Languages 235 VOLUME 5 NUMBER 4 WINTER 1998 SELECTED PAPERS OF THE EUROPEAN SYMPOSIUM ON PROGRAMMING (ESOP'98), APRIL 2-3, 1998: C. Hankin Guest Editor's Foreword 265 M. Abadi and A. D. Gordon A Bisimulation Method for Cryptographic Protocols 267 C. Fecht and H. Seidl Propagating Differences: an Efficient New Fixpoint Algorithm for Distributive Constraint Systems 304 K. R. M. Leino Recursive Object Types in a Logic of Object-Oriented Programs 330 J. L. Ross and M. Sagiv Building a Bridge between Pointer Aliases and Program Dependences 361 Author Index Volume 5 (1998) 387 VOLUME 6, NUMBER 1, SPRING 1999 SELECTED PAPERS OF THE EIGHTH NORDIC WORKSHOP ON PROGRAMMING ENVIRONMENT RESEARCH (NWPER'98), AUGUST 21-23, 1998: K. A. Mughal and A. L. Opdahl Guest Editors' Foreword: Programming and Software Development Environment Research in the Nordic Countries 1 H. B. Christensen The Ragnarok Software Development Environment 4 K. KjelstrÃ¸m and P. Petersen A CASE Tool for COM Development 22 E. Bjarnason, G. Hedin, and K. Nilsson Interactive Language Development for Embedded Systems 36 H. RÃ¸n An Overview of a Dynamic Programming Environment Based on Extensibility 55 E. Ernst Dynamic Inheritance in a Statically Typed Language 72 M. Harsu Translation of Conditional Compilation 93 K. NÃ¸rmark, L. Iversen, and P. Madsen Animation and Presentation Tools for Object-Oriented Design 110 L. Bendix and U. Asklund Summary of the Subworkshop on Change Management 129 VOLUME 6, NUMBER 2, SUMMER 1999 SELECTED PAPERS OF THE SIXTH SCANDINAVIAN WORKSHOP ON ALGORITHM THEORY (SWAT'98), JULY 8-10, 1998: J. Lagergren and P. B. Miltersen Guest Editors' Foreword 135 N. H. Sleumer Output-Sensitive Cell Enumeration in Hyperplane Arrangements 137 S. S. Seiden Randomized Online Multi-Threaded Paging 148 V. Raman and S. Ramnath Improved Upper Bounds for Time-Space Trade-offs for Selection 162 P. Berman and C. Coulston Speed is More Powerful than Clairvoyance 181 S. Sen and N. Gupta Distribution-Sensitive Algorithms 194 VOLUME 6, NUMBER 3, FALL 1999 SELECTED PAPERS OF THE TENTH NORDIC WORKSHOP ON PROGRAMMING THEORY (NWPT'98), OCTOBER 14-16, 1998: K. Sere Guest Editor's Foreword 213 P. Ciancarini, A. Omicini and F. Zambonelli Coordination Technologies for Internet Agents 215 M. Haveraaen, H. A. Friis and T. A. Johansen Formal Software Engineering for Computational Modelling 241 K. G. Larsen, J. Pearson, C. Weise and W Yi Clock Difference Diagrams 271 C. J. Lillieroth and S. Singh Formal Verification of FPGA Cores 299 E. A. Troubitsyna Reliability Assessment through Probabilistic Refinement 320 T. Uustalu and V. Vene Mendler-Style Inductive Types, Categorically 343 VOLUME 6 NUMBER 4 WINTER 1999 M.-S. Hwang A Dynamic Key Generation Scheme for Access Control in a Hierarchy 363 S. Tahar and P. Curzon Comparing HOL and MDG: a Case Study on the Verification of an ATM Switch Fabric 372 J. Larsen and I. Pedersen Experiments with the Auction Algorithm for the Shortest Path Problem 403 M. Andreou and S. D. Nikolopoulos NC Coloring Algorithms for Permutation Graphs 422 D. Krznaric, C. Levcopoulos and B. J. Nilsson Minimum Spanning Trees in d Dimensions 446 O. Devillers and A. Mukhopadhyay Finding an Ordinary Conic and an Ordinary Hyperplane 462 J. Gudmundsson and C. Levcopoulos A Fast Approximation Algorithm for TSP with Neighborhoods 469 Author Index Volume 6 (1999) 489 VOLUME 7 NUMBER 1 SPRING 2000 J. KarhumÃ¤ki, W. Plandowski, and W. Rytter Pattern-Matching Problems for Two-Dimensional Images Described by Finite Automata 1 H. L. Bodlaender and K. Jansen On the Complexity of the Maximum Cut Problem 14 J. Gudmundsson and C. Levcopoulos A Parallel Approximation Algorithm for Minimum Weight Triangulation 32 M. Zito Linear Time Maximum Induced Matching Algorithm for Trees 58 VOLUME 7 NUMBER 2 SUMMER 2000 SELECTED PAPERS OF THE EIGHTH NORDIC WORKSHOP ON PROGRAMMING ENVIRONMENT RESEARCH (NWPER'2000), MAY 28-30, 2000: A. L. Opdahl and D. I. K. SjÃ¸berg Guest Editors' Foreword: Programming and Software Development Environment Research in the Nordic Countries 65 E. Magnusson and G. Hedin Program Visualization Using Reference Attributed Grammars 67 K. NÃ¸rmark Elucidative Programming 87 T. Vestdam Documentation Threads - Presentation of Fragmented Documentation 106 M. Harsu Identifying Object-Oriented Features from Procedural Software 126 L. Bendix, U. Asklund, and J. Persson Summary of the Subworkshop on Change Management for Open Source Software 143 VOLUME 7 NUMBER 3 FALL 2000 SELECTED PAPERS OF THE SEVENTH SCANDINAVIAN WORKSHOP ON ALGORITHM THEORY (SWAT'2000), JULY 5--7, 2000: M. M. HalldÃ³rsson Guest Editor's Foreword 149 R. Pagh A Trade-Off for Worst-Case Efficient Dictionaries 151 A. Berry, J.-P. Bordat and P. Heggernes Recognizing Weakly Triangulated Graphs by Edge Separability 164 P. Berman A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs 178 S. Doddi, M. V. Marathe, S. S. Ravi, D. S. Taylor and P. Widmayer Approximation Algorithms for Clustering to Minimize the Sum of Diameters 185 V. Liberatore Scheduling Jobs before Shut-Down 204 P. K. Agarwal, L. J. Guibas, S. Har-Peled, A. Rabinovitch and M. Sharir Penetration Depth of Two Convex Polytopes in 3D 227 T. Asano, T. Matsui and T. Tokuyama Optimal Roundings of Sequences and Matrices 241 VOLUME 7 NUMBER 4 WINTER 2000 SELECTED PAPERS OF THE EUROPEAN SYMPOSIUM ON PROGRAMMING (ESOP'2000), MARCH 25 -- APRIL 2, 2000: G. Smolka Guest Editor's Foreword 257 M. Hofmann A Type System for Bounded Space and Functional In-Place Update 258 L. Mauborgne An Incremental Unique Representation for Regular Trees 290 F. Pottier A Versatile Constraint-Based Type Inference System 312 C. V. Russo First-Class Structures for Standard ML 348 H. Seidl and B. Steffen Constraint-Based Inter-Procedural Analysis of Parallel Programs 375 Author Index Volume 7 (2000) 401 VOLUME 8 NUMBER 1 SPRING 2001 SELECTED PAPERS OF THE ELEVENTH NORDIC WORKSHOP ON PROGRAMMING THEORY (NWPT'99), OCTOBER 13--15, 1999: K. Sere and W. Yi Guest Editors' Foreword 1 R.-J. Back, L. Petre and I. Porres Continuous Action Systems as a Model for Hybrid Systems 2 A. Bove Simple General Recursion in Type Theory 22 T. Hune, K. G. Larsen and P. Pettersson Guided Synthesis of Control Programs Using UPPAAL 43 B. Jonsson, T. Margaria, G. Naeser, J. NystrÃ¶m and B. 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 S. MÃ¸rk Distributed Implementation of a Process-Algebra Based Pro- gramming Language for Embedded Systems 121 M. RÃ¶nkkÃ¶ and X. Li Linear Hybrid Action Systems 159 VOLUME 8 NUMBER 2 SUMMER 2001 Th. Ottmann, S. Schuierer and S. Soundaralakshmi Enumerating Extreme Points in Higher Dimensions 179 K. Sere and M. WaldÃ©n Structuring and Verifying Distributed Algorithms 193 J. Gudmundsson, C. Levcopoulos and G. Narasimhan Approximating a Minimum Manhattan Network 219 H. Riis Nielson and F. Nielson Shape Analysis for Mobile Ambients 233 VOLUME 8 NUMBER 3 FALL 2001 SELECTED PAPERS OF THE TWELFTH NORDIC WORKSHOP ON PROGRAMMING THEORY (NWPT'00), OCTOBER 11--13, 2000: M. Haveraaen and O. Owe Guest Editors' Foreword 277 W. Dosch and S. Magnussen Computer Aided Fusion for Algebraic Program Derivation 279 Y. Lamo and M. Walicki Specification of Parameterized Programs -- Persistency Revisited 298 V. Petersson and S. Vorobyov A Randomized Subexponential Algorithm for Parity Games 324 H. Fecher A Real-Time Process Algebra with Open Intervals and Maximal Progress 346 T. Uustalu, V. Vene, and A. Pardo Recursion Schemes from Comonads 366 J. E. Labra Gayo, J. M. Cueva, M. C. Luengo and A. Cernuda Modular Development of Interpreters from Semantic Building Blocks 391 VOLUME 8 NUMBER 4 WINTER 2001 B. BollobÃ¡s, G. Das, D. Gunopulos and H. Mannila Time-Series Similarity Problems and Well-Separated Geometric Sets 409 P. R. J. Ã–stergÃ¥rd A New Algorithm for the Maximum-Weight Clique Problem 424 B. Grobauer and J. L. Lawall Partial Evaluation of Pattern Matching in Strings, revisited 437 J. Boyar, L. M. Favrholdt, K. S. Larsen and M. N. Nielsen The Competitive Ratio for On-Line Dual Bin Packing with Restricted Input Sequences 463 NOTE: J. Burghardt Maintaining Partial Sums in Logarithmic Time 473 Author Index Volume 8(2001) 475 VOLUME 9 NUMBER 1 SPRING 2002 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, B. J. Nilsson and S. Schuierer Improved Exploration of Rectilinear Polygons 32 M. Crochemore, C. Iliopoulos, C. Makris, W. Rytter, A. Tsakalidis and K. Tsichlas Approximate String Matching with Gaps 54 NOTE: K. N. Klipsch and D. S. Wise Blood from Dahm's Turnip 66 VOLUME 9 NUMBER 2 SUMMER 2002 SELECTED PAPERS OF THE EIGHTH INTERNATIONAL WORKSHOP ON EXPRESSIVENESS IN CONCURRENCY (EXPRESS'01), AUGUST 20, 2001: 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, C. Palamidessi and F. D. Valencia Temporal Concurrent Constraint Programming: Denotation, Logic and Applications 145 VOLUME 9 NUMBER 3 FALL 2002 SELECTED PAPERS OF THE TENTH NORDIC WORKSHOP ON PROGRAMMING ENVIRONMENT RESEARCH (NWPER'2002), AUGUST 18--20, 2002: K. Ã˜sterbye Guest Editor's Foreword 189 E. Ernst Safe Dynamic Multiple Inheritance 191 T. Vestdam Elucidative Program Tutorials 209 E. Arisholm, D. I. K. SjÃ¸berg, 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 VOLUME 9 NUMBER 4 2002 SELECTED PAPERS OF THE THIRTEENTH NORDIC WORKSHOP ON PROGRAMMING THEORY (NWPT'01), OCTOBER 10--12, 2001: M. Haveraaen and M. R. Hansen Guest Editors' Foreword 267 T. Amnell, E. Fersman, P. Pettersson, 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, 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 Author Index Volume 9 (2002) 436 VOLUME 10 NUMBER 1 SPRING 2003 SELECTED PAPERS OF THE PRAGUE STRINGOLOGY CONFERENCE (PSC'02), SEPTEMBER 23--24, 2002: J. Holub Guest Editor's Foreword 1 K. Baba, A. Shinohara, M. Takeda, S. Inenaga and S. Arikawa A Note on Randomized Algorithm for String Matching with Mismatches 2 L. Cinque, S. De Agostino and F. Liberati A Work-Optimal Parallel Implementation of Lossless Image Compression by Block Matching 13 F. Franek, 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, M. Mohamed, L. Mouchard, K. G. Perdikuri, W. F. Smyth and A. K. Tsakalidis String Regularities with Don't Cares 40 S. Inenaga Bidirectional Construction of Suffix Trees 52 VOLUME 10 NUMBER 2 SUMMER 2003 SELECTED PAPERS OF THE NINTH INTERNATIONAL WORKSHOP ON EXPRESSIVENESS IN CONCURRENCY (EXPRESS'02), AUGUST 19, 2002: 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 amb: Properties and Applications 134 V. Sassone and P. Sobocinski Deriving Bisimulation Congruences using 2-categories 163 VOLUME 10 NUMBER 3 FALL 2003 K. LemstrÃ¶m and J. Tarhio Transposition Invariant Pattern Matching for Multi-Track Strings 185 J. Fiala, P. Heggernes, P. Kristiansen and J. A. Telle 206 Generalized H-coloring and H-covering of Trees M. Segal Placing an Obnoxious Facility in Geometric Networks 224 J. Katajainen and F. Vitale Navigation Piles with Applications to Sorting, Priority Queues, and Priority Deques 238 VOLUME 10 NUMBER 4 WINTER 2003 SELECTED PAPERS OF THE FOURTEENTH NORDIC WORKSHOP ON PROGRAMMING THEORY (NWPT'02), NOVEMBER 20--22, 2002: M. Haveraaen and J. Vain Guest Editors' Foreword 263 M. Benke, 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, M. R. Hansen and R. Sharp An Approach to Analyzing Availability Properties of Security Protocols 337 Author Index Volume 10 (2003) 374 VOLUME 11 NUMBER 1 SPRING 2004 M. Gairing, R. M. Geist, 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. Tronicek Episode Directed Acyclic Subsequence Graph 35 A. Berlea and H. Seidl Binary Queries for Document Trees 41 VOLUME 11 NUMBER 2 SUMMER 2004 SELECTED PAPERS OF THE FIFTEENTH NORDIC WORKSHOP ON PROGRAMMING THEORY (NWPT'03), OCTOBER 29--31, 2003: 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 VOLUME 11 NUMBER 3 FALL 2004 SELECTED PAPERS OF THE ELEVENTH NORDIC WORKSHOP ON PROGRAMMING ENVIRONMENT RESEARCH (NWPER'2004), AND THE SECOND NORDIC WORKSHOP ON UML, MODELING, METHODS AND TOOLS (NWUML'2004), AUGUST 17--20, 2004: J. Lilius and K. Ã˜sterbye Guest Editors' Foreword: Programming and Software Development Environment Research in the Nordic Countries 211 A. Nilsson, A. Ive, T. Ekman and G. Hedin Implementing Java Compilers Using ReRAGs 213 P. Selonen, M. Siikarla, K. Koskimies and T. Mikkonen Towards the Unification of Patterns and Profiles in UML 235 M. Staron, 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 VOLUME 11 NUMBER 4 WINTER 2004 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 Author Index Volume 11 (2004) 386 VOLUME 12 NUMBER 1 SPRING 2005 D. Krizanc, P. Morin and M. Smid Range Mode and Range Median Queries on Lists and Trees 1 W. Fokkink, J.-H. Hoepman and J. Pang A Note on K-State Self-stabilization in a Ring with K=N 18 A. Elmasry Deterministic Jumplists 27 V. MÃ¤kinen and G. Navarro Succinct Suffix Arrays based on Run-Length Encoding 40 VOLUME 12 NUMBER 2 SUMMER 2005 SELECTED PAPERS OF THE SIXTEENTH NORDIC WORKSHOP ON PROGRAMMING THEORY (NWPT'04), OCTOBER 6-8, 2004: P. Pettersson and W. Yi Guest Editors' Foreword 67 J. Ernits Memory Arbiter Synthesis and Verification for a Radar Memory Interface Card 68 L. Kristiansen and P. J. Voda Programming Languages Capturing Complexity Classes 89 M. Kyas, F. S. de Boer and W.-P. de Roever A Compositional Trace Logic for Behavioural Interface Specifications 116 H. Nestra Transfinite Corecursion 133 R. K. Runde, Ã˜. Haugen and K. StÃ¸len Refining UML Interactions with Underspecification and Nondeterminism 157 T. L. Veldhuizen Language Embeddings that Preserve Staging and Safety 189 VOLUME 12 NUMBER 3 FALL 2005 SELECTED PAPERS OF THE SECOND INTERNATIONAL WORKSHOP ON MODEL-BASED METHODOLOGIES FOR PERVASIVE AND EMBEDDED SOFTWARE (MOMPES'05), JUNE 6, 2005, RENNES, FRANCE: J. Lilius, R. J. Machado, D. Truscan, J. M. Fernandes and I. Porres Guest Editors' Foreword 199 I. Al-Azzoni, D. G. Down and R. Khedri Modeling and Verification of Cryptographic Protocols Using Coloured Petri Nets and Design/CPN 201 J. P. Barros and J. B. JÃ¸rgensen A Case Study on Coloured Petri Nets in Object-Oriented Analysis and Design 229 J. Billington, G. E. Gallasch and L. Petrucci Fast Verification of the Class of Stop-and-Wait Protocols Modelled by Coloured Petri Nets 251 GENERAL PAPERS: E. Petrank and D. Rawitz The Hardness of Cache Conscious Data Placement 275 E. Prieto and C. Sloper Reducing to Independent Set Structure -- the Case of k-Internal Spanning Tree 308 VOLUME 12 NUMBER 4 WINTER 2005 SELECTED PAPERS OF THE THIRD NORDIC WORKSHOP ON UML AND SOFTWARE MODELING (NWUML'2005), AUGUST 29-31, 2005: K. Koskimies and L. Kuzniarz Guest Editors' Foreword 319 M. Alanen, T. Lundkvist and I. Porres Comparison of Modeling Frameworks for Software Engineering 321 L. Dobrzanski and L. Kuzniarz Practical Refactoring of Executable UML Models 343 J. Lilius, T. Lillqvist, T. Lundkvist, I. Oliver, I. Porres, K. SandstrÃ¶m, G. Sveholm and A. P. Zaka An Architecture Exploration Environment for System on Chip Design 361 S. Wenzel Automatic Detection of Incomplete Instances of Structural Patterns in UML Class Diagrams 379 Author Index Volume 12 (2005) 395 VOLUME 13 NUMBER 1-2 SUMMER 2006 SELECTED PAPERS OF THE 17TH NORDIC WORKSHOP ON PROGRAMMING THEORY (NWPT'05), OCTOBER 19--21, 2005: N. D. Jones Guest Editor's Foreword 1 M. Bortin, E. B. Johnsen and C. LÃ¼th Structured Formal Development in Isabelle 2 I. BrÃ¼ckner, B. Metzler and H. Wehrheim Optimizing Slicing of Formal Specifications by Deductive Verification 22 T. Crolard, S. Lacas and P. Valarcher On the Expressive Power of the Loop Language 46 T. C. Damgaard and L. Birkedal Axiomatizing Binding Bigraphs 58 M. Nesi and G. Nocera Deriving the Type Flaw Attacks in the Otway-Rees Protocol by Rewriting 78 C. R. Nielsen and H. R. Nielson Static Analysis for Blinding 98 K. StÃ¸vring Higher-Order Beta Matching with Solutions in Long Beta-Eta Normal Form 117 L. Tsiopoulos and M. WaldÃ©n Formal Development of NoC Systems in B 127 VOLUME 13 NUMBER 3 FALL 2006 SELECTED PAPERS OF THE FOURTH NORDIC WORKSHOP ON UML AND SOFTWARE MODELLING (NWUML'06), JUNE 12--14, 2006: A. Prinz and M. S. Tveit Guest Editors' Foreword 147 P. Byckling, P. Gerdt, L. Kuzniarz and J. Sajaniemi Increasing Comprehensibility of Object Models: Making the Roles of Attributes Explicit in UML Diagrams 149 J. Koskinen, A. Ruokonen and T. SystÃ¤ A Pattern-Based Approach to Generate Code from API Usage Scenarios 162 M. Siikarla, J. Peltonen and J. Koskinen Towards Unambiguous Model Fragments 180 A. L. Santos, K. Koskimies and A. Lopes A Model-Driven Approach to Variability Management in Product-Line Engineering 196 VOLUME 13 NUMBER 4 WINTER 2006 A. H. Gebremedhin, M. EssaÃ¯di, I. GuÃ©rin Lassous, J. Gustedt and J. A. Telle PRO: A Model for the Design and Analysis of Efficient and Scalable Parallel Algorithms 215 A. Berlea Online Evaluation of Regular Tree Queries 240 R. K. Poddar and P. Bhaduri Verification of Giotto based Embedded Control Systems 266 P. Gupta Range-Aggregate Query Problems Involving Geometric Aggregation Operations 294 K. Subramani and J. Argentieri Chain Programming over Difference Constraints 309 D. Lemire Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element 328 NOTE: M. Schellekens, R. Agarwal, E. Popovici and K. L. Man A Simplified Derivation of Timing Complexity Lower Bounds for Sorting by Comparisons 340 Author Index Volume 13 (2006) 347 VOLUME 14 NUMBER 1-2 SUMMER 2007 Parosh Aziz Abdulla, Johann Deneux, Pritha Mahata, Aletta NylÃ©n Using Forward Reachability Analysis for Verification of Timed Petri Nets 1 Vitus S.W. Lam A Formalism for Reasoning about UML Activity Diagrams 43 Ka Lok Man Formal Specification and Analysis of Hardware Systems in Timed Chi 65 Pinar Heggernes, Dieter Kratsch Linear-Time Certifying Recognition Algorithms and Forbidden Induced Subgraphs 87 Anat Bremler-Barr, Leah Epstein Path Layout on Tree Networks: Bounds in Different Label Switching Models 109 Meena Mahajan, Raghavan Rama, S. Vijayakumar Block Sorting: A Characterization and Some Heuristics 126 VOLUME 14 NUMBER 3 FALL 2008 Mark Cieliebak, Stephan Eidenbenz, Aris T. Pagourtzis, Konrad Schlude On the Complexity of Variations of Equal Sum Subsets 151 Qiwen Xu, Naijun Zhan Formalising Scheduling Theories in Duration Calculus 173 Evangelos Kranakis, Danny Krizanc and Sunil Shende Tracking Mobile Users in Cellular Networks Using Timing Information 202 Y. Boichut, P.-C. HÃ©am and O. Kouchnarenko Approximation-Based Tree Regular Model-Checking 216 VOLUME 14 NUMBER 3 FALL 2008 E. Hvannberg Guest Editor's Foreword 243 C. Carrez, L. Johansen, P. CieÅ›lak and S. HÃ¤nsgen Service Engineering with the SIMS Design and Validation Tools 245 S. Lahtinen and K. Koskimies A Model-Based Approach to Reflective Command Interfaces 264 K. Lind and R. Heidal Estimation of Real-Time Software Component Size 282 P. Mohagheghi, V. Dehlen and T. Neple A Metamodel and Supporting Process and Tool for Specifying Quality Models in Model-Based Software Development 301 M. Raatikainen, Varvana MyllÃ¤rniemi and Tomi MÃ¤nnistÃ¶. Featback: Method for Enhancing Management of Agile Development 321 O. RÃ¤ihÃ¤, K. Koskimies, E. MÃ¤kinen and T. SystÃ¤ Pattern-Based Genetic Model Refinements in MDA 338 Author Index Volume 13 (2006) 356 VOLUME 15 NUMBER 1 SPRING 2013 SELECTED PAPERS OF THE ELEVENTH SYMPOSIUM ON PROGRAMMING LANGUAGES AND SOFTWARE TOOLS (SPLST'09) AND THE SEVENTH NORDIC WORKSHOP ON MODEL DRIVEN SOFTWARE ENGINEERING (NW-MODE'09), AUGUST 26--28, 2009: J. Peltonen Guest Editor's Foreword 1 M. Harsu, T. Bakota, I. Siket, K. Koskimies and T. SystÃ¤ Code Clones: Good, Bad. or Ugly? 3 Z. Herczeg, G. LÃ³ki, T. Szirbucz and Ã Kiss Validating JavaScript Guidelines across Multiple Web Browsers 18 M. Sakkinen, P. Lahire and C.-B. ChirilÄƒ Towards Fully-Fledged Reverse Inheritance in Eiffel 32 M. Tiusanen and A. Valmari Good to Know about the Efficiency of State Space Methods 53 VOLUME 15 NUMBER 2 SUMMER 2015 M.R. Mousavi, T. Basten, M.A. Reniers and M. Chaudron Timed-Gamma and its Coordination Language 75 C. Knieke and M. Huhn Semantic Foundation and Validation of Live Activity Diagrams 112 G.B. Purdy and J.W. Smith On Finding Ordinary or Monochromatic Intersection Points 141 N. Shankar, K. Subramani and P. Eirinakis Identifying Negative Cost Cycles in Strongly Polynomial Space 154