F. Bao et al., SOME RESULTS ON DECOMPOSABILITY OF WEAKLY INVERTIBLE FINITE AUTOMATA, IEICE transactions on information and systems, E79D(1), 1996, pp. 1-7
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.