BRICS Research Series, 2002

March 26, 2004

This document is also available as PostScript and DVI.

Bibliography

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 Stølting Brodal, Rolf Fagerberg, Anna Östlin, Christian N. S. Pedersen, and S. Srinivasa Rao.
Computing Refined Buneman Trees in Cubic Time.
December 2002.
14 pp. Appears in Benson and Page, editors, Algorithms in Bioinformatics: 2nd International Workshop, WABI '03 Proceedings, LNCS 2812, 2003, pages 259-270.

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, Jancar, Kretínský 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.
Zoltán Ésik.
Extended Temporal Logic on Finite Words and Wreath Product of Monoids with Distinguished Generators.
December 2002.
16 pp. Appears in Ito and Toyama, editors, 6th International Conference, Developments in Language Theory, DLT '02 Revised Papers, LNCS 2450, 2003, pages 43-48.

RS-02-46

Abstract, PostScript, PDF, DVI.
Zoltán É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.
Zoltán Ésik and Zoltán L. Németh.
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 Ingólfsdóttir, Jacob Johnsen, and John Knudsen.
Checking Consistency of Pedigree Information is NP-complete (Preliminary Report).
October 2002.
16 pp. Superseeded by RS-03-17.

RS-02-41

Abstract, PostScript, PDF, DVI.
Stephen L. Bloom and Zoltán Ésik.
Axiomatizing Omega and Omega-op Powers of Words.
October 2002.
16 pp.

RS-02-40

Abstract, PostScript, PDF, DVI.
Luca Aceto, Willem Jan Fokkink, and Anna Ingólfsdóttir.
A Note on an Expressiveness Hierarchy for Multi-exit Iteration.
September 2002.
8 pp. Appears in Information Processing Letters, Elsevier, 87(1):17-23, 2003.

RS-02-39

Abstract, PostScript, PDF.
Stephen L. Bloom and Zoltán É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 SIGPLAN 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. Appears in Proceedings of the Steklov Institute of Mathematics, 242:136-164, 2003.

RS-02-30

Olivier Danvy and Ulrik P. Schultz.
Lambda-Lifting in Quadratic Time.
June 2002.
17 pp. Appears in Hu and Rodríguez-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 Laurentiu Leustean.
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 Vardi and Voronko, editors, Logic for Programming, Artificial Intelligence, and Reasoning, 10th International Conference, LPAR '03 Proceedings, LNCS 2860, 2003, pages 290-301. Appeared earlier in Ésik and Ingólfsdóttir, 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 Hüttel.
Deciding Framed Bisimilarity.
May 2002.
20 pp. Appears in Antonín 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 Møller, and Michael I. Schwartzbach.
Static Analysis for Dynamic XML.
May 2002.
13 pp.

RS-02-23

Abstract, PostScript, PDF, DVI.
Antonio Di Nola and Laurentiu Leustean.
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.
Zoltán Ésik and Werner Kuich.
Formal Tree Series.
April 2002.
66 pp.

RS-02-20

Abstract.
Zoltán Ésik and Kim G. Larsen.
Regular Languages Definable by Lindström 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 Zoltán É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 Stølting 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 Ammitzbøll Madsen, Jesper Makholm Byskov, and Bjarke Skjernaa.
On the Number of Maximal Bipartite Subgraphs of a Graph.
April 2002.
7 pp.

RS-02-16

Abstract, PostScript, PDF, DVI.
Jirí 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 Stølting 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 Møller, 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 Ingólfsdóttir, 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, Zoltán Ésik, and Anna Ingólfsdóttir.
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 Møller, and Michael I. Schwartzbach.
The <bigwig> Project.
January 2002.
36 pp. This revised report supersedes the earlier BRICS report RS-00-42.

Last modified: 2004-03-26 by webmaster.