Post B6N1DQ4pyiaCR7FxlQ by kevin@fedi.kbg.sh
 (DIR) More posts by kevin@fedi.kbg.sh
 (DIR) Post #B6Mw4wiojjprJ064eG by kevin@fedi.kbg.sh
       0 likes, 0 repeats
       
       Somewhat niche question I’ve been wondering about:Consider the set of directed graphs with labeled nodes. What’s the largest subset that can be described with a linear, textual notation that implicitly represents edges? Which is to say, you can’t use node IDs or duplication to indicate an edge between nodes. 1/
       
 (DIR) Post #B6Mw4wxLrhSg24tgIq by kevin@fedi.kbg.sh
       0 likes, 0 repeats
       
       For example, we can obviously represent the set of n-ary trees using XML/S-Expression/JSON like notation.What’s less obvious though is that we can actually describe some kinds of DAGs using “improperly” nested XML-like tags. This is the basis of things like SGML’s CONCUR, and other systems of non hierarchical markup. E.g.<a>1<b>2</a>3</b>Where there’s edges from a to 1 and 2, and from b to 2 and 3. 2/
       
 (DIR) Post #B6Mw4xDIuODopYMQAS by kevin@fedi.kbg.sh
       0 likes, 0 repeats
       
       But can we do better than this kind of non-hierarchical markup? And is there a name for the class of graphs that can be notated with non-hierarchical markup?I can sort of imagine a scheme which can notate cycles without IDs by wrapping an acyclic structure in something which describes where the cycles are, but that’s sort of stretching my sense of “implicit” so I’m not going to allow it. 3/
       
 (DIR) Post #B6Mw4xPiAG99S2AKVU by wolf480pl@mstdn.io
       0 likes, 0 repeats
       
       @kevin considered on a purely textual level, </a> already kinda uses an ID to determine which opening tag it closes.I guess you could define it sth like:Pick a language that can be defined with a context-free grammar, then alter it in such a way that no finite automaton can tell the difference between the altered version and the original. What DAGs can you represent using that language?1/
       
 (DIR) Post #B6MwRz3QEOoHCQih1M by wolf480pl@mstdn.io
       0 likes, 0 repeats
       
       @kevin though that alone won't work without "don't use IDs" because I could just()()()(1 2)(2 3)(and adding "don't use IDs" rules out XML closing tags)Maybe "represent a graph in such a way that words that are in the original language represent their own parse trees" though that's not strict either, and possibly also overfitting :/
       
 (DIR) Post #B6N1DQ4pyiaCR7FxlQ by kevin@fedi.kbg.sh
       0 likes, 0 repeats
       
       @wolf480pl yeah these are all good points. I guess I’d say something like, “given N kinds of distinguishable sets of left and right brackets, what kinds of graphs can you represent?”