Representing First Order Logic Using Graphs

Arend Rensink

doi:10.1007/978-3-540-30203-2_23

Representing First Order Logic Using Graphs

Arend Rensink

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

92 Citations (Scopus)

41 Downloads (Pure)

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.

Original language	Undefined
Title of host publication	Graph Transformations
Subtitle of host publication	Second International Conference, ICGT 2004, Rome, Italy, September 28–October 1, 2004. Proceedings
Editors	H Ehrig, G. Engels, F. Parisi-Presicce, G. Rozenberg
Publisher	Springer
Pages	319-335
Number of pages	17
ISBN (Electronic)	978-3-540-30203-2
ISBN (Print)	978-3-540-23207-0
DOIs	https://doi.org/10.1007/978-3-540-30203-2_23
Publication status	Published - 2004
Event	2nd International Conference on Graph Transformations, ICGT 2004 - Rome, Italy Duration: 28 Sept 2004 → 1 Oct 2004 Conference number: 2

Publication series

Name	Lecture notes in computer science
Volume	3256
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2nd International Conference on Graph Transformations, ICGT 2004
Abbreviated title	ICGT
Country/Territory	Italy
City	Rome
Period	28/09/04 → 1/10/04

Keywords

METIS-220508

Access to Document

10.1007/978-3-540-30203-2_23

Cite this

Rensink, A. (2004). Representing First Order Logic Using Graphs. In H. Ehrig, G. Engels, F. Parisi-Presicce, & G. Rozenberg (Eds.), Graph Transformations: Second International Conference, ICGT 2004, Rome, Italy, September 28–October 1, 2004. Proceedings (pp. 319-335). (Lecture notes in computer science; Vol. 3256). Springer. https://doi.org/10.1007/978-3-540-30203-2_23

@inproceedings{6b853a3f761a4a4892049a3fd602c8bf,

title = "Representing First Order Logic Using Graphs",

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.",

keywords = "METIS-220508",

author = "Arend Rensink",

year = "2004",

doi = "10.1007/978-3-540-30203-2_23",

language = "Undefined",

isbn = "978-3-540-23207-0",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "319--335",

editor = "H Ehrig and G. Engels and F. Parisi-Presicce and G. Rozenberg",

booktitle = "Graph Transformations",

address = "Germany",

note = "2nd International Conference on Graph Transformations, ICGT 2004 ; Conference date: 28-09-2004 Through 01-10-2004",

}

Rensink, A 2004, Representing First Order Logic Using Graphs. in H Ehrig, G Engels, F Parisi-Presicce & G Rozenberg (eds), Graph Transformations: Second International Conference, ICGT 2004, Rome, Italy, September 28–October 1, 2004. Proceedings. Lecture notes in computer science, vol. 3256, Springer, pp. 319-335, 2nd International Conference on Graph Transformations, ICGT 2004, Rome, Italy, 28/09/04. https://doi.org/10.1007/978-3-540-30203-2_23

Representing First Order Logic Using Graphs. / Rensink, Arend.
Graph Transformations: Second International Conference, ICGT 2004, Rome, Italy, September 28–October 1, 2004. Proceedings. ed. / H Ehrig; G. Engels; F. Parisi-Presicce; G. Rozenberg. Springer, 2004. p. 319-335 (Lecture notes in computer science; Vol. 3256).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Representing First Order Logic Using Graphs

AU - Rensink, Arend

N1 - Conference code: 2

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

KW - METIS-220508

U2 - 10.1007/978-3-540-30203-2_23

DO - 10.1007/978-3-540-30203-2_23

M3 - Conference contribution

SN - 978-3-540-23207-0

T3 - Lecture notes in computer science

SP - 319

EP - 335

BT - Graph Transformations

A2 - Ehrig, H

A2 - Engels, G.

A2 - Parisi-Presicce, F.

A2 - Rozenberg, G.

PB - Springer

T2 - 2nd International Conference on Graph Transformations, ICGT 2004

Y2 - 28 September 2004 through 1 October 2004

ER -