Relational and Algebraic Methods in Computer Science
12th International Conference, RAMICS 2011, Rotterdam, The Netherlands, May 30--June 3, 2011, Proceedings
Published on 7. June 2011
VIII, 363 pages
978-3-642-21070-9 (ISBN)
Description
This book constitutes the proceedings of the 12 International Conference on Relational and Algebraic Methods in Computer Science, RAMICS 2011, held in Rotterdam, The Netherlands, in May/June 2011.
This conference merges the RelMICS (Relational Methods in Computer Science) and AKA (Applications of Kleene Algebra) conferences, which have been a main forum for researchers who use the calculus of relations and similar algebraic formalisms as methodological and conceptual tools. Relational and algebraic methods and software tools turn out to be useful for solving problems in social choice and game theory. For that reason this conference included a special track on Computational Social Choice and Social Software. The 18 papers included were carefully reviewed and selected from 27 submissions. In addition the volume contains 2 invited tutorials and 5 invited talks.
More details
Other editions
Additional editions
Harrie de Swart
Relational and Algebraic Methods in Computer Science
12th International Conference, RAMICS 2011, Rotterdam, The Netherlands, May 30--June 3, 2011, Proceedings
Book
05/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Building Structured Theories
- Introduction
- Theories and Definitions
- Sequential Composition
- Annihilation
- Characterising Failure
- Further Aspects of Sequential Composition
- Concurrency
- The Frame Rule and Separation Logic
- Choice
- Choice and Composition: Idempotent Semirings
- Converse and Relation Algebra
- Iteration
- Tests: Modelling Sets of States
- Domain and Antidomain
- Modal Operators: Diamond and Box
- Logics of Knowledge and Belief
- Quantales and Temporal Logics
- Conclusion and Outlook
- References
- Social Networks: Prestige, Centrality, and Influence
- Introduction
- The Basic Concepts in Network Theory
- Different Measures of Centrality in Networks
- Degree Centrality
- Closeness Centrality
- Betweenness Centrality
- Prestige- and Eigenvector-Related Centrality Measures
- Categorizing Centrality Measures by a Topology of Network Flows
- The Model of Influence in a Social Network
- The Hoede-Bakker Index
- The Influence Indices
- Followers and Kernel
- Further Research on Influence
- Relation-Algebraic Preliminaries
- Applying Relation Algebra to the Model of Influence
- Modeling the Inclination and Decision Vectors
- Computing the Group Decisions
- Computing the Hoede-Bakker Index
- Computing the Influence Indices
- Computing the Sets of Followers
- Concluding Remarks
- References
- Synthesising Terminating Tableau Calculi for Relational Logics
- Introduction
- Tableau Calculus Synthesis
- Tableau Calculus Refinement
- Adding Blocking
- Applying the Framework
- Concluding Remarks
- References
- From Arrow's Impossibility to Schwartz's Tournament Equilibrium Set
- References
- Automated Engineering of Relational and Algebraic Methods in Isabelle/HOL
- Introduction
- Isabelle/HOL
- Implementing a Kleene Algebra Hierarchy
- Integrating Relation Algebras
- Automated Algebraic Proofs with Isabelle
- Higher-Order Features
- Abstract versus Set-Theoretic Classes
- Integrated Point-Wise and Point-Free Reasoning
- Future Directions
- Conclusion
- References
- Explaining Voting Paradoxes
- Including Arrow's and Sen's Theorems
- References
- Relation Algebraic Approaches to Fuzzy Relations
- References
- A First-Order Calculus for Allegories
- Introduction
- Relational Preliminaries
- A First-Order Language for Allegories
- Syntax
- Semantics
- A First-Order Calculus
- The System RelAPS
- A Short Tour through the System
- Conclusion and Future Work
- References
- Relational Modelling and Solution of Chessboard Problems
- Introduction
- Relation Algebra and RelView
- Chessboard Independence and Domination Problems
- Computation of Independent and Dominating Sets
- Computation of Chessboard Relations
- Experimental Results Concerning Independence
- Proof of the Bishops Independence Number
- Conclusion
- References
- A Functional, Successor List Based Version of Warshall's Algorithm with Applications
- Introduction
- Relation-Algebraic Preliminaries
- Transitive Closures and Warshall's Algorithm
- Computing Transitive Closures Using Relation Algebra
- From Relation Algebra to Successor Functions
- From Successor Functions to Lists of Sets
- From Lists of Sets to List of Lists and Haskell
- Some Graph-Theoretic Applications
- Concluding Remarks
- References
- Variable Side Conditions and Greatest Relations in Algebraic Separation Logic
- Introduction
- The Frame Rule and the Set of Modified Variables
- Algebraic Separation Logic
- States: Compatibility and Splitting
- The Frame Rule Algebraically
- Variable Preservation and Variable Side Conditions
- Variable Conditions in Information Hiding
- A Relational Treatment of a Queue Module
- Greatest Local Relations
- Related Work
- Conclusion and Outlook
- References
- An Algebraic Approach to Preference Relations
- Introduction
- Definitions and Notation
- Preference Frames and Preference Algebras
- The Complex Algebra of a Preference Frame
- The Canonical Frame of a Preference Algebra
- The Duality Result
- Conclusion and Outlook
- References
- Relational and Multirelational Representation Theorems for Complete Idempotent Left Semirings
- Introduction
- Complete Idempotent Left Semirings
- Relational Representation Theorem
- Multirelational Representation Theorem
- CCPA Complete IL-semiring and Multirelational Complete IL-semiring
- Conclusion
- References
- Using Bisimulations for Optimality Problems in Model Refinement
- Introduction
- General Ideas
- Recent Work
- Overview
- Dioids and Models
- Dioids and Cumulative Dioids
- Models and Costs
- Optimality in Models
- Models with Cumulative S-Dioids
- Models with Non-cumulative S-Dioids
- Bisimulations
- Basic Definitions
- Quotient and Expansion
- Application to Optimality
- Putting the Pieces Together
- Applicability and Efficiency
- Conclusion and Further Work
- References
- Pathfinding through Congruences
- Introduction
- Internet Pathfinding in the Abstract
- Congruences
- Applications in Routing
- Forbidden Paths
- Only Simple Paths
- Algebraic Correctness in Finite Structures
- Conclusion
- References
- Towards a Typed Omega Algebra
- Introduction
- Axioms
- Omega Algebra
- 1-Free Omega Algebra
- Typed 1-Free Omega Algebra
- Matrices
- Matrices over Typed 1-Free Omega Algebra
- Matrices in General Correctness
- Matrices in Total and General Correctness
- Typing
- Embedding 1-Free Omega Algebra into Omega Algebra
- Embedding Typed 1-Free Omega Algebra into 1-Free Omega Algebra
- Conclusion
- References
- Towards an Algebra of Routing Tables
- Introduction
- AODV and Its Design Challenges
- Overview of AODV
- Basic Protocol
- Algebraic Approaches for Routing Protocols
- Semirings, Kleene Algebras and Extensions
- Routes and Routing Tables
- AODV Control Messages Algebraically
- Conclusion and Outlook
- References
- Dependently-Typed Formalisation of Relation-Algebraic Abstractions
- Introduction
- Introduction to Agda: Types, Sets, Equality
- Generalised Heterogeneous Concrete Relations
- Semigroupoids, Categories, Allegories, Collagories
- Domain
- Restricted Residuals
- Generalised Algebras
- Related Work
- Conclusion
- References
- Omega Algebras and Regular Equations
- Introduction
- Left Omega Algebras
- Languages, Relations and Traces
- Conditions for Defining Omega
- Arden's Rule Abstractly
- Omega and Regular Languages
- Soundness and Completeness for Regular Languages
- Omega and Traces
- Omega and Relations
- Conclusion and Future Work
- References
- On Probabilistic Kleene Algebras, Automata and Simulations
- Introduction
- Probabilistic Kleene Algebras
- An Automata-Based Model
- Automata Labelled by Terms
- A Completeness Result
- Conclusion
- References
- Ampersand
- Introduction
- Language for Requirements
- Ampersand
- Syntax
- Semantics
- Type System
- Feedback System
- Error Messages
- Demonstration
- Conclusions and Further Research
- References
- Programming from Galois Connections
- Introduction
- Galois Connections as Program Specifications
- Calculating Galois Adjoints
- The ``Shrink'' Operator
- Properties of Shrinking
- Inductive Relations
- Program Calculation by Optimization - ``Shrinking Specs into Programs
- Example of Greedy Programming
- Example of DP-Programming
- Case Study: Scheduling as a Galois Connection
- Conclusions and Future Work
- References
- Constructions around Partialities
- Introduction
- Synoptic Regions
- Relation-Algebraic Preliminaries
- Two Elementary Constructions
- Row- Resp. Column-Less Relations
- Existential Images
- The 1-Element Boolean Lattice and Non-connectedness
- Direct Sum Construction
- Lifting Relations to Partialities
- Concluding Remark
- References
- Splitting Atoms in Relational Algebras
- Introduction
- Relation Algebras
- Atom Structures and Complex Algebras
- Splitting Atoms in Relation Algebra
- The Extension of a Relation Algebra
- Further Examples
- Conclusion and Outlook
- References
- Relational Heterogeneity Relaxed by Subtyping
- Introduction
- Goal
- Result
- Definitions
- Heterogeneous Relation Calculus
- Adding Supertyping
- Adapting the Operations
- New Composition
- New Order
- Interfaces
- Example
- Application in Ampersand
- Conclusion
- References
- Author Index
