Finite Automata and Application to Cryptography

Author: Tao Jiren
Language: English
ISBN/ISSN: 7302175308
Published on: 2008-01
Hardcover

Foreword by Arto Salomaa
Preface
1. Introduction
　1.1 Preliminaries
　　1.1.1 Relations and Functions
　　1.1.2 Graphs
　1.2 Definitions of Finite Automata
　　1.2.1 Finite Automata as Transducers
　　1.2.2 Special Finite Automata
　　1.2.3 Compound Finite Automata
　　1.2.4 Finite Automata as Recognizers
　1.3 Linear Finite Automata
　1.4 Concepts on Invertibility
　1.5 Error Propagation and Feedforward Invertibility.
　1.6 Labelled Trees as States of Finite Automata
2. Mutual Invertibility and Search
　2.1 Minimal Output Weight and Input Set
　2.2 Mutual Invertibility of Finite Automata
　2.3 Find Input by Search
　　2.3.1 On Output Set and Input Tree
　　2.3.2 Exhausting Search
　　2.3.3 Stochastic Search
3. Ra Rb Transformation Method
　3.1 Suificient Conditions and Inversion
　3.2 Generation of Finite Automata with Invertibility
　3.3 Invertibility of Quasi-Linear Finite Automata
　　3.3.1 Decision Criteria
　　3.3.2 Structure Problem
4. Relations Between Transformations
　4.1 Relations Between Ra -Rb Transformations
　4.2 Composition of Ra Rb Transformations
　4.3 Reduced Echelon Matrix
　4.4 Canonical Diagonal Matrix Polynomial
　　4.4.1 Ra Rb Transformations over Matrix Polynomial
　　4.4.2 Relations Between Ra Rb Transformation and Canonical Diagonal Form
　　4.4.3 Relations of Right-Parts
　　4.4.4 Existence of Terminating Re Rb Transformation Sequence
5. Structure of Feedforward Inverses
　5.1 A Decision Criterion
　5.2 Delay Free
　5.3 One Step Delay
　5.4 Two Step Delay
6. Some Topics on Structure Problem
　6.1 Some Variants of Finite Automata
　　6.1.1 Partial Finite Automata
　　6.1.2 Nondeterministic Finite Automata
　6.2 Inverses of a Finite Automaton
　6.3 Original Inverses of a Finite Automaton
　6.4 Weak Inverses of a Finite Automaton
　6.5 Original Weak Inverses of a Finite Automaton
　6.6 Weak Inverses with Bounded Error Propagation of a Finite
　　Automaton
7. Linear Autonomous Finite Automata
　7.1 Binomial Coefficient
　7.2 Root Representation
　7.3 Translation and Period
　　7.3.1 Shift Registers
　　7.3.2 Finite Automata
　7.4 Linearization
　7.5 Decimation
8. One Key Cryptosystems and Latin Arrays
　8.1 Canonical Form for Finite Automaton One Key Cryptosystems
　8.2 Latin Arrays
　　8.2.1 Definitions
　……
9 Finite Automaton Public Key Crytosystems
References
Index