Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

First of all, I'm looking for a book, publication, project or any kind of information that should probably exceed the limits normally imposed on answers in this kind of forum. I know the rules about not asking to advice a book, but hold your breath, don't vote to close yet.

I've been searching every place and returned empty-handed. Eventually I came across the mention of "Theory of data structures by relational and graph grammars" book, but I cannot find it. This book is really old, the author didn't continue the work in the same direction, instead he published several books related to programming practices rather then theory.

Well, I cannot believe that was the only book. Will you please help me find more?


The motivation, if you are interested. Through the course of last few years I was specifically trying to reach to any, even if very exotic languages to have a better idea of how they organize their system of data structures. The reason to do so was that the mainstream languages provide the programmers with very fragmented, not unified under any rigorous theory set of tools. Some try to build a hierarchy / heterarchy of things they put into that basket, but really, it's just random.

SQL has very nice theory (relational algebra) to back it up, alas, that doesn't include the very common things, like strings or lists etc. For some time I had a gut feeling that the general case of any data structure must be a graph and other data structures would be some kinds of either degenerate graph (list is an acyclic direct graph with the requirement that there should not be a vertex that connect more then one other vertex, etc.) or a "projection", like a two-dimensional relation.

I found several pages from the book I mentioned earlier, where the author expresses what I've taken to be the same / similar idea. But there must be more to it. Similar to how relational algebra defines a set of operations on relations, that book mentioned basic graph operations, but the details were lost.

share|improve this question

closed as off-topic by gnat, GlenH7, Bart van Ingen Schenau, Thomas Owens Feb 10 '14 at 20:16

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions asking us to recommend a tool, library or favorite off-site resource are off-topic for Programmers as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – gnat, GlenH7, Bart van Ingen Schenau, Thomas Owens
If this question can be reworded to fit the rules in the help center, please edit the question.

This may be a paper (by Valjich?) in a proceedings book. Look for Lecture Notes in Computer Science: Automata Languages and Programming, vol 52. It was published in 1977. ABEbooks has at least 8 copies ranging from $17 to $90+. –  mkennedy Aug 7 '13 at 16:30
@mkennedy thanks, unfortunately, there's a technical difficulty for me to order from therm... but that aside, this book is older then I am, and I want to believe that the ideas expressed in it lived and evolved. So I'd rather search for something newer. –  wvxvw Aug 7 '13 at 17:54

2 Answers 2

up vote 2 down vote accepted

Well, I cannot believe that was the only book. Will you please help me find more?

You are correct: graph rewriting is a whole research area in Computer Science, which has been developed over several decades and has a theoretical foundation as well as practical applications. The paper you have cited also refers to other authors / papers from the graph rewriting / graph transformation community.

The basic idea of graph rewriting / graph transformation is to transform a graph by finding a pattern and replacing it with a new subgraph. Since there are many possible ways of performing this kind of pattern-matching and substitution, there are many different approaches to graph transformation, with different expressive powers. Some of these are more useful in practical applications, while others are more interesting from a theoretical point of view, e.g. for generating sets of graphs.

Among the applications of this technique there is data structure modelling, picture generation, model transformation, and many others.

You can find a general introduction and several references to related books and publications in this wikipedia page.

share|improve this answer
Thanks, especially for the references, this is super useful! –  wvxvw Feb 12 '14 at 20:57

I cannot give you an actual pointer to the book you are looking for, but have you tried the computer science departments of a local university/college.

The one I went to had book sales bi-annually and I still go to see if I can find some rare books or not so popular publications. If you do not have access to a university in person, try contacting the librarians in person in search for books.

I used to work in the university library as a student and the librarians there were always glad to help point out or even search for papers and books. Most of the time with great success.

share|improve this answer
Ha, good call. In the time of interwebs... I think I've not been to a library in ages. Just didn't occur to me, but is a valid point :) –  wvxvw Aug 7 '13 at 8:09
Got to love the simple solutions ;) –  Ben McDougall Aug 7 '13 at 8:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.