On Generalized Records and Spatial Conjunction in Role Logic

Details On Generalized Records and Spatial Conjunction in Role Logic On Generalized Records and Spatial Conjunction in Role Logic

2004-08-05

arxiv.org/abs/cs/0408019v1

Computer Science

Programming Languages

30 pages. A version appears in SAS 2004

Scientific paper

We have previously introduced role logic as a notation for describing properties of relational structures in shape analysis, databases and knowledge bases. A natural fragment of role logic corresponds to two-variable logic with counting and is therefore decidable. We show how to use role logic to describe open and closed records, as well the dual of records, inverse records. We observe that the spatial conjunction operation of separation logic naturally models record concatenation. Moreover, we show how to eliminate the spatial conjunction of formulas of quantifier depth one in first-order logic with counting. As a result, allowing spatial conjunction of formulas of quantifier depth one preserves the decidability of two-variable logic with counting. This result applies to two-variable role logic fragment as well. The resulting logic smoothly integrates type system and predicate calculus notation and can be viewed as a natural generalization of the notation for constraints arising in role analysis and similar shape analysis approaches.

Affiliated with

Also associated with

No associations

Rating

On Generalized Records and Spatial Conjunction in Role Logic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Generalized Records and Spatial Conjunction in Role Logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Generalized Records and Spatial Conjunction in Role Logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-500775