An equational axiomatization of dynamic negation and relational composition


Abstract
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
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 41,668
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Incremental Dynamics.Jan van Eijck - 2001 - Journal of Logic, Language and Information 10 (3):319-351.
Dynamic Relation Logic is the Logic of DPL-Relations.Albert Visser - 1997 - Journal of Logic, Language and Information 6 (4):441-452.
Sequential Dynamic Logic.Alexander Bochman & Dov M. Gabbay - 2012 - Journal of Logic, Language and Information 21 (3):279-298.
Some Modal Aspects of XPath.Balder ten Cate, Gaëlle Fontaine & Tadeusz Litak - 2010 - Journal of Applied Non-Classical Logics 20 (3):139-171.

View all 7 citations / 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.

Analytics

Added to PP index
2009-01-28

Total views
26 ( #318,654 of 2,250,064 )

Recent downloads (6 months)
3 ( #605,446 of 2,250,064 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature