Words, Semigroups, and Transductions

The following sections are included:

• Preface

• Contents

We study the structure of partially ordered monoids generated by certain operators on families of fuzzy languages. These operators are induced by simple, well-known operations on fuzzy languages, like fuzzy homomorphism, fuzzy finite substitution and intersection with regular fuzzy languages. The structure of these monoids provides better insight in the (in)dependency of closure properties of some families of fuzzy languages.

The present paper is part of a larger research activity aiming at transferring to linguistics several operations inspired from genetics. Here we deal with mixed links, that are a type of operations based on DNA biochemistry which however do not exist in nature. In short, we combine pieces with blunt ends with pieces with staggered ends. In this paper we will apply this operation to linguistic structures checking out if it is useful to explain some syntactic phenomena, in general, with examples from Catalan.

Estimations of truth values of the Liar's Paradox, computed in an infinite valued logic, may produce chaotic sequences which can be generated by simple morphisms. Web, Cantor, and dragon plots will illustrate sensitivity to initial conditions. Relations to Maxwell's demon, Thue-Morse, and Mephisto-Waltz numbers will also be discussed.

We further investigate here the hairpin languages defined in [13] and introduce a similar type of languages, namely the loop languages, for which we study some decidability matters. Then related operations are defined and the closure properties of the families in the Chomsky hierarchy under these operations are considered. Finally, a few directions for further research in this area are briefly discussed.

A conditional grammar is a usual context-free grammar where with any production a regular set is associated as a condition, and a rule p with condition R can be applied to a sentential form w if and only if ω ∈ R. In this paper we restrict the regular languages used as conditions by syntactic complexity measures as the number of nonterminals or productions which are necessary to generate the language by regular grammars or the number of states necessary to accept the language by deterministic finite automata. With respect to the number of nonterminals or states we obtain a finite hierarchy whereas the number of productions produces an infinite hierarchy.

We introduce a new type of directed graph completeness and we characterize the class of digraphs having this property. Some consequences of this characterization are also discussed.

Ciliates (an ancient group of single cell organisms) have two sorts of nuclei with different functionalities: the micronucleus and the macronucleus. After the cell mating the micronuclear genes are converted into the macronuclear genes in the process called gene assembly. This is one of the most complex examples of DNA processing known in any organisms, and it is fascinating from the computational point of view. This paper continues the investigation of gene assembly in the framework of three molecular operations: ld-excision, hi-excision/reinsertion, and dlad-excision/reinsertion. In general, for a given micronuclear gene there exists many strategies for using these three operations to accomplish gene assembly. Since it is not known yet which strategies are actually used by ciliates, it is important to study the invariants of gene assembly, i.e., those properties of gene assembly that are common to all these strategies. A macronuclear gene (before its excision and capping with telomeres) can be assembled either in a linear or in a circular molecule. We prove in this paper that the circularity property (whether or not a given gene will be assembled in a circular molecule) is an invariant. We give a simple decision algorithm for the circularity property, and discuss a number of other related invariants.

We prove that for any finite commutative ordered semiring K such that 0 ≤ K for all k ∈ K, and for any set A, theK-semialgebra K^rat«A*» of rational power series over A with coefficients in K is freely generated by the set A in the class of all ordered K-semialgebras equipped with a star operation satisfying the fixed point identity, the least pre-fixed point rule and its dual. When K is the boolean semiring B = {0,1}, this gives Kozen's axiomatization of the equational theory of the regular sets.

A language L over a finite alphabet X containing more than one letter is a forest language if L = ∪_f∈Λf⁺ for some Λ ⊆ Q, where Q is the set of all primitive words over X. If X⁺ is a disjoint union of subsemigroups S_i, then each S_i is a forest language. Moreover, the natural languages like Dyck language D and the balanced language H are examples of forest languages. A pair of languages (A, B) is a catenation closed pair if A ∩ B = ∅ and each is closed under catenation. For a subsemigroup L, L is a forest language if and only if L is pure. For a catenation closed pair (A, B), we give a characterization of the fact that both A and B are forest languages. We obtained a characterization of the fact that the pair (A, Ā) is a catenation closed pair, where Ā = X⁺\A. In Section 3, we investigate the free property of A and Ā, when (A, Ā) is a catenation closed pair and, in fact, we are able to list all the cases that can appear.

We discuss an extension of valence grammars, where the value of a valid derivation is allowed to be an element of a given target set. We discuss closure properties of language families generated by such grammars. Moreover, we investigate the generative power of valence grammars with target sets over the groups ℤ^k, over the monoids ℕ^k and over finite monoids. This way, we also prove a conjecture due to M. Jantzen stating that unordered vector languages can be characterized by grammars controlled by permutations of regular languages. Furthermore, we show that matrix languages are characterized by valence grammars with target sets over (arbitrary) finite monoids.

In this paper, the monotone tree and nondeterministic tree automata are studied. First, the isomorphically complete systems of tree automata for the class of monotone tree automata are characterized with respect to the α₀-product. Then it is proved that every monotone nondeterministic tree automaton can be embedded into a suitable α₀-power of a monotone nondeterministic tree automata of three states. Finally, it is shown that there is no isomorphically complete system for the class of monotone nondeterministic tree automata with respect to the α₀-product which consists of two-state monotone nondeterministic automata.

The sets recognized by deterministic root-to-frontier tree recognizers, the DR tree languages, are determined by their path languages. A path language of a tree language T consists of the words describing the paths leading from the root of a tree in T to its leaves labeled with a given leaf symbol. The Nerode path congruence of a tree language T is defined as the greatest right congruence saturating all path languages of T. We prove a Nerode-like theorem for DR tree languages and show how Nerode path congruences correspond to minimal DR recognizers. Similarly, the greatest congruence saturating the path languages yields the syntactic path monoid of T which is finite for a path closed T exactly in case T is a DR tree language.

The fact that each word in a free semigroup is uniquely expressible as a positive integer power of a primitive word allows the words in a free semigroup to be displayed in a coherent manner as co-ordinate pairs on a half plane. The traditional x-axis is labeled with primitive words and the upper portion of the y-axis is labeled with positive integers in the usual fashion of elementary algebra. Since languages are subsets of free semigroups they may then be viewed as subsets of the resulting half plane. This suggests new, visually motivated, language concepts and questions for investigation. In order to produce a simple visual display of any given language, we allow the primitive words to be ordered along the x-axis in whatever manner will yield a suggestive and coherent display of the language. We say that two languages are sketch equivalent if two, possibly distinct, orderings of the set of primitive words can be found with respect to which the displays of the two languages coincide. We associate a set of invariants with each language in such a way that two languages are sketch equivalent if and only if they have the same set of invariants. For each regular language the set of invariants is finite. Moreover, an effective procedure is given for computing the set of invariants of a regular language. Definitions are given for ten classes of languages suggested by visual considerations. Membership of a language in each of the ten defined classes can be determined by inspecting the invariants of the language. We hope that the visual approach taken here will stimulate the development of additional concepts and that the effective procedures given can be extended beyond the class of regular languages.

Latteux and Thierrin have characterized sparse context-free languages by showing that a context-free language L is sparse if and only if L is bounded. We prove a similar result for binary 0L languages which are not D0L languages.

A language L is k-poly-slender if the number of words of length n in L is of order and Parikh k-poly-slender if the number of words with the same Parikh vector is of order . We give a characterization of Parikh k-poly-slender context-free languages and prove the decidability of both k-poly-slenderness and Parikh k-poly-slenderness for context-free languages.

Introducing a new partial product on a locally inverse *-semigroup, we characterize a prehomomorphisms between locally inverse *-semigroups.

In 1988 X-machines were proposed as a basis for a possible specification language and since then a number of further investigations have demonstrated the value of this idea. A number of classes of X-machines have been identified and studied, most importantly the class of stream X-machines. A theory of testing based on stream X-machine translators has also been developed. This allows the generation of test sets that are proved to guarantee the correctness of implementation against the specification under certain circumstances. This paper extends this theory in more than one way. Firstly, it considers the general X-machine model rather than the particular stream X-machine class. Secondly, a non-deterministic device is considered and two different testing strategies are defined.

In this note we present some new results on BCK structures, mainly about finite BCK.

First, we give a new definition of BCK which is equivalent to an old definition (for example, see [1], [5], [7], [8]). Let P be a set with a partial order ≤. We assume that P has a least element 0, and that a binary operation * is defined on P. The partial relation ≤ is reflexive, antisymmetric, and transitive…

We prove that the Parikh sets of ET0L languages are exactly the sets of vectors of natural numbers computed by P systems (without cooperating rules, without priorities, and without target indications) which can create new membranes as a result of objects evolution (at any moment of a computation, the number of membranes is bounded by a given constant; two membranes at any moment are sufficient).

We introduce the concepts of disjunctivity and syntactic morphism for general algebras; these specialize to the usual ones for semigroups and monoids. Moreover we review some of the results on disjunctivity, in particular, those that are due to G. Thierrin or related to his work.

We introduce and investigate an operation with strings suggested by DNA processing (by means of exonucleases): the operation of cutting strings of equal length from the beginning and the end of a string. A related operation is that of cutting a square of a string from the prefix of a string. The closure properties of families in the Chomsky hierarchy are investigated (and, with some exceptions, settled).

It is proved by Ito et al. in [8] that the construction of 2-codes defined over an alphabet Y consisting of at least two elements may be reduced to the construction of primitive words over Y. In this paper we give some grammars generating sets of primitive words.

A uniquely parsable grammar (UPG) introduced by Morita et al. (1997) is a kind of generative grammar, where parsing can be performed without backtracking. In this paper, we investigate a uniquely parallel parsable grammar (UPPG). We give a simple sufficient condition on morphism languages, and show that every such morphism language can be parsed efficiently in parallel by a UPPG. We show that the Fibonacci and Thue-Morse languages, which are instances of such languages, can be parsed in logarithmic time in parallel by UPPGs.

Iterated (finite state sequential) transducers are generative devices well studied in formal language theory (e.g., in relation to Lindenmayer systems, and DNA computing). It is known that such mechanisms can characterize the family of recursively enumerable languages, and recently it was proven that four states are enough in order to characterize the recursively enumerable languages, three states cover the ET0L languages, while two states can cover the E0L (hence also contextfree) languages. Here we continue the study of such devices, by showing that context-sensitive languages can be generated with only three states. This allows us to obtain another proof of the universality of four states, and some simple corollaries. Some open problems concern with the optimality of our results and with the relationship between the four states universality and the Geffert normal form for recursively enumerable languages.

A time-varying distributed H system (in short, a TVDH system) of degree n is a well-known model of splicing computations which has the following special feature: at different moments one uses different sets of splicing rules (the number of these sets of splicing rules is called the degree of the TVDH system). It is known that there is a universal TVDH system of degree 1. Now we prove that TVDH systems of degree 1 generate all recursively enumerable languages.

By proving that they accept some quite complicated languages it is shown that the RRWW-automata of Jančar et al (1998) are fairly powerful. In particular, it is shown that they accept an NP-complete language, which implies that the closure LOG-RRWW of the class of languages accepted by RRWW-automata under log-space reductions coincides with the complexity class NP.

A new controlled context-free grammar, called Parikh controlled context-free grammar, is defined. Such a grammar has a control function which maps the Parikh vector of the current sentential form to the set of productions to be applied to the current sentential form. It is shown that the family of languages generated by Parikh controlled context-free grammars coincides with the family of recursively enumerable languages. Some restricted Parikh controlled grammars are considered as well as their generative power.

In [1] the concept of nondecreasing Dyck paths was introduced. We continue this research by looking at it from the point of view of words, rational languages, planted plane trees, and continued fractions. We construct a bijection with planted plane trees of height ≤ 4 and compute various statistics on trees that are the equivalents of nondecreasing Dyck paths.

The following sections are included:

• Introduction

• Semilattice Amalgamation

• Symmetry and the Semidirect Product

• References

The following sections are included:

• Introduction

• Preliminaries

• Main Results

• References

Watson-Crick complementarity can be viewed as a language-theoretic operation: “bad” words obtained through a generative process are replaced by their complementary ones. This idea seems particularly suitable for Lindenmayer systems. D0L systems augmented with a specific complementarity transition, Watson-Crick D0L systems, have turned out to be a most interesting model and have already been extensively studied. In the present paper, attention is focused on Watson-Crick D0L systems, where the alphabet is the original four-letter DNA alphabet {A, G, T, C}. Growth functions and various decision problems will be investigated. Previously known cases about growth functions that are not Z-rational deal with alphabets bigger than the DNA alphabet, and it has been an open problem whether similar constructions can be carried out for the DNA alphabet. The main result in this paper shows that this is indeed the case.

The following sections are included:

• Notation

• Preliminary Considerations

• The ω-Language of Disjunctive Sequences

• The Topology of Forbidden Words

• A Metric Related to Languages

• References

The following sections are included:

• GABRIEL THIERRIN
  • The Publications of Gabriel Thierrin