Symbolic equations

To describe a graph symbolically, let the nodes be represented by variables, such as the capital letters X, Y, Z, and the links by constants, such as the lower case letters a, b, c. Entrance equations for the graph may be written in the form

which say that one arrives at the node X by having previously arrived at the node Y and then following the link a, by having arrived at Z followed by b, or by simply remaining at the node X. The latter alternative is used when X is a terminal point, otherwise the term would be dropped from the equation.

Conversely exit equations take the form

with marking initial nodes. In either event, the entire diagram is described by a system of equations which can be written in the appropriate symbolic matricial form,

whose symbolic matricial solutions according to Arden's lemma,

have been described by John Conway [3], and in considerably greater detail by Backhouse and Carré [4]. The essence of the method consists in a recursive application of the identity

to a suitably partitioned A, where

Trying to split A in half is an efficient way to reduce the amount of calculation required; removing the first row and column yields very tractable iterative formulas. Alternatively, rewriting A as a sum via sundry regular expression identities yields analogues of the LR factorization of matrices, wherein the stars of triangular factors are much easier to compute than for full matrices.

---

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx