BRICS Research Series, 1999

April 30, 2003

This document is also available as PostScript and DVI.

Bibliography

RS-99-57: Abstract, PostScript, PDF, DVI.
Peter D. Mosses.
A Modular SOS for ML Concurrency Primitives.
December 1999.
22 pp.
RS-99-56: Abstract, PostScript, PDF, DVI.
Peter D. Mosses.
A Modular SOS for Action Notation.
December 1999.
39 pp. Full version of paper appearing in Mosses and Watt, editors, Second International Workshop on Action Semantics, AS '99 Proceedings, BRICS Notes Series NS-99-3, 1999, pages 131-142.
RS-99-55: Abstract, PostScript, PDF, DVI.
Peter D. Mosses.
Logical Specification of Operational Semantics.
December 1999.
18 pp. Invited paper. Appears in Flum, Rodríguez-Artalejo and Mario, editors, European Association for Computer Science Logic: 13th International Workshop, CSL '99 Proceedings, LNCS 1683, 1999, pages 32-49.
RS-99-54: Abstract, PostScript, PDF, DVI.
Peter D. Mosses.
Foundations of Modular SOS.
December 1999.
17 pp. Full version of paper appearing in Kuty $\l$ owski, Pacholski and Wierzbicki, editors, Mathematical Foundations of Computer Science: 24th International Symposium, MFCS '99 Proceedings, LNCS 1672, 1999, pages 70-80.
RS-99-53: Abstract, PostScript, PDF.
Torsten K. Iversen, Kåre J. Kristoffersen, Kim G. Larsen, Morten Laursen, Rune G. Madsen, Steffen K. Mortensen, Paul Pettersson, and Chris B. Thomasen.
Model-Checking Real-Time Control Programs -- Verifying LEGO Mindstorms Systems Using UPPAAL.
December 1999.
9 pp. Appears in Toetenel, editor, 12th Euromicro Conference on Real-Time Systems, ECRTS '00 Proceedings, 2000, pages 147-155.
RS-99-52: Abstract, PostScript, PDF, DVI.
Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, and P. S. Thiagarajan.
Towards a Theory of Regular MSC Languages.
December 1999.
43 pp.
RS-99-51: Abstract, PostScript, PDF, DVI.
Olivier Danvy.
Formalizing Implementation Strategies for First-Class Continuations.
December 1999.
16 pp. Appears in Smolka, editor, Programming Languages and Systems: Ninth European Symposium on Programming, ESOP '00 Proceedings, LNCS 1782, 2000pp. 88-103.
RS-99-50: Abstract, PostScript, PDF, DVI.
Gerth Stølting Brodal and Srinivasan Venkatesh.
Improved Bounds for Dictionary Look-up with One Error.
December 1999.
5 pp. Appears in Information Processing Letters 75(1-2):57-59, 2000.
RS-99-49: Abstract, PostScript, PDF, DVI.
Alexander A. Ageev and Maxim I. Sviridenko.
An Approximation Algorithm for Hypergraph Max -Cut with Given Sizes of Parts.
December 1999.
12 pp. Appears in Paterson, editor, Eighteenth Annual European Symposiumon on Algorithms, ESA '00 Proceedings, LNCS 1879, 2000, pages 32-49.
RS-99-48: Abstract, PostScript, PDF.
Rasmus Pagh.
Faster Deterministic Dictionaries.
December 1999.
14 pp. Appears in Shmoys, editor, The Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '00 Proceedings, 2000, pages 487-493. Journal version in Journal of Algorithms, 41(1):69-85, 2001, with the title Deterministic Dictionaries.
RS-99-47: Abstract, PostScript, PDF, DVI.
Peter Bro Miltersen and Vinodchandran N. Variyam.
Derandomizing Arthur-Merlin Games using Hitting Sets.
December 1999.
21 pp. Appears in Beame, editor, 40th Annual Symposium on Foundations of Computer Science, FOCS '99 Proceedings, 1999, pages 71-80.
RS-99-46: Abstract, PostScript, PDF, DVI.
Peter Bro Miltersen, Vinodchandran N. Variyam, and Osamu Watanabe.
Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy.
December 1999.
14 pp. Appears in Asano, Imai, Lee, Nakano and Tokuyama, editors, Computing and Combinatorics: 5th Annual International Conference, COCOON '99 Proceedings, LNCS 1627, 1999, pages 210-220.
RS-99-45: Abstract, PostScript, PDF, DVI.
Torben Amtoft.
Partial Evaluation for Constraint-Based Program Analyses.
December 1999.
13 pp.
RS-99-44: Abstract, PostScript, PDF, DVI.
Uwe Nestmann, Hans Hüttel, Josva Kleist, and Massimo Merro.
Aliasing Models for Mobile Objects.
December 1999.
ii+46 pp. Appears in Information and Computation 172:1-31, 2002. An extended abstract of this revision, entitled Aliasing Models for Object Migration, appeared as Distinguished Paper in Amestoy, Berger, Daydé, Duff, Frayssé, Giraud and Daniel, editors, 5th International Euro-Par Conference, EURO-PAR '99 Proceedings, LNCS 1685, 1999, pages 1353-1368, which in turn is a revised part of another paper called Migration = Cloning ; Aliasing that appeared in Cardelli, editor, Foundations of Object-Oriented Languages: 6th International Conference, FOOL6 Informal Proceedings, 1999 and as such supersedes the corresponding part of the earlier BRICS report RS-98-33.
RS-99-43: Abstract, PostScript, PDF, DVI.
Uwe Nestmann.
What is a `Good' Encoding of Guarded Choice?
December 1999.
ii+34 pp. Appears in Information and Computation, 156:287-319, 2000. This revised report supersedes the earlier BRICS report RS-97-45.
RS-99-42: Abstract, PostScript, PDF, DVI.
Uwe Nestmann and Benjamin C. Pierce.
Decoding Choice Encodings.
December 1999.
ii+62 pp. Appears in Journal of Information and Computation, 163:1-59, 2000. An extended abstract appeared in Montanari and Sassone, editors, Concurrency Theory: 7th International Conference, CONCUR '96 Proceedings, LNCS 1119, 1996, pages 179-194.
RS-99-41: Abstract, PostScript, PDF.
Nicky O. Bodentien, Jacob Vestergaard, Jakob Friis, Kåre J. Kristoffersen, and Kim G. Larsen.
Verification of State/Event Systems by Quotienting.
December 1999.
17 pp. Presented at Nordic Workshop in Programming Theory, Uppsala, Sweden, October 6-8, 1999.
RS-99-40: Abstract, PostScript, PDF, DVI.
Bernd Grobauer and Zhe Yang.
The Second Futamura Projection for Type-Directed Partial Evaluation.
November 1999.
44 pp. Extended version of an article appearing in Lawall, editor, ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, PEPM '00 Proceedings, 2000, pages 22-32. A revised and extended version appears in Higher-Order and Symbolic Computation 14(2-3):173-219 (2001) and Also available as BRICS Report RS-00-44.
RS-99-39: Abstract, PostScript, PDF, DVI.
Romeo Rizzi.
On the Steiner Tree $\frac {3}{2}$ -Approximation for Quasi-Bipartite Graphs.
November 1999.
6 pp.
RS-99-38: Abstract, PostScript, PDF.
Romeo Rizzi.
Linear Time Recognition of -Indifferent Graphs.
November 1999.
11 pp. Appears in Discrete Mathematics, 239(1-3):161-169, 2001.
RS-99-37: Abstract, PostScript, PDF, DVI.
Tibor Jordán.
Constrained Edge-Splitting Problems.
November 1999.
23 pp. A preliminary version with the title Edge-Splitting Problems with Demands appeared in Cornujols, Burkard and Wöginger, editors, Integer Programming and Combinatorial Optimization: 7th International Conference, IPCO '99 Proceedings, LNCS 1610, 1999, pages 273-288.
RS-99-36: Abstract, PostScript, PDF, DVI.
Gian Luca Cattani and Glynn Winskel.
Presheaf Models for CCS-like Languages.
November 1999.
ii+46 pp.
RS-99-35: Abstract, PostScript, PDF, DVI.
Tibor Jordán and Zoltán Szigeti.
Detachments Preserving Local Edge-Connectivity of Graphs.
November 1999.
16 pp.
RS-99-34: Abstract, PostScript, PDF.
Flemming Friche Rodler.
Wavelet Based 3D Compression for Very Large Volume Data Supporting Fast Random Access.
October 1999.
36 pp. Extended version of paper appearing in 7th Pacific Conference on Computer Graphics and Applications, PG '99 Proceedings, 1999, pages 108-117.
RS-99-33: Abstract, PostScript, PDF, DVI.
Luca Aceto, Zoltán Ésik, and Anna Ingólfsdóttir.
The Max-Plus Algebra of the Natural Numbers has no Finite Equational Basis.
October 1999.
25 pp. A revised version of this paper appears Theoretical Computer Science 293(1):169-188, 17 January 2003.
RS-99-32: Abstract, PostScript, PDF.
Luca Aceto and François Laroussinie.
Is your Model Checker on Time? -- On the Complexity of Model Checking for Timed Modal Logics.
October 1999.
11 pp. Appears in Kuty $\l$ owski, Pacholski and Wierzbicki, editors, Mathematical Foundations of Computer Science: 24th International Symposium, MFCS '99 Proceedings, LNCS 1672, 1999, pages 125-136.
RS-99-31: Abstract, PostScript, PDF, DVI.
Ulrich Kohlenbach.
Foundational and Mathematical Uses of Higher Types.
September 1999.
34 pp. A revised version appears in W. Sieg et al. (eds.), Reflections on the Foundations of Mathematics. Essays in Honor of Solomon Feferman, Lecture Notes in Logic 15, A. K. Peters, Ltd., pp. 92-116, 2002.
RS-99-30: Abstract, PostScript, PDF, DVI.
Luca Aceto, Willem Jan Fokkink, and Chris Verhoef.
Structural Operational Semantics.
September 1999.
128 pp. Appears in Bergstra, Ponse and Smolka, editors, Handbook of Process Algebra, 2001, pages 197-292.
RS-99-29: Abstract, PostScript, PDF, DVI.
Søren Riis.
A Complexity Gap for Tree-Resolution.
September 1999.
33 pp.
RS-99-28: Abstract, PostScript, PDF, DVI.
Thomas Troels Hildebrandt.
A Fully Abstract Presheaf Semantics of SCCS with Finite Delay.
September 1999.
37 pp. Appears in Hofmann, Rosolini and Pavlovic, editors, Category Theory and Computer Science: 8th International Conference, CTCS '99 Proceedings, ENTCS 29, 1999, 25 pp.
RS-99-27: Abstract, PostScript, PDF, DVI.
Olivier Danvy and Ulrik P. Schultz.
Lambda-Dropping: Transforming Recursive Equations into Programs with Block Structure.
September 1999.
57 pp. Appears in Theoretical Computer Science, 248(1-2):243-287, November 2000. This revised report supersedes the earlier BRICS report RS-98-54.
RS-99-26: Abstract, PostScript, PDF, DVI.
Jesper G. Henriksen.
An Expressive Extension of TLC.
September 1999.
20 pp. Appears in International Journal of Foundations of Computer Science, 13(3):341-360, 2002. Conference version in Thiagarajan and Yap, editors, Fifth Asian Computing Science Conference, ASIAN '99 Proceedings, LNCS 1742, 1999, pages 126-138.
RS-99-25: Abstract, PostScript, PDF, DVI.
Gerth Stølting Brodal and Christian N. S. Pedersen.
Finding Maximal Quasiperiodicities in Strings.
September 1999.
20 pp. Appears in Giancarlo and Sankoff, editors, Combinatorial Pattern Matching: 11th Annual Symposium, CPM '00 Proceedings, LNCS 1848, 2000, pages 397-411.
RS-99-24: Abstract, PostScript, PDF, DVI.
Luca Aceto, Willem Jan Fokkink, and Chris Verhoef.
Conservative Extension in Structural Operational Semantics.
September 1999.
23 pp. Appears in the Bulletin of the European Association for Theoretical Computer Science, 70:110-132, 1999.
RS-99-23: Abstract, PostScript, PDF, DVI.
Olivier Danvy, Belmina Dzafic, and Frank Pfenning.
On proving syntactic properties of CPS programs.
August 1999.
14 pp. Appears in Gordon and Pitts, editors, 3rd Workshop on Higher Order Operational Techniques in Semantics, HOOTS '99 Proceedings, ENTCS 26, 1999, pages 19-31.
RS-99-22: Abstract, PostScript, PDF, DVI.
Luca Aceto, Zoltán Ésik, and Anna Ingólfsdóttir.
On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers.
August 1999.
22 pp. Appears in Reichel and Tison, editors, 17th Annual Symposium on Theoretical Aspects of Computer Science Proceedings, STACS '00 Proceedings, LNCS 1770, 2000, pages 267-278.
RS-99-21: Abstract, PostScript, PDF, DVI.
Olivier Danvy.
An Extensional Characterization of Lambda-Lifting and Lambda-Dropping.
August 1999.
13 pp. Extended version of an article appearing in Middeldorp and Sato, editors, Fourth Fuji International Symposium on Functional and Logic Programming, FLOPS '99 Proceedings, LNCS 1722, 1999, pages 241-250. This report supersedes the earlier BRICS report RS-98-2.
RS-99-20: Abstract, PostScript, PDF, DVI.
Ulrich Kohlenbach.
A Note on Spector's Quantifier-Free Rule of Extensionality.
August 1999.
5 pp. Appears in Archive for Mathematical Logic, 40:89-92, 2001.
RS-99-19: Abstract, PostScript, PDF, DVI.
Marcin Jurdzinski and Mogens Nielsen.
Hereditary History Preserving Bisimilarity is Undecidable.
June 1999.
18 pp. An extended abstract appears in Reichel and Tison, editors, 17th Annual Symposium on Theoretical Aspects of Computer Science Proceedings, STACS '00 Proceedings, LNCS 1770, 2000, pages 358-369.
RS-99-18: Abstract, PostScript, PDF, DVI.
M. Oliver Möller and Harald Rueß.
Solving Bit-Vector Equations of Fixed and Non-Fixed Size.
June 1999.
18 pp. Revised version of an article appearing under the title Solving Bit-Vector Equations in Gopalakrishnan and Windley, editors, Formal Methods in Computer-Aided Design: Second International Conference, FMCAD '98 Proceedings, LNCS 1522, 1998, pages 36-48.
RS-99-17: Abstract, PostScript, PDF, DVI.
Andrzej Filinski.
A Semantic Account of Type-Directed Partial Evaluation.
June 1999.
23 pp. Appears in Nadathur, editor, International Conference on Principles and Practice of Declarative Programming, PPDP '99 Proceedings, LNCS 1702, 1999, pages 378-395.
RS-99-16: Abstract, PostScript, PDF.
Rune B. Lyngsø and Christian N. S. Pedersen.
Protein Folding in the 2D HP Model.
June 1999.
15 pp. Appears in Proceedings of the 1st Journées Ouvertes: Biologie, Informatique et Mathématiques (JOBIM 2000).
RS-99-15: Abstract, PostScript, PDF.
Rune B. Lyngsø, Michael Zuker, and Christian N. S. Pedersen.
An Improved Algorithm for RNA Secondary Structure Prediction.
May 1999.
24 pp. An alloy of two articles appearing in Istrail, Pevzner and Waterman, editors, Third Annual International Conference on Computational Molecular Biology, RECOMB '99 Proceedings, 1999, pages 260-267, and Bioinformatics, 15(6):440-445, June 1999.
RS-99-14: Abstract, PostScript, PDF, DVI.
Marcelo P. Fiore, Gian Luca Cattani, and Glynn Winskel.
Weak Bisimulation and Open Maps.
May 1999.
22 pp. Appears in Longo, editor, Fourteenth Annual IEEE Symposium on Logic in Computer Science, LICS '99 Proceedings, 1999, pages 67-76.
RS-99-13: Abstract, PostScript, PDF.
Rasmus Pagh.
Hash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions.
May 1999.
11 pp. A short version appears in Dehne, Gupta, Sack and Tamassia, editors, Algorithms and Data Structures: 6th International Workshop, WADS '99 Proceedings, LNCS 1663, 1999, pages 49-54.
RS-99-12: Abstract, PostScript, PDF.
Gerth Stølting Brodal, Rune B. Lyngsø, Christian N. S. Pedersen, and Jens Stoye.
Finding Maximal Pairs with Bounded Gap.
April 1999.
31 pp. Appears in Crochemore and Paterson, editors, Combinatorial Pattern Matching: 10th Annual Symposium, CPM '99 Proceedings, LNCS 1645, 1999, pages 134-149. Journal version in Journal of Discrete Algorithms, 1:77-104, 2000.
RS-99-11: Abstract, PostScript, PDF, DVI.
Ulrich Kohlenbach.
On the Uniform Weak König's Lemma.
March 1999.
13 pp. An extended version appears in Annals of Pure and Applied Logic (special issue in honor of A. S. Troelstra, 2001) vol. 114, pp. 103-116 (2002).
RS-99-10: Abstract, PostScript, PDF, DVI.
Jon G. Riecke and Anders B. Sandholm.
A Relational Account of Call-by-Value Sequentiality.
March 1999.
51 pp. To appear in Information and Computation, LICS '97 Special Issue. Extended version of an article appearing in Twelfth Annual IEEE Symposium on Logic in Computer Science, LICS '97 Proceedings, 1997, pages 258-267. This report supersedes the earlier BRICS report RS-97-41.
RS-99-9: Abstract, PostScript, PDF.
Claus Brabrand, Anders Møller, Anders B. Sandholm, and Michael I. Schwartzbach.
A Runtime System for Interactive Web Services.
March 1999.
21 pp. Appears in endelzon, editor, Eighth International World Wide Web Conference, WWW8 Proceedings, 1999, pages 313-323 and Computer Networks, 31:1391-1401, 1999.
RS-99-8: Abstract, PostScript, PDF.
Klaus Havelund, Kim G. Larsen, and Arne Skou.
Formal Verification of a Power Controller Using the Real-Time Model Checker UPPAAL.
March 1999.
23 pp. Appears in Katoen, editor, 5th International AMAST Workshop on Real-Time and Probabilistic Systems, ARTS '99 Proceedings, LNCS 1601, 1999, pages 277-298.
RS-99-7: Abstract, PostScript, PDF, DVI.
Glynn Winskel.
Event Structures as Presheaves--Two Representation Theorems.
March 1999.
16 pp. Appears in Baeten and Mauw, editors, Concurrency Theory: 10th International Conference, CONCUR '99 Proceedings, LNCS 1664, 1999, pages 541-556.
RS-99-6: Abstract, PostScript, PDF.
Rune B. Lyngsø, Christian N. S. Pedersen, and Henrik Nielsen.
Measures on Hidden Markov Models.
February 1999.
27 pp. Appears in Lengauer, Schneider, Bork, Brutlag, Glasgow, Mewes and Zimmer, editors, Seventh International Conference on Intelligent Systems for Molecular Biology, ISMB '99 Proceedings, 1999 as Metrics and similarity measures for hidden Markov models.
RS-99-5: Abstract, PostScript, PDF, DVI.
Julian C. Bradfield and Perdita Stevens.
Observational Mu-Calculus.
February 1999.
18 pp.
RS-99-4: Abstract, PostScript, PDF.
Sibylle B. Fröschle and Thomas Troels Hildebrandt.
On Plain and Hereditary History-Preserving Bisimulation.
February 1999.
21 pp. Appears in Kuty $\l$ owski, Pacholski and Wierzbicki, editors, Mathematical Foundations of Computer Science: 24th International Symposium, MFCS '99 Proceedings, LNCS 1672, 1999, pages 354-365.
RS-99-3: Abstract, PostScript, PDF, DVI.
Peter Bro Miltersen.
Two Notes on the Computational Complexity of One-Dimensional Sandpiles.
February 1999.
8 pp.
RS-99-2: Abstract, PostScript, PDF, DVI.
Ivan B. Damgård.
An Error in the Mixed Adversary Protocol by Fitzi, Hirt and Maurer.
February 1999.
4 pp.
RS-99-1: Abstract, PostScript, PDF, DVI.
Marcin Jurdzinski and Mogens Nielsen.
Hereditary History Preserving Simulation is Undecidable.
January 1999.
15 pp.

Last modified: 2003-06-04 by webmaster.