Free and Latest article publishing for websites and ezines!


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 = is cyclic and the number of input alphabet set is equal to the number of output alphabet set. We also discuss a form of structure of feedforward inverse finite automata with delay T in the situation that the number of input alphabet set is different to the number of output alphabet,set. At last, we give a form of structure of weakly invertible finite automata with delay r, and an algorithm to construct the n-ary weakly invertible finite automata with delay 2.In the third part, we study the decomposition of weakly invertible finite automata. First, we present an algorithm to decompose a kind of weakly invertible finite automata with delay 2 satisfied the special condition. Then we extend this algorithm so that we can decompose a kind of weakly invertible finite automata with delay r satisfied the special condition. Next, we give an algorithm to attack the finite automata public key cryptosystem. At last, we analyse the time complexity of the algorithm. The time complexity of this attack algorithm is O(pmτ-m-r1-r2-....rτ-|S|). So, the finite automata public key cryptosystem can resist this attack under the computation power of the computer now.

Recommended Articles from the IT Science Category:

Most Viewed ScienceArticles in the IT Science Category:

  1. Study on the Political Function of Mass Media
  2. Research on Algorithms of GPU-Based 3D Medical Image Processing
  3. Channel Model Simulation and Spread Spectrum OFDM for HF Communication
  4. Research on QoS Based Multicast Routing Protocols in Mobile Ad Hoc Networks
  5. Study of Parallel FDTD Algorithm and EM Scattering in Layered Half-space
  6. High-utility Association Rule Mining
  7. The Application and Study of Electrochemical Biosensors Based on Nanomaterials
  8. Research on MAC Layer Scheduling and Resource Management for IEEE 802.16e OFDM System
  9. Large Scale Image Content Analysis, Retrieval, and Automatic Annotation in Web Environment
  10. Reaearch on Optimization Problem of Manufacturing Process in a Discrete Manufacturing Industry
  11. Research on Optical Fiber Sensor Based on Metal Nanoparticles
  12. A Study of Space-Frequency Coding and Signal Detection in MIMO-OFDM Systems
  13. Study on Techniques of Signal Processing for Cross-Track/Along-Track Interferometric Synthetic Apertu
  14. MOCVD Growth of ZnO Films and ZnO/Si Light-Emitting Devices
  15. Research and Application on Discrete Swarm Intelligence Optimization


© 2004-2009 Latest-Science-Articles.com - All Rights Reserved Worldwide.