BRICS Research Series, 1994

July 9, 2003

This document is also available as PostScript and DVI.

Bibliography

RS-94-48

Abstract, PostScript, DVI.
Jens Chr. Godskesen and Kim G. Larsen.
Synthesizing Distinguishing Formulae for Real Time Systems.
December 1994.
21 pp. Extended abstract appears in Wiedermann and Hájek, editors, Mathematical Foundations of Computer Science: 20th International Symposium, MFCS '95 Proceedings, LNCS 969, 1995, pages 519-528.

RS-94-47

Abstract, PostScript, DVI.
Kim G. Larsen, Bernhard Steffen, and Carsten Weise.
A Constraint Oriented Proof Methodology based on Modal Transition Systems.
December 1994.
13 pp.

RS-94-46

Abstract, PostScript, DVI.
Amos Beimel, Anna Gál, and Mike Paterson.
Lower Bounds for Monotone Span Programs.
December 1994.
14 pp. Appears in 36th Annual Symposium on Foundations of Computer Science, FOCS '95 Proceedings, 1995, pages 674-681.

RS-94-45

Abstract, PostScript.
Jørgen H. Andersen, Kåre J. Kristoffersen, Kim G. Larsen, and Jesper Niedermann.
Automatic Synthesis of Real Time Systems.
December 1994.
17 pp. Appears in Fülöp and Gécseg, editors, 22nd International Colloquium on Automata, Languages, and Programming, ICALP '95 Proceedings, LNCS 944, 1995, pages 535-546.

RS-94-44

Abstract, PostScript.
Sten Agerholm.
A HOL Basis for Reasoning about Functional Programs.
December 1994.
PhD thesis. viii+224 pp.

RS-94-43

Abstract, PostScript, DVI.
Luca Aceto and Alan S. A. Jeffrey.
A Complete Axiomatization of Timed Bisimulation for a Class of Timed Regular Behaviours (Revised Version).
December 1994.
18 pp. Appears in Theoretical Computer Science vol. 152(2) pages 251-268, December 1995.

RS-94-42

Abstract, PostScript, DVI.
Dany Breslauer and Leszek Gasieniec.
Efficient String Matching on Coded Texts.
December 1994.
20 pp. Appears with the title Efficient String Matching on Packed Texts in Galil and Ukkonen, editors, Combinatorial Pattern Matching: 6th Annual Symposium, CPM '95 Proceedings, LNCS 937, 1995, pages 27-40 and in RAIRO Informatique Théorique et Applications, 30(6):521-544, 1996.

RS-94-41

Abstract, PostScript, DVI.
Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson.
On Data Structures and Asymmetric Communication Complexity.
December 1994.
17 pp. Appears in The Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC '95 Proceedings, 1995, pages 103-111. Appears also in Journal of Computer and System Sciences, 57(1):37-49, 1998.

RS-94-40

Abstract, PostScript, DVI.
Luca Aceto and Anna Ingólfsdóttir.
CPO Models for GSOS Languages -- Part I: Compact GSOS Languages.
December 1994.
70 pp. An extended abstract of the paper appears in: Proceedings of CAAP '95, LNCS 915, 1995, pages 439-453. Full version also appears in Information and Computation, 129(2):107-141, September 1996.

RS-94-39

Abstract, PostScript, DVI.
Ivan B. Damgård, Oded Goldreich, and Avi Wigderson.
Hashing Functions can Simplify Zero-Knowledge Protocol Design (too).
November 1994.
18 pp.

RS-94-38

Abstract, PostScript, DVI.
Ivan B. Damgård and Lars Ramkilde Knudsen.
Enhancing the Strength of Conventional Cryptosystems.
November 1994.
12 pp.

RS-94-37

Abstract, PostScript, DVI.
Jaap van Oosten.
Fibrations and Calculi of Fractions.
November 1994.
21 pp. Appears in Journal of Pure and Applied, 146(1):77-102, 2000.

RS-94-36

Abstract, PostScript, DVI.
Alexander A. Razborov.
On provably disjoint NP-pairs.
November 1994.
27 pp.

RS-94-35

Abstract, PostScript.
Gerth Stølting Brodal.
Partially Persistent Data Structures of Bounded Degree with Constant Update Time.
November 1994.
24 pp. Appears in Nordic Journal of Computing, 3(3):238-255, 1996.

RS-94-34

Abstract, PostScript, DVI.
Henrik Reif Andersen, Colin Stirling, and Glynn Winskel.
A Compositional Proof System for the Modal $\mu$-Calculus.
October 1994.
18 pp. Appears in Ninth Annual IEEE Symposium on Logic in Computer Science, LICS '94 Proceedings, 1994, pages 144-153. Superseeded by BRICS Report RS-98-40.

RS-94-33

Abstract, PostScript, DVI.
Vladimiro Sassone.
Strong Concatenable Processes: An Approach to the Category of Petri Net Computations.
October 1994.
40 pp. Workshop version appears in Engberg, Larsen and Mosses, editors, 6th Nordic Workshop on Programming Theory, NWPT '6 Proceedings, BRICS Notes Series NS-94-6, December 1994, 1994, pages 385-399 with the title An Approach to the Category of Net Computations. Revised version appears in Mosses, Nielsen and Schwartzbach, editors, Theory and Practice of Software Development: 6th International Conference Joint Conference CAAP/FASE, TAPSOFT '95 Proceedings, LNCS 915, 1995, pages 334-348 with the title On the Category of Petri Net Computations.

RS-94-32

Abstract, PostScript, DVI.
Alexander Aiken, Dexter Kozen, and Ed Wimmers.
Decidability of Systems of Set Constraints with Negative Constraints.
October 1994.
33 pp. Appears in Information and Computation, 122(1):30-44, October 1995.

RS-94-31

Abstract, PostScript, DVI.
Noam Nisan and Amnon Ta-Shma.
Symmetric Logspace is Closed Under Complement.
September 1994.
8 pp.

RS-94-30

Abstract, PostScript.
Thore Husfeldt.
Fully Dynamic Transitive Closure in Plane Dags with one Source and one Sink.
September 1994.
26 pp. Appears in Spirakis, editor, Third Annual European Symposiumon on Algorithms, ESA '95 Proceedings, LNCS 979, 1995, pages 199-212.

RS-94-29

Abstract, PostScript, DVI.
Ronald Cramer and Ivan B. Damgård.
Secure Signature Schemes Based on Interactive Protocols.
September 1994.
24 pp. Appears in Coppersmith, editor, Advances in Cryptology: 15th Annual International Cryptology Conference, CRYPTO '95 Proceedings, LNCS 963, 1995, pages 297-310.

RS-94-28

Abstract, PostScript, DVI.
Oded Goldreich.
Probabilistic Proof Systems.
September 1994.
19 pp.

RS-94-27

Abstract, PostScript, DVI.
Torben Braüner.
A Model of Intuitionistic Affine Logic from Stable Domain Theory (Revised and Expanded Version).
September 1994.
19 pp. Full version of paper appearing in Abiteboul and Shamir, editors, Automata, Languages and Programming: 21st International Colloquium, ICALP '94 Proceedings, LNCS 820, 1994, pages 340-351. This report is a revised and expanded version of DAIMI IR-118.

RS-94-26

Abstract, PostScript, DVI.
Søren Riis.
Count($q$) versus the Pigeon-Hole Principle.
August 1994.
3 pp. Appears in Archive for Mathematical Logic 36(3):157-188 (1997) (expanded to a selfcontained paper).

RS-94-25

Abstract, PostScript, DVI.
Søren Riis.
Bootstrapping the Primitive Recursive Functions by 47 Colors.
August 1994.
5 pp. Improved version appears in Decrete Mathematics 169(1-3):269-272 (1997) under the title Bootstrapping the Primitive Recursive Functions by Only 27 Colors.

RS-94-24

Abstract, PostScript, DVI.
Søren Riis.
A Fractal which violates the Axiom of Determinacy.
August 1994.
3 pp.

RS-94-23

Abstract, PostScript, DVI.
Søren Riis.
Finitisation in Bounded Arithmetic.
August 1994.
31 pp. Manuscript presented at The Tenth Workshop on the Mathematical Foundations of Programming Semantics, Kansas, USA, 1994.

RS-94-22

Abstract, PostScript, DVI.
Torben Braüner.
A General Adequacy Result for a Linear Functional Language.
August 1994.
39 pp. Presented at Mathematical Foundations of Programming Semantics: 10th International Conference, MFPS '94. Strongly revised version accepted for publication in a special issue of Theoretical Computer Science devoted the proceedings of MFPS '94.

RS-94-21

Abstract, PostScript, DVI.
Søren Riis.
Count($q$) does not imply Count($p$).
July 1994.
55 pp. Appears in Annals of Pure and Applied Logic 90(1-3):1-56 (1997).

RS-94-20

Abstract, PostScript, DVI.
Peter D. Mosses and Martín Musicante.
An Action Semantics for ML Concurrency Primitives.
July 1994.
21 pp. Appears in Naftalin, Denvir and Bertran, editors, Industrial Benefit of Formal Methods: First International Symposium of Formal Methods Europe, FME '94 Proceedings, LNCS 873, 1994, pages 461-479.

RS-94-19

Abstract, PostScript.
Jens Chr. Godskesen, Kim G. Larsen, and Arne Skou.
Automatic Verification of Real-Timed Systems Using EPSILON.
June 1994.
8 pp. Appears in Voung and Chanson, editors, Fourteenth International IFIP Symposium on Protocol Specification, Testing and Verification, PSTV '94 Proceedings, 1994, pages 323-330.

RS-94-18

Abstract, PostScript, DVI.
Sten Agerholm.
LCF Examples in HOL.
June 1994.
16 pp. Revised version appears in The Computer Journal, 38(2): 121-130, 1995. Also in Melham and Camilleri, editors, Higher Order Logic Theorem Proving and Its Applications: 7th International Workshop, HOLTPA '94 Proceedings, LNCS 859, 1994, pages 1-16.

RS-94-17

Abstract.
Allan Cheng.
Local Model Checking and Traces.
June 1994.
30 pp. Please refer to the revised version BRICS-RS-95-39.

RS-94-16

Abstract.
Lars Arge.
External-Storage Data Structures for Plane-Sweep Algorithms.
June 1994.
37 pp. Revised version appears in Akl, Dehne, Sack and Santoro, editors, Algorithms and Data Structures: 4th Workshop, WADS '95 Proceedings, LNCS 955, 1995, pages 334-345. Please refer to the revised and extended version BRICS-RS-96-28.

RS-94-15

Abstract.
Mogens Nielsen and Glynn Winskel.
Petri Nets and Bisimulations.
May 1994.
36 pp. Please refer to the revised and corrected version BRICS-RS-95-4.

RS-94-14

Abstract, PostScript.
Nils Klarlund.
The Limit View of Infinite Computations.
May 1994.
16 pp. Appears in Jonsson and Parrow, editors, Concurrency Theory: 5th International Conference, CONCUR '94 Proceedings, LNCS 836, 1994, pages 351-366.

RS-94-13

Abstract, PostScript, DVI.
Glynn Winskel.
Stable Bistructure Models of PCF.
May 1994.
26 pp. Preliminary draft. Invited lecture for MFCS '94. Appears in Prívara, Rovan and Ruzicka, editors, Mathematical Foundations of Computer Science: 19th International Symposium, MFCS '94 Proceedings, LNCS 841, 1994, pages 177-197.

RS-94-12

Abstract.
Glynn Winskel and Mogens Nielsen.
Models for Concurrency.
May 1994.
144 pp. Appears as a chapter in the Handbook of Logic and the Foundations of Computer Science, vol. 4, pages 1-148, Oxford University Press, 1995.

RS-94-11

Abstract, PostScript.
Nils Klarlund.
A Homomorphism Concept for $\omega$-Regularity.
May 1994.
16 pp. Appears in Pacholski and Tiuryn, editors, European Association for Computer Science Logic: 8th Workshop, CSL '94 Selected Papers, LNCS 933, 1995, pages 471-485.

RS-94-10

Abstract, PostScript.
Jakob L. Jensen, Michael E. Jørgensen, and Nils Klarlund.
Monadic Second-order Logic for Parameterized Verification.
May 1994.
14 pp.

RS-94-9

Abstract, PostScript, DVI.
Gordon Plotkin and Glynn Winskel.
Bistructures, Bidomains and Linear Logic.
May 1994.
16 pp. Appears in Abiteboul and Shamir, editors, Automata, Languages and Programming: 21st International Colloquium, ICALP '94 Proceedings, LNCS 820, 1994, pages 352-363.

RS-94-8

Abstract, PostScript, DVI.
Javier Esparza and Mogens Nielsen.
Decidability Issues for Petri Nets.
May 1994.
23 pp. Appears in Journal of Information Processing and Cybernet. EIK, 30:143-160, 1994.

RS-94-7

Abstract, PostScript, DVI.
André Joyal, Mogens Nielsen, and Glynn Winskel.
Bisimulation from Open Maps.
May 1994.
42 pp. Appears in LICS '93 special issue of Information and Computation, 127(2):164-185, June 1986.

RS-94-6

Abstract, PostScript, DVI.
Mogens Nielsen and Christian Clausen.
Bisimulations, Games, and Logic.
April 1994.
37 pp. Full version of paper appearing in Karhumäki, Maurer and Rozenberg, editors, Results and Trends in Theoretical Computer Science: Colloquium in Honor of Arto Salomaa, RTTCS '94 Selected Papers, LNCS 812, 1994, pages 289-305.

RS-94-5

Abstract, PostScript, DVI.
Peter D. Mosses.
Unified Algebras and Abstract Syntax.
March 1994.
21 pp. Appears in Ehrig and Orejas, editors, Recent Trends in Data Type Specification, 9th Workshop on Specification of Abstract Data Types, RTDTS '92 Selected Papers, LNCS 785, 1994, pages 280-294.

RS-94-4

Abstract, PostScript, DVI.
Nils Klarlund and Michael I. Schwartzbach.
Graphs and Decidable Transductions based on Edge Constraints.
February 1994.
19 pp. Appears in Tison, editor, Trees in Algebra and Programming: 19th International Colloquium, CAAP '94 Proceedings, LNCS 787, 1994, pages 187-201.

RS-94-3

Abstract, PostScript, DVI.
Uffe H. Engberg and Glynn Winskel.
Linear Logic on Petri Nets.
February 1994.
54 pp. Appears in Bakker, de Roever and Rozenberg, editors, A Decade of Concurrency: Reflections and Perspectives, REX School/Symposium, REX '94 Proceedings, LNCS 803, 1994, pages 176-229.

RS-94-2

Abstract, PostScript, DVI.
Alexander E. Andreev.
Complexity of Nondeterministic Functions.
February 1994.
47 pp.

RS-94-1

PostScript.
Glynn Winskel.
Semantics, Algorithmics and Logic: Basic Research in Computer Science. BRICS Inaugural Talk.
February 1994.
8 pp.

Last modified: 2003-06-09 by webmaster.