{\huge Triads and Dyads}

Not dryads and naiads... \vspace{.5in}

Charles Peirce, who is regarded among the greatest logicians and philosophers, wrote a paper in 1897 titled ``The Logic of Relatives.'' Now we might want a guide to the logic of our own relatives, and in fact the word ``brother'' furnished Peirce's first example. But what Peirce meant by ``relative'' is a term that attains its meaning only in conjunction with another noun as object, plus a word or other sign giving the relation. Examples, the first two his, are ``brother of Napoleon,'' ``slayer of giants,'' and ``among the greatest logicians and philosophers.'' The last has a wordless sign after ``among'' where the others have ``of,'' but then the rest may seem to make it a four-way relation. However, Peirce gave a general calculus of how all four and higher-way relations in semiotics could be decomposed into twos and threes. Such ``relatives'' and other three-way relations, however, he proved to be irreducible within his system.

Today we consider an open problem about decomposing 3-ary finite automata.

Peirce's name is usually written with at least the `S.' of his middle name. He was born Charles Sanders Peirce, but late in life he inserted ``Santiago'' before or replacing his middle name. As ``St. James'' in Spanish, this was said to honor his friend the philosopher William James, whose son Pierce designated as second heir after his own wife Juliette. However, earlier usages may have honored the European origins of Juliette herself. His taking up with Juliette before his divorce from his first wife became final was made a scandal that cost Peirce the one academic position he ever had, from Johns Hopkins University in 1884.

I was prompted to write this by a response from Jon Awbrey, who frequents our pages and writes the blog ``Inquiry Into Inquiry.'' In Boolean logic every $latex {N}&fg=000000$-way function can be decomposed as a circuit of binary functions, indeed composed entirely of the binary NOR function, as Peirce himself discovered. Awbrey termed it a ``trap'' to infer that this carries over to logical semantics. The rest of this post isn't related to Pierce, but we offer it toward the general question, when do threes decompose into twos?

Multi-tape Finite Automata

The familiar idea of a finite automaton $latex {M}&fg=000000$ can be generalized to any number $latex {k}&fg=000000$ of input tapes. If each input head must advance one cell on each move, then the input strings may as well be padded to the same length $latex {n}&fg=000000$ with an extra symbol $ added to the alphabet $latex {\Sigma}&fg=000000$. Then they can be shuffled into one string of length $latex {n}&fg=000000$ over the alphabet $latex {\Sigma' = \Sigma^k}&fg=000000$, whereupon $latex {M}&fg=000000$ becomes equivalent to the resulting ordinary one-tape finite automaton $latex {M'}&fg=000000$.

Things are more interesting when one or more heads are allowed to stay stationary on each move. Then the string-matching relation can be recognized by a nondeterministic 2-tape finite automaton (2-NFA). This relation consists of all pairs $latex {(x,y)}&fg=000000$ such that $latex {y}&fg=000000$ can be written as $latex {y = uxv}&fg=000000$ for some $latex {u,v \in \Sigma^*}&fg=000000$. The 2-NFA pauses its first tape head and advances the second until it guesses where $latex {x}&fg=000000$ may start in the input $latex {y}&fg=000000$, and accepts if and when it matches all characters of $latex {x}&fg=000000$ on consiecutive steps. It is easy to show that no 2-DFA can recognize this relation. Thus the equality ``NFA = DFA'' does not carry over to multiple tapes when pausing is allowed.

A three-way relation that is deterministically recognizable is the concatenation relation $latex {C(x,y,z) = (xy = z)}&fg=000000$. With $latex {x}&fg=000000$ and $latex {y}&fg=000000$ on two separate tapes, a 3-DFA can recognize where $latex {x}&fg=000000$ stops upon reading the (implicit or explicit) terminal $ on that tape, and then begin matching the rest of the third tape against $latex {y}&fg=000000$. In an early paper, I showed that there is a bijection $latex {f: \{0,1\}^* \times \{0,1\}^* \longrightarrow \{0,1\}^*}&fg=000000$ whose graph is similarly recognizable as a three-way relation. Indeed I gave a two-tape finite transducer to compute it. This showed a pairing function that is linear-time computable and invertible, while previous examples used integer multiplication for which linear time is unknown.

Multi-tape Finite Transducers and the Problem

The definition of a $latex {k}&fg=000000$-tape finite-state transducer ($latex {k}&fg=000000$-FST) is straightforward: Each transition has the form

$latex \displaystyle (p,(c_1,\dots,c_k),(D_1,\dots,D_k),y,q)&fg=000000$

An example of a function computed by a 3-FST is the ternary concatenation function $latex {c_3(x,y,z) = xyz}&fg=000000$. The latter two tapes pause while $latex {x}&fg=000000$ is copied to the output, then $latex {y}&fg=000000$, then $latex {z}&fg=000000$. This function, however, can be written as the composition

$latex \displaystyle c_3(x,y,z) = c_2(c_2(x,y),z)&fg=000000$

Can every 3-FST function be computed by a finite composition of 2-FSTs?

We can think of other problems involving relations and functions computed by binary and ternary finite automata that seem to have ready answers. One is whether every 3-DFA relation can be written as a Boolean combination of 2-DFA relations on its three pairs of inputs---consider the relation $latex {z = x \oplus y}&fg=000000$ where $latex {\oplus}&fg=000000$ is bitwise exclusive-or. The answer for the function question has, however, eluded me---I suspect it is no, but have not even found a ``killer'' candidate function for being 3-FST only.

Open Problems

Can you prove the answer?

What about other cases of $latex {k}&fg=000000$-way into $latex {2}&fg=000000$-way decomposition?