Words, Languages & Combinatorics III

Preface.

Table of Contents.

This is a survey of recent results related to semidirect products of an arbitrary pseudovariety with the pseudovariety of all finite groups. The main flavour is the establishment of links between various operators on pseudovarieties, some obviously computable, others known not to be so. This not only leads to decidability results but does so in a sort of uniform way which has a structural tint even though the arguments are mostly syntactical.

This paper proposes an algebraic way of sentence valuations in a semiring. Actually, throughout the paper only valuations in the ring of integers with usual addition and multiplication are considered. These valuations take into consideration both words and their positions within the sentences. Two synonymy relations, with respect to a given valuation, are introduced. All sentences that are synonymous form a synonymy class which is actually a formal language. Some basic problems regarding the synonymy classes are formulated in the general setting but the results presented concern only very special valuations.

A constructive proof of the equation.

is presented where H denotes any arborescent pseudovariety of groups. In addition, a larger class of pseudovarieties of groups is found for which that equation holds.

We introduce a new notion of the arithmetical complexity of a word, that is, the number of words of a given length which occur in it in arithmetical progressions. The arithmetical complexity is related to the well-known function of subword complexity and cannot be less than it. However, our main results show that the behaviour of the arithmetical complexity is not determined only by the subword complexity growth: if the latter grows linearly, the arithmetical complexity can increase both linearly and exponentially. To prove it, we consider a family of D0L words with high arithmetical complexity and a family of Toeplitz words with low complexity. In particular, we find the arithmetical complexity of the Thue-Morse word and the paperfolding word.

In his book “The Emperor’s New Mind” Roger Penrose implicitly defines some criteria which should be met by a reasonable notion of recursiveness for subsets of Euclidean space. We discuss two such notions with regard to Penrose’s criteria: one originated from computable analysis, and the one introduced by Blum, Shub and Smale.

An iterative array is a line of interconnected interacting finite automata. One distinguished automaton, the communication cell, is connected to the outside world and fetches the input serially symbol by symbol. Sometimes in the literature this model is referred to as cellular automaton with sequential input mode. We are investigating iterative arrays with a nondeterministic communication cell. All the other cells are deterministic ones. The number of nondeterministic state transitions is regarded as a limited resource which depends on the length of the input.

It is shown that the limit can be reduced by a constant factor without affecting the language accepting capabilities, but for sublogarithmic limits there exists an infinite hierarchy of properly included real-time language families. Finally we prove several closure properties of these families.

Following the recently proved variety theorem for transfinite words we give, in this paper, three instances of correspondence between varieties of finite ω₁-semigroups and varieties of ω₁-languages. We first characterize the class of languages which are recognized by automata in which overlapping limit transitions end in the same state. It turns out that the corresponding variety of ω₁-semigroups is defined by an equation which has a topological interpretation in the case of infinite words. It characterizes languages of infinite words in the class Δ₂ = Π₂ ∩ Σ₂ of the Borel hierarchy. This result is used to prove that an ω₁-language is recognized by an extensive automaton if and only if its syntactic ω₁-semigroup is -trivial and satisfies the Δ₂-equation. This result extends Eilenberg’s result concerning -trivial semigroups and extensive automata. We finally characterize ω₁-languages recognized by extensive automata whose limit transitions are trivial.

No abstract received.

We introduce the notion of a network of Watson-Crick D0L systems, a distributed system of language determining devices motivated by Watson-Crick complementarity. In this paper we compare the behaviour of particular variants of these networks using different protocols for communication, we deal with the growth of the number of strings at the nodes under functioning, and we make observations concerning the decidability of the existence of a so-called black hole in the network.

The differentiation function of a language generating device counts the number of words which can be generated by the device in a given number of steps. In this paper we summarize results on the differentiation function of deterministic tabled Lindenmayer systems, evolutionary grammars and context-free grammars. We present sharp upper bounds for the differentiation function, prove the closure under some algebraic operations, relate this function with other functions studied in formal language theory and consider decision problems for the differentiation function.

Cellular automaton is a special sort of automata and heavily studied in automata theory [2]. Cellular automata consist of automata are put next to each other. They can be in a line, in a grid or even higher dimensional arrangements. These automata differ from the other well-known basic automata, firstly they have not got any tape. Secondly, the transition function is different, the new state of an automaton is determined by its current state and the current states of its direct neighbouring automata. These finite state machines work synchronously.

In this paper we show a visualization of cellular automata in a three dimensional environment. We represent the automata with their properties. We discuss the aspects of designing and developing of an engine which simulates the work of automata. This engine applies the automata’s transition rules in each step. We analyze how the engine works and how the simulation and visualization are accomplished.

The number and form of cellular automata, their initial states and the transition rules are required for this software as input. The output consists of those states of automata which states the automata had during the execution. Every state can be assigned any special coloured and sized shape supported by the three-dimensional environment. For each arbitrary cellular automata the most appropriate assignment can be done for better understanding the result of the run.

In this note we consider a special class of hypercodes whose elements are called supercodes. Characterizations of supercodes, maximal supercodes are established. Embedding a supercode in a maximal supercode is considered.

No abstract received.

An improvement of iteration lemmata is given for context-free languages.

Various quantum versions of the most basic models of the classical finite automata have already been introduced and various modes of their computations have already started to be investigated. In this paper we overview basic models, approaches, techniques and results in this promising area of quantum automata that is expected to play an important role also in theoretical computer science. We also summarize some open problems and research directions to pursue in this area.

The class of the commutative asynchronous automata are investigated here. By characterizing the subdirectly irreducible members of this class, it is proved that every commutative asynchronous automaton can be embedded isomorphically into a quasi-direct power of a suitable two-state automaton. We also prove that the exact bound for the maximal lengths of minimum-length directing words of an n states directable commutative asynchronous automata is equal to n − 1, moreover, it is [log₂(n)] for the subclass containing all directable commutative asynchronous automata generated by one element.

No abstract received.

No abstract received.

In the context of storing/transmitting words of a language L using a noisy medium, the language property of error-detection is fundamental. It ensures that the medium cannot transform a word from L to another word of L. This paper defines some basic error-detecting properties of languages and obtains a few basic results on error-detection. Moreover, some error-detecting capabilities of uniform, solid, and shuffle codes are considered. It is shown that those codes provide certain error-detection either for free or when a simpler condition is satisfied.

We consider the problem of finding one-variable patterns consistent with given positive examples and negative examples. We try to give some evidence that the pattern finding problem is computationally difficult by finding an NP-complete graph problem (called MCP) such that the pattern finding problem is a subproblem of MCP. We also give sufficient conditions such that the pattern finding problem is polynomial-time computable and show that some of the conditions are related with solving word-equations in one variable.

The star height of a rational language, introduced by Eggan in 1963, has proved to be the most puzzling invariant defined for rational languages. Here, we give a new proof of Eggan’s theorem on the relationship between the cycle rank of an automaton and the star height of an expression that describes the language accepted by the automaton. We then present a new method for McNaughton’s result on the star height of pure-group language. It is based on the definition of a (finite) automaton which can be canonically associated to every (rational) language and which we call universal. In contrast with the minimal automaton, the universal automaton of a pure-group language has the property that it contains a subautomaton of minimal cycle rank that recognizes the language.

A hyperoperation on a finite set A is a mapping from Aⁿ (n > 0) into the set of all non-empty subsets of A, and a hyperclone on A is a (hyper-)composition-closed subset of hyperoperations containing all selectors. In this paper we present the following basic properties of hyperoperations and hyperclones: (i) The existence of a normal form for hyperoperations, (ii) the existence of Sheffer hyperoperations and (iii) the fact that the lattice of all hyperclones on {0, 1} has the cardinality of the continuum.

Given a positive integer n and a finite alphabet A, a word w over A is said to guarantee minimal image if, for every homomorphism φ from the free monoid A* over A into the monoid of all transformations of an n-element set, the range of the transformation ωφ has the minimum cardinality among the ranges of all transformations of the form vφ where υ runs over A*. Although the existence of words guaranteeing minimal image is pretty obvious, the problem of their explicit description is very far from being trivial. Sauer and Stone in 1991 gave a recursive construction for such a word w but the length of the word resulting from that construction was doubly exponential (as a function of n). We first show that some known results of automata theory immediately lead to an alternative construction which yields a simpler word that guarantees minimal image: it has exponential length, more precisely, its length is . Then using a different approach, we find a word guaranteeing minimal image similar to that of Sauer and Stone but of the length O( |A|^{½ (n2-n)} ). On the other hand, we observe that the length of any word guaranteeing minimal image cannot be less than |A|ⁿ⁻¹.

We show that the pseudovariety of semigroups which are locally block groups is precisely that generated by power semigroups of semigroups which are locally groups; that is P(LG) = L(PG) (using that PG = BG). We also will show that this pseudovariety corresponds to the Boolean polynomial closure of the LG-languages which is hence polynomial time decidable.

More generally, it is shown that if H is a pseudovariety of groups closed under semidirect product with the pseudovariety of p-groups for some prime p, then the pseudovariety of semigroups associated to the Boolean polynomial closure of the LH-languages is P(LH). The polynomial closure of the LH-languages is similarly characterized.

This paper is an overview of some basic facts about routes and trajectories. We introduce and investigate a new operation of parallel composition of words. This operation can be used both for DNA computation as well as for parallel computation. For instance the recombination of DNA sequences produces a new sequence starting from two parent sequences. The resulting sequence is formed by starting at the left end of one parent sequence, copying a substring, crossing over to some site in the other parent sequence, copying a substring, crossing back to some site in the first parent sequence and so on. The new method that we introduce is based on syntactic constraints on the crossover operation.

No abstract received.

Jančar et al (1995) developed the restarting automaton as a formal model for certain syntactical aspects of natural languages. Here it is shown that with respect to its expressive power the use of nonterminal symbols by restarting automata corresponds to the language theoretical operation of intersection with regular languages. Further, we establish another characterization of the class of Church-Rosser languages by showing that it coincides with the class of languages accepted by the det-RRWW-automata, thus extending an earlier result presented at DLT’99. Finally, we show that the Gladkij language L_Gl is accepted by an RRWW-automaton, which implies that the class GCSL of growing context-sensitive languages is properly contained in the class .

Information transmission in cellular automata(CA) is studied using polynomials over finite fields. The state set is thought to be a finite field and the local function is expressed in terms of a polynomial over it. The information is expressed by an unknown variable X, which takes a value from the state set and information transmission is discussed using polynomials in X. The idea is presented for the basic one dimensional CA with neighborhood index {−1, 0, +1}, although it works for general CAs. We give first the algebraic framework for the extension of CA and then show some fundamental results on extended CAs.

In [16] the last three authors introduced the notion of generalized directable automata as a generalization of many already known types of automata. The algorithms for testing whether a finite automaton belongs to some of important subclasses of the class of generalized directable automata are studied by the authors in [18]. In this paper structural properties of finite and infinite generalized directable automata are considered, tests for membership of a finite automaton in the pseudovarieties of generalized directable and locally directable automata are given, and the least generalized directing and locally directing congruences on a finite automaton are described.

No abstract received.

The free partially commutative monoid M (A, Θ) defined by a set of commutation relations Θ on an alphabet A can be viewed as a model for concurrent computing: indeed, the independence or the simultaneity of two actions can be interpreted by the commutation of two letters that encode them. In this context, the commutation class C_Θ(w) of a word w of the free monoid A* plays a crucial role. In this paper we present:.

- A characterization of the minimal automaton A_Θ(w) for C_Θ(w) with the help of the new notion of Θ-dissection.

- A parallel algorithm which computes the minimal automaton A_Θ(w). This algorithm is optimal if the size of A is constant.

- An optimal parallel algorithm for testing if a word belongs to the commutation class C_Θ(w).

Our approach differs completely from the methods (based on Foata’s normal form) used by C. Cérin and A. Petit [2, 3] for solving similar problems. Under some assumptions the first algorithm achieves an optimal speedup. The second algorithm achieves also an optimal speedup and has a time complexity in O(log n) if the number of processors is in O(n) where n is the length of the word w, the total number of operations is in O(n) and does not depend on the size of the alphabet A as for the classical sequential algorithm.

Okniński and Putcha proved that any finite semigroup S is an amalgamation base for all finite semigroups if the -classes of S are linearly ordered and the semigroup algebra ℝ [S] over ℂ has a zero Jacobson radical. As its consequence they proved that every finite inverse semigroup U whose all of the -classes form a chain is an amalgamation base for finite semigroups. In this paper we give another proof of the result for finite inverse semigroups by making use of semigroup representations only.

In this paper, we study the subdirect product structure of left Clifford semigroups. It is shown that subdirect product of left groups with zero possibly adjoined is related with left Clifford semigroups. Subdirect product of a group and left normal bands is also considered.

In this paper we survey several applications of tree automata and regular tree languages in term rewriting theory. Also some recently introduced types of tree automata by which the range of such applications can be extended beyond the linear cases are considered.

Our goal is to propose a key agreement protocol that is secure even if the discrete logarithm problem can be efficiently solved in the underlying abelian group. The protocol is defined over a non-cyclic finite abelian group whereas the Diffie-Hellman protocol is defined over a cyclic finite abelian group. We analyze the generic reductions of breaking the proposed protocol to the discrete logarithm problem and show that a large number of queries to the discrete logarithm oracle are required to break the proposed protocol in the generic algorithm model.

We will speculate on some computational properties of the system of Rademacher functions {ϕ_n}. The n-th Rademacher function ϕ_n is a step function on the interval [0, 1), jumping at finitely many dyadic rationals of size and assuming values {1, −1} alternatingly.

Author Index.