Representing First-Order Logic Using Graphs


Share/Save/Bookmark

Rensink, A. (2004) Representing First-Order Logic Using Graphs. In: International Conference on Graph Transformations (ICGT).

[img]
Preview
PDF
321Kb
Abstract:Abstract. We show how edge-labelled graphs can be used to represent first-order logic formulae. This gives rise to recursively nested structures, in which each level of nesting corresponds to the negation of a set of existentials. The model is a direct generalisation of the negative application conditions used in graph rewriting, which count a single level of nesting and are thereby shown to correspond to the fragment ∃¬∃ of first-order logic. Vice versa, this generalisation may be used to strengthen the notion of application conditions. We then proceed to show how these nested models may be flattened to (sets of) plain graphs, by allowing some structure on the labels. The resulting formulae-as-graphs may form the basis of a unification of the theories of graph transformation and predicate transformation.
Item Type:Conference or Workshop Item
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/66358
Official URL:http://dx.doi.org/10.1007/b100934
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page