How much are your geraniums? Taking graph conditions beyond first Order

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

2 Downloads (Pure)

Abstract

Previous work has shown how first-order logic can equivalently be expressed through nested graph conditions, also called condition trees, with surprisingly few ingredients. In this paper, we extend condition trees by adding set-based operators such as sums and products, calculated over operands that are themselves characterised by first-order logic formulas. This provides a greatly improved way to specify computations such as: given that the price of a geranium plant equals 2 per flower petal, return the average price of all geraniums with at least one flower. We claim the same level of expressive equivalence as before between (extended) condition trees and a certain class of logic formulas; we show that the latter go beyond what can be expressed in first-order logic. On the practical side, we evaluate the performance and usability of set-based operators by specifying and comparing the example geranium property, with and without set-based operators, in the graph transformation tool GROOVE.

Original languageEnglish
Title of host publicationModelEd, TestEd, TrustEd
Subtitle of host publicationEssays Dedicated to Ed Brinksma on the Occasion of His 60th Birthday
EditorsJoost-Pieter Katoen, Rom Langerak, Arend Rensink
PublisherSpringer
Pages191-213
Number of pages23
Volume10500 LNCS
ISBN (Print)9783319682693
DOIs
Publication statusPublished - 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10500 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Fingerprint

First-order Logic
First-order
Graph in graph theory
Operator
Graph Transformation
Usability
Equivalence
Logic
Evaluate

Cite this

Rensink, A. (2017). How much are your geraniums? Taking graph conditions beyond first Order. In J-P. Katoen, R. Langerak, & A. Rensink (Eds.), ModelEd, TestEd, TrustEd: Essays Dedicated to Ed Brinksma on the Occasion of His 60th Birthday (Vol. 10500 LNCS, pp. 191-213). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10500 LNCS). Springer. https://doi.org/10.1007/978-3-319-68270-9_10
Rensink, Arend. / How much are your geraniums? Taking graph conditions beyond first Order. ModelEd, TestEd, TrustEd: Essays Dedicated to Ed Brinksma on the Occasion of His 60th Birthday. editor / Joost-Pieter Katoen ; Rom Langerak ; Arend Rensink. Vol. 10500 LNCS Springer, 2017. pp. 191-213 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inbook{2bb05ccac82a403c968fb4a9280878b7,
title = "How much are your geraniums? Taking graph conditions beyond first Order",
abstract = "Previous work has shown how first-order logic can equivalently be expressed through nested graph conditions, also called condition trees, with surprisingly few ingredients. In this paper, we extend condition trees by adding set-based operators such as sums and products, calculated over operands that are themselves characterised by first-order logic formulas. This provides a greatly improved way to specify computations such as: given that the price of a geranium plant equals 2 per flower petal, return the average price of all geraniums with at least one flower. We claim the same level of expressive equivalence as before between (extended) condition trees and a certain class of logic formulas; we show that the latter go beyond what can be expressed in first-order logic. On the practical side, we evaluate the performance and usability of set-based operators by specifying and comparing the example geranium property, with and without set-based operators, in the graph transformation tool GROOVE.",
author = "Arend Rensink",
year = "2017",
doi = "10.1007/978-3-319-68270-9_10",
language = "English",
isbn = "9783319682693",
volume = "10500 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "191--213",
editor = "Joost-Pieter Katoen and Rom Langerak and Arend Rensink",
booktitle = "ModelEd, TestEd, TrustEd",

}

Rensink, A 2017, How much are your geraniums? Taking graph conditions beyond first Order. in J-P Katoen, R Langerak & A Rensink (eds), ModelEd, TestEd, TrustEd: Essays Dedicated to Ed Brinksma on the Occasion of His 60th Birthday. vol. 10500 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10500 LNCS, Springer, pp. 191-213. https://doi.org/10.1007/978-3-319-68270-9_10

How much are your geraniums? Taking graph conditions beyond first Order. / Rensink, Arend.

ModelEd, TestEd, TrustEd: Essays Dedicated to Ed Brinksma on the Occasion of His 60th Birthday. ed. / Joost-Pieter Katoen; Rom Langerak; Arend Rensink. Vol. 10500 LNCS Springer, 2017. p. 191-213 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10500 LNCS).

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

TY - CHAP

T1 - How much are your geraniums? Taking graph conditions beyond first Order

AU - Rensink, Arend

PY - 2017

Y1 - 2017

N2 - Previous work has shown how first-order logic can equivalently be expressed through nested graph conditions, also called condition trees, with surprisingly few ingredients. In this paper, we extend condition trees by adding set-based operators such as sums and products, calculated over operands that are themselves characterised by first-order logic formulas. This provides a greatly improved way to specify computations such as: given that the price of a geranium plant equals 2 per flower petal, return the average price of all geraniums with at least one flower. We claim the same level of expressive equivalence as before between (extended) condition trees and a certain class of logic formulas; we show that the latter go beyond what can be expressed in first-order logic. On the practical side, we evaluate the performance and usability of set-based operators by specifying and comparing the example geranium property, with and without set-based operators, in the graph transformation tool GROOVE.

AB - Previous work has shown how first-order logic can equivalently be expressed through nested graph conditions, also called condition trees, with surprisingly few ingredients. In this paper, we extend condition trees by adding set-based operators such as sums and products, calculated over operands that are themselves characterised by first-order logic formulas. This provides a greatly improved way to specify computations such as: given that the price of a geranium plant equals 2 per flower petal, return the average price of all geraniums with at least one flower. We claim the same level of expressive equivalence as before between (extended) condition trees and a certain class of logic formulas; we show that the latter go beyond what can be expressed in first-order logic. On the practical side, we evaluate the performance and usability of set-based operators by specifying and comparing the example geranium property, with and without set-based operators, in the graph transformation tool GROOVE.

UR - http://www.scopus.com/inward/record.url?scp=85032689383&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-68270-9_10

DO - 10.1007/978-3-319-68270-9_10

M3 - Chapter

SN - 9783319682693

VL - 10500 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 191

EP - 213

BT - ModelEd, TestEd, TrustEd

A2 - Katoen, Joost-Pieter

A2 - Langerak, Rom

A2 - Rensink, Arend

PB - Springer

ER -

Rensink A. How much are your geraniums? Taking graph conditions beyond first Order. In Katoen J-P, Langerak R, Rensink A, editors, ModelEd, TestEd, TrustEd: Essays Dedicated to Ed Brinksma on the Occasion of His 60th Birthday. Vol. 10500 LNCS. Springer. 2017. p. 191-213. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-68270-9_10