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, exist?


1 Answer 1


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.

  • $\begingroup$ 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 ;). $\endgroup$
    – Samdney
    Nov 7, 2023 at 21:52
  • $\begingroup$ 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. $\endgroup$
    – JimN
    Nov 8, 2023 at 0:21

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.