BRICS Research Series, 2002

March 26, 2004

This document is also available as PostScript and DVI.

References

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

Olivier Danvy. A Lambda-Revelation of the SECD Machine. December 2003. 15 pp. Superseeded by the BRICS report RS-03-33.

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

Olivier Danvy. A New One-Pass Transformation into Monadic Normal Form. December 2002. 16 pp. Appears in Hedin, editor, Compiler Construction, 12th International Conference, CC ’03 Proceedings, LNCS 2622, 2003, pages 77–89.

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

Gerth Stlting Brodal, Rolf Fagerberg, Anna stlin, Christian N. S. Pedersen, and S. Srinivasa Rao. Computing Refined Buneman Trees in Cubic Time. December 2002. 14 pp.

[RS-02-50] Abstract, PostScript, PDF.

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, and V. Vinay. Circuits on Cylinders. December 2002. 16 pp.

[RS-02-49] Abstract, PostScript, PDF, DVI.

Mikkel Nygaard and Glynn Winskel. HOPLA—A Higher-Order Process Language. December 2002. 18 pp. Appears in Brim, Jančar, Křetnský and Antonín, editors, Concurrency Theory: 13th International Conference, CONCUR ’02 Proceedings, LNCS 2421, 2002, pages 434–448.

[RS-02-48] Abstract, PostScript, PDF, DVI.

Mikkel Nygaard and Glynn Winskel. Linearity in Process Languages. December 2002. 27 pp. Appears in Plotkin, editor, Seventeenth Annual IEEE Symposium on Logic in Computer Science, Lics ’02 Proceedings, 2002, pages 433–446.

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

Zoltn sik. Extended Temporal Logic on Finite Words and Wreath Product of Monoids with Distinguished Generators. December 2002. 16 pp. To appear in 6th International Conference, Developments in Language Theory, DLT ’02 Revised Papers, LNCS, 2002.

[RS-02-46] Abstract, PostScript, PDF, DVI. Zoltn sik and Hans Lei. Greibach Normal Form in Algebraically Complete Semirings. December 2002. 43 pp. An extended abstract appears in Bradfield, editor, European Association for Computer Science Logic: 16th International Workshop, CSL ’02 Proceedings, LNCS 2471, 2002, pages 135–150.

[RS-02-45] Abstract, PostScript, PDF. Jesper Makholm Byskov. Chromatic Number in Time O(2.4023^{n}) Using Maximal Independent Sets. December 2002. 6 pp.

[RS-02-44] Abstract, PostScript, PDF. Zoltn sik and Zoltn L. Nmeth. Higher Dimensional Automata. November 2002. 32 pp. A preliminary version appears under the title Automata on Series-Parallel Biposets in Kuich, Rozenberg and Salomaa, editors, 5th International Conference, Developments in Language Theory, DLT ’01 Revised Papers, LNCS 2295, 2002, pages 217–227. This report supersedes the earlier BRICS report RS-01-24.

[RS-02-43] Abstract, PostScript, PDF. Mikkel Christiansen and Emmanuel Fleury. Using IDDs for Packet Filtering. October 2002. 25 pp.

[RS-02-42] Abstract, PostScript, PDF. Luca Aceto, Jens Alsted Hansen, Anna Inglfsdttir, Jacob Johnsen, and John Knudsen. Checking Consistency of Pedigree Information is NP-complete (Preliminary Report). October 2002. 16 pp.

[RS-02-41] Abstract, PostScript, PDF, DVI. Stephen L. Bloom and Zoltn sik. Axiomatizing Omega and Omegaop Powers of Words. October 2002. 16 pp.

[RS-02-40] Abstract, PostScript, PDF, DVI. Luca Aceto, Willem Jan Fokkink, and Anna Inglfsdttir. A Note on an Expressiveness Hierarchy for Multi-exit Iteration. September 2002. 8 pp. To appear in Information Processing Letters, Elsevier.

[RS-02-39] Abstract, PostScript, PDF. Stephen L. Bloom and Zoltn sik. Some Remarks on Regular Words. September 2002. 27 pp.

[RS-02-38] Abstract, PostScript, PDF. Daniele Varacca. The Powerdomain of Indexed Valuations. September 2002. 54 pp. Short version appears in Plotkin, editor, Seventeenth Annual IEEE Symposium on Logic in Computer Science, Lics ’02 Proceedings, 2002, pages 299–308.

[RS-02-37] Abstract, PostScript, PDF, DVI. Mads Sig Ager, Olivier Danvy, and Mayer Goldberg. A Symmetric Approach to Compilation and Decompilation. August 2002. 45 pp. Appears in Mogensen, Schmidt and Sudborough, editors, The Essence of Computation: Complexity, Analysis, Transformation, LNCS 2556, 2002, pages 296–331.

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

Daniel Damian and Olivier Danvy. CPS Transformation of Flow Information, Part II: Administrative Reductions. August 2002. 9 pp. To appear in the Journal of Functional Programming. This report supersedes the earlier BRICS report RS-01-40.

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

Patricia Bouyer. Timed Automata May Cause Some Troubles. August 2002. 44 pp.

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

Morten Rhiger. A Foundation for Embedded Languages. August 2002. 29 pp. To appear in TOPLAS, ACM Transactions on Programming Languages and Systems.

[RS-02-33] Abstract, PostScript, PDF.

Vincent Balat and Olivier Danvy. Memoization in Type-Directed Partial Evaluation. July 2002. 18 pp. Appears in Batory, Consel and Taha, editors, ACM SIGPLAN/SIGSOFT Conference on Generative Programming and Component Engineering, GPCE ’02 Proceedings, LNCS 2487, 2002, pages 78–92.

[RS-02-32] Abstract, PostScript, PDF, DVI.

Mads Sig Ager, Olivier Danvy, and Henning Korsholm Rohde. On Obtaining Knuth, Morris, and Pratt’s String Matcher by Partial Evaluation. July 2002. 43 pp. Appears in Chin, editor, ACM SIG-PLAN ASIAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, ASIA-PEPM ’02 Proceedings, 2002, pages 32–46.

[RS-02-31] Abstract, PostScript, PDF, DVI.

Ulrich Kohlenbach and Paulo B. Oliva. Proof Mining: A Systematic Way of Analysing Proofs in Mathematics. June 2002. 47 pp. To appear in Proceedings of the Steklov Institute of Mathematics.

[RS-02-30] Olivier Danvy and Ulrik P. Schultz. Lambda-Lifting in Quadratic Time. June 2002. 17 pp. Appears in Hu and Rodrguez-Artalejo, editors, Sixth International Symposium on Functional and Logic Programming, FLOPS ’02 Proceedings, LNCS 2441, 2002, pages 134– 151. Superseeded by the BRICS report RS-03-26.

[RS-02-29] Abstract, PostScript, PDF.

Christian N. S. Pedersen and Tejs Scharling. Comparative Methods for Gene Structure Prediction in Homologous Sequences. June 2002. 20 pp. Appears in Guig and Gusfield, editors, Algorithms in Bioinformatics: 2nd International Workshop, WABI ’02 Proceedings, LNCS 2452, 2002, pages 220–234.

[RS-02-28] Abstract, PostScript, PDF, DVI.

Ulrich Kohlenbach and Laurenţiu Leuştean. Mann Iterates of Directionally Nonexpansive Mappings in Hyperbolic Spaces. June 2002. 33 pp. To appear in Abstract and Applied Analysis.

[RS-02-27] Abstract, PostScript, PDF, DVI.

Anna stlin and Rasmus Pagh. Simulating Uniform Hashing in Constant Time and Optimal Space. 2002. 11 pp.

[RS-02-26] Abstract, PostScript, PDF, DVI.

Margarita Korovina. Fixed Points on Abstract Structures without the Equality Test. June 2002. 14 pp. Appears in sik and Inglfsdttir, editors, Preliminary Proceedings of the Workshop on Fixed Points in Computer Science, FICS ’02, (Copenhagen, Denmark, July 20 and 21, 2002), BRICS Notes Series NS-02-2, 2002, pages 58–61.

[RS-02-25] Abstract, PostScript, PDF, DVI.

Hans Httel. Deciding Framed Bisimilarity. May 2002. 20 pp. Appears in Antonn and Mayr, editors, 4th International Workshop on Verification of Infinite-State Systems, INFINITY ’02 Proceedings, ENTCS 68(6), 2002, 18 pp.

[RS-02-24] Abstract, PostScript, PDF.

Aske Simon Christensen, Anders Mller, and Michael I. Schwartzbach. Static Analysis for Dynamic XML. May 2002. 13 pp.

[RS-02-23] Abstract, PostScript, PDF, DVI.

Antonio Di Nola and Laurenţiu Leuştean. Compact Representations of BL-Algebras. May 2002. 25 pp.

[RS-02-22] Abstract, PostScript, PDF.

Mogens Nielsen, Catuscia Palamidessi, and Frank D. Valencia. On the Expressive Power of Concurrent Constraint Programming Languages. May 2002. 34 pp. Appears in Pfenning, editor, 4th International Conference on Principles and Practice of Declarative Programming, PPDP ’02 Proceedings, 2002, pages 156–157.

[RS-02-21] Abstract, PostScript, PDF, DVI.

Zoltn sik and Werner Kuich. Formal Tree Series. April 2002. 66 pp.

[RS-02-20] Abstract.

Zoltn sik and Kim G. Larsen. Regular Languages Definable by Lindstrm Quantifiers (Preliminary Version). April 2002. 56 pp. Superseeded by the BRICS report RS-03-28.

[RS-02-19] Abstract, PostScript, PDF, DVI.

Stephen L. Bloom and Zoltn sik. An Extension Theorem with an Application to Formal Tree Series. April 2002. 51 pp. Appears in Blute and Selinger, editors, Category Theory and Computer Science: 9th International Conference, CTCS ’02 Proceedings, ENTCS 69, 2003 under the title Unique Guarded Fixed Points in an Additive Setting.

[RS-02-18] Gerth Stlting Brodal and Rolf Fagerberg. Cache Oblivious Distribution Sweeping. April 2002. Appears in Widmayer, Triguero, Morales, Hennessy, Eidenbenz and Conejo, editors, 29th International Colloquium on Automata, Languages, and Programming, ICALP ’02 Proceedings, LNCS 2380, 2002, pages 426–438.

[RS-02-17] Abstract, PostScript, PDF. Bolette Ammitzbll Madsen, Jesper Makholm Nielsen, and Bjarke Skjernaa. On the Number of Maximal Bipartite Subgraphs of a Graph. April 2002. 7 pp.

[RS-02-16] Abstract, PostScript, PDF, DVI. Jiř Srba. Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds. April 2002. 33 pp. To appear in Acta Informatica.

[RS-02-15] Abstract, PostScript, PDF, DVI. Jesper Makholm Nielsen. On the Number of Maximal Independent Sets in a Graph. April 2002. 10 pp.

[RS-02-14] Abstract, PostScript, PDF, DVI. Ulrich Berger and Paulo B. Oliva. Modified Bar Recursion. April 2002. 23 pp. To appear in Lecture Notes in Logic.

[RS-02-13] Abstract, PostScript, PDF, DVI. Gerth Stlting Brodal, Rune B. Lyngs, Anna stlin, and Christian N. S. Pedersen. Solving the String Statistics Problem in Time O(n log n). March 2002. 28 pp. Shorter version appears in Widmayer, Triguero, Morales, Hennessy, Eidenbenz and Conejo, editors, 29th International Colloquium on Automata, Languages, and Programming, ICALP ’02 Proceedings, LNCS 2380, 2002, pages 728–739.

[RS-02-12] Abstract, PostScript, PDF, DVI. Olivier Danvy and Mayer Goldberg. There and Back Again. March 2002. ii+11 pp. Appears in Peyton Jones, editor, Proceedings of the 7th ACM SIGPLAN International Conference on Functional Programming, 2002, pages 230–234. This report supersedes the earlier report BRICS RS-01-39.

[RS-02-11] Abstract, PostScript, PDF. Aske Simon Christensen, Anders Mller, and Michael I. Schwartzbach. Extending Java for High-Level Web Service Construction. March 2002. 54 pp. To appear in ACM Transactions on Programming Languages and Systems.

[RS-02-10] Abstract, PostScript, PDF, DVI. Ulrich Kohlenbach. Uniform Asymptotic Regularity for Mann Iterates. March 2002. 17 pp. Appears in Journal of Mathematical Analysis and Applications, 279(2):531–544, 2003.

[RS-02-9] Abstract, PostScript, PDF, DVI. Anna stlin and Rasmus Pagh. One-Probe Search. February 2002. 17 pp. Appears in Widmayer, Triguero, Morales, Hennessy, Eidenbenz and Conejo, editors, 29th International Colloquium on Automata, Languages, and Programming, ICALP ’02 Proceedings, LNCS 2380, 2002, pages 439–450.

[RS-02-8] Abstract, PostScript, PDF, DVI. Ronald Cramer and Serge Fehr. Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups. February 2002. 19 pp. Appears in Yung, editor, Advances in Cryptology: 22nd Annual International Cryptology Conference, CRYPTO ’02 Proceedings, LNCS 2442, 2002, pages 272–287.

[RS-02-7] Abstract, PostScript, PDF. Anna Inglfsdttir, Anders Lyhne Christensen, Jens Alsted Hansen, Jacob Johnsen, John Knudsen, and Jacob Illum Rasmussen. A Formalization of Linkage Analysis. February 2002. vi+109 pp.

[RS-02-6] Abstract, PostScript, PDF, DVI. Luca Aceto, Zoltn sik, and Anna Inglfsdttir. Equational Axioms for Probabilistic Bisimilarity (Preliminary Report). February 2002. 22 pp. Appears in Kirchner and Ringeissen, editors, Algebraic Methodology and Software Technology: 9th International Conference, AMAST ’02 Proceedings, LNCS 2422, 2002, pages 239–253.

[RS-02-5] Abstract, PostScript, PDF, DVI. Federico Crazzolara and Glynn Winskel. Composing Strand Spaces. February 2002. 30 pp.

[RS-02-4] Abstract, PostScript, PDF, DVI. Olivier Danvy and Lasse R. Nielsen. Syntactic Theories in Practice. January 2002. 34 pp. This revised report supersedes the earlier BRICS report RS-01-31.

[RS-02-3] Abstract, PostScript, PDF, DVI. Olivier Danvy and Lasse R. Nielsen. On One-Pass CPS Transformations. January 2002. 18 pp.

[RS-02-2] Abstract, PostScript, PDF, DVI. Lasse R. Nielsen. A Simple Correctness Proof of the Direct-Style Transformation. January 2002. 11 pp.

[RS-02-1] Abstract, PostScript, PDF. Claus Brabrand, Anders Mller, and Michael I. Schwartzbach. The <bigwig> Project. January 2002. 36 pp. This revised report supersedes the earlier BRICS report RS-00-42.