International Journal of Foundations of Computer Science

Reaction systems are a formal framework for investigating processes carried out by biochemical reactions. This paper is an introduction to reaction systems. It provides basic notions together with the underlying intuition and motivation as well as two examples (a binary counter and transition systems) of "programming" with reaction systems. It also provides a tour of some research themes.

Tiling recognizable two-dimensional languages, also known as REC, generalize recognizable string languages to two dimensions and share with them several theoretical properties. Nevertheless family REC is not closed under complementation and this implies that it is intrinsically non-deterministic. We consider different notions of unambiguity and determinism and the corresponding REC subclasses: they define a hierarchy inside REC. We show that some definitions of unambiguity are equivalent to particular notions of determinism and therefore the corresponding classes have linear parsing algorithms and are closed under complementation.

We summarize results on the complexity of regular(-like) expressions and tour a fragment of the literature. In particular we focus on the descriptional complexity of the conversion of regular expressions to equivalent finite automata and vice versa, to the computational complexity of problems on regular-like expressions such as, e.g., membership, inequivalence, and non-emptiness of complement, and finally on the operation problem measuring the required size for transforming expressions with additional language operations (built-in or not) into equivalent ordinary regular expressions.

The ring of integers and the ring of polynomials over a finite field share a lot of properties. Using a bounded number of polynomial coefficients, any polynomial can be decomposed as a linear combination of powers of a non-constant polynomial P playing the role of the base of the numeration. Having in mind the theorem of Cobham from 1969 about recognizable sets of integers, it is natural to study P-recognizable sets of polynomials. Based on the results obtained in the Ph.D. thesis of the second author, we study the logical characterization of such sets and related properties like decidability of the corresponding first-order theory.

Recently, Carpi and D'Alessandro have formulated a conjecture whose validity would imply an O(n²) upper bound for the minimum length of reset for synchronizing automata with n states. We refute this conjecture as well as a related conjecture by Rystsov and suggest a weaker version that still suffices to achieve a quadratic upper bound.

Parallel communicating finite automata (PCFAs) are systems of several finite state automata which process a common input string in a parallel way and are able to communicate by sending their states upon request. We consider deterministic and nondeterministic variants and distinguish four working modes. It is known that these systems in the most general mode are as powerful as one-way multi-head finite automata. It is additionally known that the number of heads corresponds to the number of automata in PCFAs in a constructive way. Thus, undecidability results as well as results on the hierarchies induced by the number of heads carry over from multi-head finite automata to PCFAs in the most general mode. Here, we complement these undecidability and hierarchy results also for the remaining working modes. In particular, we show that classical decidability questions are not semi-decidable for any type of PCFAs under consideration. Moreover, it is proven that the number of automata in the system induces infinite hierarchies for deterministic and nondeterministic PCFAs in three working modes.

The partial derivative automaton () is usually smaller than other nondeterministic finite automata constructed from a regular expression, and it can be seen as a quotient of the Glushkov automaton (). By estimating the number of regular expressions that have ε as a partial derivative, we compute a lower bound of the average number of mergings of states in and describe its asymptotic behaviour. This depends on the alphabet size, k, and for growing k's its limit approaches half the number of states in . The lower bound corresponds to consider the automaton for the marked version of the regular expression, i.e. where all its letters are made different. Experimental results suggest that the average number of states of this automaton, and of the automaton for the unmarked regular expression, are very close to each other.

We show that for every deterministic bottom-up tree transducer, a unique equivalent transducer can be constructed which is minimal. The construction is based on a sequence of normalizing transformations which, among others, guarantee that non-trivial output is produced as early as possible. For a deterministic bottom-up transducer where every state produces either none or infinitely many outputs, the minimal transducer can be constructed in polynomial time.

We design and implement highly parallel algorithms that use light as the tool of computation. Our computational laboratory consists of an ordinary xerox machine supplied with a box of transparencies. Our most basic operation is the evaluation of a Boolean function at arbitrarily many truth settings simultaneously. We find the maximum in a list of n-bit numbers of arbitrary length using at most n xerox copying steps. We count the number of elements in a list of arbitrary length of subsets of a given n-element set simultaneously in O(n²) copying steps. We decide, for any graph having n vertices and m edges, whether a 3-coloring exists in at most 2n + 4m copying steps. For large instances of problems such as the 3-color problem, this solution method may require the production of transparencies that display challengingly high densities of information. Our ultimate purpose here is to give hand tested 'ultra-parallel' algorithmic procedures that may provide useful suggestions for future technologies using light.

We continue the investigation of union-free regular languages that are described by regular expressions without the union operation. We also define deterministic union-free languages as languages accepted by one-cycle-free-path deterministic finite automata, and show that they are properly included in the class of union-free languages. We prove that (deterministic) union-freeness of languages does not accelerate regular operations, except for the reversal in the nondeterministic case.

A general framework of parallel insertion and deletion based on p-schemata is proposed. A p-schema is a set of tuples of words. When being used for parallel insertion of a language into a word, an element of p-schema specifies how to split the word into factors between which the language to be inserted. As its inverse operation, parallel deletion based on the p-schema is defined. Several algebraic properties of these operations such as closure properties of language classes under them are proved. The main contribution of this paper is to propose algorithms to solve language equations involving p-schema-based insertions or deletions based on syntactic congruence. These algorithms not only decide whether a given equation has a solution but construct the set of all of its maximal or minimal solutions. The algorithms are extensible so as to solve some multiple-variables equations and inequalities. Related undecidability results are also presented.

We consider five operators on a regular language. Each of them is a tool for constructing a code (respectively prefix, suffix, bifix, infix) and a hypercode out of a given regular language. We give the precise values of the (deterministic) state complexity of these operators: over a constant-size alphabet for the first four of them and over a quadratic-size alphabet for the hypercode operator.

If all proper factors of a word u are β-power-free while u itself is not, then u is a minimal β-power. We consider the following general problem: for which numbers k,β, and p there exists a k-ary minimal β-power of period p? For the case β ≥ 2 we completely solve this problem. If the number β < 2 is relatively "big" w.r.t. k, we show that any number p can be the period of a minimal β-power. Finally, for "small" β we describe some sets of forbidden periods and provide a numerical evidence that for k ≥ 9 these sets are almost exhaustive.

The results of several papers concerning the Černý conjecture are deduced as consequences of a simple idea that I call the averaging trick. This idea is implicitly used in the literature, but no attempt was made to formalize the proof scheme axiomatically. Instead, authors axiomatized classes of automata to which it applies.

We solve instances of a general class of problems defined as follows: Preprocess a set S of possibly weighted colored geometric objects (e.g. points/orthogonal segments/rectangles) in IR^d, d ≥ 1 such that given a query orthogonal range q (e.g. hyperbox/point), we can report efficiently for each distinct color c of the points in S ∩ q, the tuple where is a function (e.g. weighted sum, bounding box etc.) of the objects of color c in q.

The star graph proposed by [1] has many advantages over the n-cube. However it suffers from having large gaps in the number of possible vertices. The (n,k)-star graph was proposed in [18] to address this issue. Since it is a generalization of the star graph, it retains many of the nice properties of the star graph. There are many different measures of structural integrity of interconnection networks. In this paper, we prove results of the following type for the (n,k)-star graph. If n + (r - 1)k - g(r) vertices are deleted from an (n,k)-star graph, the resulting graph will either be connected or has a large component and small components having at most r - 1 vertices in total. Additional results on conditional vertex connectivity and cycle connectivity will also be given.

Gene insertion and deletion are the operations that occur commonly in DNA processing and RNA editing. Based on these evolutionary transformations, a computing model has been formulated in formal language theory known as insertion-deletion systems. In this paper, we study about the ambiguity issues of insertion systems. First, we define six levels of ambiguity for insertion systems based on the components used in the derivation such as axiom, contexts and strings. Next, we show that there are inherently i-ambiguous insertion languages which are j-unambiguous for the combinations (i, j) ∈ {(5,0), (5,4), (4,3), (4,2), (3,1),(2,1), (1,0), (0,1)}. Finally, we prove an important result that the ambiguity problem of insertion systems is undecidable.