Search

We consider a restricted variant of the hairpin completion called bounded hairpin completion. The hairpin completion is a formal operation inspired from biochemistry. Applied to a word encoding a single stranded molecule x such that either a suffix or a prefix of x is complementary to a subword of x , hairpin completion produces a new word z , which is a prolongation of x to the right or to the left by annealing. The restriction considered here concerns the length of all prefixes and suffixes that are added to the current word by hairpin completion. They cannot be longer than a given constant. Closure properties of some classes of formal languages under the non-iterated and iterated bounded hairpin completion are investigated. We also define the inverse operation, namely bounded hairpin reduction, and consider the set of all primitive bounded hairpin roots of a regular language.

Duplication and repeat-deletion are the basic models of errors occurring during DNA replication from the viewpoint of formal languages. During DNA replication, subsequences of a strand of DNA may be copied several times (duplication) or skipped (repeat-deletion). Iterated duplication and repeat-deletion have been well-studied, but little is known about single-step duplication and repeat-deletion. In this paper, we investigate properties of these operations, such as closure properties of language families in the Chomsky hierarchy, language equations involving these operations. We also make progress towards a characterization of regular languages that are generated by duplicating a regular language.

Duplication is an operation generating a language from a single word by iterated application of rewriting rules u →uu on factors. We extend this operation to entire languages and investigate, whether the classes of the Chomsky hierarchy are closed under duplication. Here we treat mainly bounded duplication, where the factors duplicated cannot exceed a given length. While over two letters the regular languages are closed under bounded duplication, over three or more letters they are not, if the length bound is 4 or greater. For 2 they are closed under duplication, the case of 3 remains open. Finally, the class of context-free languages is closed under duplication over alphabets of any size.

In this paper, we provide some properties of classes of regular languages consisting of directing words of directable automata and some new results on the shortest directing words of nondeterministic directable automata.

The notations used below are standard. In particular, if A ⊆ X* is a language, then the principal congruence P A of A is defined as follows: For any u, υ ∈ X*, u ≡ υ(P A ) if and only if (xuy ∈ A ↔ xvy ∈ A) for any x, y ∈ X*.

In this paper, we define the n-insertion A ⊳ [n] B of a language A into a language B and provide some properties of n-insertions. For instance, the n-insertion of a regular language into a regular language is regular but the n-insertion of a context-free language into a context-free language is not always context-free. However, it can be shown that the n-insertion of a regular (context-free) language into a context-free (regular) language is context-free. We also consider the decomposition of regular languages under n-insertion.

In this paper, we consider the language over an alphabet T generated by a given Petri net with a positive initial marking, called a CPN language. This language becomes a prefix code over T. We are interested in CPN languages which are maximal prefix codes, called mCPN languages over T. We will investigate various properties of mCPN languages. Moreover, we will prove that a CPN language is a context-sensitive language in two different ways.

In [5], the directable non deterministic automata are studied. For non-deterministic automata, the directability can be defined in several ways. In each case considered, the directing words constitute a regular language and one can study the families of such regular languages. In this paper, six classes of regular languages are defined in accordance with the different definitions of directability given in [5], and we investigate the properties of the classes considered.

In this paper, we propose a new methodology for decomposing pattern classification problems based on the class relations among training data. We also propose two combination principles for integrating individual modules to solve the original problem. By using the decomposition methodology, we can divide a K-class classification problem into \(\left( {\begin{array}{*{20}c}K \\2 \\\end{array} } \right)\) relatively smaller two-class classification problems. If the twoclass problems are still hard to be learned, we can further break down them into a set of smaller and simpler two-class problems. Each of the two-class problem can be learned by a modular network independently. After learning, we can easily integrate all of the modules according to the combination principles to get the solution of the original problem. Consequently, a K-class classification problem can be solved effortlessly by learning a set of smaller and simpler two-class classification problems in parallel.

Let Q be the set of primitive words over a finite alphabet having at least two letters. We prove that Q has two rather strong context-free-like properties. The first one is that Q satisfies the nonempty, strong variant of Bader and Moura's iteration condition, and the second one is that intersecting Q with any member of a special, infinite family of regular languages, we get a context-free language. We also present two further related results. It remains an unsolved problem whether Q is non-context-free (we conjecture this).

Skew-morphisms are generalizations of endomorphisms. Sequential functions, automaton mappings and length-preserving word functions are special cases of skew-morphisms. Properties of skew-morphisms of free monoids are given, as well as a general method to construct them. Images of skew-morphisms and inverse skewmorphisms are considered. Replacing morphisms by skew-morphisms, generalizations of DOL systems, called SKDOL systems are introduced naturally. Some relations between generalized sequential functions and skew-morphisms are studied. In particular, a characterization of skew-morphisms that are generalized sequential functions is given and it is shown that in general skew-morphisms do not preserve regularity of languages.