# Distinguishing Views in Symmetric Networks: A Tight Lower Bound

2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers $n\geq D\geq 1$, there exists a port-labeled network with at most $n$ nodes and diameter at most $D$ which contains a pair of nodes whose (infinite) views are different, but whose views truncated to depth $\Omega(D\log (n/D))$ are identical.
Document type :
Journal articles

https://hal.inria.fr/hal-00875370
Submitted on : Sunday, March 8, 2015 - 2:50:37 PM
Last modification on : Wednesday, September 16, 2020 - 12:46:03 PM
Long-term archiving on: : Monday, April 17, 2017 - 4:08:17 AM

### Files

view.pdf
Files produced by the author(s)

### Citation

Dariusz Dereniowski, Adrian Kosowski, Dominik Pajak. Distinguishing Views in Symmetric Networks: A Tight Lower Bound. Theoretical Computer Science, Elsevier, 2015, 582, pp.27-34. ⟨10.1016/j.tcs.2015.03.018⟩. ⟨hal-00875370v3⟩

Record views