BRICS Research Series, 1995

July 9, 2003

This document is also available as PostScript and DVI.

Bibliography

RS-95-60: Abstract, PostScript.
Jørgen H. Andersen, Carsten H. Kristensen, and Arne Skou.
Specification and Automated Verification of Real-Time Behaviour -- A Case Study.
December 1995.
24 pp. Appears in 3rd IFAC/IFIP workshop on Algoritms and Architectures for Real-Time Control, AARTC '95 Proceedings, 1995, pages 613-628 and in Annual Reviews of Control, 20:55-70, 1996.
RS-95-59: Abstract, PostScript, DVI.
Luca Aceto and Anna Ingólfsdóttir.
On the Finitary Bisimulation.
November 1995.
29 pp.
RS-95-58: Abstract, PostScript, DVI.
Nils Klarlund, Madhavan Mukund, and Milind Sohoni.
Determinizing Asynchronous Automata on Infinite Inputs.
November 1995.
32 pp. Appears in Thiagarajan, editor, Foundations of Software Technology and Theoretical Computer Science: 15th Conference, FST&TCS '95 Proceedings, LNCS 1026, 1995, pages 456-471.
RS-95-57: Abstract, PostScript, DVI.
Jaap van Oosten.
Topological Aspects of Traces.
November 1995.
16 pp. Appears in Billington and Reisig, editors, 17th International Conference on Application and Theory of Petri Nets, ICATPN '96 Proceedings, LNCS 1091, 1996, pages 480-496.
RS-95-56: Abstract, PostScript, DVI.
Luca Aceto, Willem Jan Fokkink, Rob J. van Glabbeek, and Anna Ingólfsdóttir.
Axiomatizing Prefix Iteration with Silent Steps.
November 1995.
25 pp. Appears in Bjerner, Larsson and Nordström, editors, 7th Nordic Workshop on Programming Theory, NWPT '7 Proceedings, Programming Methodology Group's Report Series Report 86, January 1996, 1995, and in Information and Computation, 127(1):26-40, May 1996.
RS-95-55: Abstract, PostScript.
Mogens Nielsen and Kim Sunesen.
Behavioural Equivalence for Infinite Systems -- Partially Decidable!
November 1995.
38 pp. Full version of paper appearing in Billington and Reisig, editors, 17th International Conference on Application and Theory of Petri Nets, ICATPN '96 Proceedings, LNCS 1091, 1996, pages 460-479.
RS-95-54: Abstract, PostScript, DVI.
Nils Klarlund, Mogens Nielsen, and Kim Sunesen.
A Case Study in Automated Verification Based on Trace Abstractions.
November 1995.
35 pp. Full version appears in Broy, Merz and Spies, editors, Formal Systems Specification: The RPC-Memory Specification Case Study, FSS '96 Selected Solutions, LNCS 1169, 1996, pages 341-374, under the title Using Monadic Second-Order Logic over Finite Domains for Specification and Verification.
RS-95-53: Abstract, PostScript, DVI.
Nils Klarlund, Mogens Nielsen, and Kim Sunesen.
Automated Logical Verification based on Trace Abstractions.
November 1995.
19 pp. Appears in The Fifteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '96 Proceedings, 1996, pages 101-110.
RS-95-52: Abstract, PostScript, DVI.
Antonín Kucera.
Deciding Regularity in Process Algebras.
October 1995.
42 pp.
RS-95-51: Abstract, PostScript, DVI.
Rowan Davies.
A Temporal-Logic Approach to Binding-Time Analysis.
October 1995.
15 pp. Appears in Eleventh Annual IEEE Symposium on Logic in Computer Science, LICS '96 Proceedings, 1996, pages 184-195.
RS-95-50: Abstract, PostScript, DVI.
Dany Breslauer.
On Competitive On-Line Paging with Lookahead.
September 1995.
12 pp. Appears in Puech and Reischuk, editors, 13th Annual Symposium on Theoretical Aspects of Computer Science, STACS '96 Proceedings, LNCS 1046, 1996, pages 593-603.
RS-95-49: Abstract, PostScript, DVI.
Mayer Goldberg.
Solving Equations in the $\lambda$ -Calculus using Syntactic Encapsulation.
September 1995.
13 pp.
RS-95-48: Abstract, PostScript, DVI.
Devdatt P. Dubhashi.
Simple Proofs of Occupancy Tail Bounds.
September 1995.
7 pp. Appears in Random Structures and Algorithms, 11, 1997.
RS-95-47: Abstract, PostScript, DVI.
Dany Breslauer.
The Suffix Tree of a Tree and Minimizing Sequential Transducers.
September 1995.
15 pp. Appears in Hirschberg and Myers, editors, Combinatorial Pattern Matching: 7th Annual Symposium, CPM '96 Proceedings, LNCS 1075, 1996, pages 116-129 and in Theoretical Computer Science, 191(1-2):131-144, January 1998.
RS-95-46: Abstract, PostScript, DVI.
Dany Breslauer, Livio Colussi, and Laura Toniolo.
On the Comparison Complexity of the String Prefix-Matching Problem.
August 1995.
39 pp. Appears in Leeuwen, editor, Second Annual European Symposium on Algorithms, ESA '94 Proceedings, LNCS 855, 1994, pages 483-494.
RS-95-45: Abstract, PostScript.
Gudmund Skovbjerg Frandsen and Sven Skyum.
Dynamic Maintenance of Majority Information in Constant Time per Update.
August 1995.
9 pp. Revised version appears in Information Processing Letters vol. 63 (1997), pages 75-78.
RS-95-44: Abstract, PostScript.
Bruno Courcelle and Igor Walukiewicz.
Monadic Second-Order Logic, Graphs and Unfoldings of Transition Systems.
August 1995.
39 pp. Presented at the 9th Annual Conference of the European Association for Computer Science Logic, CSL '95. Journal version appears in Annals of Pure and Applied Logic, 92(1):35-62, 1998.
RS-95-43: Abstract, PostScript, DVI.
Noam Nisan and Avi Wigderson.
Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version).
August 1995.
17 pp. Appears in 36th Annual Symposium on Foundations of Computer Science, FOCS '95 Proceedings, 1995, pages 16-25. Journal version in Computational Complexity, 6(3):217-234, 1997.
RS-95-42: Abstract, PostScript, DVI.
Mayer Goldberg.
An Adequate Left-Associated Binary Numeral System in the $\lambda$ -Calculus.
August 1995.
16 pp. Revised version Also available as BRICS Report RS-96-6. The revised version appears in Journal of Functional Programming 10(6):607-623, 2000.
RS-95-41: Abstract.
Olivier Danvy, Karoline Malmkjær, and Jens Palsberg.
Eta-Expansion Does The Trick.
August 1995.
23 pp. Please refer to the revised version BRICS-RS-96-17. Now appears in ACM Transactions on Programming Languages and Systems, 8(6):730-751, 1996.
RS-95-40: Abstract, PostScript, DVI.
Anna Ingólfsdóttir and Andrea Schalk.
A Fully Abstract Denotational Model for Observational Congruence.
August 1995.
29 pp. Appears with the title A Fully Abstract Denotational Model for Observational Precongruence in Büning, editor, European Association for Computer Science Logic: 9th Workshop, CSL '95 Selected Papers, LNCS 1092, 1996, pages 335-361. Appears also in Theoretical Computer Science 254(1-2):35-61, 2001.
RS-95-39: Abstract, PostScript.
Allan Cheng.
Petri Nets, Traces, and Local Model Checking.
July 1995.
32 pp. Full version of paper appearing in Alagar and Nivat, editors, Algebraic Methodology and Software Technology: 4th International Conference, AMAST '95 Proceedings, LNCS 936, 1995, pages 322-337. Appears also in Theoretical Computer Science, 183(2):229-251, (1997).
RS-95-38: Abstract.
Mayer Goldberg.
Gödelisation in the $\lambda$ -Calculus.
July 1995.
7 pp. Appears in Information Processing Letters 75(1-2):13-16(2000). Please refer to the revised version BRICS-RS-96-5.
RS-95-37: Abstract, PostScript, DVI.
Sten Agerholm and Mike Gordon.
Experiments with ZF Set Theory in HOL and Isabelle.
July 1995.
14 pp. Appears in Schubert, Windley and Alves-Foss, editors, Higher Order Logic Theorem Proving and its Applications: 8th International Workshop, HOLTPA '95 Proceedings, LNCS 971, 1995, pages 32-45.
RS-95-36: Abstract, PostScript, DVI.
Sten Agerholm.
Non-Primitive Recursive Function Definitions.
July 1995.
15 pp. Appears in Schubert, Windley and Alves-Foss, editors, Higher Order Logic Theorem Proving and its Applications: 8th International Workshop, HOLTPA '95 Proceedings, LNCS 971, 1995, pages 17-31.
RS-95-35: Abstract, PostScript, DVI.
Mayer Goldberg.
Constructing Fixed-Point Combinators Using Application Survival.
June 1995.
14 pp.
RS-95-34: Abstract, PostScript, DVI.
Jens Palsberg.
Type Inference with Selftype.
June 1995.
22 pp.
RS-95-33: Abstract, PostScript, DVI.
Jens Palsberg, Mitchell Wand, and Patrick O'Keefe.
Type Inference with Non-structural Subtyping.
June 1995.
22 pp. Appears in Formal Aspects of Computing, 9(1):49-67, 1997.
RS-95-32: Abstract, PostScript, DVI.
Jens Palsberg.
Efficient Inference of Object Types.
June 1995.
32 pp. Appears in Information and Computation, 123(2):198-209, 1995. Preliminary version appears in Ninth Annual IEEE Symposium on Logic in Computer Science, LICS '94 Proceedings, 1994, pages 186-195.
RS-95-31: Abstract, PostScript, DVI.
Jens Palsberg and Peter Ørbæk.
Trust in the $\lambda$ -calculus.
June 1995.
32 pp. Appears in Mycroft, editor, 2nd International Static Analysis Symposium, SAS '95 Proceedings, LNCS 983, 1995, pages 314-330.
RS-95-30: Abstract, PostScript, DVI.
Franck van Breugel.
From Branching to Linear Metric Domains (and back).
June 1995.
30 pp. Abstract appeared 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 444-447.
RS-95-29: Abstract, PostScript.
Nils Klarlund.
An $n \log n$ Algorithm for Online BDD Refinement.
May 1995.
20 pp. Conference version in Grumberg, editor, Computer-Aided Verification: 9th International Conference, CAV '97 Proceedings, LNCS 1254, 1997, pages 107-118. Journal version in Journal of Algorithms, 32(2):133-154, 1999.
RS-95-28: Abstract, PostScript, DVI.
Luca Aceto and Jan Friso Groote.
A Complete Equational Axiomatization for MPA with String Iteration.
May 1995.
39 pp. Appears in Theoretical Computer Science, 211(1-2):339-374, January 1999.
RS-95-27: Abstract, PostScript, DVI.
David Janin and Igor Walukiewicz.
Automata for the $\mu$ -calculus and Related Results.
May 1995.
11 pp. Appears in Wiedermann and Hájek, editors, Mathematical Foundations of Computer Science: 20th International Symposium, MFCS '95 Proceedings, LNCS 969, 1995, pages 552-562.
RS-95-26: Abstract, PostScript, DVI.
Faith Fich and Peter Bro Miltersen.
Tables Should Be Sorted (on Random Access Machines).
May 1995.
11 pp. Appears in Akl, Dehne, Sack and Santoro, editors, Algorithms and Data Structures: 4th Workshop, WADS '95 Proceedings, LNCS 955, 1995, pages 482-493.
RS-95-25: Abstract, PostScript, DVI.
Søren B. Lassen.
Basic Action Theory.
May 1995.
47 pp.
RS-95-24: Abstract, PostScript, DVI.
Peter Ørbæk.
Can you Trust your Data?
April 1995.
15 pp. 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 575-590.
RS-95-23: Abstract, PostScript, DVI.
Allan Cheng and Mogens Nielsen.
Open Maps (at) Work.
April 1995.
33 pp. Appears with the title Observing Behaviour Categorically in Thiagarajan, editor, Foundations of Software Technology and Theoretical Computer Science: 15th Conference, FST&TCS '95 Proceedings, LNCS 1026, 1995, pages 263-278.
RS-95-22: Abstract, PostScript, DVI.
Anna Ingólfsdóttir.
A Semantic Theory for Value-Passing Processes, Late Approach, Part II: A Behavioural Semantics and Full Abstractness.
April 1995.
33 pp. To appear in Information and Computation (together with part I).
RS-95-21: Abstract, PostScript.
Jesper G. Henriksen, Ole J. L. Jensen, Michael E. Jørgensen, Nils Klarlund, Robert Paige, Theis Rauhe, and Anders B. Sandholm.
MONA: Monadic Second-Order Logic in Practice.
May 1995.
17 pp. Appears in Brinksma, Cleaveland, Larsen, Margaria and Steffen, editors, Tools and Algorithms for The Construction and Analysis of Systems: International Workshop, TACAS '95 Selected Papers, LNCS 1019, 1995, pages 89-110.
RS-95-20: Abstract, PostScript, DVI.
Anders Kock.
The Constructive Lift Monad.
March 1995.
18 pp.
RS-95-19: Abstract, PostScript, DVI.
François Laroussinie and Kim G. Larsen.
Compositional Model Checking of Real Time Systems.
March 1995.
20 pp. Appears in Lee and Smolka, editors, Concurrency Theory: 6th International Conference, CONCUR '95 Proceedings, LNCS 962, 1995, pages 27-41.
RS-95-18: Abstract, PostScript, DVI.
Allan Cheng.
Complexity Results for Model Checking.
February 1995.
18pp.
RS-95-17: Abstract, PostScript, DVI.
Jari Koistinen, Nils Klarlund, and Michael I. Schwartzbach.
Design Architectures through Category Constraints.
February 1995.
19 pp.
RS-95-16: Abstract, PostScript, DVI.
Dany Breslauer and Ramesh Hariharan.
Optimal Parallel Construction of Minimal Suffix and Factor Automata.
February 1995.
9 pp. Appears in Parallel Processing Letters, 6(1):35-44, 1996.
RS-95-15: Abstract, PostScript, DVI.
Devdatt P. Dubhashi, Grammati E. Pantziou, Paul G. Spirakis, and Christos D. Zaroliagis.
The Fourth Moment in Luby's Distribution.
February 1995.
10 pp. Appears in Theoretical Computer Science, 148(1):133-140, 1995.
RS-95-14: Abstract, PostScript, DVI.
Devdatt P. Dubhashi.
Inclusion-Exclusion Implies Inclusion-Exclusion.
February 1995.
6 pp.
RS-95-13: Abstract, PostScript, DVI.
Torben Braüner.
The Girard Translation Extended with Recursion.
February 1995.
79 pp. Full version of paper appearing in Pacholski and Tiuryn, editors, European Association for Computer Science Logic: 8th Workshop, CSL '94 Selected Papers, LNCS 933, 1995, pages 31-45.
RS-95-12: Abstract, PostScript.
Gerth Stølting Brodal.
Fast Meldable Priority Queues.
February 1995.
12 pp. Appears in Akl, Dehne, Sack and Santoro, editors, Algorithms and Data Structures: 4th Workshop, WADS '95 Proceedings, LNCS 955, 1995, pages 282-290.
RS-95-11: Abstract, PostScript, DVI.
Alberto Apostolico and Dany Breslauer.
An Optimal $O(\log\log n)$ Time Parallel Algorithm for Detecting all Squares in a String.
February 1995.
18 pp. Appears in SIAM Journal on Computing, 25(6):1318-1331, December, 1996.
RS-95-10: Abstract, PostScript, DVI.
Dany Breslauer and Devdatt P. Dubhashi.
Transforming Comparison Model Lower Bounds to the Parallel-Random-Access-Machine.
February 1995.
11 pp. Appears in Fifth Italian Conference on Theoretical Computer Science, November 1995 and in Information Processing Letters, 62(2):103-110, April 1997.
RS-95-9: Abstract, PostScript, DVI.
Lars Ramkilde Knudsen.
Partial and Higher Order Differentials and Applications to the DES.
February 1995.
24 pp.
RS-95-8: Abstract, PostScript, DVI.
Ole I. Hougaard, Michael I. Schwartzbach, and Hosein Askari.
Type Inference of Turbo Pascal.
February 1995.
19 pp. Appeas in Software--Consepts & Tools, 16:160-169, Springer-Verlag, 1995.
RS-95-7: Abstract, PostScript.
David A. Basin and Nils Klarlund.
Hardware Verification using Monadic Second-Order Logic.
January 1995.
13 pp. Appears in Wolper, editor, Computer-Aided Verification: 7th International Conference, CAV '95 Proceedings, LNCS 939, 1995, pages 31-41.
RS-95-6: Abstract, PostScript, DVI.
Igor Walukiewicz.
A Complete Deductive System for the $\mu$ -Calculus.
January 1995.
39 pp . Appears in Information and Computation, 157:142-182, 2000. Appeared earlier in Kozen, editor, Tenth Annual IEEE Symposium on Logic in Computer Science, LICS '95 Proceedings, 1995, pages 14-24.
RS-95-5: Abstract, PostScript, DVI.
Luca Aceto and Anna Ingólfsdóttir.
A Complete Equational Axiomatization for Prefix Iteration with Silent Steps.
January 1995.
27 pp. Appears in Wirsing and Nivat, editors, Algebraic Methodology and Software Technology: 5th International Conference, AMAST '96 Proceedings, LNCS 1101, 1996, pages 195-209 under the title An Equational Axiomatization of Observation Congruence for Prefix Iteration.
RS-95-4: Abstract, PostScript, DVI.
Mogens Nielsen and Glynn Winskel.
Petri Nets and Bisimulations.
January 1995.
36 pp. Appears in Theoretical Computer Science 153(1-2):211-244, January 1996.
RS-95-3: Abstract, PostScript, DVI.
Anna Ingólfsdóttir.
A Semantic Theory for Value-Passing Processes, Late Approach, Part I: A Denotational Model and Its Complete Axiomatization.
January 1995.
37 pp. To appear in Information and Comutation (together with part II).
RS-95-2: Abstract, PostScript, DVI.
François Laroussinie, Kim G. Larsen, and Carsten Weise.
From Timed Automata to Logic - and Back.
January 1995.
21 pp. Appears in Wiedermann and Hájek, editors, Mathematical Foundations of Computer Science: 20th International Symposium, MFCS '95 Proceedings, LNCS 969, 1995, pages 529-539.
RS-95-1: Abstract, PostScript, DVI.
Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, and Søren Skyum.
Dynamic Algorithms for the Dyck Languages.
January 1995.
21 pp. Appears in Akl, Dehne, Sack and Santoro, editors, Algorithms and Data Structures: 4th Workshop, WADS '95 Proceedings, LNCS 955, 1995, pages 98-108.

Last modified: 2003-06-09 by webmaster.