Descriptional Complexity of Formal Systems

One possible complexity measure for a cellular automaton is the size of its neighborhood. If a cellular automaton is reversible with a small neighborhood, the inverse automaton may need a much larger neighborhood. Our interest is to find good upper bounds for the size of this inverse neighborhood. It turns out that a linear algebra approach provides better bounds than any known combinatorial methods. We also consider cellular automata that are not surjective. In this case there must exist so-called orphans, finite patterns without a pre-image. The length of the shortest orphan measures the degree of non-surjectiveness of the map. Again, a linear algebra approach provides better bounds on this length than known combinatorial methods. We also use linear algebra to bound the minimum lengths of any diamond and any word with a non-balanced number of pre-images. These both exist when the cellular automaton in question is not surjective. All our results deal with one-dimensional cellular automata. Undecidability results imply that in higher dimensional cases no computable upper bound exists for any of the considered quantities.

The restarting automaton is a machine model that is motivated by the technique of analysis by reduction from linguistics. It consists of a finite-state control, a flexible tape with end markers and a read/write window of fixed size. This paper begins with a short description of the general model of the restarting automaton and its major variants. In particular, the question for the influence of the size of the read/write window on the expressive power of the various types of restarting automata is addressed. The main part then focuses on the weakest model of the restarting automaton and its variants: the so-called R -automaton with a read/write window of size one (R(1)-automaton for short). It is well-known that R(1)-automata only accept regular languages, but it will be shown that several seemingly rather powerful extensions have just the same expressive power. Accordingly it is of interest to study the descriptional complexity of these types of restarting automata in relation to the R(1)-automata on the one hand and the (deterministic and nondeterministic) finite-state acceptors on the other hand. Then various types of cooperating distributed systems (CD-systems) of deterministic R(1)-automata are presented. If all components of such a system are stateless, then the language accepted by the system has a semi-linear Parikh image, and actually the rational trace languages and the context-free trace languages have been characterized in terms of certain CD-systems of stateless deterministic R(1)-automata. Also for these devices the question for their descriptional complexity will be addressed in short.

Unfoldings succinctly represent the set of reachable markings of a Petri net. Here, we shall consider the case of contextual nets, which extend Petri nets with read arcs, and which are more suitable to represent the case of concurrent read access. We discuss the problem of (efficiently) constructing unfoldings of such nets. On the basis of these unfoldings, various verification problems can be encoded as satisfiability problems in propositional logic.

In computations realized by finite automata, a rich understanding has come from comparing the algebraic structure of the machines to the combinatorics of the languages being recognized. In this expository paper, we will first survey some basic ideas that have been useful in this model. In the second part, we sketch how this dual approach can be generalized to study some important class of boolean circuits, what results have been obtained, what questions are still open. The intuition gained in the simple model sometimes carry through, sometimes not, so that one has to be careful on what conjectures to make.

Given a formal language L specified in various ways, we consider the problem of determining if L is nonempty. If L is indeed nonempty, we find upper and lower bounds on the length of the shortest string in L.

We study the size-cost of boolean operations on constant height deterministic pushdown automata. We prove an asymptotically optimal exponential blow-up for union and intersection, as well as polynomial blow-up for complement.

The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maximal syntactic complexity of languages in that class, taken as a function of the state complexity n of these languages. We study the syntactic complexity of prefix-, suffix-, and bifix-free regular languages. We prove that n ^n − 2 is a tight upper bound for prefix-free regular languages. We present properties of the syntactic semigroups of suffix- and bifix-free regular languages, and conjecture tight upper bounds on their size.

We present a new method for checking whether a regular language over an arbitrarily large alphabet is semi-geometrical or whether it is geometrical. This method makes use first of the partitioning of the state diagram of the minimal automaton of the language into strongly connected components and secondly of the enumeration of the simple cycles in each component. It is based on the construction of systems of linear Diophantine equations the coefficients of which are deduced from the the set of simple cycles. This paper addresses the case of a strongly connected graph.

In this paper, we study the size complexity of non-returning parallel communicating grammar systems. First we consider the problem of determining the minimal number of components necessary to generate all recursively enumerable languages. We present a construction which improves the currently known best bounds of seven (with three predefined clusters) and six (in the non-clustered case) to five, in both cases (having four clusters in the clustered variant). We also show that in the case of unary languages four components are sufficient. Then, by defining systems with dynamical clusters, we investigate the minimal number of different query symbols necessary to obtain computational completeness. We prove that for this purpose three dynamical clusters (which means two different query symbols) are sufficient in general, which (although the number of components is higher) can also be interpreted as an improvement in the number of necessary clusters when compared to the case of predefined clusters.

In this paper, we study the power of external contextual grammars with selection languages from subfamilies of the family of regular languages. If we consider families \(\mathcal F_n\) which are obtained by restriction to n states or nonterminals or productions or symbols to accept or to generate regular languages, we obtain four infinite hierarchies of the corresponding families of languages generated by external contextual grammars with selection languages in \(\mathcal F_n\). Moreover, we give some results on the power of external contextual grammars with regular commutative, regular circular, definite, suffix-free, ordered, combinational, nilpotent, and union-free selection languages.

The separating words problem asks for the size of the smallest DFA needed to distinguish between two words of length ≤ n (by accepting one and rejecting the other). In this paper we survey what is known and unknown about the problem, consider some variations, and prove several new results.

In this paper, we study the state complexities of union and intersection combined with star and reversal, respectively. We obtain the exact bounds for these combined operations on regular languages and show that, as usually, they are different from the mathematical compositions of the state complexities of their individual participating operations.

In this paper we propose a generalization of the local internal contextual grammars, introduced by Ilie in 1997, namely the k-local internal contextual grammars. These grammars are, in fact, classical internal contextual grammars, but their only permitted derivations are those that can be described in a restricted manner (that depends on the number k). Using this formalism we define different classes of languages, and obtain a series of language theoretic results for them. Also, we show that the membership problem for k-local internal contextual grammars with polynomial choice can be solved in polynomial time. This seems interesting to us, as it shows that the descriptional restrictions on the derivations of a grammar reflect on the computational efficiency of accepting the language generated by that grammar.

Motivated by applications to verification problems in string manipulating programs, we look at the problem of whether the heads in a multitape automaton are synchronized. Given an n-tape pushdown automaton M with a one-way read-only head per tape and a right end marker $ on each tape, and an integer k ≥ 0, we say that M is k-synchronized if at any time during any computation of M on any input n-tuple (x ₁, …, x _n ) (whether or not it is accepted), no pair of input heads that are not on $ are more than k cells apart. This requirement is automatically satisfied if one of the heads has reached $. Note that an n-tuple (x ₁, …, x _n ) is accepted if M reaches the configuration where all n heads are on $ and M is in an accepting state. The automaton can be deterministic (DPDA) or nondeterministic (NPDA) and, in the special case, may not have a pushdown stack (DFA, NFA). We obtain decidability and undecidability results for these devices for both one-way and two-way versions. We also consider the notion of k-synchronized one-way and two-way multihead automata and investigate similar problems.

This paper discusses the state complexity of projected regular languages represented by incomplete deterministic finite automata. It is shown that the known upper bound is reachable only by automata with one unobservable transition, that is, a transition labeled with a symbol removed by the projection. The present paper improves this upper bound by considering the structure of the automaton. It also proves that the new bounds are tight, considers the case of finite languages, and presents several open problems.

We present binary deterministic finite automata of n states that meet the upper bound 2 ⁿ on the state complexity of reversal. The automata have a single final state and are one-cycle-free-path, thus the witness languages are deterministic union-free. This result allows us to describe a binary language such that the nondeterministic state complexity of the language and of its complement is n and n + 1, respectively, while the state complexity of the language is 2 ⁿ . We also show that there is no regular language with state complexity 2 ⁿ such that both the language and its complement have nondeterministic state complexity n.

The paper determines the number of states in a two-way deterministic finite automaton (2DFA) over a one-letter alphabet sufficient and in the worst case necessary to represent the results of the following operations: (i) intersection of an m-state 2DFA and an n-state 2DFA requires between m + n and m + n + 1 states; (ii) union of an m-state 2DFA and an n-state 2DFA, between m + n and 2m + n + 4 states; (iii) Kleene star of an n-state 2DFA, (g(n) + O(n))² states, where \(g(n)=e^{\sqrt{n \ln n}(1+o(1))}\) is the maximum value of lcm(p ₁, …, p _k ) for \(\sum p_i \leqslant n\), known as Landau’s function; (iv) k-th power of an n-state 2DFA, between (k − 1)g(n) − k and k(g(n) + n) states; (v) concatenation of an m-state and an n-state 2DFAs, \(e^{(1+o(1)) \sqrt{(m+n)\ln(m+n)}}\) states.

We prove Kleene theorems for two subclasses of labelled product systems which are inspired from well-studied subclasses of 1-bounded Petri nets. For product T-systems we define a corresponding class of expressions. The algorithms from systems to expressions and in the reverse direction are both polynomial time. For product free choice systems with a restriction of structural cyclicity, that is, the initial global state is a feedback vertex set, going from systems to expressions is still polynomial time; in the reverse direction it is polynomial time with access to an NP oracle for finding deadlocks.

Two-way nondeterministic pushdown automata (\(\textrm{2PDA}\)) are classical nondeterministic pushdown automata (\(\textrm{PDA}\)) enhanced with two-way motion of the input head. In this paper, the subclass of \(\textrm{2PDA}\) accepting bounded languages and making at most a constant number of input head turns is studied with respect to descriptional complexity aspects. In particular, the effect of reducing the number of pushdown reversals to a constant number is of interest. It turns out that this reduction leads to an exponential blow-up in case of nondeterministic devices, and to a doubly-exponential blow-up in case of deterministic devices. If the restriction on boundedness of the languages considered and on the finiteness of the number of head turns is dropped, the resulting trade-offs are no longer bounded by recursive functions, and so-called non-recursive trade-offs are shown.

A common definition of tree automata operating on unranked trees uses a set of vertical states that define the bottom-up computation, and the transitions on vertical states are determined by so called horizontal languages recognized by finite automata on strings. It is known that, in this model, a deterministic tree automaton with the smallest total number of states (that is, vertical states and states used for automata to define the horizontal languages) does not need to be unique nor have the smallest possible number of vertical states. We consider the question by how much we can reduce the total number states by introducing additional vertical states. We give an upper bound for the state trade-off for deterministic tree automata where the horizontal languages are defined by DFAs (deterministic finite automata). Also, we give a lower bound construction that reduces the number of horizontal states, roughly, from 4 ⁿ to 8n by doubling the number of vertical states. The lower bound is close to the worst-case upper bound in the case where the number of vertical states is multiplied by a constant.

We show that deterministic tree automata where the horizontal languages are specified by NFAs (nondeterministic finite automata) can have no trade-offs between the numbers of vertical states and horizontal states, respectively. We study corresponding trade-offs also for nondeterministic tree automata.

One of the interesting applications of membrane computing is the ability to solve intractable problems in polynomial time. The existing variants with active membranes have several powerful features like polarizations, dissolution, evolution and communication rules as well as non-elementary membrane division. We propose a simple variant which uses elementary membrane division and communication only in the form of mobility of membranes. We show that this variant has \(\Sigma_2^P \cup \Pi_2^P\) as lower bound. This is the first known treatment of the complexity classes \(\Sigma_2^P\), \(\Pi_2^P\) using active membranes without the features of polarizations, non elementary membrane division.

A tree controlled grammar can be given as a pair (G,G′) where G is a context-free grammar and G′ is a regular grammar. Its language consists of all terminal words with a derivation in G such that all levels of the corresponding derivation tree – except the last level – belong to L(G′). We define its descriptional complexity Var(G,G′) as the sum of the numbers of nonterminals of G and G′. In [24] we have shown that tree controlled grammars (G,G′) with Var(G,G′) ≤ 9 are sufficient to generate all recursively enumerable languages. In this paper, our main result improves the bound to seven. Moreover, we show that all linear and regular simple matrix languages can be generated by tree controlled grammars with a descriptional complexity bounded by three.

State complexity of finite automata in some cases gives the same complexity value for automata which intuitively seem to have completely different complexities. In this paper we consider a new measure of descriptional complexity of finite automata — BC-complexity. Comparison of it with the state complexity is carried out here as well as some interesting minimization properties are discussed. It is shown that minimization of the number of states can lead to a superpolynomial increase of BC-complexity.

Developing the concept of crossing sequences for multitape computations proposed in 1979 by G. Wechsung, we derive new relations among complexity measures for nondeterministic multitape computations. Especially, we characterize inherent relations between nondeterministic time and space and other complexity measures related to the notion of crossing sequences. We also show a nondeterministic simulation of nondeterministic computations whose complexity depends on the length of crossing sequences of the simulated machine. To a certain extent our results mirror classical results known to hold for single-tape computations or for deterministic multitape computations.