Last update: Thu Apr 25 10:09:54 MDT 2024
Volume 1, Number 1, Spring, 1994Kathleen 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