BRICS Research Series, 2003

March 26, 2004

This document is also available as PostScript and DVI.

References

[RS-03-53] Abstract, PostScript, PDF, DVI.

Kyung-Goo Doh and Peter D. Mosses. Composing Programming Languages by Combining Action-Semantics Modules. December 2003. 39 pp. Appears in Science of Computer Programming, 47(1):2– 36, 2003.

[RS-03-52] Abstract, PostScript, PDF, DVI.

Peter D. Mosses. Pragmatics of Modular SOS. December 2003. 22 pp. Invited paper, published in Kirchner and Ringeissen, editors, Algebraic Methodology and Software Technology: 9th International Conference, AMAST ’02 Proceedings, LNCS 2422, 2002, pages 21– 40.

[RS-03-51] Abstract, PostScript, PDF, DVI.

Ulrich Kohlenbach and Branimir Lambov. Bounds on Iterations of Asymptotically Quasi-Nonexpansive Mappings. December 2003. 24 pp.

[RS-03-50] Abstract, PostScript, PDF, DVI.

Branimir Lambov. A Two-Layer Approach to the Computability and Complexity of Real Numbers. December 2003. 16 pp.

[RS-03-49] Abstract, PostScript, PDF.

Marius Mikucionis, Kim G. Larsen, and Brian Nielsen. Online Onthe-Fly Testing of Real-time Systems. December 2003. 14 pp.

[RS-03-48] Abstract, PostScript, PDF.

Kim G. Larsen, Ulrik Larsen, Brian Nielsen, Arne Skou, and Andrzej Wasowski. Danfoss EKC Trial Project Deliverables. December 2003. 53 pp.

[RS-03-47] Abstract, PostScript, PDF, DVI.

Hans Httel and Jiř Srba. Recursive Ping-Pong Protocols. December 2003. 21 pp. To appear in the proceedings of 2004 IFIP WG 1.7, ACM SIGPLAN and GI FoMSESS Workshop on Issues in the Theory of Security (WITS’04).

[RS-03-46] Abstract, PostScript, PDF, DVI. Philipp Gerhardy. The Role of Quantifier Alternations in Cut Elimination. December 2003. 10 pp. Extends paper appearing in Baaz and Makowsky, editors, European Association for Computer Science Logic: 17th International Workshop, CSL ’03 Proceedings, LNCS 2803, 2003, pages 212-225.

[RS-03-45] Abstract, PostScript, PDF, DVI. Peter Bro Miltersen, Jaikumar Radhakrishnan, and Ingo Wegener. On converting CNF to DNF. December 2003. 11 pp. A preliminary version appeared in Rovan and Vojts, editors, Mathematical Foundations of Computer Science: 28th International Symposium, MFCS ’03 Proceedings, LNCS 2747, 2003, pages 612–621.

[RS-03-44] Abstract, PostScript, PDF, DVI. Anna Gl and Peter Bro Miltersen. The Cell Probe Complexity of Succinct Data Structures. December 2003. 17 pp. Appears in Lingas and Nilsson, editors, Fundamentals of Computation Theory: 14th International Conference, FCT ’03 Proceedings, LNCS 2751, 2003, pages 442–453. An early version of this paper appeared in Baeten, Lenstra, Parrow and Woeginger, editors, 30th International Colloquium on Automata, Languages, and Programming, ICALP ’03 Proceedings, LNCS 2719, 2003, pages 332–344.

[RS-03-43] Abstract, PostScript, PDF, DVI. Mikkel Nygaard and Glynn Winskel. Domain Theory for Concurrency. December 2003. 45 pp. To appear in a Theoretical Computer Science special issue on Domain Theory.

[RS-03-42] Abstract, PostScript, PDF, DVI. Mikkel Nygaard and Glynn Winskel. Full Abstraction for HOPLA. December 2003. 25 pp. Appears in Amadio and Lugiez, editors, Concurrency Theory: 14th International Conference, CONCUR ’03 Proceedings, LNCS 2761, 2003, pages 383–398.

[RS-03-41] Abstract, PostScript, PDF, DVI. Malgorzata Biernacka, Dariusz Biernacki, and Olivier Danvy. An Operational Foundation for Delimited Continuations. December 2003. 21 pp.

[RS-03-40] Abstract, PostScript, PDF, DVI. Andrzej Filinski and Henning Korsholm Rohde. A Denotational Account of Untyped Normalization by Evaluation. December 2003. 29 pp.

[RS-03-39] Abstract, PostScript, PDF. Jrg Abendroth. Applying π-Calculus to Practice: An Example of a Unified Security Mechanism. November 2003. 35 pp.

[RS-03-38] Abstract, PostScript, PDF. Henning Bttger, Anders Mller, and Michael I. Schwartzbach. Contracts for Cooperation between Web Service Programmers and HTML Designers. November 2003. 23 pp.

[RS-03-37] Abstract, PostScript, PDF. Claude Crpeau, Paul Dumais, Dominic Mayers, and Louis Salvail. Computational Collapse of Quantum State with Application to Oblivious Transfer. November 2003. 30 pp.

[RS-03-36] Abstract, PostScript, PDF. Ivan B. Damgrd, Serge Fehr, Kirill Morozov, and Louis Salvail. Unfair Noisy Channels and Oblivious Transfer. November 2003. 26 pp. Appears in Naor, editor, The first Theory of Cryptography Conference, TCC ’04 Proceedings, LNCS 2951, 2004, pages 355–373.

[RS-03-35] Abstract, PostScript, PDF, DVI. Mads Sig Ager, Olivier Danvy, and Jan Midtgaard. A Functional Correspondence between Monadic Evaluators and Abstract Machines for Languages with Computational Effects. November 2003. 31 pp.

[RS-03-34] Abstract, PostScript, PDF, DVI. Luca Aceto, Willem Jan Fokkink, Anna Inglfsdttir, and Bas Luttik. CCS with Hennessy’s Merge has no Finite Equational Axiomatization. November 2003. 37 pp.

[RS-03-33] Abstract, PostScript, PDF, DVI. Olivier Danvy. A Rational Deconstruction of Landin’s SECD Machine. October 2003. 32 pp. This report supersedes the earlier BRICS report RS-02-53.

[RS-03-32] Abstract, PostScript, PDF, DVI. Philipp Gerhardy and Ulrich Kohlenbach. Extracting Herbrand Disjunctions by Functional Interpretation. October 2003. 17 pp.

[RS-03-31] Abstract, PostScript, PDF, DVI. Stephen Lack and Paweł Sobociński. Adhesive Categories. October 2003. 25 pp.

[RS-03-30] Abstract, PostScript, PDF. Jesper Makholm Byskov, Bolette Ammitzbll Madsen, and Bjarke Skjernaa. New Algorithms for Exact Satisfiability. October 2003. 31 pp.

[RS-03-29] Abstract, PostScript, PDF. Aske Simon Christensen, Christian Kirkegaard, and Anders Mller. A Runtime System for XML Transformations in Java. October 2003. 15 pp.

[RS-03-28] Abstract, PostScript, PDF, DVI. Zoltn sik and Kim G. Larsen. Regular Languages Definable by Lindstrm Quantifiers. August 2003. 82 pp. This report supersedes the earlier BRICS report RS-02-20.

[RS-03-27] Abstract, PostScript, PDF, DVI. Luca Aceto, Willem Jan Fokkink, Rob J. van Glabbeek, and Anna Inglfsdttir. Nested Semantics over Finite Trees are Equationally Hard. August 2003. 31 pp.

[RS-03-26] Abstract, PostScript, PDF, DVI. Olivier Danvy and Ulrik P. Schultz. Lambda-Lifting in Quadratic Time. August 2003. 23 pp. Extended version of a paper appearing in Hu and Rodrguez-Artalejo, editors, Sixth International Symposium on Functional and Logic Programming, FLOPS ’02 Proceedings, LNCS 2441, 2002, pages 134–151. This report supersedes the earlier BRICS report RS-02-30.

[RS-03-25] Abstract.

Biernacki Dariusz and Danvy Olivier. From Interpreter to Logic Engine by Defunctionalization. June 2003. 13 pp. Presented at the International Symposium on Logic Based Program Development and Transformation, LOPSTR 2003, Uppsala, Sweden, August 25–27, 2003. This report is superseded by the later report BRICS RS-04-5.

[RS-03-24] Abstract, PostScript, PDF, DVI. Mads Sig Ager, Olivier Danvy, and Jan Midtgaard. A Functional Correspondence between Call-by-Need Evaluators and Lazy Abstract Machines. June 2003. 13 pp.

[RS-03-23] Abstract, PostScript, PDF, DVI. Margarita Korovina. Recent Advances in Σ-definability over Continuous Data Types. June 2003. 24 pp.

[RS-03-22] Abstract, PostScript, PDF, DVI. Ivan B. Damgrd and Mads J. Jurik. Scalable Key-Escrow. May 2003. 15 pp.

[RS-03-21] Abstract, PostScript, PDF, DVI. Ulrich Kohlenbach. Some Logical Metatheorems with Applications in Functional Analysis. May 2003. 55 pp. Slighly revised and extended version to appear in Transactions of the American Mathematical Society.

[RS-03-20] Abstract, PostScript, PDF. Mads Sig Ager, Olivier Danvy, and Henning Korsholm Rohde. Fast Partial Evaluation of Pattern Matching in Strings. May 2003. 16 pp. Final version in Leuschel, editor, ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, PEPM ’03 Proceedings, 2003, pages 3–9. This report supersedes the earlier BRICS report RS-03-11.

[RS-03-19] Abstract, PostScript, PDF. Christian Kirkegaard, Anders Mller, and Michael I. Schwartzbach. Static Analysis of XML Transformations in Java. May 2003. 29 pp.

[RS-03-18] Abstract, PostScript, PDF, DVI. Bartek Klin and Paweł Sobociński. Syntactic Formats for Free: An Abstract Approach to Process Equivalence. April 2003. 41 pp. Appears in Amadio and Lugiez, editors, Concurrency Theory: 14th International Conference, CONCUR ’03 Proceedings, LNCS 2761, 2003, pages 72–86.

[RS-03-17] Abstract, PostScript, PDF.

Luca Aceto, Jens Alsted Hansen, Anna Inglfsdttir, Jacob Johnsen, and John Knudsen. The Complexity of Checking Consistency of Pedigree Information and Related Problems. March 2003. 31 pp. This paper supersedes BRICS Report RS-02-42.

[RS-03-16] Abstract, PostScript, PDF, DVI.

Ivan B. Damgrd and Mads J. Jurik. A Length-Flexible Threshold Cryptosystem with Applications. March 2003. 31 pp.

[RS-03-15] Abstract, PostScript, PDF, DVI.

Anna Inglfsdttir. A Semantic Theory for Value–Passing Processes Based on the Late Approach. March 2003. 48 pp.

[RS-03-14] Abstract, PostScript, PDF, DVI.

Mads Sig Ager, Dariusz Biernacki, Olivier Danvy, and Jan Midtgaard. From Interpreter to Compiler and Virtual Machine: A Functional Derivation. March 2003. 36 pp.

[RS-03-13] Abstract, PostScript, PDF, DVI.

Mads Sig Ager, Dariusz Biernacki, Olivier Danvy, and Jan Midtgaard. A Functional Correspondence between Evaluators and Abstract Machines. March 2003. 28 pp.

[RS-03-12] Abstract, PostScript, PDF, DVI.

Mircea-Dan Hernest and Ulrich Kohlenbach. A Complexity Analysis of Functional Interpretations. February 2003. 70 pp.

[RS-03-11] Mads Sig Ager, Olivier Danvy, and Henning Korsholm Rohde. Fast Partial Evaluation of Pattern Matching in Strings. February 2003. 14 pp. This report is superseded by the later report BRICS RS-03-20.

[RS-03-10] Abstract, PostScript, PDF.

Federico Crazzolara and Giuseppe Milicia. Wireless Authentication in χ-Spaces. February 2003. 20 pp.

[RS-03-9] Abstract, PostScript, PDF.

Ivan B. Damgrd and Gudmund Skovbjerg Frandsen. An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates. February 2003. 53 pp. Appears in Lingas and Nilsson, editors, Fundamentals of Computation Theory: 14th International Conference, FCT ’03 Proceedings, LNCS 2751, 2003, pages 118–131.

[RS-03-8] Abstract, PostScript, PDF, DVI.

Ivan B. Damgrd and Gudmund Skovbjerg Frandsen. Efficient Algorithms for gcd and Cubic Residuosity in the Ring of Eisenstein Integers. February 2003. 11 pp. Appears in Lingas and Nilsson, editors, Fundamentals of Computation Theory: 14th International Conference, FCT ’03 Proceedings, LNCS 2751, 2003, pages 109–117.

[RS-03-7] Abstract, PostScript, PDF, DVI.

Claus Brabrand, Michael I. Schwartzbach, and Mads Vanggaard.

The METAFRONT System: Extensible Parsing and Transformation. February 2003. 24 pp.

[RS-03-6] Abstract, PostScript, PDF. Giuseppe Milicia and Vladimiro Sassone. Jeeg: Temporal Constraints for the Synchronization of Concurrent Objects. February 2003. 41 pp. Short version appears in Fox and Getov, editors, Joint ACM-ISCOPE Conference on Java Grande, JGI ’02 Proceedings, 2002, pages 212–221.

[RS-03-5] Abstract, PostScript, PDF. Aske Simon Christensen, Anders Mller, and Michael I. Schwartzbach. Precise Analysis of String Expressions. February 2003. 15 pp.

[RS-03-4] Abstract, PostScript, PDF, DVI. Marco Carbone, Mogens Nielsen, and Vladimiro Sassone. A Formal Model for Trust in Dynamic Networks. January 2003. 18 pp. Appears in Cerone and Lindsay, editors, 1st International Conference on Software Engineering and Formal Methods, SEFM ’03 Proceedings, 2003, pages 54–61.

[RS-03-3] Abstract, PostScript, PDF. Claude Crpeau, Paul Dumais, Dominic Mayers, and Louis Salvail. On the Computational Collapse of Quantum Information. January 2003. 31 pp.

[RS-03-2] Abstract, PostScript, PDF, DVI. Olivier Danvy and Pablo E. Martnez Lpez. Tagging, Encoding, and Jones Optimality. January 2003. Appears in Degano, editor, Programming Languages and Systems: Twelfth European Symposium on Programming, ESOP ’03 Proceedings, LNCS 2618, 2003, pages 335–347.

[RS-03-1] Abstract, PostScript, PDF, DVI. Vladimiro Sassone and Paweł Sobocinski. Deriving Bisimulation Congruences: 2-Categories vs. Precategories. January 2003. 28 pp. Appears in Gordon, editor, Foundations of Software Science and Computation Structures, FoSSaCS ’03 Proceedings, LNCS 2620, 2003, pages 409–424.