The Design Of Efficient Algorithms for Syntactic Pattern Generation And Matching

Abstract

Picture generation using formal grammars is one of the most explored _elds of the- newlineoretical computer science. Pattern generation and matching has several applications newlineespecially in picture processing, pattern recognition and image analysis. Recently newlinethere has been some work on pattern generation and matching in which the text is newlinegenerated by a grammar. This is known as syntactic pattern matching. In this thesis, newlinewe have approached the syntactic pattern generation and matching problems in two newlineand three dimensions in which the text (or image) is generated by grammars. newlineWe have considered pattern generation and matching problems in two and three newlinedimensions: substring and subsequence matching problems in CFG, approximate newlinematching with two dimensional context free grammars, pure hexagonal context free newlinegrammar generating hexagonal pattern, hexagonal online tessellation acceptor. In newlineaddition to that, we have also proved some of the properties of hexagonal online newlinetessellation acceptor. newlineWe have proposed algorithms for substring and subsequence matching in CFG. newlineFor CFG the algorithm runs in O(n3) time complexity for recognizing context free newlinelanguages, where n is the length of the input string. Next we have considered ap- newlineproximation pattern matching scheme for two dimensional contexts free grammars. newlineIn this scheme, we have given polynomial time algorithms. newlineIn this thesis, we discuss pure hexagonal context free grammar which is related newlineto isometric array grammars. The notion of pure hexagonal context free grammar newlineinvolves only terminal symbols as in any pure grammar and tables of context free newlinerules. Here we introduce a new hexagonal context free grammar based on pure context newlinefree rules, called pure hexagonal context free grammar for hexagonal picture array newlinegeneration. These grammars generate hexagonal picture arrays on triangular grids. newlineWe also examine certain closure properties of pure hexagonal context free languages. newlineIn this model we allow rewriting from upper left vertex to upper right vertex, upper newlineright to right most v