Representing First Order Logic Using Graphs

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    91 Citations (Scopus)
    6 Downloads (Pure)


    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 languageUndefined
    Title of host publicationGraph Transformations
    Subtitle of host publicationSecond International Conference, ICGT 2004, Rome, Italy, September 28–October 1, 2004. Proceedings
    EditorsH Ehrig, G. Engels, F. Parisi-Presicce, G. Rozenberg
    Number of pages17
    ISBN (Electronic)978-3-540-30203-2
    ISBN (Print)978-3-540-23207-0
    Publication statusPublished - 2004
    Event2nd International Conference on Graph Transformations, ICGT 2004 - Rome, Italy
    Duration: 28 Sept 20041 Oct 2004
    Conference number: 2

    Publication series

    NameLecture notes in computer science
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference2nd International Conference on Graph Transformations, ICGT 2004
    Abbreviated titleICGT


    • METIS-220508

    Cite this