Relational and Algebraic Methods in Computer Science

1. Front Matter

   PDF

2. Applications to Software Specification and Correctness

   1. Transitive Separation Logic

      • Han-Hing Dang, Bernhard Möller

      Pages 1-16

   2. Unifying Lazy and Strict Computations

      • Walter Guttmann

      Pages 17-32

   3. Foundations of Coloring Algebra with Consequences for Feature-Oriented Programming

      • Peter Höfner, Bernhard Möller, Andreas Zelend

      Pages 33-49

   4. Towards an Algebra for Real-Time Programs

      • Brijesh Dongol, Ian J. Hayes, Larissa Meinicke, Kim Solin

      Pages 50-65

3. Mechanised Resoning in Relational Algebras

   1. Automated Reasoning in Higher-Order Regular Algebra

      • Alasdair Armstrong, Georg Struth

      Pages 66-81

   2. Towards Certifiable Implementation of Graph Transformation via Relation Categories

      • Wolfram Kahl

      Pages 82-97

   3. Deciding Regular Expressions (In-)Equivalence in Coq

      • Nelma Moreira, David Pereira, Simão Melo de Sousa

      Pages 98-113

4. Algebraic Program Derivation

   1. Simple Rectangle-Based Functional Programs for Computing Reflexive-Transitive Closures

      • Rudolf Berghammer, Sebastian Fischer

      Pages 114-129

   2. Using Relations to Develop a Haskell Program for Computing Maximum Bipartite Matchings

      • Nikita Danilenko

      Pages 130-145

   3. Relations as Executable Specifications: Taming Partiality and Non-determinism Using Invariants

      • Nuno Macedo, Hugo Pacheco, Alcino Cunha

      Pages 146-161

5. Theoretical Foundations

   1. Left-Handed Completeness

      • Dexter Kozen, Alexandra Silva

      Pages 162-178

   2. On Completeness of Omega-Regular Algebras

      • Michael R. Laurence, Georg Struth

      Pages 179-194

   3. Categories of Algebraic Contexts Equivalent to Idempotent Semirings and Domain Semirings

      • Peter Jipsen

      Pages 195-206

   4. Relational Representation Theorem for Powerset Quantales

      • Koki Nishizawa, Hitoshi Furusawa

      Pages 207-218

   5. Point Axioms in Dedekind Categories

      • Hitoshi Furusawa, Yasuo Kawahara

      Pages 219-234

6. Relations and Algorithms

   1. Two Observations in Dioid Based Model Refinement

      • Roland Glück

      Pages 235-247

   2. Relation Algebras, Matrices, and Multi-valued Decision Diagrams

      • Francis Atampore, Michael Winter

      Pages 248-263

   3. Incremental Pseudo Rectangular Organization of Information Relative to a Domain

      • Sahar Ismail, Ali Jaoua

      Pages 264-277

7. Preference Relations

   1. Relational Concepts in Social Choice

      • Gunther Schmidt

      Pages 278-293

This book constitutes the thoroughly refereed post-conference proceedings of the 13th International Conference on Relational and Algebraic Methods in Computer Science, RAMiCS 13, held in Cambridge, UK, in September 2012. The 23 revised full papers presented were carefully selected from 39 submissions in the general area of relational and algebraic methods in computer science, adding special focus on formal methods for software engineering, logics of programs and links with neighboring disciplines. The papers are structured in specific fields on applications to software specification and correctness, mechanized reasoning in relational algebras, algebraic program derivation, theoretical foundations, relations and algorithms, and properties of specialized relations.

• Isabelle
• Kleene algebra
• complex preferences
• functional programs
• graphs

• Department of Computing and Software, McMaster University, Hamilton, Canada

  Wolfram Kahl

• Computer Laboratory, University of Cambridge, Cambridge, UK

  Timothy G. Griffin

Policies and ethics