Inference of Parsable Graph Grammars for Syntactic Pattern Recognition

• Autorzy: Flasiński, M.
• Języki publikacji: EN

Abstrakty

EN

A research into a syntactic pattern recognition model based on ( edNLC) graph grammars (introduced and investigated in Janssens and Rozenberg Inform. Sci. 20 (1980), 191-216, and Janssens, Rozenberg and Verraedt Comp. Vis. Graph. Image Process. 18 (1982), 279-304) has resulted in defining the efficient, O(n2), parsing schemes for the ETPL(k) subclass of these grammars and applying it for scene analysis, CAD/CAM object analysis and constructing AI systems (Flasiński Patt. Recogn. 21 (1988), 623-629, Flasiński Comp. Vis. Graph. Image Process. 47 (1989), 1-21, Flasiński Patt. Recogn. 26 (1993), 1-16, Flasiński Comp. Aided-Des. 27 (1995), 403-433, Flasiński Theor. Comp. Sci. 201 (1998), 189-231). In the paper the grammatical inference method for the parsable ETPL(k) graph grammars is defined, completing the development of this syntactic pattern recognition model.

Słowa kluczowe

EN

syntactic pattern recognition; graph grammar; graph parsing; grammatical inference problem

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 80, nr 4
• Strony: 379-413
• Opis fizyczny: bibliogr. 40 poz., tab., wykr.

Twórcy

autor

Flasiński, M.

• Information Technology Systems, Jagiellonian University, ul. Straszewskiego 27, 31-110 Cracow, Poland,

Bibliografia

• [1] H. Freeman, On the encoding of arbitrary geometric configurations, Trans. Electron. Comput. EC-10 (1961), 260-268.
• [2] R.S. Ledley, Programming and Utilizing Digital Computers, McGraw-Hill, New York, 1962.
• [3] R.C. Gonzales,M.G. Thomason, On the inference of tree grammars for pattern recognition, Proc. 1974 IEEE Int. Conf. Syst. Man Cybern. (1974), 2-4.
• [4] B.K. Bhargava, K.S. Fu, Transformation and inference of tree grammars for syntactic pattern recognition, Proc. 1974 Int. Conf. Syst. Man Cybern. (1974).
• [5] J.M. Brayer, K.S. Fu, A note on the k-tail method of tree grammar inference, IEEE Trans. Syst. Man Cybern. SMC-5, (1975), 409-422.
• [6] B. Levine, The use of tree derivatives and a sample support parameter for inferring tree systems, IEEE Trans. Patt. Anal. Mach. Intell. PAMI-4 (1982), 25-34.
• [7] A. Barrero, Inference of tree grammars using negative samples, Pattern Recognition 24 (1991), 1-8.
• [8] R.C. Carrasco, J. Oncina, J. Calera-Rubio, Stochastic inference of regular tree languages, Machine Learning 44 (2001), 185-197.
• [9] K.S. Fu, Syntactic Pattern Recognition and Applications, Prentice Hall, Englewood Cliffs, 1982.
• [10] E. Tanaka, Theoretical aspects of syntactic pattern recognition, Pattern Recognition 28 (1995), 1053-1061.
• [11] F.J. Branderburg, On the complexity of the membership problem of graph grammars, Proc. Int. Workshop Graphteoret. Concepts in Comp. Sci. Osnabr¨uck, Germany, Trauner Verlag, June 1983, 40-49.
• [12] G. Turan, On the complexity of graph grammars, Techn. Rep. Theory Research Group, Szeged, 1982.
• [13] M. Blum, C. Hewitt, Automata on a two-dimensional tape, Proc. 8th IEEE Conf. Switching Automaton Theory, 1968, 155-160.
• [14] J.L Pfaltz, A. Rosenfeld,Web grammars, Proc. First Int. Conf. Artif. Intell.,Washington, DC, 1969, 609-619.
• [15] A. Rosenfeld, D.L. Milgram,Web automata and web grammars,Machine Intell. 7 (1972), 307-324.
• [16] J.M. Brayer, Parsing of web grammars, Proc. IEEEWorkshop Data Descr. Manag., Long Beach, CA, 1977.
• [17] R. Franck, A class of linearly parsable graph grammars, Acta Inform. 10 (1978), 175-201.
• [18] P. Della Vigna, C. Ghezzi, Context-free graph grammars, Inform. Control 37 (1978), 207-233.
• [19] M. Kaul, Parsing of graphs in linear time, Lecture Notes in Computer Science 153 (1983), 206-218.
• [20] Q.Y. Shi, K.S. Fu, Parsing and translation of attributed expansive graph languages for scene analysis, IEEE Trans. Pattern Analysis Mach. Intell. PAMI-5 (1983), 472-485.
• [21] C. Lautemann, Efficient algorithms on context-free graph languages, Lecture Notes in Computer Science 317(1988), 362-378.
• [22] H.O. Bunke, B. Haller, A parser for context free plex grammars, Lecture Notes in Computer Science 411 (1990), 136-150.
• [23] K.J. Peng, T. Yamamoto, Y. Aoki, A new parsing scheme for plex grammars, Pattern Recognition 23 (1990), 393-402.
• [24] D. Janssens, G. Rozenberg,On the structure of node-label-controlled graph languages, Inform. Sci. 20 (1980), 191-216.
• [25] D. Janssens, G. Rozenberg, R. Verraedt, On sequential and parallel node-rewriting graph grammars, Comput. Graphics Image Process. 18 (1982), 279-304.
• [26] D. Janssens, G. Rozenberg, Graph grammars with node-label controlled rewriting and embedding, Lecture Notes in Computer Science 153 (1983), 186-205.
• [27] M. Flasiński, Parsing of edNLC-graph grammars for scene analysis, Pattern Recognition 21 (1988), 623-629.
• [28] M. Flasiński, Characteristics of edNLC - graph grammars for syntactic pattern recognition, Comput. Vision Graphics Image Process. CGIP-47 (1989), 1-21.
• [29] M. Flasiński, Distorted pattern analysis with the help of Nodel Label Controlled graph languages, Pattern Recognition 23 (1990), 765-774.
• [30] M. Flasiński, Some notes on a problem of constructing the best matched graph, Pattern Recognition 24 (1991), 1223-1224.
• [31] M. Flasiński, On the parsing of deterministic graph languages for syntactic pattern recognition, Pattern Recognition 26 (1993), 1-16.
• [32] M. Flasiński, Power properties of NLC graph grammars with a polynomialmembership problem, Theoretical Computer Science 201 (1998), 189-231.
• [33] M. Flasiński, L. Kotulski, On the use of graph grammars for the control of a distributed software allocation, The Computer Journal 35 (1992), A165-A175.
• [34] M. Flasiński, R. Schaefer, W. Toporkiewicz, Optimal stochastic scaling of CAE parallel computations, Lecture Notes in Computer Science 1424 (1998), 557-564.
• [35] M. Flasiński, Use of graph grammars for the description of mechanical parts, Computer Aided Design 27 (1995), 403-433.
• [36] U. Behrens, M. Flasiński, L. Hagge, J. Jurek, K. Ohrenberg, ZEX - an expert system for ZEUS, IEEE Trans. Nucl. Sci. NS-43 (1996), 65-68.
• [37] M. Flasiński, J. Jurek, Dynamically programmed automata for quasi context sensitive languages as a tool for inference support in pattern recognition-based real-time control expert systems, Pattern Recognition 32 (1999), 671-690.
• [38] M. Flasiński, Automata-based multi-agent model as a tool for constructing real-time intelligent control systems, Lecture Notes in Computer Science - Lecture Notes in Artificial Intelligence 2296 (2002), 103-110.
• [39] L. Miclet, Structural Methods in Pattern Recognition, Chapman and Hall, 1986.
• [40] M. Flasiński, J. Jurek, On the analysis of fuzzy string patterns with the help of extended and stochastic GDPLL(k) grammars, Fundamenta Informaticae 71 (2006), 1-14.