
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Some Results on Decomposability of Weakly Invertible Finite Automata
Feng BAO Yoshihide IGARASHI Xiaomei YU
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E79D
No.1
pp.17 Publication Date: 1996/01/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Automata,Languages and Theory of Computing Keyword: finite automata, transducers, informationlossless, weakly invertible, machine decompositions,
Full Text: PDF>>
Summary:
An invertible length preserving transducer is called a weakly invertible finite automaton (WIFA for short). If the first letter of any input string of length τ + 1 is uniquely determined by the corresponding output string by a WIFA and its initial state, it is called a WIFA with delay τ. The composition of two WIFAs is the natural concatenation of them. The composition is also a WIFA whose delay is less than or equal to the sum of the delays of the two WIFAs. In this paper we derive 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 essence of the decomposability problem, we concentrate on WIFAs such that their input alphabets and their output alphabets are identical. A WIFA with size n of the input and output alphabet is denoted by an nWIFA. We prove that for any n > 1, there exists an nWIFA with delay 2 which cannot be decomposed into two nWIFAs with delay 1. A oneelement logic memory cell is a special WIFA with delay 1, and it is called a delay unit. We show that for any prime number p, every strongly connected pWIFA with delay 1 can be decomposed into a WIFA with delay 0 and a delay unit, and that any 2WIFA can be decomposed into a WIFA wiht delay 0 and a sequence of k delay units if and only if every state of the 2WIFA has delay k.

