Some Results on Decomposability of Weakly Invertible Finite Automata

概要

論文の詳細を見る
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 T+1 is uniquely determined by the corresponding output string by a WIFA and its initial state, it is called a WIFA with delay T. 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 n-WIFA. We prove that for any n>1, there exists an n-WIFA with delay 2 which 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 delay unit. We show that for any prime number p, every strongly connected 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 delay 0 and a sequence of k delay units if and only if every state of the 2-WIFA has delay k.
社団法人電子情報通信学会の論文
1996-01-25