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?

  • 1
    $\begingroup$ 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? $\endgroup$ – Radu GRIGore Mar 8 '12 at 17:20
  • $\begingroup$ @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. $\endgroup$ – Andreas Mar 8 '12 at 17:51
  • $\begingroup$ I was recently thinking about self-referential paradoxes on graphs. nice question ! $\endgroup$ – Suresh Venkat Mar 8 '12 at 18:00
  • $\begingroup$ there are recursively defined graphs that exhibit self-similarity properties, e.g. the diamond graphs used for dimension reduction lower bounds: www.cs.washington.edu/homes/jrl/papers/diamond1.pdf $\endgroup$ – Sasho Nikolov Mar 8 '12 at 21:51

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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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