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

Main Article Content

Mariusz Flasiński


Keywords : syntactic pattern recognition, graph grammar, parsing, interpreted graph, model theory
Abstract
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.

Article Details

How to Cite
Flasiński, M. (2018). Interpreted Graphs and ETPR(k) Graph Grammar Parsing for Syntactic Pattern Recognition. Machine Graphics and Vision, 27(1/4), 3–19. https://doi.org/10.22630/MGV.2018.27.1.1
References

T. Pavlidis. Structural Pattern Recognition. Springer, New York, 1977. (Crossref)

R.C. Gonzales and M.G. Thomason. Syntactic Pattern Recognition: An Introduction. Addison-Wesley, Reading, 1978.

K.S. Fu. Syntactic Pattern Recognition and Applications. Prentice Hall, Englewood Cliffs, 1982.

H. Bunke and A. Sanfeliu (eds.). Syntactic and Structural Pattern Recognition – Theory and Applications. World Scientific, Singapore, 1990. (Crossref)

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. https://doi.org/10.1007/BFb0025713. (Crossref)

H. Ehrig, M. Nagl and G. Rozenberg (eds.). Graph Grammars and Their Application to Computer Science. Lecture Notes in Computer Science 153, 1983. https://doi.org/10.1007/BFb0000094. (Crossref)

H. Ehrig, M. Nagl and G. Rozenberg (eds.). Graph Grammars and Their Application to Computer Science. Lecture Notes in Computer Science 291, 1987. https://doi.org/10.1007/3-540-18771-5. (Crossref)

H. Ehrig, H.-J. Kreowski and G. Rozenberg (eds.). Graph Grammars and Their Application to Computer Science. Lecture Notes in Computer Science 532, 1991. https://doi.org/10.1007/BFb0017372. (Crossref)

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. https://doi.org/10.1007/3-540-61228-9. (Crossref)

H. Ehrig, G. Engels, H.-J. Kreowski and G. Rozenberg (eds.). Theory and Application of Graph Transformations. Lecture Notes in Computer Science 1764, 2000. https://doi.org/10.1007/b75045. (Crossref)

A. Corradini, H. Ehrig, H.-J. Kreowski and G. Rozenberg (eds.). Graph Transformations. Lecture Notes in Computer Science 2505, 2002. https://doi.org/10.1007/3-540-45832-8. (Crossref)

H. Ehrig, G. Engels, F. Parisi-Presicce and G. Rozenberg (eds.). Graph Transformations. Lecture Notes in Computer Science 3256, 2004. https://doi.org/10.1007/b100934. (Crossref)

A. Corradini, H. Ehrig, U. Montanari, L. Ribeiro and G. Rozenberg (eds.). Graph Transformations. Lecture Notes in Computer Science 4178, 2006. https://doi.org/10.1007/11841883. (Crossref)

H. Ehrig, R. Heckel, G. Rozenberg and G. Taentzer (eds.). Graph Transformations. Lecture Notes in Computer Science 5214, 2008. https://doi.org/10.1007/978-3-540-87405-8. (Crossref)

H. Ehrig, A. Rensink, G. Rozenberg and A. Schurr (eds.). Graph Transformations. Lecture Notes in Computer Science 6372, 2010. https://doi.org/10.1007/978-3-642-15928-2. (Crossref)

H. Ehrig, G. Engels, H.-J. Kreowski and G. Rozenberg (eds.). Graph Transformations. Lecture Notes in Computer Science 7562, 2012. https://doi.org/10.1007/978-3-642-33654-6. (Crossref)

H. Giese and B. K¨onig (eds.). Graph Transformations. Lecture Notes in Computer Science 8571, 2014. https://doi.org/10.1007/978-3-319-09108-2. (Crossref)

F. Parisi-Presicce and B. Westfechtel (eds.). Graph Transformations. Lecture Notes in Computer Science 9151, 2015. https://doi.org/10.1007/978-3-319-21145-9. (Crossref)

R. Echahed and M. Minas (eds.). Graph Transformations. Lecture Notes in Computer Science 9761, 2016. https://doi.org/10.1007/978-3-319-40530-8. (Crossref)

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. https://doi.org/10.1109/TPAMI.1983.4767426. (Crossref)

H.O. Bunke and B. Haller. A parser for context free plex grammars. Lecture Notes in Computer Science, 411:136–150, 1990. https://doi.org/10.1007/3-540-52292-1_10. (Crossref)

K.J. Peng, T. Yamamoto and Y. Aoki. A new parsing scheme for plex grammars. Pattern Recognition, 23:393–402, 1990. https://doi.org/10.1016/0031-3203(90)90026-H. (Crossref)

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. https://doi.org/10.1016/S1045-926X(05)80004-7. (Crossref)

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. https://doi.org/10.1109/VL.1994.363611. (Crossref)

J. Rekers and A. Schurr. Defining and parsing visual languages with layered graph grammars. Journal Visual Languages Computing, 8:27–55, 1997. https://doi.org/10.1006/jvlc.1996.0027. (Crossref)

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. https://doi.org/10.1093/comjnl/44.3.186. (Crossref)

D. Janssens and G. Rozenberg. On the structure of node-label-controlled graph languages. Information Sciences, 20:191–216, 1980. https://doi.org/10.1016/0020-0255(80)90038-9. (Crossref)

M. Flasiński. Parsing of edNLC-graph grammars for scene analysis. Pattern Recognition, 21:623–629, 1988. https://doi.org/10.1016/0031-3203(88)90034-9. (Crossref)

M. Flasiński. Characteristics of edNLC-graph grammars for syntactic pattern recognition. Computer Vision Graphics Image Processing, 47:1–21, 1989. https://doi.org/10.1016/0734-189X(89)90050-9. (Crossref)

M. Flasiński. Distorted pattern analysis with the help of Nodel Label Controlled graph languages. Pattern Recognition, 23:765–774, 1990. https://doi.org/10.1016/0031-3203(90)90099-7. (Crossref)

M. Flasiński. Some notes on a problem of constructing the best matched graph. Pattern Recognition, 24:1223–1224, 1991. https://doi.org/10.1016/0031-3203(91)90147-W. (Crossref)

M. Flasiński. On the parsing of deterministic graph languages for syntactic pattern recognition. Pattern Recognition, 26:1–16, 1993. https://doi.org/10.1016/0031-3203(93)90083-9. (Crossref)

M. Flasiński. Power properties of NLC graph grammars with a polynomial membership problem. Theoretical Computer Science, 201:189–231, 1998. https://doi.org/10.1016/S0304-3975(97)00212-0. (Crossref)

M. Flasiński. Inference of parsable graph grammars for syntactic pattern recognition. Fundamenta Informaticae, 80:379–413, 2007.

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.

M. Flasiński. Use of graph grammars for the description of mechanical parts. Computer-Aided Design, 27:403–433, 1995. https://doi.org/10.1016/0010-4485(94)00015-6. (Crossref)

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. https://doi.org/10.1007/978-3-319-11331-9_24. (Crossref)

U. Behrens, M. Flasiński, L. Hagge and K. Ohrenberg. ZEX – an expert system for ZEUS. IEEE Trans. Nuclear Science, 41:152–156, 1994. https://doi.org/10.1109/23.281478. (Crossref)

M. Flasiński, R. Schaefer and W. Toporkiewicz. Supporting CAE parallel computations with IE-graph solid representation. J. Geometry Graphics, 1:23–29, 1997.

M. Flasiński. Introduction to Artificial Intelligence. Springer International, Switzerland, 2016. https://doi.org/10.1007/978-3-319-40022-8. (Crossref)

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:2249–2264, 2010. https://doi.org/10.1016/j.patcog.2010.01.004. (Crossref)

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. (Crossref)

D.E. Knuth. On the translation of languages from left to right. Information Control 8:607–639, 1965. https://doi.org/10.1016/S0019-9958(65)90426-2. (Crossref)

Statistics

Downloads

Download data is not yet available.
Recommend Articles
Similar Articles

You may also start an advanced similarity search for this article.