Generative power of reduction-based parsable ETPR(k) graph grammars for syntactic pattern recognition

• Autorzy: Flasiński M.

Identyfikatory

DOI

10.14313/JAMRIS_2-2018/12

• Języki publikacji: EN

Abstrakty

EN

Further results of research into parsable graph grammars used for syntactic pattern recognition (Pattern Recognition: 21, 623-629 (1988); 23, 765-774 (1990); 24, 12-23 (1991); 26, 1-16 (1993); 43, 2249-2264 (2010), Comput. Vision Graph. Image Process. 47, 1-21 (1989), Computer-Aided Design 27, 403-433 (1995), Theoret. Comp. Sci. 201, 189-231 (1998), Pattern Analysis Applications bf 17, 465-480 (2014)) are presented in the paper. The generative power of reduction-based parsable ETPR(k) graph grammars is investigated. The analogy between the triad of CF - LL(k) - LR(k) string languages and the triad of NLC - ETPL(k) - ETPR(k) graph languages is discussed.

Słowa kluczowe

EN

syntactic pattern recognition; graph grammar; parsing

PL

rozpoznawanie wzoru syntaktycznego; gramatyka grafowa

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2018
• Tom: Vol. 12, No. 2
• Strony: 61--81
• Opis fizyczny: Bibliogr. 55 poz., rys.

Twórcy

autor

Flasiński M.

• Information Technology Systems Department, Jagiellonian University, ul. prof. St. Łojasiewicza 4, Cracow 30-348, Poland, www: www.ksi.uj.edu.pl/~mfl

Bibliografia

• [1] M. Bauderon and B. Courcelle, “Graph expressions and graph rewritings”, Mathematical Systems Theory, vol. 20, 1987, 83–127.
• [2] U. Behrens, M. Flasiński, L. Hagge, and K. Ohrenberg, “ZEX - An expert system for ZEUS”, IEEE Trans. Nuclear Science, vol. 41, 1994, 152–156.
• [3] M. Blum and C. Hewitt, “Automata on a twodimensional tape”. In: Proc. 8th IEEE Annual Symposium Switching and Automata Theory, Austin, TX, USA, 1967, 155–160.
• [4] F. J. Brandenburg, “On the complexity of the membership problem of graph grammars”. In: Proc. Int. Workshop on Graphtheoretic Concepts in Computer Sci. (WG’83), Osnabrück, Germany, 1983, 40–49.
• [5] F. J. Brandenburg and K. Skodinis, “Finite graph automata for linear and boundary graph languages”, Theoretical Computer Science, vol. 332, 2005, 199–232.
• [6] J. M. Brayer, “Parsing of web grammars”. In: Proc. IEEE Workshop Picture Data Description and Management, Chicago, IL, USA, 1977.
• [7] H. O. Bunke and B. Haller, “A parser for context free plex grammars”, Lecture Notes in Computer Science, vol. 411, 1990, 136–150.
• [8] P. Della Vigna and C. Ghezzi, “Context-free graph grammars”, Information and Control, vol. 37, 1978, 207–233.
• [9] F. Drewes, B. Hoffmann, and M. Minas, “Predictive top-down parsing for hyperedge replacement grammars”, Lecture Notes in Computer Science, vol. 9151, 2015, 19–34.
• [10] H. Ehrig, , H. J. Kreowski, U. Montanari, and G. Rozenberg, eds., Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 3: Concurrency, Parallelism, and Distribution, World Scientific: Singapore, 1999.
• [11] H. Ehrig, G. Engels, H. J. Kreowski, and G. Rozenberg, eds., Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 2: Applications, Languages and Tools, World Scientific: Singapore, 1999.
• [12] J. Feder, “Plex languages”, Information Sciences, vol. 3, 1971, 225–241.
• [13] M. Flasiński, “Parsing of edNLC-graph grammars for scene analysis”, Pattern Recognition, vol. 21, 1988, 623–629.
• [14] M. Flasiński, “Characteristics of edNLC-graph grammars for syntactic pattern recognition”, Computer Vision, Graphics and Image Processing, vol. 47, 1989, 1–21.
• [15] M. Flasiński, “Distorted pattern analysis with the help of Node Label Controlled graph languages”, Pattern Recognition, vol. 23, 1990, 765–774.
• [16] M. Flasiński, “On the parsing of deterministic graph languages for syntactic pattern recognition”, Pattern Recognition, vol. 26, 1993, 1–16.
• [17] M. Flasiński. “Further development of the ZEUS Expert System: Computer science foundations of design”. Technical Report 94-048, Deutsches Eletronen-Synchrotron, Hamburg, Germany, 1994.
• [18] M. Flasiński, “Use of graph grammars for the description of mechanical parts”, Computer-Aided Design, vol. 27, 1995, 403–433.
• [19] M. Flasiński, “Power properties of NLC graph grammars with a polynomial membership problem”, Theoretical Computer Science, vol. 201, 1998, 189–231.
• [20] M. Flasiński, “Inference of parsable graph grammars for syntactic pattern recognition”, Fundamenta Informaticae, vol. 80, 2007, 379–413.
• [21] M. Flasiński, Introduction to Arti􀏔icial Intelligence, Springer International: Switzerland, 2016.
• [22] M. Flasiński. “Syntactic pattern recognition: paradigm issues and open problems”. In: C. H. Chen, ed., Handbook of Pattern Recognition and Computer Vision, 3–25. World Scientific, New Jersey-London-Singapore, 2016.
• [23] M. Flasiński, “Interpreted graphs and ETPR(k) graph grammar parsing for syntactic pattern recognition”, Machine Graphics and Vision, vol. 27, 2018, 3–19.
• [24] M. Flasiński, Syntactic Pattern Recognition, World Scientific: New Jersey - London - Singapore,2019.
• [25] M. Flasiński and L. Kotulski, “On the use of graph grammars for the control of a distributed software allocation”, The Computer Journal, vol. 35, 1992, A165–A175.
• [26] 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, vol. 43, 2010, 2249–2264.
• [27] M. Flasiński, R. Schaefer, and W. Toporkiewicz, “Supporting CAE parallel computations with IE-graph solid representation”, J. Geometry Graphics, vol. 1, 1997, 23–29.
• [28] R. Franck, “A class of linearly parsable graph grammars”, Acta Informatica, vol. 10, 1978, 175–201.
• [29] A. Habel and H. J. Kreowski, “May we introduce to you: hyperedge replacement”, Lecture Notes in Computer Science, vol. 291, 1987, 15–26.
• [30] D. Janssens and G. Rozenberg, “On the structure of node-label-controlled graph languages”, Information Sciences, vol. 20, 1980, 191–216.
• [31] D. Janssens and G. Rozenberg, “Graph grammarswith neighbourhood-controlled embedding”, Theoretical Computer Science, vol. 21, 1982, 55–74.
• [32] D. Janssens, G. Rozenberg, and R. Verraedt, “On sequential and parallel node-rewriting graph grammars”, Computer Graphics and Image Processing, vol. 18, 1982, 279–304.
• [33] M. Kaul, “Parsing of graphs in linear time”, Lecture Notes in Computer Science, vol. 153, 1983, 206–218.
• [34] D. Knuth, “On the translation of languages from left to right”, Information and Control, vol. 8, 1965, 607–639.
• [35] C. Lautemann, “Efficient algorithms on contextfree graph languages”, Lecture Notes in Computer Science, vol. 317, 1988, 362–378.
• [36] P. M. Lewis II and R. E. Stearns, “Syntax-ditected transduction”, Journal of the Association for Computing Machinery, vol. 15, 1968, 465–488.
• [37] S. Mazanek and M. Minas, “Functional-logic graph parser combinators”, Lecture Notes in Computer Science, vol. 5117, 2008, 261–275.
• [38] M. D. Mickunas, R. L. Lancaster, and V. B. Schneider, “Transforming LR(k) grammars to LR(1), SLR(1), and (1,1) bounded right-context grammars”, Journal of the Association for Computing Machinery, vol. 23, 1976, 511–533.
• [39] K. J. Peng, T. Yamamoto, and Y. Aoki, “A new parsing scheme for plex grammars”, Pattern Recognition, vol. 23, 1990, 393–402.
• [40] J. L. Pfaltz and A. Rosenfeld, “Web grammars”. In: Proceedings First Int. Conf. Artificial Intelligence, 1969, 609–619.
• [41] T. W. Pratt, “Pair grammars, graph languages and string-to-graph translations”, Journal of Computer and System Sciences, vol. 5, 1971, 560–595.
• [42] J. Rekers and A. Schürr, “Defining and parsing visual languages with layered graph grammars”, Journal of Visual Languages and Computing, vol. 8, 1997, 27–55.
• [43] A. Rosenfeld and D. L. Milgram. “Web automata and web grammars”. In: B. Meltzer and E. Michie, eds., Machine Intelligence 7. Edinburgh University Press, Edinburgh, 1972.
• [44] D. J. Rosenkrantz and R. E. Stearns, “Properties of deterministic top-down grammars”, Information and Control, vol. 17, 1970, 226–256.
• [45] G. Rozenberg, ed., Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 1: Foundations, World Scientific: Singapore, 1997.
• [46] G. Rozenberg and E. Welzl, “Boundary NLC graph grammars - basic definitions, normal forms, and complexity”, Information and Control, vol. 69, 1986, 136–167.
• [47] S. Seifert and I. Fischer, “Parsing string generating hypergraph grammars”, Lecture Notes in Computer Science, vol. 3256, 2004, 352–367.
• [48] Q. Y. Shi and K. S. Fu, “Parsing and translation of attributed expansive graph languages for scene analysis”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 5, 1983, 472–485.
• [49] A. O. Slisenko, “Context-free grammars as a tool for describing polynomial-time subclasses of hard problems”, Information Processing Letters, vol. 14, 1982, 52–56.
• [50] M. Tucci, G. Vitiello, and G. Costagliola, “Parsing nonlinear languages”, IEEE Trans. Software Engineering, vol. 20, 1994, 720–739.
• [51] G. Turan. “On the complexity of graph grammars”. Rep. automata theory research group, Szeged, Hungary, 1982.
• [52] W. Vogler, “Recognizing edge replacement graph languages in cubic time”, Lecture Notes in Computer Science, vol. 532, 1991, 676–687.
• [53] L. M. Wills, “Using attributed graph parsing to recognize clichés in programs”, Lecture Notes in Computer Science, vol. 1073, 1996, 170–184.
• [54] K. Wittenburg, L. Weitzman, and J. Talley, “Unification-based grammars and tabular parsing for graphical languages”, Journal of Visual Languages and Computing, vol. 2, 1991, 347–370.
• [55] D. Q. Zhang, K. Zhang, and J. Cao, “A contextsensitive graph grammar formalism for the specification of visual languages”, The Computer Journal, vol. 44, 2001, 186–200.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).