<p>I assume you mean that you want to represent a <strong>set</strong> of binary strings with a graph or hypergraph (since you mention a binary tree which I think is a set of binary strings - a unique string for every root-to-leaf path, like a Huffman tree.)</p>
<p>The whole field of automata theory explores various graph (machine) models that can represent  (i.e. compute, i.e. decide which are and are not in a set of) strings. Pick up any textbook on computability theory and it will present Deterministic Finite Automata (DFAs), Non-deterministic ones (NFAs), variants of those, push-down automata (deterministic and non-deterministic), and Turing machines (which also have a graph representation).</p>
<p>A deBruijn graph is a special case of a DFA, one with a very specialized structure.</p>

CC BY-SA 4.0
2023-11-07T21:52:08.213Z
Thanks for the answer but I don't! mean automata. Yes, of course, you can say each possible state transition is a 0 or 1 value and considering all the state transitions, but that's not what I'm looking for, else I already would wrote this in my queston ;).
Samdney
CC BY-SA 4.0
2023-11-08T00:21:57.523Z
You included deBruijn graph, so I'm not sure what sort of structures you are looking for if you are saying that De Bruijn graphs are an example while DFAs are not.
JimN
CC BY-SA 4.0
2023-11-07T20:40:34.987Z
2023-11-07T20:40:34.987Z
JimN
<p>Let <span class="math-container">$\Sigma$</span> be the set <span class="math-container">$\{ 0, 1 \}$</span>, then the set of all finite binary strings of length <span class="math-container">$n$</span> is written as <span class="math-container">$\Sigma^{\star}_{n}$</span>.</p>
<p>Question: Which further ways of representing binary strings of length <span class="math-container">$n$</span> by a graph or hypergraph, apart from binary trees, De Bruijn graphs, or this <a href="https://yadda.icm.edu.pl/baztech/element/bwmeta1.element.baztech-c4bc6968-2775-4bda-81b3-1ecf3bca67e9/c/2018_2_art_02.pdf" rel="nofollow noreferrer">work here</a>, exist?</p>

<reference-request><graph-theory><graph-algorithms><application-of-theory>
Representation of binary strings by graphs and hypergraphs
Samdney
# Representation of binary strings by graphs and hypergraphs

(Asked by: username_0 on 2023-10-30)

Let $\Sigma$ be the set $\{ 0, 1 \}$, then the set of all finite binary strings of length $n$ is written as $\Sigma^{\star}\_{n}$.

Question: Which further ways of representing binary strings of length $n$ by a graph or hypergraph, apart from binary trees, De Bruijn graphs, or this [work here](https://yadda.icm.edu.pl/baztech/element/bwmeta1.element.baztech-c4bc6968-2775-4bda-81b3-1ecf3bca67e9/c/2018_2_art_02.pdf), exist?

**Tags:** reference-request, graph-theory, graph-algorithms, application-of-theory


---

## 1 answers

### Answer by username_1 on 2023-11-07. Score: 0

I assume you mean that you want to represent a **set** of binary strings with a graph or hypergraph (since you mention a binary tree which I think is a set of binary strings - a unique string for every root-to-leaf path, like a Huffman tree.)

The whole field of automata theory explores various graph (machine) models that can represent (i.e. compute, i.e. decide which are and are not in a set of) strings. Pick up any textbook on computability theory and it will present Deterministic Finite Automata (DFAs), Non-deterministic ones (NFAs), variants of those, push-down automata (deterministic and non-deterministic), and Turing machines (which also have a graph representation).

A deBruijn graph is a special case of a DFA, one with a very specialized structure.

> **Comments:**
> **username_0**: Thanks for the answer but I don't! mean automata. Yes, of course, you can say each possible state transition is a 0 or 1 value and considering all the state transitions, but that's not what I'm looking for, else I already would wrote this in my queston ;).  
> **username_1**: You included deBruijn graph, so I'm not sure what sort of structures you are looking for if you are saying that De Bruijn graphs are an example while DFAs are not.  

---

