SOME RESULTS ON DECOMPOSABILITY OF WEAKLY INVERTIBLE FINITE AUTOMATA

An invertible length preserving transducer is called a weakly invertib le finite automaton (WIFA for short). If the first letter of any input string of length tau + 1 is uniquely determined by the corresponding output string by a WIFA and its initial state, it is called a WIFA wit h delay tau. The composition of two WIFAs is the natural concatenation of them. The composition is also a WIFA whose delay is less than or e qual to the sum of the delays of the two WIFAs. In this paper we deriv e various results on a decomposition of a WIFA into WIFAs with smaller delays. The motivation of this subject is from theoretical interests as well as an application to cryptosystems. In order to capture the es sence of the decomposability problem, we concentrate on WIFAs such tha t their input alphabets and their output alphabets are identical. A WI FA with size n of the input and output alphabet is denoted by an n-WIF A. We prove that for any n > 1, there exists an n-WIFA with delay 2 wh ich cannot be decomposed into two n-WIFAs with delay 1. A one-element logic memory cell is a special WIFA with delay 1, and it is called a d elay unit. We show that for any prime number p, every strongly connect ed p-WIFA with delay 1 can be decomposed into a WIFA with delay 0 and a delay unit, and that any 2-WIFA can be decomposed into a WIFA with d elay 0 and a sequence of k delay units if and only if every state of t he 2-WIFA has delay k.