The state complexity, respectively, nondeterministic state complexity of a regular language L is the number of states of the minimal deterministic, respectively, of a minimal nondeterministic finite automaton for L. Some of the most studied state complexity questions deal with size comparisons of nondeterministic finite automata of differing degree of ambiguity. More generally, if for a regular language we compare the size of description by a finite automaton and by a more powerful language definition mechanism, such as a context-free grammar, we encounter non-recursive trade-offs. Operational state complexity studies the state complexity of the language resulting from a regularity preserving operation as a function of the complexity of the argument languages. Determining the state complexity of combined operations is generally challenging and for general combinations of operations that include intersection and marked concatenation it is uncomputable.

This special issue celebrates the 85th birthday of Andrzej Ehrenfeucht, an iconic scientist. He has contributed many seminal results and opened new research directions in mathematical logic, theoretical computer science, and natural computing. His research is characterized by originality and elegance -he is famous for discovering unique approaches to and elegant structures within problems he works on.

We present schemes of deterministic finite automata such that, for every nontrivial automaton A resulting from the scheme with n states, the state complexity of the mirror image of the language L(A) equals 2n . The construction leads to cases, where

A membrane computing system (also called P system) consists of computing cells which are organized hierarchically by the inclusion relation: cells may include cells, which again may include cells, etc. Each cell is enclosed by its membrane. Each cell is an independent computing agent with its own computing program, which produces objects. The interaction between cells consists of the exchange of objects through membranes. The output of a computation is a partially ordered set of objects which leave the system through its external membrane. The fundamental properties of computations in such P systems with external output are investigated. These include the computing power, normal forms, and basic decision problems.

Continuing the work begun in [14], we consider contextual grammars (as introduced in [6] with linguistic motivation) with parallel derivations, in which the whole current string participates to a derivation step in the sense that it is splitted into substrings to which contexts are adjoined in a parallel manner. The generative power of such grammars is investigated, when the parallelism is total or partial, and when the selection of contexts is limited to strings in sets of a given type (finite, regular etc.) Then we consider the languages consisting of strings which cannot be further derived (we call them blocking languages). Some open problems are also formulated.

We consider grammar systems in which several components are active at the same moment (a team of components is working). The power of such mechanisms is investigated and it is found that in many cases the team feature increases the generative capacity of grammar systems. In the so-called t-mode of derivation (a team works as much as it can) it is found that the team size does not induce an infinite hierarchy of languages. However, the family obtained in this case is a full abstract family of languages properly including ETOL.

For every triple (k, /, m) of nonnegaUve integers, every context-free grammar G can be transformed rote a normal form where (1) each nontermmating production is of the type A ~ wkBwtCw,~ with I wk [ = k, I wll --/, and I w,~ [ = m, and 00 each terminating producUon A ~ w has the property that I wl appears m the length set of L(G).Apphcations and generalizations of this result are discussed.

A technique ts presented for constructing dense hierarchies of grammatical subfamthes of context-free languages The question of "where" such dense hierarchies may lie is also investigated Infinite hierarchies of successors are studied.The major open problems concern questions deahng with fimte grammar forms Categories and SubJect Descriptors.F 4 3 ]

Encouraged by positive experiences with so-called uniform-interpretations of L-forms, we investigate in this paper a suitable analogous definition of uniform interpretations of grammar forms. Concerning CF grammar forms it is shown that a rich variety of language families can be obtained. CF grammar forms with a single variable are extensively examined both with regard to generative capacity (including a characterization of subregular, sublinear and subfinite index families) and with regard to the notion of goodness and badness. Concerning non-CF grammar forms it is shown that each of the families of EOL-, ETOL-, matrix-, scattered context-, context sensitive, type 0-languages (and many others) can be obtained by using interpretations of one form specific to this family.

This paper continues the study of EOL forms. The notion of a good EOL form is introduced as an important generalization of the notion of complete and very complete EOL forms. Transformations preserving the property good are obtained and the existence of a variety of good and bad (i.e. not good) forms is demonstrated. It is further shown that good and complete (i.e. vomplete) EOL forms do exist; that propagating EOL forms are bad except under very special circumstances; and that synchronized EOL forms are always bad.

The theory of finite automata is closely linked with the theory of Kleene's regular expressions. In this paper, two formal systems for the algebraic transformation of regular expressions are developed. Both systems are consistent and complete; i.e., the set of equations derivable within the system equals the set of equations between two regular expressions denoting the same event. One of the systems is based upon the uniqueness of the solution of certain regular expression equations, whereas some facts concerning the representation theory of regular events are used in connection with the other.

Consider functions whose variables, finite in number, range over a fixed finite set N and whose values are elements of N. The elements of N are denoted simply by the natural numbers 1,2, …, n. There are nnm distinct m-place functions. If N is chosen to be the set of n truth-values then the functions considered are obviously truth-functions in n-valued logic.