Theme One Program • Exposition 3

Coding Logical Graphs

My earliest experiments coding logical graphs as dynamic “pointer” data structures taught me that conceptual and computational efficiencies of a critical sort could be achieved by generalizing their abstract graphs from trees to the variety graph theorists know as cacti.  The genesis of that generalization is a tale worth telling another time, but for now it’s best to jump right in and proceed by way of generic examples.

Figure 1 shows a typical example of a painted and rooted cactus.

Painted And Rooted Cactus

Figure 2 shows a way to visualize the correspondence between cactus graphs and cactus strings, demonstrated on the cactus from Figure 1.  By way of convenient terminology, the polygons of a cactus graph are called its lobes.  An edge not part of a larger polygon is called a 2‑gon or a bi‑gon.  A terminal bi‑gon is called a spike.

Cactus Graph and Cactus Expression

The correspondence between a cactus graph and a cactus string is obtained by an operation called traversing the graph in question.

  • One traverses a cactus graph by beginning at the left hand side of the root node, reading off the list of paints one encounters at that point.  Since the order of elements at any node is not significant, one may start the cactus string with that list of paints or save them for the end.  We have done the latter in this case.
  • One continues by climbing up the left hand side of the leftmost lobe, marking the ascent by means of a left parenthesis, traversing whatever cactus one happens to reach at the first node above the root, that done, proceeding from left to right along the top side of the lobe, marking each interlobal span by means of a comma, traversing each cactus in turn one meets along the way, on completing the last of them climbing down the right hand side of the lobe, marking the descent by means of a right parenthesis, and then traversing each cactus in turn, in left to right order, that is incident with the root node.

The string of letters, parentheses, and commas one obtains by this procedure is called the traversal string of the graph, in this case, a cactus string.


cc: Conceptual GraphsCyberneticsLaws of FormOntolog Forum
cc: FB | Theme One ProgramStructural ModelingSystems Science

This entry was posted in Algorithms, Animata, Artificial Intelligence, Boolean Functions, C.S. Peirce, Cactus Graphs, Cognition, Computation, Constraint Satisfaction Problems, Data Structures, Differential Logic, Equational Inference, Formal Languages, Graph Theory, Inquiry Driven Systems, Laws of Form, Learning Theory, Logic, Logical Graphs, Mathematics, Minimal Negation Operators, Painted Cacti, Peirce, Propositional Calculus, Semiotics, Spencer Brown, Visualization and tagged , , , , , , , , , , , , , , , , , , , , , , , , , , . Bookmark the permalink.

6 Responses to Theme One Program • Exposition 3

  1. Pingback: Survey of Theme One Program • 4 | Inquiry Into Inquiry

  2. Pingback: Theme One Program • Discussion 8 | Inquiry Into Inquiry

  3. Pingback: Theme One Program • Discussion 7 | Inquiry Into Inquiry

  4. Pingback: Theme One Program • Discussion 9 | Inquiry Into Inquiry

  5. Pingback: Theme One Program • Exposition 6 | Inquiry Into Inquiry

  6. Pingback: Survey of Theme One Program • 5 | Inquiry Into Inquiry

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.