|
Some Results of Finite Automata Invertibility
|
The main domains of automata theory include the function, structure and relation of the discrete digital system. With the development of electronic technology and the information theory, automata theory goes into every area of information technology, and provides theoretical models, design technology and algorithm to them. The invertibility of finite automata is one of the areas in automata theory and it has been studied since the concepts of the information lossless and the information lossless of finite order were proposed. The proposition and application of the finite automata public key cryptosystem stimulates the investigation of invertibility of finite automata. In this thesis, several results are given in the areas of the invertibility of finite automata.The main work of this thesis contains three parts: the invertibility of finite automata on matrix ring, the structure of feedforward inverse finite automata and weakly invertible finite automata, and the decomposition of weakly invertible finite automata.In the first part, we study the invertibility of finite automata over a matrix ring. Matrix ring is a typical noncommutative ring and it has fine structure and lots of achievement. We get the following result: Let M be a QL-type finite automaton over a matrix ring and M the corresponding linear finite automaton of M over the basic field, then M is weakly invertible with delay τ if and only if M is weakly invertible with delay T. Therefore, the invertibility of finite automata over a matrix ring is transformed into the invertibility of finite automata over a field. Then, we give some results of the invertibility of finite automata over a matrix ring.In the second part, we study the structure of feedforward inverse finite automata in general case, and we also discuss the structure of weakly invertible finite automata. A form of structure of feedforward inverse finite automata with delay r is given in the situation that C(Ma, f) i.s a c-order semi-input-memory finite automata where autonomous finite automaton Ma =