×

An algorithm for hypergraph completion according to hyperedge replacement grammars. (English) Zbl 1175.68228

Ehrig, Hartmut (ed.) et al., Graph transformations. 4th international conference, ICGT 2008, Leicester, United Kingdom, September 7–13, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-87404-1/pbk). Lecture Notes in Computer Science 5214, 39-53 (2008).
Summary: The algorithm of Cocke, Younger, and Kasami is a dynamic programming technique well-known from string parsing. It has been adopted to hypergraphs successfully by Lautemann. Therewith, many practically relevant hypergraph languages generated by hyperedge replacement can be parsed in an acceptable time. In this paper we extend this algorithm by hypergraph completion: If necessary, appropriate fresh hyperedges are inserted in order to construct a derivation. The resulting algorithm is reasonably efficient and can be directly used, among other things, for auto-completion in the context of diagram editors.
For the entire collection see [Zbl 1148.68002].

MSC:

68Q42 Grammars and rewriting systems
05C65 Hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)

Software:

AToM3; DiaGen
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Drewes, F.; Habel, A.; Kreowski, H. J.; Rozenberg, G., Hyperedge replacement graph grammars, Handbook of Graph Grammars and Computing by Graph Transformation, Foundations, 95-162 (1997), Singapore: World Scientific, Singapore · Zbl 0908.68095
[2] Lautemann, C., The complexity of graph languages generated by hyperedge replacement, Acta Inf., 27, 5, 399-421 (1989) · Zbl 0725.68055 · doi:10.1007/BF00289017
[3] Kasami, T.: An efficient recognition and syntax analysis algorithm for context free languages. Scientific Report AF CRL-65-758, Air Force Cambridge Research Laboratory, Bedford, Massachussetts (1965)
[4] Minas, M., Concepts and realization of a diagram editor generator based on hypergraph transformation, Science of Computer Programming, 44, 2, 157-180 (2002) · Zbl 1002.68735 · doi:10.1016/S0167-6423(02)00037-0
[5] Mazanek, S.; Minas, M.; Voronkov, A., Functional-logic graph parser combinators, RTA 2008, 261-275 (2008), Heidelberg: Springer, Heidelberg · Zbl 1145.68376
[6] Minas, M.: Spezifikation und Generierung graphischer Diagrammeditoren. Shaker-Verlag, Aachen (2001) zugl. Habilitationsschrift Universität Erlangen-Nürnberg (2000)
[7] Bengoetxea, E.; Pedro Larra, n.; Bloch, I.; Perchant, A.; Figueiredo, M.; Zerubia, J.; Jain, A. K., Estimation of distribution algorithms: A new evolutionary computation approach for graph matching problems, Energy Minimization Methods in Computer Vision and Pattern Recognition, 454-468 (2001), Heidelberg: Springer, Heidelberg · Zbl 1001.68882 · doi:10.1007/3-540-44745-8_30
[8] Kaul, M.; Tinhofer, G.; Schmidt, G., Specification of error distances for graphs by precedence graph grammars and fast recognition of similarity, Graph-Theoretic Concepts in Computer Science, 29-40 (1987), Heidelberg: Springer, Heidelberg · Zbl 0643.68132
[9] Sánchez, G.; Lladós, J.; Tombre, K.; Blostein, D.; Kwon, Y.-B., An error-correction graph grammar to recognize texture symbols, Graphics Recognition. Algorithms and Applications, 128-138 (2002), Heidelberg: Springer, Heidelberg · Zbl 1064.68556 · doi:10.1007/3-540-45868-9_10
[10] Costagliola, G.; Deufemia, V.; Polese, G.; Risi, M., Building syntax-aware editors for visual languages, Journal of Visual Languages and Computing, 16, 6, 508-540 (2005) · doi:10.1016/j.jvlc.2005.06.001
[11] de Lara, J.; Vangheluwe, H.; Kutsche, R.-D.; Weber, H., Atom3: A tool for multi-formalism and meta-modelling, Fundamental Approaches to Software Engineering, 174-188 (2002), Heidelberg: Springer, Heidelberg · Zbl 1059.68561
[12] Sen, S., Baudry, B., Vangheluwe, H.: Domain-specific model editors with model completion. In: Multi-paradigm Modelling Workshop at MoDELS 2007 (2007)
[13] Taentzer, G., Crema, A., Schmutzler, R., Ermel, C.: Generating domain-specific model editors with complex editing commands. In: Proc. Third Intl. Workshop and Symposium on Applications of Graph Transformation with Industrial Relevance (AGTIVE 2007) (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.