On the construction of transition functions for DPLL(k) automata for syntactic pattern recognition

• Autorzy: Jurek J.
• Języki publikacji: EN

Abstrakty

EN

DPLL(k) automata have been introduced as a tool for inference support in pattern recognition-based real-time expert systems. The automata can be characterised by the two following features: they can recognise languages of a big descriptive power (quasi context sensitive languages), and they are efficient (i.e. they are of linear computational complexity). The two features make the automata useful in case of many practical applications, such as the on-line analysis of complex trend functions describing behaviour of industrial equipment. In this paper we present a method for construction of transition functions for the automata and a formal proof of its correctness.

Słowa kluczowe

EN

syntactic pattern recognition; context sensitive languages; parsing

• Wydawca: Institute of Information Technology of the Warsaw University of Life Sciences – SGGW
• Czasopismo: Machine Graphics and Vision
• Rocznik: 2003
• Tom: Vol. 12, No. 4
• Strony: 489--513
• Opis fizyczny: Bibliogr. 20 poz., rys., tab.

Twórcy

autor

Jurek J.

• Institute of Computer Science, Jagiellonian University, Nawojki 11 30-072 Cracow, Poland,

Bibliografia

• [1] Freeman H.: On the encoding of arbitrary geometric configurations. IEEE Trans. Electron. Comput.,EC-10, 260-268. 1961.
• [2] Ledley R.S.: Programming and Utilizing Digital Computers. McGraw-Hill, NY. 1962.
• [3] Aho A. V.: Indexed grammars - an extension of context-free grammars, J. ACM, 15, 647-671. 1968.
• [4] Rosenkrantz D.J.: Programmed grammars and classes of forma! languages. J . ACM, 16, 107-131. 1969.
• [5] Shaw A.C.: A formal picture description scheme as as basis for picture processing systems. Information and Control, 14, 9-52. 1969.
• [6] Rosenkrantz D.J., Stearns R.E.: Properties of deterministic top-down grammars . Information and Control, 17, 226-256. 1970.
• [7] Aho A.V., Ullman .J.D.: The Theory of Parsing , Translation , and Compiling. Prentice-Hall, Englewood Cliffs, NJ. 1972.
• [8] Fu K.S.: Syntactic Pattern Recognition and Applications. Preutice Hall, Englewood Cliffs. 1982.
• [9] Skordolakis E.: Syntactic ECG processing: A review. PR, 19, 305-313. 1986.
• [10] Pietka E.: Feature extraction in computerized approach to the ECG analysis. PR, 24(2), 139-146. 1991.
• [11] Behrens U., Flasiński M., Hagge L., Jurek J., Ohrenberg K.: Status of the ZEUS Expert System (ZEX), Proc. Int. Conf. on Computing in High Energy Physics CHEP'95, Rio de Janeiro, Brasil, 18-22 Sept., 888-891. 1995.
• [12] Koski A., Juhola M., Meriste M.: Synta.ctic recognition of ECG signals by attributed finite automata. PR, 28(12), 1927-1940. 1995.
• [13] Tanaka E.: Theoretical aspects of syntactic pattern recognition. PR, 28, 1053-1061. 1995.
• [14] Behrens U., Flasiński M., Hagge L., Jurek J., Ohrenberg K.: Recent developments of the ZEUS expert system ZEX, IEEE Trans. Nuci. Sci., NS-43, 65-68. 1996.
• [15] Flasiński M., Jurek J.: Dynamically programmed automata for quasi context sensitive languages as a tool for inference support in pattern recognition-based real-time control expert systems. PR, 32(4), 671-690. 1999.
• [16] Jurek J.: On the pattern generation power of parsable DPLL(k) languages. Proc. First National Conf. On Computer Recognition Systems, KOSYR'99, Trzebieszowice, Poland, 24-27 May, 367-373. 1999.
• [17] Jurek J.: On the linear computational complexity of the parser for quasi context sensitive languages. PRL, 21, 179-187. 2000.
• [18] Jurek J.: Syntactic pattern recognition-based agents for real-time expert systems. LNCS (LNAI), 2296, 161-168. 2002.
• [19] Flasiński M., Reroń E., .Jurek J., Wójtowicz P ., Atlasiewicz K.: Mathematical linguistics model for medical diagnostics of organ of hearing in neonates. Accepted for publication in LNCS (LNAI). 2003.
• [20] Jurek J.: On the construction of hybrid expert systems for the application in the power industry. (Paper in Polish). Proc. 5th National Conf. Inzynieria Wiedzy i Systemy Ekspertowe, Wrocław, Poland, 11-13 June, 2, 54-61. 2003.