On the state complexity of reversals of regular languages

We compare the number of states between minimal deterministic finite automata accepting a regular language and its reversal (mirror image). In the worst case the state complexity of the reversal is 2ⁿ for an n-state language. We present several classes of languages where this maximal blow-up is actually achieved and study the conditions for it. In the case of finite languages the maximal blow-up is not possible but still a surprising variety of different growth types can be exhibited.     

A characterization of average case communication complexity

It is well known that the average case deterministic communication complexity is bounded below by an entropic quantity, which one would now call deterministic information complexity. In this paper we show a corresponding upper bound. We also improve known lower bounds for the public coin Las Vegas communication complexity by a constant factor.     

On the descriptional complexity of scattered context grammars

This paper proves that every recursively enumerable language is generated by a scattered context grammar with no more than four nonterminals and three non-context-free productions. In its conclusion, it gives an overview of the results and open problems concerning scattered context grammars and languages.     

Operational state complexity of nested word automata

We introduce techniques to prove lower bounds for the number of states needed by finite automata operating on nested words. We study the state complexity of Boolean operations and obtain lower bounds that are tight within an additive constant. The results for union and complementation differ from corresponding bounds for ordinary finite automata. For reversal and concatenation, we establish lower bounds that are of a different order than the worst-case bounds for ordinary finite automata.     

On the complexity of computing the profinite closure of a rational language

Profinite topology is used in the classification of rational languages. In particular, several important decidability problems, related to the Malcev product, reduce to the computation of the closure of a rational language in the profinite topology. It is known that, given a rational language by a deterministic automaton, computing a deterministic automaton accepting its profinite closure can be done with an exponential upper bound. This paper is dedicated the study of a lower bound for this problem: we prove that, in some cases, if the alphabet contains at least three letters, it requires an exponential time.     

An average complexity measure that yields tight hierarchies

A new definition is given for the average growth of a functionf: ^* N with respect to a probability measure on ^* This allows us to define meaningful average distributional complexity classes for arbitrary time bounds (previously, one could not guarantee arbitrary good precision). It is shown that, basically, only the ranking of the inputs by decreasing probabilities is of importance.To compare the average and worst case complexity of problems, we study average complexity classes defined by a time bound and a bound on the complexity of possible distributions. Here, the complexity is measured by the time to compute the rank functions of the distributions. We obtain tight and optimal separation results between these average classes. Also, the worst case classes can be embedded into this hierarchy. They are shown to be identical to average classes with respect to distributions of exponential complexity.     

On the subword complexity of locally catenative dol languages

The subword complexity of language K, denoted Gv;_K, is the function of positive integers such that Gv;_K(n) equals the number of subwords of length n that occur in (words of) K. It is proved that if K is a locally catenative DOL language, then Gv;_K is bounded by a linear function.     

On the degree of scattered context-sensitivity

In this paper, we prove that every recursively enumerable language can be generated by a scattered context grammar with no more than two context-sensitive productions.     

On the subword complexity of m-free D0L languages

A word is called m-free (m ? 2) if it does not contain a subword of the form x^m where x is a nonempty word. A language is called m-free if it consists of m-free words only. The subword complexity of a language K, denoted π_K, is a function of positive integers which to each positive integer n assigns the number of different subwords of length n occuring in words of K. It is known that if a D0L language K is m-free for some m ? 2, then, for all n, π_K(n) ? qn log₂n for some positive integer q. We demonstrate that there exists a 3-free D0L language K on three letters such that, for all n ? n₀, π_K(n) ? rn log₂n for some positive real r and a positive integer n₀. We also demonstrate that if m ? 3 and K is an m-free D0L language on two letters, then, for all n, π_K(n) ? pn for some positive integer p.     

Nonterminal complexity of tree controlled grammars

This paper studies the nonterminal complexity of tree controlled grammars. It is proved that the number of nonterminals in tree controlled grammars without erasing rules leads to an infinite hierarchy of families of tree controlled languages, while every recursively enumerable language can be generated by a tree controlled grammar with erasing rules and at most nine nonterminals.