Watson Crick automata are finite automata working on double strands. Extensive research work has already been done on non deterministic Watson Crick automata and on deterministic Watson Crick automata. Parallel Commun...Watson Crick automata are finite automata working on double strands. Extensive research work has already been done on non deterministic Watson Crick automata and on deterministic Watson Crick automata. Parallel Communicating Watson Crick automata systems have been introduced by E. Czeziler et al. In this paper we discuss about a variant of Watson Crick automata known as the two-way Watson Crick automata which are more powerful than non-deterministic Watson Crick automata. We also establish the equivalence of different subclasses of two-way Watson crick automata. We further show that recursively enumerable (RE) languages can be realized by an image of generalized sequential machine (gsm) mapping of two-way Watson-Crick automata.展开更多
η-quantum languages are discussed and some of their properties are derived. Furthermore the q-quantum language is defined. It is shown that L(A1A2)=L(A1)∩L(A2), L(A)=L(A1)∪L(A2). So over the same alphabet the int...η-quantum languages are discussed and some of their properties are derived. Furthermore the q-quantum language is defined. It is shown that L(A1A2)=L(A1)∩L(A2), L(A)=L(A1)∪L(A2). So over the same alphabet the intersection and union of two different q-quantum languages are also q-quantum languages.展开更多
We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be ...We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be decomposed into at least two nontrivial codes as the same for the languages. In the paper, a linear time algorithm is designed, which finds the prime decomposition. If codes or finite languages are presented as given by its minimal deterministic automaton, then from the point of view of abstract algebra and graph theory, this automaton has special properties. The study was conducted using system for computational Discrete Algebra GAP. .展开更多
Some concepts in Fuzzy Generalized Automata （FGA） are established. Then an important new algorithm which would calculate the minimal FGA is given. The new algorithm is composed of two parts： the first is called E-r...Some concepts in Fuzzy Generalized Automata （FGA） are established. Then an important new algorithm which would calculate the minimal FGA is given. The new algorithm is composed of two parts： the first is called E-reduction which contracts equivalent states, and the second is called RE-reduction which removes retrievable states. Finally an example is given to illuminate the algorithm of minimization.展开更多
Due to its importance in security, syntax analysis has found usage in many high-level programming languages. The Lisp language has its share of operations for evaluating regular expressions, but native parsing of Lisp...Due to its importance in security, syntax analysis has found usage in many high-level programming languages. The Lisp language has its share of operations for evaluating regular expressions, but native parsing of Lisp code in this way is unsupported. Matching on lists requires a significantly more complicated model, with a different programmatic approach than that of string matching. This work presents a new automata-based approach centered on a set of functions and macros for identifying sequences of Lisp S-expressions using finite tree automata. The objective is to test that a given list is an element of a given tree language. We use a macro that takes a grammar and generates a function that reads off the leaves of a tree and tries to parse them as a string in a context-free language. The experimental results indicate that this approach is a viable tool for parsing Lisp lists and expressions in the abstract interpretation展开更多
The limit inguages of cellular automata are defined and their complexity are discussed. New tools, which include skew evolution, skew periodic string, trace string, some algebraic calculation method, and restricted me...The limit inguages of cellular automata are defined and their complexity are discussed. New tools, which include skew evolution, skew periodic string, trace string, some algebraic calculation method, and restricted membership problem, are developed through a discussion focusing on the limit language of an elementary cellular automata of rule 94. It is proved that this language is non-regular.展开更多
文摘Watson Crick automata are finite automata working on double strands. Extensive research work has already been done on non deterministic Watson Crick automata and on deterministic Watson Crick automata. Parallel Communicating Watson Crick automata systems have been introduced by E. Czeziler et al. In this paper we discuss about a variant of Watson Crick automata known as the two-way Watson Crick automata which are more powerful than non-deterministic Watson Crick automata. We also establish the equivalence of different subclasses of two-way Watson crick automata. We further show that recursively enumerable (RE) languages can be realized by an image of generalized sequential machine (gsm) mapping of two-way Watson-Crick automata.
基金The National Science Foundation of China(No.10671030)
文摘η-quantum languages are discussed and some of their properties are derived. Furthermore the q-quantum language is defined. It is shown that L(A1A2)=L(A1)∩L(A2), L(A)=L(A1)∪L(A2). So over the same alphabet the intersection and union of two different q-quantum languages are also q-quantum languages.
文摘We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be decomposed into at least two nontrivial codes as the same for the languages. In the paper, a linear time algorithm is designed, which finds the prime decomposition. If codes or finite languages are presented as given by its minimal deterministic automaton, then from the point of view of abstract algebra and graph theory, this automaton has special properties. The study was conducted using system for computational Discrete Algebra GAP. .
基金Supported by Supported by National Natural Science Foundation of China (No.60074014)
文摘Some concepts in Fuzzy Generalized Automata （FGA） are established. Then an important new algorithm which would calculate the minimal FGA is given. The new algorithm is composed of two parts： the first is called E-reduction which contracts equivalent states, and the second is called RE-reduction which removes retrievable states. Finally an example is given to illuminate the algorithm of minimization.
文摘Due to its importance in security, syntax analysis has found usage in many high-level programming languages. The Lisp language has its share of operations for evaluating regular expressions, but native parsing of Lisp code in this way is unsupported. Matching on lists requires a significantly more complicated model, with a different programmatic approach than that of string matching. This work presents a new automata-based approach centered on a set of functions and macros for identifying sequences of Lisp S-expressions using finite tree automata. The objective is to test that a given list is an element of a given tree language. We use a macro that takes a grammar and generates a function that reads off the leaves of a tree and tries to parse them as a string in a context-free language. The experimental results indicate that this approach is a viable tool for parsing Lisp lists and expressions in the abstract interpretation
基金the Special Funds for Major State Basic Research Projects.
文摘The limit inguages of cellular automata are defined and their complexity are discussed. New tools, which include skew evolution, skew periodic string, trace string, some algebraic calculation method, and restricted membership problem, are developed through a discussion focusing on the limit language of an elementary cellular automata of rule 94. It is proved that this language is non-regular.
