Two – Dimensional Grammars Based on Patterns

Authors

  • Kezia Parimalam
  • j.D. Emerald Emerald

Keywords:

Two-dimensional patterns, Component, Two-dimensional axioms, Catenation, Factorization of arrays

Abstract

A language generating model called Pattern languages was introduced by Dassow , motivated by Angulin’s Pattern languages that use strings as language descriptors. Investigation of patterns has been of relevance in many areas such as combinatorics on words, learning theory and so on. Pattern grammars provide an alternative method in defining languages in automaton theory. Several methods to generate two-dimensional languages known as array languages or picture languages have been defined and investigated in literature and they have been extending the techniques and results of formal string language theory. A picture is defined as a rectangular array of terminal symbols in a rectangular plane. In this paper we extend the Pattern languages defined for strings by Dassow, to a two-dimensional case, while the simplicity and compactness of their descriptors as defined in one dimensional case are preserved. Hence, Two-dimensional Pattern languages are defined and investigated for their closure properties based on array operations.

References

[1] D. Angulin, “Finding Pattern common to set of strings,” Journal of Computer and System Sciences 21, 46-62, (1980)

[2] D. Giammarresi, A. Restivo, “Recognizable picture languages," International Journal of Pattern Recognition and Artificial Intelligence. 6:31-46, 1992.

[3] H. Fernau, Markus L. Schmid, K.G. Subramanian, “Two-Dimensional Pattern Languages”, In S.Bensch, F. Drewes, R. Freund, and F.Otto, editors, “Fifth Workshop on Non-Classical Models for Automata and Applications, NCMA, Volume 294 of books@ocg.at, pp.117-132. Osterreichische Computer Gesellschaft, 2013.

[4] J. Dassow, G.Paun, A.Salomaa, “Grammars based on Patterns,” International Journal of Foundations of Computer Science, Vol 4: 1-14, 1993.

Downloads

Published

2025-11-25

How to Cite

[1]
C. Kezia Parimalam and j.D. E. Emerald, “Two – Dimensional Grammars Based on Patterns”, Int. J. Comp. Sci. Eng., vol. 7, no. 5, pp. 216–220, Nov. 2025.

Issue

Vol. 7 No. 5 (2019): IJCSE Special Issue Mar Edition

Section

Research Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.