BRICS Research Series, 2005

March 6, 2006

This document is also available as PostScript and DVI.

References

[RS-05-38] Abstract, PostScript, PDF, DVI.

Małgorzata Biernacka and Olivier Danvy. A Syntactic Correspondence between Context-Sensitive Calculi and Abstract Machines. December 2005. iii+39 pp. Revised version of BRICS RS-05-22.

[RS-05-37] Abstract, PostScript, PDF, DVI.

Gerth Stølting Brodal, Kanela Kaligosi, Irit Katriel, and Martin Kutz. Faster Algorithms for Computing Longest Common Increasing Subsequences. December 2005. 16 pp.

[RS-05-36] Abstract, PostScript, PDF, DVI.

Dariusz Biernacki, Olivier Danvy, and Chung-chieh Shan. On the Static and Dynamic Extents of Delimited Continuations. December 2005. ii+33 pp. To appear in the journal Science of Computer Programming. Supersedes BRICS RS-05-13.

[RS-05-35] Abstract, PostScript, PDF, DVI.

Kristian Støvring. Extending the Extensional Lambda Calculus with Surjective Pairing is Conservative. November 2005. 19 pp. To appear in Logical Methods in Computer Science.

[RS-05-34] Abstract, PostScript, PDF, DVI.

Henning Korsholm Rohde. Formal Aspects of Polyvariant Specialization. November 2005. 27 pp.

[RS-05-33] Abstract, PostScript, PDF, DVI.

Luca Aceto, Willem Jan Fokkink, Anna Ingólfsdóttir, and Sumit Nain. Bisimilarity is not Finitely Based over BPA with Interrupt. October 2005. 33 pp. This paper supersedes BRICS Report RS-04-24. An extended abstract of this paper appeared in Algebra and Coalgebra in Computer Science, 1st Conference, CALCO 2005, Swansea, Wales, 3–6 September 2005, Lecture Notes in Computer Science 3629, pp. 54–68, Springer-Verlag, 2005.

[RS-05-32] Abstract, PostScript, PDF.

Anders Møller, Mads Østerby Olesen, and Michael I. Schwartzbach. Static Validation of XSL Transformations. October 2005. 50 pp.

[RS-05-31] Abstract, PostScript, PDF. Christian Kirkegaard and Anders Møller. Type Checking with XML Schema in Xact. September 2005. 20 pp.

[RS-05-30] Abstract, PostScript, PDF. Karl Krukow. An Operational Semantics for Trust Policies. September 2005. 38 pp.

[RS-05-29] Abstract, PostScript, PDF, DVI. Olivier Danvy and Henning Korsholm Rohde. On Obtaining the Boyer-Moore String-Matching Algorithm by Partial Evaluation. September 2005. ii+9 pp. To appear in Information Processing Letters. This version supersedes BRICS RS-05-14.

[RS-05-28] Abstract, PostScript, PDF, DVI. Jiří Srba. On Counting the Number of Consistent Genotype Assignments for Pedigrees. September 2005. 15 pp. To appear in FSTTCS ’05.

[RS-05-27] Abstract, PostScript, PDF, DVI. Pascal Zimmer. A Calculus for Context-Awareness. August 2005. 21 pp.

[RS-05-26] Abstract, PostScript, PDF. Henning Korsholm Rohde. Measuring the Propagation of Information in Partial Evaluation. August 2005. 39 pp.

[RS-05-25] Abstract, PostScript, PDF, DVI. Dariusz Biernacki and Olivier Danvy. A Simple Proof of a Folklore Theorem about Delimited Control. August 2005. ii+11 pp. To appear in Journal of Functional Programming. This version supersedes BRICS RS-05-10.

[RS-05-24] Abstract, PostScript, PDF, DVI. Małgorzata Biernacka, Dariusz Biernacki, and Olivier Danvy. An Operational Foundation for Delimited Continuations in the CPS Hierarchy. August 2005. iv+43 pp. To appear in the journal Logical Methods in Computer Science. This version supersedes BRICS RS-05-11.

[RS-05-23] Abstract, PostScript, PDF, DVI. Karl Krukow, Mogens Nielsen, and Vladimiro Sassone. A Framework for Concrete Reputation-Systems. July 2005. 48 pp. This is an extended version of a paper to be presented at ACM CCS’05.

[RS-05-22] Abstract, PostScript, PDF, DVI. Małgorzata Biernacka and Olivier Danvy. A Syntactic Correspondence between Context-Sensitive Calculi and Abstract Machines. July 2005. iv+39 pp.

[RS-05-21] Abstract, PostScript, PDF, DVI. Philipp Gerhardy and Ulrich Kohlenbach. General Logical Metatheorems for Functional Analysis. July 2005. 65 pp.

[RS-05-20] Abstract, PostScript, PDF, DVI. Ivan B. Damgård, Serge Fehr, Louis Salvail, and Christian Schaffner. Cryptography in the Bounded Quantum Storage Model. July 2005. 23 pp.

[RS-05-19] Abstract, PostScript, PDF. Luca Aceto, Willem Jan Fokkink, Anna Ingólfsdóttir, and Bas Luttik. Finite Equational Bases in Process Algebra: Results and Open Questions. June 2005. 28 pp.

[RS-05-18] Abstract, PostScript, PDF, DVI. Peter Bogetoft, Ivan B. Damgård, Thomas Jakobsen, Kurt Nielsen, Jakob Pagter, and Tomas Toft. Secure Computing, Economy, and Trust: A Generic Solution for Secure Auctions with Real-World Applications. June 2005. 37 pp.

[RS-05-17] Abstract, PostScript, PDF, DVI. Ivan B. Damgård, Thomas B. Pedersen, and Louis Salvail. A Quantum Cipher with Near Optimal Key-Recycling. May 2005. 29 pp.

[RS-05-16] Abstract, PostScript, PDF, DVI. Dariusz Biernacki, Olivier Danvy, and Kevin Millikin. A Dynamic Continuation-Passing Style for Dynamic Delimited Continuations. May 2005. ii+24 pp.

[RS-05-15] Abstract, PostScript, PDF, DVI. Małgorzata Biernacka and Olivier Danvy. A Concrete Framework for Environment Machines. May 2005. ii+25 pp.

[RS-05-14] Abstract, PostScript, PDF, DVI. Olivier Danvy and Henning Korsholm Rohde. On Obtaining the Boyer-Moore String-Matching Algorithm by Partial Evaluation. April 2005. ii+8 pp. Superseded by BRICS RS-05-29.

[RS-05-13] Abstract, PostScript, PDF, DVI. Dariusz Biernacki, Olivier Danvy, and Chung-chieh Shan. On the Dynamic Extent of Delimited Continuations. April 2005. ii+32 pp. Extended version of an article to appear in Information Processing Letters. Subsumes BRICS RS-05-2.

[RS-05-12] Abstract, PostScript, PDF, DVI. Małgorzata Biernacka, Olivier Danvy, and Kristian Støvring. Program Extraction from Proofs of Weak Head Normalization. April 2005. 19 pp. Extended version of an article to appear in the preliminary proceedings of MFPS XXI, Birmingham, UK, May 2005.

[RS-05-11] Abstract, PostScript, PDF, DVI. Małgorzata Biernacka, Dariusz Biernacki, and Olivier Danvy. An Operational Foundation for Delimited Continuations in the CPS Hierarchy. March 2005. iii+42 pp. A preliminary version appeared in Thielecke, editor, 4th ACM SIGPLAN Workshop on Continuations, CW ’04 Proceedings, Association for Computing Machinery (ACM) SIGPLAN Technical Reports CSR-04-1, 2004, pages 25–33. This version supersedes BRICS RS-04-29, but is superseded by BRICS RS-05-24.

[RS-05-10] Abstract, PostScript, PDF, DVI. Dariusz Biernacki and Olivier Danvy. A Simple Proof of a Folklore Theorem about Delimited Control. March 2005. ii+11 pp. Superseded by BRICS RS-05-25.

[RS-05-9] Abstract, PostScript, PDF, DVI. Gudmund Skovbjerg Frandsen and Peter Bro Miltersen. Reviewing Bounds on the Circuit Size of the Hardest Functions. March 2005. 6 pp. To appear in Information Processing Letters.

[RS-05-8] Abstract, PostScript, PDF, DVI. Peter D. Mosses. Exploiting Labels in Structural Operational Semantics. February 2005. 15 pp. Appears in Fundamenta Informaticae, 60:17–31, 2004.

[RS-05-7] Abstract, PostScript, PDF, DVI. Peter D. Mosses. Modular Structural Operational Semantics. February 2005. 46 pp. Appears in Journal of Logic and Algebraic Programming, 60–61:195–228, 2004.

[RS-05-6] Abstract, PostScript, PDF. Karl Krukow and Andrew Twigg. Distributed Approximation of Fixed-Points in Trust Structures. February 2005. 41 pp.

[RS-05-5] Abstract, PostScript, PDF, DVI. Dariusz Biernacki, Olivier Danvy, and Kevin Millikin. A Dynamic Continuation-Passing Style for Dynamic Delimited Continuations (Preliminary Version). February 2005. ii+16 pp. Superseded by BRICS RS-05-16.

[RS-05-4] Abstract, PostScript, PDF, DVI. Andrzej Filinski and Henning Korsholm Rohde. Denotational Aspects of Untyped Normalization by Evaluation. February 2005. 51 pp. Extended version of an article to appear in the FOSSACS 2004 special issue of RAIRO, Theoretical Informatics and Applications.

[RS-05-3] Abstract, PostScript, PDF, DVI. Olivier Danvy and Mayer Goldberg. There and Back Again. January 2005. iii+16 pp. Extended version of an article to appear in Fundamenta Informaticae. This version supersedes BRICS RS-02-12.

[RS-05-2] Abstract, PostScript, PDF, DVI. Dariusz Biernacki and Olivier Danvy. On the Dynamic Extent of Delimited Continuations. January 2005. ii+30 pp.

[RS-05-1] Abstract, PostScript, PDF, DVI. Mayer Goldberg. On the Recursive Enumerability of Fixed-Point Combinators. January 2005. 7 pp. Superseedes BRICS report RS-04-25.