Narrow Results

We investigate the descriptional complexity of the ${\nu }_i$- and ${\alpha }_i$-products with $0\le i\le 2$ of two automata, for reset, permutation, permutation-reset, and finite automata in general. This is a continuation of the recent studies on the state complexity of the well-known cascade product undertaken in [7, 8]. Here we show that in almost all cases, except for the direct product (${\nu }_0$) and the cascade product (${\alpha }_0$) for certain types of automata operands, the whole range of state complexities, namely the interval $[1,nm]$, where $n$ is the state complexity of the left operand and $m$ that of the right one, is attainable. To this end we prove a simulation result on products of automata that allows us to reduce the products of automata in question to the ${\nu }_0$, ${\alpha }_0$, and a double sided ${\alpha }_0$-product.

We design Latvian quantum finite state automata (LQFAs) recognizing unary regular languages with isolated cut point $\frac{1}{2}$. From an architectural viewpoint, we suitably combine two LQFAs recognizing with isolated cut point, respectively, the finite part and the ultimately periodic part any given unary regular language $L$ consists of. In particular, both these LQFAs incorporate a sub-module discriminating strings on the basis of their length.

Both the number of basis states and the isolation around the cut point of the resulting LQFAs for $L$ exponentially depend on the size of the minimal deterministic finite state automaton for $L$. Moreover, the recognition of $L$ tends to becoming deterministic as the number of the basis states employed in the length-discriminating sub-module grows.

While the closure of a language family $\mathcal{ℒ}$ under certain language operations is the least family of languages which contains all members of $\mathcal{ℒ}$ and is closed under all of the operations, a kernel of $\mathcal{ℒ}$ is a maximal family of languages which is a sub-family of $\mathcal{ℒ}$ and is closed under all of the operations. Here we investigate properties of kernels of general language families and operations defined thereon as well as kernels of (deterministic) (linear) context-free languages with a focus on Boolean operations. While the closures of language families are unique, this uniqueness is not obvious for kernels. We consider properties of language families and of operations that yield unique and non-unique, i.e. a set, of kernels. For the latter case, the question whether the union of all kernels coincides with the language family, or whether there are languages that do not belong to any kernel is addressed. Additionally, languages that are mandatory for each (Boolean) kernel and languages that are optional for (Boolean) kernels are studied. That is, we consider the intersection of all Boolean kernels as well as their union. The expressive capacities of these families are addressed leading to a hierarchical structure. Further closure properties are considered. Furthermore, we study descriptional complexity aspects of these families, where languages are represented by context-free grammars with proofs attached. It turns out that the size trade-offs between all families in question and deterministic context-free languages are non-recursive. That is, one can choose an arbitrarily large recursive function $f$, but the gain in economy of description eventually exceeds $f$ when changing from the latter system to the former.

Single-tape nondeterministic Turing machines that are allowed to replace the symbol in each tape cell only when it is scanned for the first time are also known as $1$-limited automata. These devices characterize, exactly as finite automata, the class of regular languages. However, they can be extremely more succinct. Indeed, in the worst case, the size gap from $1$-limited automata to one-way deterministic finite automata is double exponential.

Here we introduce two restricted versions of $1$-limited automata, once-marking$1$-limited automata and always-marking$1$-limited automata, and study their descriptional complexity. We prove that once-marking $1$-limited automata still exhibit a double exponential size gap to one-way deterministic finite automata. However, their deterministic restriction is polynomially related in size to two-way deterministic finite automata, in contrast to deterministic $1$-limited automata, whose equivalent two-way deterministic finite automata in the worst case are exponentially larger. For always-marking $1$-limited automata, we prove that the size gap to one-way deterministic finite automata is only a single exponential. The gap remains exponential even in the case the given machine is deterministic.

We obtain other size relationships between different variants of these machines and finite automata and we present some problems that deserve investigation.

If the machines of some type A have enough resources to (i) solve problems that no machine of type B can solve, and (ii) simulate any unary two-way deterministic finite automaton that has access to a linearly-bounded counter, then typically no recursive function can upper bound the increase in the size of description when a machine of type A is replaced by an equivalent machine of type B.

Non-recursive trade-offs between different representations of languages reveal a basic phenomenon. The gain in economy of description can be arbitrary. The purpose of this paper is to survey the main aspects and results regarding different representations of languages whose relative succinctness is not recursively bounded. Basic properties of descriptional systems and reasonable size measures are addressed, and the unified fundamental proof schemes emerging from the literature are presented. A comprehensive overview of results is given. Finally, some new results are shown. In particular, it is proved that between each two levels of the infinite one-way k-head finite automata hierarchies there is a non-recursive trade-off. Moreover, non-recursive trade-offs are shown between nondeterministic 2-head and deterministic k-head automata.

In this paper, we study the tradeoffs in descriptional complexity of NFA (nondeterministic finite automata) of various amounts of ambiguity. We say that two classes of NFA are separated if one class can be exponentially more succinct in descriptional sizes than the other. New results are given for separating DFA (deterministic finite automata) from UFA (unambiguous finite automata), UFA from MDFA (DFA with multiple initial states) and UFA from FNA (finitely ambiguous NFA). We present a family of regular languages that we conjecture to be a good candidate for separating FNA from LNA (linearly ambiguous NFA).

Language equations with all Boolean operations and concatenation and a particular order on the set of solutions are proved to be equal in expressive power to the first-order Peano arithmetic. In particular, it is shown that the class of sets representable using k variables (for every k ≥ 2) is exactly the k-th level of the arithmetical hierarchy, i.e., the sets definable by recursive predicates with k alternating quantifiers. The property of having an extremal solution is shown to be nonrepresentable in first-order arithmetic.

Metalinear CD grammar systems are context-free CD grammar systems where each component consists of metalinear productions. The maximal number of nonterminals in all starting productions is referred to as the width of a CD grammar system. It is shown that between the class of CD grammar systems of width m + 1 and of width m there are savings concerning the size of the grammar system not bounded by any recursive function. This is called a non-recursive trade-off. Furthermore, it is proven that there are non-recursive trade-offs between the class of metalinear CD grammar systems of width m and the class of (2m - 1)-linear context-free grammars. In addition, some decidability results are presented.

We consider tissue P systems with symport/antiport rules and investigate their computational power when using only a (very) small number of symbols and cells. Even when using only one symbol, we need at most six (seven when allowing only one channel between a cell and the environment) cells to generate any recursively enumerable set of natural numbers. On the other hand, with only one cell we can only generate regular sets when using one channel with the environment, whereas one cell with two channels between the cell and the environment obtains computational completeness with five symbols. Between these extreme cases of one symbol and one cell, respectively, there seems to be a trade-off between the number of cells and the number of symbols. For example, for the case of tissue P systems with two channels between a cell and the environment we show that computational completeness can be obtained with two cells and three symbols as well as with three cells and two symbols, respectively. Moreover, we also show that some variants of tissue P systems characterize the families of finite or regular sets of natural numbers.

For each alphabet Σ_n = {a₁,a₂,…,a_n}, linearly ordered by a₁ < a₂ < ⋯ < a_n, let C_n be the language of circular or cyclic shifts over Σ_n, i.e., C_n = {a₁a₂ ⋯ a_n-1a_n, a₂a₃ ⋯ a_na₁,…,a_na₁ ⋯ a_n-2a_n-1}. We study a few families of context-free grammars G_n (n ≥1) in Greibach normal form such that G_n generates C_n. The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals ν(n), the number of rules π(n) and the number of leftmost derivations δ(n) of G_n. As in the case of Chomsky normal form, these ν, π and δ are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal w. r. t. all these measures remains open.

We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if no multiset of rules containing a rule from each set of rules assigned to the membranes is applicable anymore, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for (catalytic) P systems and antiport P systems working in different derivation modes.

In this paper, the descriptional complexity of extended finite splicing systems is studied. These systems are known to generate exactly the class of regular languages. Upper and lower bounds are shown relating the size of these splicing systems, defined as the total length of the rules and the initial language of the system, to the size of their equivalent minimal nondeterministic finite automata (NFA). In addition, an accepting model of extended finite splicing systems is studied. Using this variant one can obtain systems which are more than polynomially more succinct than the equivalent NFA or generating extended finite splicing system.

Nondeterministic finite automata (NFAs) were introduced in [68], where their equivalence to deterministic finite automata was shown. Over the last 50 years, a vast literature documenting the importance of finite automata as an enormously valuable concept has been developed. In the present paper, we tour a fragment of this literature. Mostly, we discuss recent developments relevant to NFAs related problems like, for example, (i) simulation of and by several types of finite automata, (ii) minimization and approximation, (iii) size estimation of minimal NFAs, and (iv) state complexity of language operations. We thus come across descriptional and computational complexity issues of nondeterministic finite automata. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved.

The simulation of deterministic pushdown automata defined over a one-letter alphabet by finite state automata is investigated from a descriptional complexity point of view. We show that each unary deterministic pushdown automaton of size s can be simulated by a deterministic finite automaton with a number of states that is exponential in s. We prove that this simulation is tight. Furthermore, its cost cannot be reduced even if it is performed by a two-way nondeterministic automaton. We also prove that there are unary languages for which deterministic pushdown automata cannot be exponentially more succinct than finite automata. In order to state this result, we investigate the conversion of deterministic pushdown automata into context-free grammars. We prove that in the unary case the number of variables in the resulting grammar is strictly smaller than the number of variables needed in the case of nonunary alphabets.

We introduce PC grammar systems where the components form clusters and the query symbols refer to clusters not individual grammars, i.e., the addressee of the query is not precisely identified. We prove that if the same component replies to all queries issued to a cluster in a rewriting step, then non-returning PC grammar systems with 3 clusters and 7 context-free components are able to generate any recursively enumerable language. We also provide open problems and directions for future research.

A symbol a is called active in an L system G if there is a rule a → υ with a ≠ υ in some table of G. By Ac_X(L) we denote the number of active symbols necessary to generate L by L systems of type X. For two types X and Y of L systems such that the corresponding languages families and satisfy , we say that Y is more efficient than X, if there is a sequence of languages , n ≥ 1, such that Ac_X(L_n) ≥ n and Ac_Y(L_n) ≤ k for some constant k. In this paper we shall show that the inclusion implies that Y is more efficient than X. Analogous results are presented for some modifications of the measure of active symbols.

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.

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.

With this contribution we would like to commemorate Chandra M. R. Kintala, who passed away in November 2009. We will give short overviews of his CV and his contributions to the field of theoretical and applied computer science and, given the opportunity, will attempt to present his influence on areas like limited nondeterminism and resources as well as software reliability in an exemplary fashion. Finally, we will briefly touch on some research topics which hopefully will be addressed in the not-so-distant future.