Developments in Language Theory

A Conway semiring is a semiring

S

equipped with a unary operation

*

:

S

→

S

, called star, satisfying the sum star and product star equations. An iteration semiring is a Conway semiring satisfying Conway’s group equations. In this extended abstract, we review the role of iteration semirings in the axiomatization of regular languages and rational power series, and in the axiomatization of the equational theory of continuous and complete semirings.

Determining the birth date of computer science is a very complicated task and certainly reliant to the standpoint chosen. Some may point out the work of Kurt Gödel [18], Alan Turing [31], and Alonso Church [11], thus locating the appearance of computer science to 1930’s. Some want to mention Charles Babbage’s engines, some Gottfried Leibniz’ Calculus Ratiocinator, and some refer back to the Euclidean algorithm.

In contrast to the minimization of deterministic finite automata (DFA’s), the task of constructing a minimal nondeterministic finite automaton (NFA) for a given NFA is PSPACE-complete. This fact motivates the following computational problems:

(i) Find a minimal NFA for a regular language

L

, if

L

is given by another suitable formal description, resp. come up with a small NFA.

(ii) Estimate the size of minimal NFA’s or find at least a good approximation of their sizes.

Here, we survey the known results striving to solve the problems formulated above and show that also for restricted versions of minimization of NFA’s there are no efficient algorithms.

Since one is unable to efficiently estimate the size of a minimal NFA in an algorithmic way, one can ask at least for developing mathematical proof methods that help in proving good lower bounds on the size of a minimal NFA for a given regular language. We show here that even the best known methods for this purpose fail for some concrete regular languages.

Finally, we give an overview of the results about the influence of the degree of ambiguity on the size of NFA’s and discuss the relation between the descriptional complexity of NFA’s and NFA’s with

ε

-transitions.

The paper tries to highlight some crucial ideas appearing in the decidability and undecidability proofs for the bisimilarity problem on models originating in language theory, like context-free grammars and pushdown automata. In particular, it focuses on the method of finite bases of bisimulations in the case of decidability and the method of “Defender’s forcing” in the case of undecidability. An intent was to write an easy-to-read article in a slightly informal way, which should nevertheless convey the basic ideas with sufficient precision.

Let

x

1

,

x

2

, ...,

x

n

be positive integers. It is well-known that every sufficiently large integer can be represented as a non-negative integer linear combination of the

x

i

if and only if

$\gcd(x_1, x_2, \ldots, x_n) = 1$

. The

Frobenius problem

is the following: given positive integers

x

1

,

x

2

, ...,

x

n

with

$\gcd(x_1, x_2, \ldots, x_n) = 1 $

, compute the largest integer

not

representable as a non-negative integer linear combination of the

x

i

. This largest integer is sometimes denoted

g

(

x

1

,...,

x

n

).

The concept of well quasi-order is a generalization of the classical notion of well order and plays a role in the studying of several problems of Mathematics and Theoretical Computer Science. This paper concerns some applications of well quasi-orders to Formal Language Theory. In particular, we present a survey of classical and recent results, based upon such structures, concerning context-free and regular languages. We also focus our attention to some application of well quasi-orders in the studying of languages obtained by using the operators of shuffle and iterated shuffle of finite languages.

In this paper we study the non-deterministic communication complexity of regular languages. We show that a regular language has either constant or at least logarithmic non-deterministic communication complexity. We prove several linear lower bounds which we know cover a wide range of regular languages with linear complexity. Furthermore we find evidence that previous techniques (Tesson and Thérien 2005) for proving linear lower bounds, for instance in deterministic and probabilistic models, do not work in the non-deterministic setting.

This paper presents efficient algorithms for testing the finite, polynomial, and exponential ambiguity of finite automata with

ε

-transitions. It gives an algorithm for testing the exponential ambiguity of an automaton

A

in time

$O(|A|_E^2)$

, and finite or polynomial ambiguity in time

$O(|A|_E^3)$

, where |

A

|

E

denotes the number of transitions of

A

. These complexities significantly improve over the previous best complexities given for the same problem. Furthermore, the algorithms presented are simple and based on a general algorithm for the composition or intersection of automata. We also give an algorithm to determine in time

$O(|A|_E^3)$

the degree of polynomial ambiguity of a polynomially ambiguous automaton

A

. Finally, we present an application of our algorithms to an approximate computation of the entropy of a probabilistic automaton.

We consider

multi-pushdown automata

, a multi-stack extension of pushdown automata that comes with a constraint on stack operations: a pop can only be performed on the first non-empty stack (which implies that we assume a linear ordering on the collection of stacks). We show that the emptiness problem for multi-pushdown automata is 2ETIME-complete wrt. the number of stacks. Containment in 2ETIME is shown by translating an automaton into a grammar for which we can check if the generated language is empty. The lower bound is established by simulating the behavior of an alternating Turing machine working in exponential space. We also compare multi-pushdown automata with the model of bounded-phase multi-stack (visibly) pushdown automata.

We prove that, for the uniform distribution over all sets

X

of

m

(that is a fixed integer) non-empty words whose sum of lengths is

n

,

$\mathcal{D}_X$

, one of the usual deterministic automata recognizing

X

*

, has on average

$\mathcal{O}(n)$

states and that the average state complexity of

X

*

is

Θ

(

n

). We also show that the average time complexity of the computation of the automaton

$\mathcal{D}_X$

is

$\mathcal{O}(n\log n)$

, when the alphabet is of size at least three.

Systems of parallel finite automata communicating by states are investigated. We consider deterministic and nondeterministic devices and distinguish four working modes. It is known that systems in the most general mode are as powerful as one-way multihead finite automata. Here we solve some open problems on the computational capacity of systems working in the remaining modes. In particular, it is shown that deterministic returning and non-returning devices are equivalent, and that there are languages which are accepted by deterministic returning and centralized systems but cannot be accepted by deterministic non-returning centralized systems. Furthermore, we show that nondeterministic centralized systems are strictly more powerful than their deterministic variants. Finally, incomparability with the class of (deterministic) (linear) context-free languages as well as the Church-Rosser languages is derived.

In a recent paper with L. Q. Zamboni the authors introduced the class of

ϑ-episturmian

words, where

ϑ

is an involutory antimorphism of the free monoid

A

*

. In this paper, we introduce and study

ϑ-characteristic morphisms

, that is, morphisms which map standard episturmian words into standard

ϑ

-episturmian words. They are a natural extension of standard episturmian morphisms. The main result of the paper is a characterization of these morphisms when they are injective.

The present work clarifies the relation between domains of universal machines and r.e. prefix-free supersets of such sets. One such characterisation can be obtained in terms of the spectrum function

s

W

(

n

) mapping

n

to the number of all strings of length

n

in the set

W

. An r.e. prefix-free set

W

is the superset of the domain of a universal machine iff there are two constants

c

,

d

such that

s

W

(

n

) + 

s

W

(

n

 + 1) + ... + 

s

W

(

n

 + 

c

) is between 2

n

 − 

H

(

n

) − 

d

and 2

n

 − 

H

(

n

) + 

d

for all

n

;

W

is the domain of a universal machine iff there is a constant

c

such that for each

n

the pair of

n

and

s

W

(

n

) + 

s

W

(

n

 + 1) + ... + 

s

W

(

n

 + 

c

) has at least the prefix-free Description complexity

n

. There exists a prefix-free r.e. superset

W

of a domain of a universal machine which is the not a domain of a universal machine; still, the halting probability

Ω

W

of such a set

W

is Martin-Löf random. Furthermore, it is investigated to which extend this results can be transferred to plain universal machines.

Two objects are independent if they do not affect each other. Independence is well-understood in classical information theory, but less in algorithmic information theory. Working in the framework of algorithmic information theory, the paper proposes two types of independence for arbitrary infinite binary sequences and studies their properties. Our two proposed notions of independence have some of the intuitive properties that one naturally expects. For example, for every sequence

x

, the set of sequences that are independent with

x

has measure one. For both notions of independence we investigate to what extent pairs of independent sequences, can be effectively constructed via Turing reductions (from one or more input sequences). In this respect, we prove several impossibility results. For example, it is shown that there is no effective way of producing from an arbitrary sequence with positive constructive Hausdorff dimension two sequences that are independent (even in the weaker type of independence) and have super-logarithmic complexity. Finally, a few conjectures and open questions are discussed.

By the famous theorem of Morse and Hedlund, a word is ultimately periodic if and only if it has bounded subword complexity,

i.e.

, for sufficiently large

n

, the number of factors of length

n

is constant. In this paper we consider relational periods and relationally periodic sequences, where the relation is a similarity relation on words induced by a compatibility relation on letters. We investigate what would be a suitable definition for a relational subword complexity function such that it would imply a Morse and Hedlund-like theorem for relationally periodic words. We consider strong and weak relational periods and two candidates for subword complexity functions.

We show a

Θ

(

n

log

n

) bound on the maximal number of occurrences of primitively-rooted

k

-th powers occurring in a string of length

n

for any integer

k

,

k

 ≥ 2. We also show a

Θ

(

n

2

) bound on the maximal number of primitively-rooted powers with fractional exponent

e

, 1 < 

e

 < 2, occurring in a string of length

n

. This result holds obviously for their maximal number of occurrences. The first result contrasts with the linear number of occurrences of maximal repetitions of exponent at least 2.

A graph

$\mathcal{H}$

is

computable

if there is a graph

$\mathcal{G}=(V,E)$

isomorphic to

$\mathcal{H}$

where the set

V

of vertices and the edge relation

E

are both computable. In this case

$\mathcal{G}$

is called a

computable copy

of

$\mathcal{H}$

. The

reachability problem

for

$\mathcal{H}$

in

$\mathcal{G}$

is, given

u

,

w

 ∈ 

V

, to decide whether there is a path from

u

to

w

. If the reachability problem for

$\mathcal{H}$

is decidable in

all

computable copies of

$\mathcal{H}$

then the problem is

intrinsically decidable

. This paper provides syntactic-logical characterizations of certain classes of graphs with intrinsically decidable reachability relations.

We introduce some new cooperation protocols for cooperating distributed (CD) grammar systems. They depend on the number of different nonterminals present in the sentential form if a component has finished its work, i.e. on the final competence or efficiency of the grammar on the string (the competence is large if the number of the different nonterminals is small). We prove that if the underlying derivation mode is the

t

-mode derivation, then some variants of these systems determine the class of random context ET0L languages. If these CD grammar systems use the

k

step limited derivations (for

k

 ≥ 3) as underlying derivations, they are able to generate any recursively enumerable language.

The synchronization problem is investigated for a new class of deterministic automata called strongly transitive. An extension to unambiguous automata is also considered.

We give a new proof for the decidability of the equivalence of two

k

-valued transducers, a result originally established by Culik and Karhümaki and independently by Weber. Our proof relies on two constructions we have recently introduced to decompose a

k

-valued transducer and to decide whether a transducer is

k

-valued. As a result, our proof is entirely based on the structure of the transducers under inspection, and the complexity it yields is of single exponential order on the number of states. This improves Weber’s result by one exponential.

In this paper we study some decidable properties of two-dimensional cellular automata (2D CA). The notion of closingness is generalized to the 2D case and it is linked to permutivity and openness. The major contributions of this work are two deep constructions which have been fundamental in order to prove our new results and we strongly believe it will be a valuable tool for proving other new ones in the near future.

An aperiodic tile set was first constructed by R. Berger while proving the undecidability of the domino problem. It turned out that aperiodic tile sets appear in many topics ranging from logic (the Entscheidungsproblem) to physics (quasicrystals)

We present a new construction of an aperiodic tile set that is based on Kleene’s fixed-point construction instead of geometric arguments. This construction is similar to J. von Neumann self-reproducing automata; similar ideas were also used by P. Gács in the context of error-correcting computations.

The flexibility of this construction allows us to construct a “robust” aperiodic tile set that does not have periodic (or close to periodic) tilings even if we allow some (sparse enough) tiling errors. This property was not known for any of the existing aperiodic tile sets.

Extended multi bottom-up tree transducers are defined and investigated. They are an extension of multi bottom-up tree transducers by arbitrary, not just shallow, left-hand sides of rules; this includes rules that do not consume input. It is shown that such transducers can compute any transformation that is computed by a linear extended top-down tree transducer. Moreover, the classical composition results for bottom-up tree transducers are generalized to extended multi bottom-up tree transducers. Finally, a characterization in terms of extended top-down tree transducers is presented.

We show that for several classes of idempotent semirings the least fixed-point of a polynomial system of equations

is equal to the least fixed-point of a

linear

system obtained by “linearizing” the polynomials of

in a certain way. Our proofs rely on derivation tree analysis, a proof principle that combines methods from algebra, calculus, and formal language theory, and was first used in [5] to show that Newton’s method over commutative and idempotent semirings converges in a linear number of steps. Our results lead to efficient generic algorithms for computing the least fixed-point. We use these algorithms to derive several consequences, including an

O

(

N

3

) algorithm for computing the throughput of a context-free grammar (obtained by speeding up the

O

(

N

4

) algorithm of [2]), and a generalization of Courcelle’s result stating that the downward-closed image of a context-free language is regular [3].

A tree automaton with global tree equality and disequality constraints, TAGED for short, is an automaton on trees which allows to test (dis)equalities between subtrees which may be arbitrarily faraway. In particular, it is equipped with an (dis)equality relation on states, so that whenever two subtrees

t

and

t

′ evaluate (in an accepting run) to two states which are in the (dis)equality relation, they must be (dis)equal. We study several properties of TAGEDs, and prove decidability of emptiness of several classes. We give two applications of TAGEDs: decidability of an extension of Monadic Second Order Logic with tree isomorphism tests and of unification with membership constraints. These results significantly improve the results of [10].

We study the inclusion problem for pattern languages, which is shown to be undecidable by Jiang et al. (J. Comput. System Sci. 50, 1995). More precisely, Jiang et al. demonstrate that there is no effective procedure deciding the inclusion for the class of

all

pattern languages over

all

alphabets. Most applications of pattern languages, however, consider classes over

fixed

alphabets, and therefore it is practically more relevant to ask for the existence of

alphabet-specific

decision procedures. Our first main result states that, for all but very particular cases, this version of the inclusion problem is also undecidable. The second main part of our paper disproves the prevalent conjecture on the inclusion of so-called similar E-pattern languages, and it explains the devastating consequences of this result for the intensive previous research on the most prominent open decision problem for pattern languages, namely the equivalence problem for general E-pattern languages.

We give an

O

(

n

 + 

t

) time algorithm to determine whether an NFA with

n

states and

t

transitions accepts a language of polynomial or exponential growth. Given a NFA accepting a language of polynomial growth, we can also determine the order of polynomial growth in

O

(

n

 + 

t

) time. We also give polynomial time algorithms to solve these problems for context-free grammars.

We consider two formalisms for representing regular languages: constant height pushdown automata and straight line programs for regular expressions. We constructively prove that their sizes are polynomially related. Comparing them with the sizes of finite state automata and regular expressions, we obtain optimal exponential and double exponential gaps, i.e., a more concise representation of regular languages.

We investigate deterministic forgetting automata, i.e., deterministic linear bounded automata which can only use the operations ‘move’, ‘erase’ (rewrite with a blank symbol) and ‘delete’ (remove completely). We give a taxonomy of deterministic forgetting automata and draw comparisons to other kinds of automata (namely deterministic one-turn pushdown automata and one-way one-counter automata).

We study the problem of finding good elimination orderings for the state elimination algorithm, which is one of the most popular algorithms for the conversion of finite automata into equivalent regular expressions. Based on graph separator techniques we are able to describe elimination strategies that remove states in large induced subgraphs that are “simple” like, e.g., independent sets or subgraphs of bounded treewidth, of the underlying automaton, that lead to regular expressions of moderate size. In particular, we show that there is an elimination ordering such that every language over a binary alphabet accepted by an

n

-state

deterministic

finite automaton has alphabetic width at most

O

(1.742

n

), which is, to our knowledge, the algorithm with currently the best known performance guarantee. Finally, we apply our technique to the question on the effect of language operations on regular expression size. In case of the intersection operation we prove an upper bound which matches, up to a small factor, a lower bound recently obtained in [9,10], and thus settles an open problem stated in [7].

Let

w

be an equality word of two nonperiodic binary morphisms

g

,

h

:{

a

,

b

}

*

→

Δ

*

. Suppose that no overflow occurs twice in

w

and that

w

contains at least 9 occurrences of

a

and at least 9 occurrences of

b

.

Then either

w

 = (

ab

)

i

a

, or

w

 = 

a

i

b

j

with

$\gcd(i,j)=1$

, up to the exchange of letters

a

and

b

.

Finite words and their overlap properties are considered in this paper. Let

w

be a finite word of length

n

with period

p

and where the maximum length of its unbordered factors equals

k

. A word is called unbordered if it possesses no proper prefix that is also a suffix of that word. Suppose

k

 < 

p

in

w

. It is known that

n

 ≤ 2

k

 − 2, if

w

has an unbordered prefix

u

of length

k

. We show that, if

n

 = 2

k

 − 2 then

u

ends in

ab

i

, with two different letters

a

and

b

and

i

 ≥ 1, and

b

i

occurs exactly once in

w

. This answers a conjecture by Harju and the second author of this paper about a structural property of maximum Duval extensions. Moreover, we show here that

i

 < 

k

/3, which in turn leads us to the solution of a special case of a problem raised by Ehrenfeucht and Silberger in 1979.

Duplication and repeat-deletion are the basic models of errors occurring during DNA replication from the viewpoint of formal languages. During DNA replication, subsequences of a strand of DNA may be copied several times (duplication) or skipped (repeat-deletion). Iterated duplication and repeat-deletion have been well-studied, but little is known about single-step duplication and repeat-deletion. In this paper, we investigate properties of these operations, such as closure properties of language families in the Chomsky hierarchy, language equations involving these operations. We also make progress towards a characterization of regular languages that are generated by duplicating a regular language.

We examine the deterministic and nondeterministic state complexity of complements, stars, and reversals of regular languages. Our results are as follows:

1

The nondeterministic state complexity of the complement of an

n

-state NFA language over a five-letter alphabet may reach each value in the range from log

n

to 2

n

.

1

The state complexity of the star (reversal) of an

n

-state DFA language over a growing alphabet may reach each value in the range from 1 to

$\frac{3}{4}2^n$

(from log

n

to 2

n

, respectively).

1

The nondeterministic state complexity of the star (reversal) of an

n

-state NFA binary language may reach each value in the range from 1 to

n

 + 1 (from

n

 − 1 to

n

 + 1, respectively).

We also obtain some partial results on the nondeterministic state complexity of the complements of binary regular languages. As a bonus, we get an exponential number of values that are non-magic, which improves a similar result of Geffert (

Proc. 7th DCFS

, Como, Italy, 23–37).

The number of states in two-way deterministic finite automata (2DFAs) is considered. It is shown that the state complexity of basic operations is: at least

m

 + 

n

 − 

o

(

m

 + 

n

) and at most 4

m

 + 

n

 + 1 for union; at least

m

 + 

n

 − 

o

(

m

 + 

n

) and at most

m

 + 

n

 + 1 for intersection; at least

n

and at most 4

n

for complementation; at least

$\Omega(\frac{m}{n}) + \frac{2^{\Omega(n)}}{\log m}$

and at most

$2m^{m+1}\cdot 2^{n^{n+1}}$

for concatenation; at least

$\frac{1}{n} 2^{\frac{n}{2}-1}$

and at most

$2^{O(n^{n+1})}$

for both star and square; between

n

and

n

 + 2 for reversal; exactly 2

n

for inverse homomorphism. In each case

m

and

n

denote the number of states in 2DFAs for the arguments.

We examine the succinctness of

one-way

,

rotating

,

sweeping

, and

two-way

deterministic finite automata (1

dfas

,

rdfas

,

sdfas

, 2

dfas

). Here, a

sdfa

is a

2dfa

whose head can change direction only on the endmarkers and a

rdfa

is a

sdfa

whose head is reset on the left end of the input every time the right endmarker is read. We introduce a list of language operators and study the corresponding closure properties of the size complexity classes defined by these automata. Our conclusions reveal the logical structure of certain proofs of known separations in the hierarchy of these classes and allow us to systematically construct alternative problems to witness these separations.

We analyze and reprove the famous theorem of Hmelevskii, which states that the general solutions of constant-free equations on three unknowns are finitely parameterizable, that is expressible by a finite collection of formulas of word and numerical parameters. The proof is written, and simplified, by using modern tools of combinatorics on words. As a new aspect the size of the finite representation is estimated; it is bounded by a double exponential function on the size of the equation.

The classes of languages which are boolean combinations of languages of the form

$$A^*a_1A^*a_2A^*\dots A^*a_\ell A^*, \text{ where } a_1,\dots ,a_\ell\in A,\ \ell\le k\,,$$

for a fixed

k

 ≥ 0, form a natural hierarchy within piecewise testable languages and have been studied in papers by Simon, Blanchet-Sadri, Volkov and others. The main issues were the existence of finite bases of identities for the corresponding pseudovarieties of monoids and generating monoids for these pseudovarieties.

Here we deal with similar questions concerning the finite unions and positive boolean combinations of the languages of the form above. In the first case the corresponding pseudovarieties are given by a single identity, in the second case there are finite bases for

k

equal to 1 and 2 and there is no finite basis for

k

 ≥ 4 (the case

k

 = 3 remains open). All the pseudovarieties are generated by a single algebraic structure.

Since recognizable tree languages are closed under the rational operations, every regular tree expression denotes a recognizable tree language. We provide an alternative proof to this fact that results in smaller tree automata. To this aim, we transfer Antimirov’s partial derivatives from regular word expressions to regular tree expressions. For an analysis of the size of the resulting automaton as well as for algorithmic improvements, we also transfer the methods of Champarnaud and Ziadi from words to trees.

We study balance properties of circular words over alphabets of size greater than two. We give some new characterizations of balanced words connected to the Kawasaki-Ising model and to the notion of derivative of a word. Moreover we consider two different generalizations of the notion of balance, and we find some relations between them. Some of our results can be generalised to non periodic infinite words as well.

Shared-memory systems appear as a generalization of asynchronous cellular automata. In this paper we relate the partial-order semantics of shared-memory systems to Mazurkiewicz trace languages by means of a new refinement construction. We show that a set of labeled partial orders is recognized by some unambiguous shared-memory system if and only if it is definable in monadic second-order logic and media-bounded.

We determine the complexity of topological properties of regular

ω

-languages (i.e., classes of

ω

-languages closed under inverse continuous functions). We show that they are typically NL-complete (PSPACE-complete) for the deterministic Muller, Mostowski and Büchi automata (respectively, for the nondeterministic Rabin, Muller, Mostowski and Büchi automata). For the deterministic Rabin and Streett automata and for the nondeterministic Streett automata upper and lower complexity bounds for the topological properties are established.