0
$\begingroup$

Let GRAPHS be the set of all directed graphs.

Is there a set of strings STRYNGS such that there exists a bijection between GRAPHS and STRYNGS?

The canonical definition of directed graph comes to mind:
An ordered pair of two sets, (V, E) such that V is a set of vertices and E is a set of ordered pairs of elements in V.

Perhaps the following string is in the set of strings:

(  {0, 1, 2} ,    {(0, 1), (1, 0), (1, 2), (2, 0)}   )

Maybe we can use Zermelo's definition of natural number:

1 = { }     
2 = {{ }}      
3 = {{{ }}} 
and so on...

The following two graphs are isomorphic:

(  {0, 1, 2} ,    {(0, 1), (1, 0), (1, 2), (2, 0)}   )
(  {9, 5, 3} ,    {(9, 5), (5, 9), (5, 3), (3, 9)}   )

STRYNGS need not contain all graphs per se, but merely at least one representative from each equivalence class defined by the graph isomorphism relation.

If there there exists such set of strings STRYNGS, and there exists a bijection between the strings and the set of digraphs GRAPHS, does there also exist a grammar describing STRYNGS?

The grammar can be Context-sensitive, context-free or otherwise; any kind of grammar will do.

$\endgroup$
  • $\begingroup$ Just in case you have not noticed, unrestricted grammar is equivalent to Turing machines. $\endgroup$ – Apass.Jack Jan 6 at 3:14
  • $\begingroup$ With respect to the above comment, I recommend that you update your question to "does there exist a context-sensitive grammar that describes STRYNGS?". $\endgroup$ – Apass.Jack Jan 6 at 3:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.