6
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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
    Commented Mar 8, 2012 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
    Commented Mar 8, 2012 at 17:51
  • $\begingroup$ I was recently thinking about self-referential paradoxes on graphs. nice question ! $\endgroup$
    – Suresh Venkat
    Commented Mar 8, 2012 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
    Commented Mar 8, 2012 at 21:51

1 Answer 1

Reset to default
5
$\begingroup$

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

http://philpapers.org/rec/RABDRG

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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