Graphs and Decidable Transductions based on Edge Constraints

Forfattere

  • Nils Klarlund
  • Michael I. Schwartzbach

DOI:

https://doi.org/10.7146/brics.v1i4.21666

Resumé

We give examples to show that not even c-edNCE, the most general known notion of context-free graph grammar, is suited for the specification of some common data structures.

To overcome this problem, we use monadic second-order logic and introduce edge constraints as a new means of specifying a large class of graph families. Our notion stems from a natural dichotomy found in programming practice between ordinary pointers forming spanning trees and auxiliary pointers cutting across.

Our main result is that for certain transformations of graphs definable in monadic second-order logic, the question of whether a graph family given by a specification A is mapped to a family given by a specification B is decidable. Thus a decidable Hoare logic arises.

Downloads

Publiceret

1994-02-03

Citation/Eksport

Klarlund, N., & Schwartzbach, M. I. (1994). Graphs and Decidable Transductions based on Edge Constraints. BRICS Report Series, 1(4). https://doi.org/10.7146/brics.v1i4.21666

Nummer

Nr. 4 (1994): RS-4 Graphs and Decidable Transductions based on Edge Constraints

Sektion

Artikler

Licens

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    1. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  1. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).