Theme One • A Program Of Inquiry : 8

Re: Laws Of Form Discussions • (1)(2)(3)
Re: Peirce List Discussions • (1)(2)

Coding Logical Graphs

My earliest experiments with coding logical graphs as 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 call 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.

       o
   a   |       d
   o---o       o
    \ /  b c   |
     o----o----o b e
      \       /
       \     /
        \   /
         \ /
          @ a c e

   Figure 1.  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 a part of a larger polygon is called a 2-gon or a bi-gon.  A terminal bi-gon is called a spike.

       o
   a  (|)        d
   o---o         o
   (\ /)  b c   (|)
     o--,--o--,--o b e
      \         /
       \       /
     (  \     /  )
         \   /
          \ /
           @ a c e

   ( ( a , ( ) ) , b c , ( d ) b e ) a c e

   Figure 2.  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.

Resources

This entry was posted in Algorithms, Animata, Artificial Intelligence, Boolean Functions, C.S. Peirce, Cactus Graphs, Computation, Computational Complexity, Cybernetics, Data Structures, Differential Logic, Form, Formal Languages, Graph Theory, Inquiry, Inquiry Driven Systems, Intelligent Systems, Laws of Form, Learning, Logic, Logical Graphs, Mathematics, Minimal Negation Operators, Painted Cacti, Peirce, Pragmatics, Programming, Propositional Calculus, Propositional Equation Reasoning Systems, Reasoning, Semantics, Semiotics, Spencer Brown, Syntax, Theorem Proving and tagged , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , . Bookmark the permalink.

One Response to Theme One • A Program Of Inquiry : 8

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

Leave a Reply

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

WordPress.com Logo

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

Google+ photo

You are commenting using your Google+ 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.