Structure of weakly invertible semi-input-memory finite automata with delay 1. (English) Zbl 1012.68104
Summary: Semi-input-memory finite automata, a kind of finite automata introduced by the first author of this paper for studying error propagation, are a generalization of input-memory finite automata by appending an autonomous finite automaton component. In this paper, we give a characterization of the structure of weakly invertible semi-input-memory finite automata with delay 1, in which the state graph of each autonomous finite automaton is a cycle. From a result on mutual invertibility of finite automata obtained by the authors recently, it leads to a characterization of the structure of feedforward inverse finite automata with delay 1.
MSC:
| 68Q45 | Formal languages and automata |
Keywords:
semi-input-memory finite automataReferences:
| [1] | Huffman D A. Canonical forms for information-lossless finite-state logical machines.IRE Trans. Circuit Theory, 1959, CT-6 (special supplement): 41–59. · Zbl 0166.26802 |
| [2] | Kurmit A A. Information Lossless Automata of Finite Order. John Wiley, New York, 1974. · Zbl 0363.94053 |
| [3] | Tao J. Invertible linear finite automata.Scientia Sinica, 1973, 16(4): 565–581. · Zbl 0341.94027 |
| [4] | Tao R J. Invertibility of Finite Automata. Science Press, Beijing, 1979. (in Chinese) · Zbl 0609.68041 |
| [5] | Tao R J. Relationship between bounded error propagation and feedforward invertibility.Kexue Tongbao, 1982, 27(6): 680–682. · Zbl 0583.68027 |
| [6] | Tao R J. Some results on the structure of feedforward inverses.Scientia Sinica, Ser. A, 1984, 27(2): 157–162. · Zbl 0527.68033 |
| [7] | Tao R J. Invertibility of linear finite automata over a ring. InICALP’88, Automata, Languages and Programming, Lecture Notes in Computer Science 317, Springer-Verlag, Berlin, 1988, pp.489–501. |
| [8] | Tao R J, Chen S H. Some properties on the structure of invertible and inverse finite automata with delay r.Chinese J. Computers, 1980, 3(4): 289–297. (in Chinese) |
| [9] | Tao R J, Chen S H. A necessary condition on invertibility of finite automata.Science in China, Ser. E, 1997, 40(6): 637–643. · Zbl 0895.68090 |
| [10] | Tao R J, Chen S H. Constructing finite automata with invertibility by transformation method.J. Computer Science and Technology, 2000, 15(1): 10–26. · Zbl 1044.94535 · doi:10.1007/BF02951923 |
| [11] | Tao R J, Chen S H. Input-trees of finite automata and application to cryptanalysis.J. Computer Science and Technology, 2000, 15(4): 305–325. · Zbl 0976.94024 · doi:10.1007/BF02948867 |
| [12] | Chen S H. On the structure of inverses of a weakly invertible linear finite automaton.Chinese J. Computers, 1981, 4(6): 409–419. (in Chinese) |
| [13] | Chen S H. On the structure of finite automata of whichM’ is an (weak) inverse with delayr.J. Computer Science and Technology, 1986, 1(2): 54–59. · Zbl 0605.68043 · doi:10.1007/BF02943272 |
| [14] | Chen S H. On the structure of (weak) inverses of an (weakly) invertible finite automaton.J. Computer Science and Technology, 1986, 1(3): 92–100. · doi:10.1007/BF02979465 |
| [15] | Chen S H, Tao R J. The structure of weak inverses of a finite automaton with bounded error propagation.Kexue Tongbao, 1987, 32(10): 713–714; full paper inAdvances in Chinese Computer Science, Vol.1, World Scientific, Singapore, 1988, pp. 205–211. |
| [16] | Chen S H, Tao R J. Invertibility of quasi-linear finite automata. InAdvances in Cryptology – CHINACRYPT’92, Science Press, Beijing, 1992, pp.77–86. (in Chinese) |
| [17] | Zhu X J. On the structure of binary feedforward inverses with delay 2.J. Computer Science and Technology, 1989, 4(2): 163–171. · Zbl 0688.68052 · doi:10.1007/BF02943364 |
| [18] | Bao F. On the structure ofn-ary feedforward inverses with delay 1 [Thesis]. Institute of Software, Chinese Academy of Sciences, 1986. (in Chinese) |
| [19] | Bao F. Limited error-propagation, self-synchronization and finite input memory FSMs as weak inverses InAdvances in Chinese Computer Science, Vol.3, World Scientific, Singapore, 1991, pp.1–24. |
| [20] | Bao F. Composition and decomposition of weakly invertible finite automata.Science in China, Ser. A, 1993, 23(7): 759–766 (in Chinese) |
| [21] | Bao F. Two results about the decomposition of delay step of weakly invertible finite automata.Chinese J. Computers, 1993, 16(8): 629–632. (in Chinese) |
| [22] | Gao X, Bao F. Decomposition of binary weakly invertible finite automata.Chinese J. Computers, 1994, 17(5): 330–337. (in Chinese) |
| [23] | Zhou S Y. On the weakly invertibility of type I Abelian FGHSS.Chinese J. Computers, 1982, 5(3): 221–222. (in Chinese) |
| [24] | Lü S Z. Some results on the invertibility of linear finite automata over a ring.Chinese J. Computers, 1991, 14(8): 570–578. (in Chinese) |
| [25] | Dai Z D, Ye D F. Weak invertibility of nonlinear finite automata over commutative rings.Chinese Science Bulletin, 1995, 40(15): 1357–1360. (in Chinese) |
| [26] | Wang H.R a Rb transformation of compound finite automata over commutative rings.J. Computer Science and Technology, 1997, 12(1): 40–48. · Zbl 0865.68079 · doi:10.1007/BF02943143 |
| [27] | Wang H. On weak invertibility of linear finite automata.Chinese J. Computers, 1997, 20(11): 1003–1008 (in Chinese) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
