BRICS Research Series, 2004

May 20, 2005

This document is also available as PostScript and DVI.

Bibliography

RS-04-41: Abstract, PostScript, PDF, DVI.
Olivier Danvy.
Sur un Exemple de Patrick Greussay.
December 2004.
14 pp.
RS-04-40: Abstract, PostScript, PDF.
Mads Sig Ager, Olivier Danvy, and Henning Korsholm Rohde.
Fast Partial Evaluation of Pattern Matching in Strings.
December 2004.
22 pp. To appear in TOPLAS. Supersedes BRICS report RS-03-20.
RS-04-39: Abstract, PostScript, PDF, DVI.
Olivier Danvy and Lasse R. Nielsen.
CPS Transformation of Beta-Redexes.
December 2004.
ii+11 pp. Extended version of an article appearing in Information Processing Letters, 94(5):217-224, 2005. Also superseedes BRICS report RS-00-35.
RS-04-38: Abstract, PostScript, PDF.
Olin Shivers and Mitchell Wand.
Bottom-Up $\beta$ -Substitution: Uplinks and $\lambda$ -DAGs.
December 2004.
iv+32 pp.
RS-04-37: Abstract, PostScript, PDF.
Jørgen Iversen and Peter D. Mosses.
Constructive Action Semantics for Core ML.
December 2004.
68 pp. To appear in a special Language Definitions and Tool Generation issue of the journal IEE Proceedings Software.
RS-04-36: Abstract, PostScript, PDF.
Mark van den Brand, Jørgen Iversen, and Peter D. Mosses.
An Action Environment.
December 2004.
27 pp. Appears in Hedin and Van Wyk, editors, Fourth ACM SIGPLAN Workshop on Language Descriptions, Tools and Applications, LDTA '04, 2004, pages 149-168.
RS-04-35: Abstract, PostScript, PDF, DVI.
Jørgen Iversen.
Type Checking Semantic Functions in ASDF.
December 2004.
29 pp.
RS-04-34: Abstract, PostScript, PDF, DVI.
Anders Møller and Michael I. Schwartzbach.
The Design Space of Type Checkers for XML Transformation Languages.
December 2004.
21 pp. Appears in Eiter and Libkin, editors, Database Theory: 10th International Conference, ICDT '05 Proceedings, LNCS 3363, 2005, pages 17-36.
RS-04-33: Abstract, PostScript, PDF.
Aske Simon Christensen, Christian Kirkegaard, and Anders Møller.
A Runtime System for XML Transformations in Java.
December 2004.
15 pp. Appears in Bellahsene, Milo, Rys, Suciu and Unland, editors, Database and XML Technologies: Second International XML Database Symposium, XSym '04 Proceedings, LNCS 3186, 2004, pages 143-157. Supersedes the earlier BRICS report RS-03-29.
RS-04-32: Abstract, PostScript, PDF, DVI.
Philipp Gerhardy.
A Quantitative Version of Kirk's Fixed Point Theorem for Asymptotic Contractions.
December 2004.
9 pp.
RS-04-31: Abstract, PostScript, PDF, DVI.
Philipp Gerhardy and Ulrich Kohlenbach.
Strongly Uniform Bounds from Semi-Constructive Proofs.
December 2004.
31 pp.
RS-04-30: Abstract, PostScript, PDF, DVI.
Olivier Danvy.
From Reduction-Based to Reduction-Free Normalization.
December 2004.
27 pp. Invited talk at the 4th International Workshop on Reduction Strategies in Rewriting and Programming, WRS 2004 (Aachen, Germany, June 2, 2004). To appear in ENTCS.
RS-04-29: Abstract, PostScript, PDF, DVI.
Ma $\l$ gorzata Biernacka, Dariusz Biernacki, and Olivier Danvy.
An Operational Foundation for Delimited Continuations in the CPS Hierarchy.
December 2004.
iii+45 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.
RS-04-28: 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.
December 2004.
44 pp. Extended version of an article to appear in Theoretical Computer Science.
RS-04-27: Abstract, PostScript, PDF.
Gerth Stølting Brodal, Rolf Fagerberg, and Gabriel Moruz.
On the Adaptiveness of Quicksort.
December 2004.
23 pp. To appear in Demetrescu and Tamassia, editors, Seventh Workshop on Algorithm Engineering and Experiments, ALENEX '05 Proceedings, 2005.
RS-04-26: Abstract, PostScript, PDF, DVI.
Olivier Danvy and Lasse R. Nielsen.
Refocusing in Reduction Semantics.
November 2004.
iii+44 pp. This report supersedes BRICS report RS-02-04. A preliminary version appears in the informal proceedings of the Second International Workshop on Rule-Based Programming, RULE 2001, Electronic Notes in Theoretical Computer Science, Vol. 59.4.
RS-04-25: Abstract, PostScript, PDF, DVI.
Mayer Goldberg.
On the Recursive Enumerability of Fixed-Point Combinators.
November 2004.
7 pp. Superseded by the later report BRICS RS-05-1.
RS-04-24: 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 2004.
30 pp.
RS-04-23: Abstract, PostScript, PDF, DVI.
Hans Hüttel and Jirí Srba.
Recursion vs. Replication in Simple Cryptographic Protocols.
October 2004.
26 pp. Appear in lncs3381, pages 175-184.
RS-04-22: Abstract, PostScript, PDF.
Gian Luca Cattani and Glynn Winskel.
Profunctors, Open Maps and Bisimulation.
October 2004.
64 pp. To appear in Mathematical Structures in Computer Science.
RS-04-21: Abstract, PostScript, PDF, DVI.
Glynn Winskel and Francesco Zappa Nardelli.
New-HOPLA--A Higher-Order Process Language with Name Generation.
October 2004.
38 pp. Appears in Lévy, Mayr and Mitchell, editors, 3rd IFIP International Conference on Theoretical Computer Science, TCS '04 Proceedings, 2004, pages 521-534.
RS-04-20: Abstract, PostScript, PDF, DVI.
Mads Sig Ager.
From Natural Semantics to Abstract Machines.
October 2004.
21 pp. Presented at the International Symposium on Logic-based Program Synthesis and Transformation, LOPSTR 2004, Verona, Italy, August 26-28, 2004.
RS-04-19: Abstract, PostScript, PDF.
Bolette Ammitzbøll Madsen and Peter Rossmanith.
Maximum Exact Satisfiability: NP-completeness Proofs and Exact Algorithms.
October 2004.
20 pp.
RS-04-18: Abstract, PostScript, PDF, DVI.
Bolette Ammitzbøll Madsen.
An Algorithm for Exact Satisfiability Analysed with the Number of Clauses as Parameter.
September 2004.
4 pp.
RS-04-17: Abstract, PostScript, PDF, DVI.
Mayer Goldberg.
Computing Logarithms Digit-by-Digit.
September 2004.
6 pp.
RS-04-16: Abstract, PostScript, PDF.
Karl Krukow and Andrew Twigg.
Distributed Approximation of Fixed-Points in Trust Structures.
September 2004.
25 pp.
RS-04-15: Abstract, PostScript, PDF, DVI.
Jesús Fernando Almansa.
The Full Abstraction of the UC Framework.
August 2004.
ii+24 pp.
RS-04-14: Abstract, PostScript, PDF, DVI.
Jesper Makholm Byskov.
Maker-Maker and Maker-Breaker Games are PSPACE-Complete.
August 2004.
5 pp.
RS-04-13: Abstract, PostScript, PDF, DVI.
Jens Groth and Gorm Salomonsen.
Strong Privacy Protection in Electronic Voting.
July 2004.
12 pp. Preliminary abstract presented at Tjoa and Wagner, editors, 13th International Workshop on Database and Expert Systems Applications, DEXA '02 Proceedings, 2002, page 436.
RS-04-12: Abstract, PostScript, PDF, DVI.
Olivier Danvy and Ulrik P. Schultz.
Lambda-Lifting in Quadratic Time.
June 2004.
34 pp. Appears in Journal of Functional and Logic Programming, 1:43, 2004. This report supersedes the earlier BRICS report RS-03-36 which was an extended version of a paper appearing in Hu and Rodríguez-Artalejo, editors, Sixth International Symposium on Functional and Logic Programming, FLOPS '02 Proceedings, LNCS 2441, 2002, pages 134-151.
RS-04-11: Abstract, PostScript, PDF.
Vladimiro Sassone and Pawe $\l$ Sobocinski.
Congruences for Contextual Graph-Rewriting.
June 2004.
29 pp.
RS-04-10: Abstract, PostScript, PDF, DVI.
Daniele Varacca, Hagen Völzer, and Glynn Winskel.
Probabilistic Event Structures and Domains.
June 2004.
41 pp. Extended version of an article appears in Gardner and Yoshida, editors, Concurrency Theory: 15th International Conference, CONCUR '04 Proceedings, LNCS 3170, 2004, pages 481-496.
RS-04-9: Abstract, PostScript, PDF, DVI.
Ivan B. Damgård, Serge Fehr, and Louis Salvail.
Zero-Knowledge Proofs and String Commitments Withstanding Quantum Attacks.
May 2004.
22 pp. Appears in Franklin, editor, Advances in Cryptology: 24th Annual International Cryptology Conference, CRYPTO '04 Proceedings, LNCS 3152, 2004, pages 254-272.
RS-04-8: Abstract, PostScript, PDF, DVI.
Petr Jancar and Jirí Srba.
Highly Undecidable Questions for Process Algebras.
April 2004.
25 pp. Appears in Lévy, Mayr and Mitchell, editors, 3rd IFIP International Conference on Theoretical Computer Science, TCS '04 Proceedings, 2004, pages 507-520.
RS-04-7: Abstract, PostScript, PDF, DVI.
Mojmír Kretínský, Vojtech Rehák, and Jan Strejcek.
On the Expressive Power of Extended Process Rewrite Systems.
April 2004.
18 pp.
RS-04-6: Abstract, PostScript, PDF, DVI.
Gudmund Skovbjerg Frandsen and Igor E. Shparlinski.
On Reducing a System of Equations to a Single Equation.
March 2004.
11 pp. Appears in Schicho and Singer, editors, ACM SIGSAM International Symposium on Symbolic and Algebraic Computation, ISSAC '04 Proceedings, 2004, pages 163-166.
RS-04-5: Abstract, PostScript, PDF, DVI.
Dariusz Biernacki and Olivier Danvy.
From Interpreter to Logic Engine by Defunctionalization.
March 2004.
20 pp. Appears in Bruynooghe, editor, International Symposium on Logic Based Program Development and Transformation, LOPSTR '03 Proceedings, Revised Selected Papers, LNCS 3018, 2004, pages 143-159. This report supersedes the earlier BRICS report RS-03-25.
RS-04-4: Abstract, PostScript, PDF.
Patricia Bouyer, Franck Cassez, Emmanuel Fleury, and Kim G. Larsen.
Optimal Strategies in Priced Timed Game Automata.
February 2004.
32 pp.
RS-04-3: Abstract, PostScript, PDF, DVI.
Mads Sig Ager, Olivier Danvy, and Jan Midtgaard.
A Functional Correspondence between Call-by-Need Evaluators and Lazy Abstract Machines.
February 2004.
17 pp. This report supersedes the earlier BRICS report RS-03-24. Extended version of an article appearing in Information Processing Letters, 90(5):223-232, 2004.
RS-04-2: Abstract, PostScript, PDF.
Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, and Norbert Zeh.
Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths.
February 2004.
19 pp. Appears in Hagerup and Katajainen, editors, 9th Scandinavian Workshop on Algorithm Theory, SWAT '04 Proceedings, LNCS 3111, 2004, pages 480-492.
RS-04-1: Abstract, PostScript, PDF, DVI.
Luca Aceto, Willem Jan Fokkink, Anna Ingólfsdóttir, and Bas Luttik.
Split-2 Bisimilarity has a Finite Axiomatization over CCS with Hennessy's Merge.
January 2004.
16 pp.

Last modified: 2005-05-20 by webmaster.