Interpreted Graphs and ETPR(k) Graph Grammar Parsing for Syntactic Pattern Recognition

• Autorzy: Flasiński M.

Identyfikatory

DOI

10.22630/MGV.2018.27.1.1

• Języki publikacji: EN

Abstrakty

EN

Further results of research into graph grammar parsing for syntactic pattern recognition (Pattern Recognit. 21:623-629, 1988; 23:765-774, 1990; 24:1223-1224, 1991; 26:1-16, 1993; 43:249-2264, 2010; Comput. Vision Graph. Image Process. 47:1-21, 1989; Fundam. Inform. 80:379-413, 2007; Theoret. Comp. Sci. 201:189-231, 1998) are presented in the paper. The notion of interpreted graphs based on Tarski's model theory is introduced. The bottom-up parsing algorithm for ETPR(k) graph grammars is defined.

Słowa kluczowe

EN

syntactic pattern recognition; graph grammar; parsing; interpreted graph; model theory

• Wydawca: Institute of Information Technology of the Warsaw University of Life Sciences – SGGW
• Czasopismo: Machine Graphics and Vision
• Rocznik: 2018
• Tom: Vol. 27, No. 1/4
• Strony: 3--19
• Opis fizyczny: Bibliogr. 43 poz., schem.

Twórcy

autor

Flasiński M.

• IT Systems Department, Jagiellonian University ul. St. Lojasiewicza 4, 30-384 Cracow, Poland

• https://orcid.org/0000-0002-0910-4928

Bibliografia

• [1] T. Pavlidis. Structural Pattern Recognition. Springer, New York, 1977.
• [2] R.C. Gonzales and M.G. Thomason. Syntactic Pattern Recognition: An Introduction. Addison-Wesley, Reading, 1978.
• [3] K.S. Fu. Syntactic Pattern Recognition and Applications. Prentice Hall, Englewood Cliffs, 1982.
• [4] H. Bunke and A. Sanfeliu (eds.). Syntactic and Structural Pattern Recognition - Theory and Applications. World Scientific, Singapore, 1990.
• [5] V. Claus, H. Ehrig and G. Rozenberg (eds.). Graph Grammars and Their Application to Computer Science and Biology. Lecture Notes in Computer Science 73, 1979. doi:10.1007/BFb0025713.
• [6] H. Ehrig, M. Nagl and G. Rozenberg (eds.). Graph Grammars and Their Application to Computer Science. Lecture Notes in Computer Science 153, 1983. doi:10.1007/BFb0000094.
• [7] H. Ehrig, M. Nagl and G. Rozenberg (eds.). Graph Grammars and Their Application to Computer Science. Lecture Notes in Computer Science 291, 1987. doi:10.1007/3-540-18771-5.
• [8] H. Ehrig, H.-J. Kreowski and G. Rozenberg (eds.). Graph Grammars and Their Application to Computer Science. Lecture Notes in Computer Science 532, 1991. doi:10.1007/BFb0017372.
• [9] J. Cuny, H. Ehrig, G. Engels and G. Rozenberg (eds.). Graph Grammars and Their Application to Computer Science. Lecture Notes in Computer Science 1073, 1996. doi:10.1007/3-540-61228-9.
• [10] H. Ehrig, G. Engels, H.-J. Kreowski and G. Rozenberg (eds.). Theory and Application of Graph Transformations. Lecture Notes in Computer Science 1764, 2000. doi:10.1007/b75045.
• [11] A. Corradini, H. Ehrig, H.-J. Kreowski and G. Rozenberg (eds.). Graph Transformations. Lecture Notes in Computer Science 2505, 2002. doi:10.1007/3-540-45832-8.
• [12] H. Ehrig, G. Engels, F. Parisi-Presicce and G. Rozenberg (eds.). Graph Transformations. Lecture Notes in Computer Science 3256, 2004. doi:10.1007/b100934.
• [13] A. Corradini, H. Ehrig, U. Montanari, L. Ribeiro and G. Rozenberg (eds.). Graph Transformations. Lecture Notes in Computer Science 4178, 2006. doi:10.1007/11841883.
• [14] H. Ehrig, R. Heckel, G. Rozenberg and G. Taentzer (eds.). Graph Transformations. Lecture Notes in Computer Science 5214, 2008. doi:10.1007/978-3-540-87405-8.
• [15] H. Ehrig, A. Rensink, G. Rozenberg and A. Schürr (eds.). Graph Transformations. Lecture Notes in Computer Science 6372, 2010. doi:10.1007/978-3-642-15928-2.
• [16] H. Ehrig, G. Engels, H.-J. Kreowski and G. Rozenberg (eds.). Graph Transformations. Lecture Notes in Computer Science 7562, 2012. doi:10.1007/978-3-642-33654-6.
• [17] H. Giese and B. König (eds.). Graph Transformations. Lecture Notes in Computer Science 8571, 2014. doi:10.1007/978-3-319-09108-2.
• [18] F. Parisi-Presicce and B. Westfechtel (eds.). Graph Transformations. Lecture Notes in Computer Science 9151, 2015. doi:10.1007/978-3-319-21145-9.
• [19] R. Echahed and M. Minas (eds.). Graph Transformations. Lecture Notes in Computer Science 9761, 2016. doi:10.1007/978-3-319-40530-8.
• [20] Q.Y. Shi and K.S. Fu. Parsing and translation of attributed expansive graph languages for scene analysis. IEEE Trans. Pattern Analysis Mach. Intell., 5:472-485, 1983. doi:10.1109/TPAMI.1983.4767426.
• [21] H.O. Bunke and B. Haller. A parser for context free plex grammars. Lecture Notes in Computer Science, 411:136-150, 1990. doi:10.1007/3-540-52292-1 10.
• [22] K.J. Peng, T. Yamamoto and Y. Aoki. A new parsing scheme for plex grammars. Pattern Recognition, 23:393-402, 1990. doi:10.1016/0031-3203(90)90026-H.
• [23] K. Wittenburg, L. Weitzman and J. Talley J. Unification-based grammars and tabular parsing for graphical languages. Journal Visual Languages Computing, 2:347-370, 1991. doi:10.1016/S1045-926X(05)80004-7.
• [24] F. Ferruci, G. Tortora, M. Tucci and G. Vitiello. A predictive parser for visual languages specified by relational grammars. In Proc. IEEE Symp. Visual Lang. VL'94, 245-252. doi:10.1109/VL.1994.363611.
• [25] J. Rekers and A. Schürr. Defining and parsing visual languages with layered graph grammars. Journal Visual Languages Computing, 8:27-55, 1997. doi:10.1006/jvlc.1996.0027.
• [26] D.Q. Zhang, K. Zhang and J. Cao. A context-sensitive graph grammar formalism for the specification of visual languages. The Computer Jornal, 44:186-200, 2001. doi:10.1093/comjnl/44.3.186.
• [27] D. Janssens and G. Rozenberg. On the structure of node-label-controlled graph languages. Information Sciences, 20:191-216, 1980. doi:10.1016/0020-0255(80)90038-9.
• [28] M. Flasiński. Parsing of edNLC-graph grammars for scene analysis. Pattern Recognition, 21:623-629, 1988. doi:10.1016/0031-3203(88)90034-9.
• [29] M. Flasiński. Characteristics of edNLC-graph grammars for syntactic pattern recognition. Computer Vision Graphics Image Processing, 47:1-21, 1989. doi:10.1016/0734-189X(89)90050-9.
• [30] M. Flasiński. Distorted pattern analysis with the help of Nodel Label Controlled graph languages. Pattern Recognition, 23:765-774, 1990. doi:10.1016/0031-3203(90)90099-7.
• [31] M. Flasiński. Some notes on a problem of constructing the best matched graph. Pattern Recognition, 24:1223-1224, 1991. doi:10.1016/0031-3203(91)90147-W.
• [32] M. Flasiński. On the parsing of deterministic graph languages for syntactic pattern recognition. Pattern Recognition, 26:1-16, 1993. doi:10.1016/0031-3203(93)90083-9.
• [33] M. Flasiński. Power properties of NLC graph grammars with a polynomial membership problem. Theoretical Computer Science, 201:189-231, 1998. doi:10.1016/S0304-3975(97)00212-0.
• [34] M. Flasiński. Inference of parsable graph grammars for syntactic pattern recognition. Fundamenta Informaticae, 80:379-413, 2007.
• [35] M. Flasiński and L. Kotulski. On the use of graph grammars for the control of a distributed software allocation. The Computer Journal, 35:A165-A175, 1992.
• [36] M. Flasiński. Use of graph grammars for the description of mechanical parts. Computer-Aided Design, 27:403-433, 1995. doi:10.1016/0010-4485(94)00015-6.
• [37] M. Flasiński and Z. Flasińska. Characteristics of bottom-up parsable edNLC graph languages for syntactic pattern recognition. In L.J. Chmielewski et al., editors, Computer Vision and Graphics: Proc. Int. Conf. ICCVG 2014, volume 8671 of Lecture Notes in Computer Science, pages 195-202, Warsaw, Poland, September 2014. Springer, Heidelberg. doi:10.1007/978-3-319-11331-9 24.
• [38] U. Behrens, M. Flasiński, L. Hagge and K. Ohrenberg. ZEX - an expert system for ZEUS. IEEE Trans. Nuclear Science, 41:152-156, 1994. doi:10.1109/23.281478.
• [39] M. Flasiński, R. Schaefer and W. Toporkiewicz. Supporting CAE parallel computations with IE-graph solid representation. J. Geometry Graphics, 1:23-29, 1997.
• [40] M. Flasiński. Introduction to Artificial Intelligence. Springer International, Switzerland, 2016. doi:10.1007/978-3-319-40022-8.
• [41] M. Flasiński and S. Myśliński. On the use of graph parsing for recognition of isolated hand postures of Polish Sign Language. Pattern Recognition 43:22492264, 2010. doi:10.1016/j.patcog.2010.01.004.
• [42] M. Flasiński. Syntactic pattern recognition: paradigm issues and open problems. In C.H. Chen (ed.), Handbook of Pattern Recognition and Computer Vision, World Scientific, New Jersey - London - Singapore, 2016, Chapt. 1, pp. 3-25.
• [43] D.E. Knuth. On the translation of languages from left to right. Information Control 8:607-639, 1965. doi:10.1016/S0019-9958(65)90426-2.