Finite state machine data storage where data transition is accom

Details Finite state machine data storage where data transition is accom Finite state machine data storage where data transition is accom

1992-03-18

1995-09-12

Bowler, Alyssa H.

Boots, shoes, and leggings

36441912, 36494342, 364DIG2, G06F 900

Patent

active

054505984

ABSTRACT:
An FSM data structure is encoded by generating a transition unit of data corresponding to each transition which leads ultimately to a final state of the FSM. Information about the states is included in the transition units, so that the encoded data structure can be written without state units of data. The incoming transition units to a final state each contain an indication of finality. The incoming transition units to a state which has no outgoing transition units each contain a branch ending indication. The outgoing transition units of each state are ordered into a comparison sequence for comparison with a received element, and all but the last outgoing transition unit contain an alternative indication of a subsequent alternative outgoing transition. The indications are incorporated with the label of each transition unit into a single byte, and the remaining byte values are allocated among a number of pointer data units, some of which begin full length pointers and some of which begin pointer indexes to tables where pointers are entered. The pointers may be used where a state has a large number of incoming transitions or where the block of transition units depending from a state is broken down to speed access. The first outgoing transition unit of a state is positioned immediately after one of the incoming transitions so that it may be found without a pointer. Each alternative outgoing transition unit is stored immediately after the block beginning with the previous outgoing transition unit so that it may be found by proceeding through the transition units until the number of alternative bits and the number of branch ending bits balance.

REFERENCES:
patent: Re31287 (1983-06-01), Patil
patent: 4241402 (1980-12-01), Mayper et al.
patent: 4241402 (1980-12-01), Mayper et al.
patent: 4285049 (1981-08-01), Bird et al.
patent: 4293783 (1981-10-01), Patil
patent: 4366551 (1982-12-01), Holtz
patent: 4376982 (1983-03-01), Bantz et al.
patent: 4450520 (1984-05-01), Hollaar et al.
patent: 4644461 (1987-02-01), Jennings
patent: 4713754 (1987-12-01), Agarwal et al.
patent: 4723211 (1988-02-01), Barker et al.
patent: 4739477 (1988-04-01), Barker et al.
patent: 4758955 (1988-07-01), chen
patent: 4771385 (1988-09-01), Egami et al.
patent: 4782464 (1988-11-01), Gray et al.
patent: 4783761 (1988-11-01), Gray et al.
patent: 4866605 (1989-09-01), Nakano et al.
patent: 4882703 (1989-11-01), Nicolai
patent: 4991135 (1991-02-01), Yoshimura et al.
patent: 4991135 (1991-02-01), Yoshimura et al.
patent: 5325091 (1994-06-01), Kaplan
Haskin, R. L., and Hollar, L. A., "Operational Characteristics of a Hardware-Based Pattern Matcher," ACM Transactions on Database Systems, vol. 8, No. 1, Mar. 1983, pp. 15-40.
Haskin, R. L., and Hollar, L. A., "Operational Characteristics of a Hardware-Based Pattern Matcher," ACM Transactions on Database Systems, vol. 8, No. 1, Mar. 1983, pp. 15-40.
Srihari, N. S.; Hull, J. J.; Choudhari, R., "Integrating Diverse Knowledge Sources in Text Recognition", ACM Transactions on Office information Systems, vol. 1, No. 1, Jan. 1983, pp. 68-87.
Carlgren, R. G., "Language-Independent Dictionary Storage and Access Technique," IBM Technical Disclosure Bulletin, vol. 26, No. 11, Apr. 1984, pp. 6085-6086.
Turba, T. N., "Checking for Spelling and Typographical Errors in Computer-Based Tex," SIGPLAN Notices, vol. 16, No. 6, Jun. 1981, pp. 51-60.
Liang, F. M., "Word Hy-Phen-A-Tion by Com-Put-Er," Stanford University, Department of Computer Science, 1983, pp. 8-28, and 39-44.
Hull, J. J.; Srihari, N. S.; Choudhari, R., "An Integrated Algorithm for Text Recognition: Comparison with a Cascaded Algorithm", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-5, No. 4, Jul. 1983, pp. 384-395.
Knuth, D. E. The Art of Computer Programming, vol. 3; Sorting and Searching. Addison-Wesley, Reading, Mass., 1973, pp. 481-505.
Peterson, J. L. "Computer Programs for Spelling Correction: AN Experiment in Program Design", Lecture Notes in Computer Science 96, Springer-Verlag, New York, Oct. 1980, pp. 57-66.
Maly, K. "Comparessed Tries." Communications of the ACM, vol. 19, No. 7, Jul. 1976, pp. 409-415.
Haskin et al., "Operational Characteristics of a Hardware-Based Pattern Matcher", ACM Transactions on Database Systems, vol. 8, No. 1, Mar. 1983, pp. 15-40.
Liang, "Word Hy-Phen-A-Ton by a Com-Pu-Ter", Jun. 1983 (Stanford University Dissertation).
ACM Transactions on Data Base Systems, vol. 8, No. 1, Mar. 1983 pp. 15-40 "Operational Characterstics of a Hardware-Based Pattern Matches" by Haskin, et al.
"Putting Pelvi Nets fo Work", by T. Agerwala (IBM), IEEE, Computer, Dec. 1979, pp. 85-94.

Affiliated with

Also associated with

Rating

Finite state machine data storage where data transition is accom does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Finite state machine data storage where data transition is accom, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finite state machine data storage where data transition is accom will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-414174