[p2] Ideas for new applications


[p2-25]

Parsing Watson-Crick Languages using the Kalman Filter

N.L.M. Zulkufli (International Islamic University Malaysia), S. Turaev (International Islamic University Malaysia)

 
Abstract

To discover the possible languages contained in deoxyribonucleic acids (DNA) and new computing methods, several models based on DNA and theory of automata have been introduced, such as Watson-Crick automata and grammars. These models can recognize/generate languages more powerful than those of the widely used Chomsky context-free languages, thus opening a new possible path in parsing algorithms for programming languages, natural language processing, and DNA data analysis. However, the computation complexity for parsing using these models are higher than Chomsky context-free grammars, as there are more possible paths to consider. This leads to difficulties in implementing the models in analysis of real data. The Kalman filter may be one of good solutions to help solving this problem. First, we build a toy model from a Watson-Crick finite automaton or Watson-Crick regular grammar. The problem chosen is the parsing problem. To help the model choose the correct path according to the given language, an additional parameter, for example, weight, is equipped with the help of Kalman filter. If successful, the use of (extended) Kalman filter in extended models such as Watson-Crick context-free grammars and Watson-Crick pushdown automata might be possible, thus leading to more efficient data assimilation methods with real data.