An equational axiomatization of dynamic negation and relational composition

We consider algebras on binary relations with two main operators: relational composition and dynamic negation. Relational composition has its standard interpretation, while dynamic negation is an operator familiar to students of Dynamic Predicate Logic (DPL) (Groenendijk and Stokhof, 1991): given a relation R its dynamic negation R is a test that contains precisely those pairs (s,s) for which s is not in the domain of R. These two operators comprise precisely the propositional part of DPL.This paper contains a finite equational axiomatization for these dynamic relation algebras. The completenessresult uses techniques from modal logic. We also lookat the variety generated by the class of dynamic relation algebras and note that there exist nonrepresentable algebras in this variety, ones which cannot be construedas spaces of relations. These results are also proved for an extension to a signature containing atomic tests and union.
Keywords Dynamic Predicate Logic  relation algebra  modal logic  dynamic logic  finite axiomatization  bisimulation  unraveling  variety  representability
Categories (categorize this paper)
Reprint years 2004
DOI 10.1023/A:1008271805106
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 25,651
Through your library
References found in this work BETA

No references found.

Add more references

Citations of this work BETA
Sequential Dynamic Logic.Alexander Bochman & Dov M. Gabbay - 2012 - Journal of Logic, Language and Information 21 (3):279-298.

Add more citations

Similar books and articles
Dynamic Relation Logic is the Logic of DPL-Relations.Albert Visser - 1997 - Journal of Logic, Language and Information 6 (4):441-452.
Contexts in Dynamic Predicate Logic.Albert Visser - 1998 - Journal of Logic, Language and Information 7 (1):21-52.
PDL has Interpolation.Tomasz Kowalski - 2002 - Journal of Symbolic Logic 67 (3):933-946.
Sequential Dynamic Logic.Alexander Bochman & Dov M. Gabbay - 2012 - Journal of Logic, Language and Information 21 (3):279-298.
Dynamic Negation, the One and Only.Marco Hollenberg & Albert Visser - 1999 - Journal of Logic, Language and Information 8 (2):137-141.

Monthly downloads

Added to index


Total downloads

17 ( #273,822 of 2,143,510 )

Recent downloads (6 months)

1 ( #386,858 of 2,143,510 )

How can I increase my downloads?

My notes
Sign in to use this feature

There  are no threads in this forum
Nothing in this forum yet.

Other forums