Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It is possible to define graphs $G$ such that whether an edge exists between two vertices $v_1$ and $v_2$ depends on non-local properties of $G$.

In particular, I am interested in directed graphs where an edge $(v_1, g(v_1, w))$ exists for each leaf vertex $w$ that is reachable from $f(v_1)$. Here, $f$ maps vertices to vertices, $g$ maps pairs of vertices to vertices.

Is there research on data structures and algorithms for working with such self-referentially defined graph structures?

share|cite|improve this question
For your example you must impose some restrictions of $f$ and $g$. If the set of vertices is $\{0,1\}$ and $f(x)=x$ and $g(x,y)=1-y$, then is $(0,1)$ an edge? – Radu GRIGore Mar 8 '12 at 17:20
@RaduGRIGore Right, the setup allows self-defeating and underspecified definitions. Any existing work that fills in $f$ and $g$ in consistent, non-trivial ways would be an answer to my question. – Andreas Mar 8 '12 at 17:51
I was recently thinking about self-referential paradoxes on graphs. nice question ! – Suresh Venkat Mar 8 '12 at 18:00
there are recursively defined graphs that exhibit self-similarity properties, e.g. the diamond graphs used for dimension reduction lower bounds: – Sasho Nikolov Mar 8 '12 at 21:51

"Dangerous reference graphs and semantic paradoxes", Rabern, Rabern & Macauley, Journal of Philosophical Logic.Here

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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