Developments in Language Theory

New results on the recognizability of sets of finite graphs, hypergraphs and relational structures are presented. The general framework of this research which associates tightly algebraic notions (equational and recognizable sets) and Monadic Second-Order logic (for defining sets and transformations of graphs, hypergraphs and relational structures) is reviewed. The lecture [3] is based on two submitted but nevertheless available articles [1,4] ; the present text is an informal overview. The numerous definitions and results can be found in the two articles.

Recently there have been some new initiatives in the field of parameterized complexity. In this paper, we will report on some of these, concentrating on some open questions, and also looking at some current investigations aimed towards applying ideas of parameterized complexity in the field of online model theory.

Natural Computing is a general term referring to computing taking place in nature and computing inspired by nature. There is a huge surge of research on natural computing, and one of the reasons for it is that two powerful and growing research trends happen at the same time (and actually strengthen and influence each other). These two trends are:

(1) trying to understand the functioning of a living cell from the cell-as-a-whole perspective,

(2) trying to free the theory of computation from classical paradigms (the ongoing transition to the so called “non-classical computation”) in order to explore a much broader notion of computation. This broader notion should take into account not only the original/classical point of view of “computation as calculation” but should also account for (be inspired by) processes, e.g., life processes, taking place in nature.

Existential bounded communication of a communicating finite-state machine means that runs can be scheduled in such a way that message channels are always bounded in size by a value that depends only on the machine. This notion leads to regular sets of representative executions, which allows to get effective algorithms. We show in this paper the equivalence of several formalisms over existentially bounded models: monadic second order logic, communicating automata and globally-cooperative compositional MSC-graphs.

We propose algebraic and topological techniques that could be employed for studying recombinant DNA processes. We show that sequence of splices performed by the operation

hi

-excision/reinsertion on one DNA molecule can be modeled by the elements of a semidirect product of

n

-copies of the cyclic group of order 2 and the symmetric group

S

n

. We associate a surface in space-time (subspace of ℝ

3

×[0,1]) with a sequence of splicings on circular molecules and present examples of applications of this model.

The aim of this paper is to give regular expressions for two-dimensional picture languages. The paper focuses on a one-letter alphabet case, that corresponds to the study of “shapes” of families of pictures. A new diagonal concatenation operation is defined. Languages denoted by regular expressions with union, diagonal concatenation and its closure are characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. The class of languages denoted by regular expressions with union, column, row and diagonal concatenation, and their closures are included in REC and strictly contains languages defined by three-way automata, but they are not comparable with ones defined by four-way automata. In order to encompass a wider class of languages, we propose some new operations that define languages that still lie in REC.

We investigate the generative power of cooperating distributed grammar systems (CDGSs), if the cooperation protocol is based on the level of competence on the underlying sentential form. A component is said to be =

k

-competent (≤

k

-, ≥

k

-competent, resp.) on a sentential form if it is able to rewrite exactly

k

(at most

k

, at least

k

, resp.) different nonterminals appearing in that string. In most cases CDGSs working according to the above described cooperation strategy turn out to give new characterizations of the language families based on random context conditions, namely random context (context-free) languages and the biologically motivated family of languages generated by ET0L systems with random context. Thus, the results presented in this paper can shed new light on some longstanding open problems in the theory of regulated rewriting.

The leaf-language mechanism associates a complexity class to a class of regular languages. It is well-known that the Σ

k

- and Π

k

-levels of the dot-depth hierarchy and the polynomial hierarchy correspond in this formalism. We extend this correspondence to the Δ

k

-levels of these hierarchies: Leaf

P

(Δ

$_{k}^{L}$

) = Δ

$_{k}^{p}$

. These results are obtained in part by relating operators on varieties of languages to operators on the corresponding complexity classes.

Input-reversal pushdown automata are pushdown automata with the additional power to reverse the unread part of the input. We show that these machines characterize the family of linear context-free indexed languages, and that

k

+ 1 input reversals are better than

k

for both deterministic and nondeterministic input-reversal pushdown automata, i.e., there are languages which can be recognized by a deterministic input-reversal pushdown automaton with

k

+ 1 input reversals but which cannot be recognized with

k

input reversals (deterministic or nondeterministic). In passing, input-reversal finite automata are investigated. Moreover, an inherent relation between input-reversal pushdown automata and controlled linear context-free languages are shown, leading to an alternative description of Khabbaz geometric hierarchy of languages by input-reversal iterated pushdown automata. Finally, some computational complexity problems for the investigated language families are considered.

We study the

maximum function

of any ℝ

 + 

-rational formal series

S

in two commuting variables, which assigns to every integer

n

 ∈ ℕ, the maximum coefficient of the monomials of degree

n

. We show that if

S

is a power of any primitive rational formal series, then its maximum function is of the order Θ(

n

k

/ 2

λ

n

) for some integer

k

≥ –1 and some positive real

λ

. Our analysis is related to the study of limit distributions in pattern statistics. In particular, we prove a general criterion for establishing Gaussian local limit laws for sequences of discrete positive random variables.

We consider the classes of ⊕-codes and⊗-codes, which are superclasses of outfix and hypercodes, respectively. These restrictions are based on the synchronized insertion operation, which serves as a model for the gene rearrangement function in certain unicellular organisms. We investigate the classes of ⊕-codes and⊗-codes from a theoretical perspective, examine their relationships with traditional code classes and consider related decidability problems.

Let

I

be a finite set of words and

$\Rightarrow_{I}^{*}$

be the derivation relation generated by the set of productions {

ε

→

u

|

u

∈

I

}. Let

L

I

ε

be the set of words

u

such that

$\epsilon {\Rightarrow_{I}^{*}}$

. We prove that the set

I

is unavoidable if and only if the relation

$\Rightarrow_{I}^{*}$

is a well quasi-order on the set

L

I

ε

. This result generalizes a theorem of [7]. Further generalizations are investigated.

We formalize the hairpin inverted repeat operation, which is known in ciliate genetics as an operation on words and languages by defining

$\mathcal{HI}(w, P)$

as the set of all words

xα

y

R

α

R

z

where

w

=

xα

yα

R

z

and the pointer

α

is in

P

. We extend this concept to language families which results in families

$\mathcal{HI}(L_{1},L_{2})$

. For

L

1

and

L

2

being the families of finite, regular, context-free, context-sensitive or recursively enumerable language, respectively, we determine the hierarchy of the families

$\mathcal{HI}(L_{1},L_{2})$

and compare these families with those of the Chomsky hierarchy. Furthermore, we give some results on the decidability of the membership problem, emptiness problem and finiteness problem for the families

$\mathcal{HI}(L_{1},L_{2})$

.

We introduce semantic shuffle on trajectories (SST) and semantic deletion along trajectories (SDT). These operations generalize the notion of shuffle on trajectories, but add sufficient power to encompass various formal language operations used in applied areas. However, the added power given to SST and SDT does not destroy many desirable properties of shuffle on trajectories, especially with respect to solving language equations involving SST. We also investigate closure properties and decidability questions related to SST and SDT.

In this paper we define Sturmian graphs and we prove that all of them have a “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of CDAWGs of central Sturmian words. We show also that, analogously to the case of Sturmian words, these graphs converge to infinite ones.

Based on a quite general definition of P systems where the rules are applied in a sequential way (and not in the maximally parallel way as it usually happens in most models of P systems considered so far in the literature), we investigate the generative power of various models of such P systems working in the sequential mode on arrays and strings, respectively. P systems working in the sequential mode on arrays/strings without priority relations for the rules reveal the same computational power as the corresponding matrix grammars without appearance checking working on arrays/strings. For obtaining the computational power of matrix grammars with appearance checking, priority relations for the rules (as one of many other possible additional features) are needed.

A new solution for the Firing Squad Synchronization Problem (FSSP) on two-dimensional square arrays is presented and its correctness is demonstrated in detail. Our new solution is time as well as communication optimal (the so-called minimal time 1-bit solution). In addition, it is shown that the technique developed and the results obtained allow also to solve in optimal time & communication FSSP for several other variants of this problem on networks shaped as square grids (with four Generals), square toruses and rings.

We consider the following definition (different from the standard definition in the literature) of “maximal parallelism” in the application of evolution rules in a P system

G

: Let

R

={

r

1

, ...

r

k

} be the set of (distinct) rules in the system.

G

operates in maximal parallel mode if at each step of the computation, a maximal subset of

R

is applied, and at most one instance of any rule is used at every step (thus at most

k

rules are applicable at any step). We refer to this system as a maximally parallel system. We look at the computing power of P systems under three semantics of parallelism.

There is a close relationship between formal language theory and data compression. Since 1990’s various types of

grammar-based text compression

algorithms have been introduced. Given an input string, a grammar-based text compression algorithm constructs a context-free grammar that only generates the string. An interesting and challenging problem is pattern matching on context-free grammars

$\mathcal{P}$

of size

m

and

$\mathcal{T}$

of size

n

, which are the descriptions of pattern string

P

of length

M

and text string

T

of length

N

, respectively. The goal is to solve the problem in time proportional

only

to

m

and

n

,

not

to

M

nor

N

. Kieffer et al. introduced a very practical grammar-based compression method called

multilevel pattern matching code

(

MPM code

). In this paper, we propose an efficient pattern matching algorithm which, given two MPM grammars

$\mathcal{P}$

and

$\mathcal{T}$

, performs in

O

(

mn

2

) time with

O

(

mn

) space. Our algorithm outperforms the previous best one by Miyazaki et al. which requires

O

(

m

2

n

2

) time and

O

(

mn

) space.

The

R

-automaton is the weakest form of the

restarting automaton

. It is shown that the class of languages accepted by these automata is incomparable under set inclusion to the class of

growing context-sensitive languages

. In fact, this already holds for the class of languages that are accepted by

2-monotone

R

-automata. Further it is shown that already this class contains

NP

-complete languages

. Thus, already the 2-monotone

R

-automaton has a surprisingly large expressive power.

The notion of

left-monotonicity

is introduced for the restarting automaton, and the expressive power of the various types of left-monotone restarting automata is studied. We concentrate on the deterministic classes, as here the results differ greatly from those for the corresponding classes of (right-) monotone restarting automata.

In this paper we study the model of a finite state automaton interacting with infinite two-dimensional geometric environments. We show that the reachability problem for a finite state automaton interacting with a quadrant of the plane extended by a power function, a polynomial function or a linear function is algorithmically undecidable, by simulating a Minsky machine. We also consider the environment defined by a parabola which impedes the direct simulation of multiplication. However we show that the model of a finite automaton interacting inside a parabola is also universal.

In [4, page166], it is asked what influence the complementarity relation plays as far as the expressiveness of sticker systems and Watson-Crick automata are concerned. Here, we give the answer: (almost) none! More precisely, we show that every language

L

of a sticker system or a Watson-Crick automaton is the language of such a system with a one-to-one complementarity relation. Our second group of results shows that

L

is the inverse block coding of a language from the same family over any nontrivial fixed complementarity relation. Finally, we prove that any Watson-Crick automaton can be transformed into an equivalent simple and all-final one. This implies the collapse of parts of the hierarchy introduced in [4].

Closures of linear context-free languages under Boolean operations are investigated. The intersection closure and the complementation closure are incomparable. By closing these closures under further Boolean operations we obtain several new language families. The hierarchy obtained by such closures of closures is proper up to level four, where it collapses to the Boolean closure which, in turn, is incomparable with several closures of the family of context-free languages. The Boolean closure of the linear context-free languages is properly contained in the Boolean closure of the context-free languages. A characterization of a class of non-unary languages that cannot be expressed as a Boolean formula over the linear context-free languages is presented.

There already exist classifications of those groups which have regular, context-free or recursively enumerable word problem. The only remaining step in the Chomsky hierarchy is to consider those groups with a context-sensitive word problem. In this paper we consider this problem and prove some results about these groups. We also establish some results about other context-sensitive decision problems in groups.

We prove several complexity and decidability results for automatic monoids: (i) there exists an automatic monoid with a P-complete word problem, (ii) there exists an automatic monoid such that the first-order theory of the corresponding Cayley-graph is not elementary decidable, and (iii) there exists an automatic monoid such that reachability in the corresponding Cayley-graph is undecidable. Moreover, we show that for every hyperbolic group the word problem belongs to LOGCFL, which improves a result of Cai [4].

In this paper we implement bottom-up tree series transducers (tst) over the semiring

$\mathcal{A}$

with the help of bottom-up weighted tree automata (wta) over an extension of

$\mathcal{A}$

. Therefore we firstly introduce bottom-up DM-monoid weighted tree automata (DM-wta), which essentially are wta using an operation symbol of a DM-monoid instead of a semiring element as transition weight. Secondly, we show that DM-wta are indeed a generalization of tst (using pure substitution). Thirdly, given a DM-wta we construct a semiring

$\mathcal{A}$

along with a wta such that the wta computes a formal representation of the semantics of the DM-wta.

Finally, we demonstrate the applicability of our presentation result by deriving a pumping lemma for deterministic tst as well as deterministic DM-wta from a pumping lemma for deterministic wta.

A fragment of linear time temporal logic (LTL) is presented. It is proved that the satisfiability problem for this fragment is NP-complete. The fragment is larger than previously known NP-complete fragments. It is obtained by prohibiting the use of until operator and requiring to use only next operators indexed by a letter.

The main result of this paper is the reduction of PCP(n) to the vector reachability problem for a matrix semigroup generated by

n

4 × 4 integral matrices. It follows that the vector reachability problem is undecidable for a semigroup generated by 7 integral matrices of dimension 4. The question whether the vector reachability problem is decidable for

n

= 2 and

n

= 3 remains open. Also we show that proposed technique can be applied to Post’s tag-systems. As a result we define new classes of counter automata that lie on the border between decidability and undecidability.

In 1982, Séébold showed that the only overlap-free binary words that are the fixed points of non-identity morphisms are the Thue–Morse word and its complement. We strengthen Séébold’s result by showing that the same result holds if the term ‘overlap-free’ is replaced with ‘

$\frac{7}{3}$

-power-free’. Furthermore, the number

$\frac{7}{3}$

is best possible.

We contribute new facets to the discussion on the equivalence problem for E-pattern languages (also referred to as extended or erasing pattern languages). This fundamental open question asks for the existence of a computable function that, given any pair of patterns, decides whether or not they generate the same language. Our main result disproves Ohlebusch and Ukkonen’s conjecture (

Theoretical Computer Science

186, 1997) on the equivalence problem; the respective argumentation, that largely deals with the nondeterminism of pattern languages, is restricted to terminal alphabets with at most four distinct letters.

In a preceding paper (Bruyère and Carton, automata on linear orderings, MFCS’01), automata have been introduced for words indexed by linear orderings. These automata are a generalization of automata for finite, infinite, bi-infinite and even transfinite words studied by Büchi. Kleene’s theorem has been generalized to these words. We prove that rational sets of words on countable scattered linear ordering are closed under complementation using an algebraic approach.

We use formal language theory to estimate the Hausdorff measure of sets of a certain shape in Cantor space. These sets are closely related to infinite iterated function systems in fractal geometry.

Our results are used to provide a series of simple examples for the non-coincidence of limit sets and attractors for infinite iterated function systems.

Chain code picture systems based on

Lindenmayer

systems can be used to generate pictures. In this paper, synchronous, deterministic tabled chain code picture systems (

sDT0L

) and their picture languages are considered. A method is given for deciding whether an

sDT0L

generates a finite picture language or not. This proves that the finiteness of picture languages of

sDT0L

system is decidable.

We show that tissue P systems with symport/antiport having 3 cells and symport/antiport rules of minimal weight generate all recursively enumerable sets of numbers. Constructed systems simulate register machines and have purely deterministic behaviour. Moreover, only 2 symport rules are used and all symbols of any system are present in finite number of copies (except for symbols corresponding to registers of the machine). At the end of the article some open problems are formulated.