<p>"Dangerous reference graphs and semantic paradoxes", Rabern, Rabern &amp; Macauley, Journal of Philosophical Logic.<a href="http://philpapers.org/rec/RABDRG">Here</a></p>

<p><a href="http://philpapers.org/rec/RABDRG">http://philpapers.org/rec/RABDRG</a></p>

CC BY-SA 3.0
2012-12-02T18:34:12.120Z
2012-12-02T18:34:12.120Z
atkinson
<p>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$. </p>

<p>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.</p>

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

CC BY-SA 3.0
2012-03-08T17:20:28.223Z
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
CC BY-SA 3.0
2012-03-08T17:51:19.797Z
@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
CC BY-SA 3.0
2012-03-08T18:00:38.943Z
I was recently thinking about self-referential paradoxes on graphs. nice question !
Suresh Venkat
CC BY-SA 3.0
2012-03-08T21:51:11.493Z
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
Sasho Nikolov
<graph-theory><graph-algorithms><ds.data-structures>
Self-referentially defined graph structures
Andreas
# Self-referentially defined graph structures

(Asked by: username_0 on 2012-03-08)

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?

**Tags:** graph-theory, graph-algorithms, ds.data-structures

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  
> **username_2**: I was recently thinking about self-referential paradoxes on graphs. nice question !  
> **username_3**: 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  

---

## 1 answers

### Answer by username_4 on 2012-12-02. Score: 5

"Dangerous reference graphs and semantic paradoxes", Rabern, Rabern & Macauley, Journal of Philosophical Logic.[Here](http://philpapers.org/rec/RABDRG)

<http://philpapers.org/rec/RABDRG>


---

