More Web Proxy on the site http://driver.im/

research-article

Taming Multirelations

Authors:

Hitoshi Furusawa,

Georg StruthAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 17, Issue 4

Article No.: 28, Pages 1 - 34

https://doi.org/10.1145/2964907

Published: 11 November 2016 Publication History

Abstract

Binary multirelations generalise binary relations by associating elements of a set to its subsets. We study the structure and algebra of multirelations under the operations of union, intersection, sequential, and parallel composition, as well as finite and infinite iteration. Starting from a set-theoretic investigation, we propose axiom systems for multirelations in contexts ranging from bi-monoids to bi-quantales.

References

[1]

R.-J. Back and J. von Wright. 1998. Refinement Calculus: A Systematic Introduction. Springer.

[2]

S. L. Bloom and Z. Ésik. 1996. Free shuffle algebras in language varieties. Theoretical Computer Science 163, 182 (1996), 55--98.

Digital Library

[3]

J. A. Brzozowski and E. L. Leiss. 1980. On equations for regular languages, finite automata, and sequential networks. Theoretical Computer Science 10 (1980), 19--35.

[4]

A. Cavalcanti, J. Woodcock, and S. Dunne. 2006. Angelic nondeterminism in the unifying theories of programming. Formal Aspects of Computing 18, 3 (2006), 288--307.

[5]

A. K. Chandra, D. Kozen, and L. J. Stockmeyer. 1981. Alternation. Journal of the ACM 28, 1 (1981), 114--133.

Digital Library

[6]

J. Desharnais, P. Jipsen, and G. Struth. 2009. Domain and antidomain semigroups. In RelMiCS 2009 (LNCS), R. Berghammer, A. Jaoua, and B. Möller (Eds.), Vol. 5827. Springer, 73--87.

Digital Library

[7]

J. Desharnais, B. Möller, and G. Struth. 2011. Algebraic notions of termination. Logical Methods in Computer Science 7, 1 (2011).

[8]

J. Desharnais and G. Struth. 2008. Domain axioms for a family of near-semirings. In AMAST 08 (LNCS), J. Meseguer and G. Rosu (Eds.), Vol. 5140. Springer, 330--345.

Digital Library

[9]

H. Furusawa, K. Nishizawa, and N. Tsumagari. 2009. Multirelational models of lazy, monodic tree and probabilistic Kleene algebras. Bulletin of Informatics and Cybernetics 41 (2009), 11--24.

[10]

H. Furusawa and G. Struth. 2015a. Binary multirelations. Archive of Formal Proofs (2015).

[11]

H. Furusawa and G. Struth. 2015b. Concurrent dynamic algebra. ACM Transactions on Computational Logic 16, 4 (2015), 30:1--30:38.

Digital Library

[12]

J. L. Gischer. 1988. The equational theory of pomsets. Theoretical Computer Science 61, 2--3 (1988), 199--224.

Digital Library

[13]

R. Goldblatt. 1992. Parallel action: Concurrent dynamic logic with independent modalities. Studia Logica 51, 3/4 (1992), 551--578.

[14]

T. Hoare, B. Möller, G. Struth, and I. Wehrman. 2011. Concurrent Kleene algebra and its foundations. Journal of Logical Algebraic Programming 80, 6 (2011), 266--296.

[15]

G. M. Kelly. 1982. Basic concepts of enriched category theory. LMS Lecture Notes Series 64 (1982).

[16]

R. D. Maddux. 2006. Relation Algebras. Elsevier.

[17]

C. E. Martin, S. A. Curtis, and I. Rewitzky. 2007. Modelling angelic and demonic nondeterminism with multirelations. Science of Computer Programming 65, 2 (2007), 140--158.

Digital Library

[18]

D. Monk. 1964. On representable relation algebras. The Michigan Mathematical Journal 11 (1964), 207--210.

[19]

A. Nerode and D. Wijesekera. 1990. Constructive Concurrent Dynamic Logic I. Technical Report 90-43. Mathematical Sciences Institute, Cornell University.

[20]

T. Nipkow, L. C. Paulson, and M. Wenzel. 2002. Isabelle/HOL - A Proof Assistant for Higher-Order Logic. LNCS, Vol. 2283. Springer.

Digital Library

[21]

K. Nishizawa, N. Tsumagari, and H. Furusawa. 2009. The cube of Kleene algebras and the triangular prism of multirelations. In Relational Methods in Computer Science (LNCS), R. Berghammer, A. Jaoua, and B. Möller (Eds.), Vol. 5827. Springer, 276--290.

Digital Library

[22]

R. Parikh. 1983. Propositional game logic. In FOCS. IEEE Computer Society, 195--200.

Digital Library

[23]

R. Parikh. 1985. The logic of games and its applications. In Topics in the Theory of Computation (Mathematics Studies), M. Karpinsky and J. van Leeuwen (Eds.), Vol. 102. North-Holland, 111--135.

Digital Library

[24]

D. M. P. Park. 1981. Concurrency and automata on infinite sequences. In Theoretical Computer Science (LNCS), P. Deussen (Ed.), Vol. 104. Springer, 167--183.

Digital Library

[25]

M. Pauly and R. Parikh. 2003. Game logic - an overview. Studia Logica 75, 2 (2003), 165--182.

[26]

D. Peleg. 1987a. Communication in concurrent dynamic logic. Journal of Computer System Science 35 (1987), 23--58.

Digital Library

[27]

D. Peleg. 1987b. Concurrent dynamic logic. Journal of the ACM 34, 2 (1987), 450--479.

Digital Library

[28]

I. Rewitzky. 2003. Binary multirelations. In Theory and Applications of Relational Structures as Knowledge Instruments (LNCS), H. C. M. de Swart, E. Orlowska, G. Schmidt, and M. Roubens (Eds.), Vol. 2929. Springer, 256--271.

[29]

I. Rewitzky and C. Brink. 2006. Monotone predicate transformers as up-closed multirelations. In Relations and Kleene Algebra in Computer Science (LNCS), R. A. Schmidt (Ed.), Vol. 4136. Springer, 311--327.

Digital Library

[30]

G. Struth. 2012. Left omega algebras and regular equations. Journal of Logical and Algebraic Programming 81, 6 (2012), 705--717.

[31]

J. van Benthem, S. Ghosh, and F. Liu. 2008. Modelling simultaneous games in dynamic logic. Synthese 165, 2 (2008), 247--268.

[32]

D. Wijesekera and A. Nerode. 2005. Tableaux for constructive concurrent dynamic logic. Annals Pure and Applied Logic 135, 1--3 (2005), 1--72.

Cited By

Furusawa HGuttmann WStruth G(2024)Modal algebra of multirelationsJournal of Logic and Computation10.1093/logcom/exae023Online publication date: 28-May-2024
https://doi.org/10.1093/logcom/exae023
Furusawa HGuttmann WStruth G(2024)Determinism of multirelationsJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2024.100976139(100976)Online publication date: Jun-2024
https://doi.org/10.1016/j.jlamp.2024.100976
Gomes L(2019)On the Construction of Multi-valued Concurrent Dynamic LogicsDynamic Logic. New Trends and Applications10.1007/978-3-030-38808-9_14(218-226)Online publication date: 7-Oct-2019
https://dl.acm.org/doi/10.1007/978-3-030-38808-9_14
Show More Cited By

Index Terms

Taming Multirelations
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Computer algebra systems
      1. Special-purpose algebraic systems
2. Theory of computation

Recommendations

The Cube of Kleene Algebras and the Triangular Prism of Multirelations
RelMiCS '09/AKA '09: Proceedings of the 11th International Conference on Relational Methods in Computer Science and 6th International Conference on Applications of Kleene Algebra: Relations and Kleene Algebra in Computer Science

We refine and extend the known results that the set of ordinary binary relations forms a Kleene algebra, the set of up-closed multirelations forms a lazy Kleene algebra, the set of up-closed finite multirelations forms a monodic tree Kleene algebra, and ...
Modelling angelic and demonic nondeterminism with multirelations

This paper presents an introduction to a calculus of binary multirelations, which can model both angelic and demonic kinds of non-determinism. The isomorphism between up-closed multirelations and monotonic predicate transformers allows a different view ...
Monotone predicate transformers as up-closed multirelations
RelMiCS'06/AKA'06: Proceedings of the 9th international conference on Relational Methods in Computer Science, and 4th international conference on Applications of Kleene Algebra

In the study of semantic models for computations two independent views predominate: relational models and predicate transformer semantics. Recently the traditional relational view of computations as binary relations between states has been generalised ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 17, Issue 4

November 2016

292 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/2996393

Editor:
Orna Kupferman
School of Computer Science and Engineering, Hebrew University, Israel

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 November 2016

Accepted: 01 June 2016

Received: 01 June 2015

Published in TOCL Volume 17, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

Algebras of multirelations

Qualifiers

Research-article
Research
Refereed

Funding Sources

Royal Society and JSPS KAKENHI

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
124
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Furusawa HGuttmann WStruth G(2024)Modal algebra of multirelationsJournal of Logic and Computation10.1093/logcom/exae023Online publication date: 28-May-2024
https://doi.org/10.1093/logcom/exae023
Furusawa HGuttmann WStruth G(2024)Determinism of multirelationsJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2024.100976139(100976)Online publication date: Jun-2024
https://doi.org/10.1016/j.jlamp.2024.100976
Gomes L(2019)On the Construction of Multi-valued Concurrent Dynamic LogicsDynamic Logic. New Trends and Applications10.1007/978-3-030-38808-9_14(218-226)Online publication date: 7-Oct-2019
https://dl.acm.org/doi/10.1007/978-3-030-38808-9_14
Furusawa HKawahara YStruth GTsumagari N(2017)Kleisli, Parikh and Peleg compositions and liftings for multirelationsJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2017.04.00290(84-101)Online publication date: Aug-2017
https://doi.org/10.1016/j.jlamp.2017.04.002
Berghammer RGuttmann W(2017)An algebraic approach to multirelations and their propertiesJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2017.02.00288(45-63)Online publication date: Apr-2017
https://doi.org/10.1016/j.jlamp.2017.02.002

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents