Search

In formal language theory, a grammar is a set of production rules that describes the possible strings in a given language. Context-free grammars, the most applicable type of the grammars, may contain production rules that do not generate any string of the language or affect the string generation processes using several unnecessary steps. Thus, the elimination of such undesirable productions is important for the optimization of the string generation processes. The "cleaning" of context-free grammars is done through the simplification process consisting of a useful substitution rule, removal of useless productions, removal of λ − productions, and removal of unit-productions. This paper presents the simplification of static Watson-Crick context-free grammars; the grammatical counterparts of sticker systems that generate double-stranded strings using context-free rules, several transformations, and substitutions. The simplification process of static Watson-Crick context-free grammars is similar to the simplification process of arbitrary context-free grammars and Watson-Crick context-free grammars. This research shows that for every static Watson-Crick context-free language, there exists an equivalent static Watson-Crick context-free grammar without useless productions, λ − productions, and unit-productions. [ABSTRACT FROM AUTHOR]

In DNA computing, a sticker system is a computing mechanism involving the Watson-Crick complementarity of DNA molecules. The sticker system is known as a language generating device based on the sticker operation which is analyzed through the concept of formal language theory. The grammar of a formal language can be described by determining finite sets of variables, terminal symbols and production rules. Research on the grammar which uses the Watson-Crick complementarity has been done previously, known as Watson-Crick grammars. As an improvement to the Watson-Crick grammars, the static Watson-Crick grammars have been proposed as an analytical counterpart of sticker system which consist of regular grammar, linear grammar and context-free grammar. In this research, the closure properties of static Watson-Crick linear and context-free grammars are investigated. The result shows that the families of languages generated by static Watson-Crick linear and context-free grammars are closed under different operations. [ABSTRACT FROM AUTHOR]

In group theory, conjugacy class is a method of partitioning the elements of a group such that the elements a and b are conjugate in a group G if xax-1 = b for some x in G. Meanwhile, a point group is a set of symmetry operations that keeps at least one point in a molecule fixed. In chemistry, symmetry of molecules is important since chemists classify molecules based on their symmetry. In this research, the conjugacy classes of point groups of order at most eight are computed. The conjugacy classes of these groups are then applied to graph theory to obtain the conjugacy class graph, which is a graph whose vertices V = (v1,...,vn) are the non-central conjugacy classes of a group and the two vertices are connected if their cardinalities are not coprime, that is the greatest common divisor of the cardinalities of the corresponding vertices is not equal to one. [ABSTRACT FROM AUTHOR]