Eingang zum Volltext
Lizenz
Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:kobv:83-opus-31269
URL: http://opus.kobv.de/tuberlin/volltexte/2011/3126/
Dodds, Mike ; Plump, Detlef
define classes of graph-like structures. In this paper, we relate the different formalisms by effectively translating restricted hyperedge-replacement grammars into formulas of a fragment of separation-logic with recursive predicates, and vice versa. The translations preserve the classes of specified graphs, and hence the two approaches are of equivalent power. It follows that our fragment of separation-logic
inherits properties of hyperedge-replacement grammars, such as inexpressibility results. We also show that several operators of full separation logic cannot be expressed using hyperedge replacement.
URN: urn:nbn:de:kobv:83-opus-31269
URL: http://opus.kobv.de/tuberlin/volltexte/2011/3126/
Dodds, Mike ; Plump, Detlef
From Hyperedge Replacement to Separation Logic and Back
| pdf-Format: |
|
Kurzfassung in Englisch
Hyperedge-replacement grammars and separation-logic formulas bothdefine classes of graph-like structures. In this paper, we relate the different formalisms by effectively translating restricted hyperedge-replacement grammars into formulas of a fragment of separation-logic with recursive predicates, and vice versa. The translations preserve the classes of specified graphs, and hence the two approaches are of equivalent power. It follows that our fragment of separation-logic
inherits properties of hyperedge-replacement grammars, such as inexpressibility results. We also show that several operators of full separation logic cannot be expressed using hyperedge replacement.
| Freie Schlagwörter (englisch): | hyperedge replacement , separation logic , graph grammars , program verification , graph transformation | |
| Collection | TU Berlin / Zeitschriften / Fakultät IV - Elektrotechnik und Informatik / Electronic Communications of the EASST- ECEASST / Volume 16 (2009): International Conference on Graph Transformation 2008 - Doctoral Symposium | |
| Institut: | Institut für Softwaretechnik und Theoretische Informatik | |
| DDC-Sachgruppe: | Informatik | |
| Dokumentart: | Aufsatz | |
| Schriftenreihe: | Electronic Communications of the EASST- ECEASST | |
| Band Nummer: | 16/02 | |
| ISBN: | 1863-2122 | |
| Quelle: | http://journal.ub.tu-berlin.de/eceasst/article/view/237 | |
| Sprache: | Englisch | |
| Erstellungsjahr: | 2009 | |
| Publikationsdatum: | 10.08.2011 | |
| Lizenz: | Standardlizenz: Typ CC by-nc-sa - Namensnennung erforderlich | Kommerziell nein | Weiterbearbeitung nur unter gleichen Bedingungen erlaubt | PoD ja |
